stl - How is C++ std::vector implemented?

Question

I have been using std::vector a lot, and recently I asked myself this question: "How is std::vector implemented?"

I had two alternatives:

1) Linked list, and then making the API feel like random access (i.e. overloading operator[]).

2) Using new, e.g. Foo* temp = new Foo[20]: I believe they do something like this, but then it raises one more question. Do they always allocate a maximum (uint32_t) storage to give random access? (This is inefficient in terms of memory.)

Or is there something else that I should be aware of?

Answer 1

It's implemented by using an underlying array.

It's not possible to implement a std::vector<T> with a linked list because the standard guarantees the elements in the list will be held in contiguous memory.