3

How are STL List and Vector implement?

I was just asked this in an an interview.

I just said maybe by using binary tree or hash table about vector. not sure about list... Am I wrong, I guess so.. give some ideas thanks.

4
  • 5
    Look it up yourself, then you will remember it :)
    – tauran
    Feb 16, 2011 at 21:06
  • You might learn something by looking in the header files <list> and <vector> that come with your compiler.
    – aschepler
    Feb 16, 2011 at 21:11
  • 3
    I think the problem is not knowing how they are implemented, but rather not knowing what they are in the first place. (A bit hard to believe someone who has used them before has no idea what they might be.)
    – UncleBens
    Feb 16, 2011 at 21:22
  • channel9.msdn.com/Shows/Going+Deep/… is a good resource.
    – Jagannath
    Feb 22, 2011 at 2:36

3 Answers 3

13

Hash table or binary tree? Why?

std::vector, as the name itself suggests, is implemented with a normal dynamically-allocated array, that is reallocated when its capacity is exhausted (usually doubling its size or something like that).

std::list instead is (usually1) implemented with a doubly-linked list.

The binary tree you mentioned is the usual implementation of std::map; the hash table instead is generally used for the unordered_map container (available in the upcoming C++0x standard).


  1. "Usually" because the standard do not mandate a particular implementation, but specifies the asymptotic complexity of its methods, and such constraints are met easily with a doubly-linked list. On the other hand, for std::vector the "contiguous space" requirement is enforced by the standard (from C++03 onwards), so it must be some form of dynamically allocated array.
3
  • 1
    The iterator of st::list must be bidirectional. This doesn't imply bidirectional list, but it certainly rules out a unidirectional list. Feb 16, 2011 at 21:31
  • 3
    @whilhelmtell: it also specifies that insertions and deletions in the middle of the list are O(1), and don't invalidate any iterators. Feb 16, 2011 at 21:55
  • for std::map we should use balanced binary search tree otherwise there are performance issue in case of skewed tree. Jul 4, 2017 at 4:10
3

std::vector uses a contiguously allocated array and placement new

std::list uses dynamically allocated chunks with pointer to the next and previous element.

nothing as fancy as binary trees or hash tables (which can be used for std::map)

3
  • 1
    You can't use a hash table with std::map unless the elements hash sorted through a comparator and lookup is O(log n). Big-oh, that is, not amortized time. I'm sure there are other constraints I forgot, that make it harder still to use a hash for std::map. Feb 16, 2011 at 21:45
  • 1
    @maxpm std::list cannot be implemented as as singly linked list, so your link (no pun intended) might be misleading.
    – YvesgereY
    Jul 29, 2018 at 13:45
  • 1
    @YvesgereY Yes, a better introduction is: en.wikipedia.org/wiki/Doubly_linked_list
    – Maxpm
    Jul 29, 2018 at 15:38
2

You can spend half a semester talking about either of the containers, but here are a few points:

std::vector is a contiguous container, which means every element follows right after the previous element in memory. It can grow at runtime, which means it allocates its storage in dynamic memory.

std::list is a bidirectional linked list. This means that the elements are scattered in memory in arbitrary layout, and that each element knows where the next and previous elements in sequence are.

std::vector, std::list and the other containers don't take ownership of the elements they hold, but they do cleanup after themselves. So, if the elements are pointers to dynamic memory then the user must free the pointers before the container destructs. But if the container contains automatic data then the data's destructors will call automatically upon the container's cleanup.

So far, very simple and roughly equivalent to any other language or toolset. What's unique about the STL is that the containers are generic and decoupled from the means of iterating over them and (for the most part) from the operations you can perform over them. Some operations can be done particularly efficiently with some containers, so the containers will provide member functions in these cases. For example, std::list has a sort() member function.

The STL doesn't provide container classes (for the most part), but rather container templates. In other words, when the library talks about a container it only refers to the data type anonymously, say, as T, never by its true name. Never int or double or Car; always T, for any type. There are exceptions, like std::vector<bool>, but this is the general case. Then, when the user instantiates a container template, they specify a type, and the compiler creates a container class from the template for that type.

The STL also offers algorithms as free template functions. These algorithms work on iterators, themselves templates. Often iterators come in pairs that denote the beginning and end of a sequence, on which the algorithm operates. std::vector, std::list and other containers then expose their own iterators that can traverse and manipulate their data. So the same free algorithm can work on a std::vector and a std::list and other containers, provided the iterators conform with specific assumptions about the iterators' abilities.

All this abstraction is done at compile-time, and that is the biggest difference when compared to other languages. This translates to outstanding performance with relatively short and concise code. The same performance that in C you'd only get with lots of copy-pasting or hardcoding.

1
  • "But if the container contains automatic data then the data's destructors will call automatically upon the container's cleanup." - that contradicts your previous statement that vector allocates its storage in dynamic memory. Then, well, container can't contain automatic data. And that's why people keep asking these questions ("how stl::* implemented/work"), and unfortunately, they keep getting confusing answers...
    – pfalcon
    Jan 16, 2013 at 22:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.