CODEWITHSUNDEEP
c++liststlvectorset
user1002288
user1002288

Reputation: 5040

what is underlying data structure of STL list, vector and set?

what is underlying data structure of STL list, vector and set ?

My solution:

Right?

Upvotes: 9

Views: 15626

Answers (2)

Brent Writes Code
Brent Writes Code

Reputation: 19603

Based on comments, to clarify, these are the most common choices, but based on desired complexity and other factors, the backing of these implementations may vary:

Vector = dynamically resizing array

List = Doubly Linked List

Set = Red/Black Tree (balanced Binary Search Tree)

I think you might possibly be mixing up Heaps and BSTs. A heap is visualized as a tree, but it's actually built on top of an indexable list structure (e.g. array or vector). C++ provides heap functions via the algorithm header in the STL . BSTs are more of a key/value based structure used for efficient lookup (which is what you generally want for a set).

Upvotes: 21

user784668
user784668

Reputation:

The standard gives no guarantees on what data structures are used, there are only complexity guarantees, so the implementation can choose any structure that fulfills them.

That said, std::vector is usually a dynamic array, std::list is probably a doubly-linked list and std::set is most often some kind of self-balancing binary tree.

Upvotes: 5

Related Questions