How is C++ std::vector implemented?

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?

Solution 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.

Solution 2:

I believe it is the third option. It can't just use new T[n] because then it would actually have to construct as many objects as it allocates. E.g

std::vector<Foo> v;
v.reserve(10);

If your implementation simply ended up doing new Foo[10] then you'd just have constructed 10 instances of Foo.

Instead it uses its allocator to allocate and deallocate raw memory (without constructing objects), and as needed (for example, when you actually push_back objects) places copy-constructed instances into correct memory locations in its reserve using placement new and removes them with explicit calls to the destructor (something you'd only do in combination with placement new). The allocator class provides following methods for that which I presume vector's implementations use

 void construct(pointer p, const_reference val);

  Returns:
    new((void *)p) T(val)

  void destroy(pointer p);

  Returns:
    ((T*)p)->~T()

(The "returns" probably should read "effect" or similar.)

More about placement new