how is push_back implemented in STL vector?

Question

I was asked this question in an interview.

The points I answered are like this

1) an index pointing to the current position;

2) resize if neccessary.

Can anybody elaborate more?

Answer 1

Thanks to some comments, I am completely revising a very incorrect original answer.

According to the STL spec, your answer was correct. The vector is implemented as a dynamically resized array:

Vector containers are implemented as dynamic arrays; Just as regular arrays, vector containers have their elements stored in contiguous storage locations, which means that their elements can be accessed not only using iterators but also using offsets on regular pointers to elements.

But unlike regular arrays, storage in vectors is handled automatically, allowing it to be expanded and contracted as needed.

Answer 2

Possibly what they were looking for is that push_back makes a copy of the object being pushed onto the vector (using its copy constructor).

With regard to resizing: The standard says a.push_back(x) is equivalent to a.insert(a.end(),x). The definition of insert says, in part: “Causes reallocation if the new size is greater than the old capacity.”

The standard says what the functions are supposed to do. But how they’re implemented is, in most cases, implementation-specific.

Answer 3

vector doesn't use a linked list. It uses continuous memory.

If there is not enough reserved space push_back allocates a new chunk of memory twice as large as the original vector. By doing that the amortized runtime is O(1).

Answer 4

An STL vector has a size (current number of stored elements) and a capacity (currently allocated storage space).

• If size < capacity, a push_back simply puts the new element at the end and increments the size by 1.
• If size == capacity before the push_back, a new, larger array is allocated (twice the size is common, but this is implementation-dependent afaik), all of the current data is copied over (including the new element), and the old allocated space is freed. This may throw an exception if the allocation fails.

The complexity of the operation is amortized O(1), which means during a push_back that causes a resize, it won't be a constant-time operation (but in general over many operations, it is).

Answer 5

That, of course, is inherently implementation defined. Assuming it's a question of how somebody would implement a dynamic array, in general, it'd be something like this:

1. push_back checks capacity() and ensures it's at least one larger than size().
2. If there is no capacity for the new element, the vector reallocates it's entire underlying storage, copying over the contents of the old storage to the new storage. The old storage is deallocated.
3. The new element is copied to the end of the dynamic array.

Some STL implementations will elide some of the copies by using swaps (i.e. for containers of containers), but for the most part that's exactly how it works.

Answer 6

How much detail did the interviewer want? For example, was he looking for you to drill down into the lower level details?

Besides the usual resize-as-needed to retain the O(1) on average semantics, some things to consider include but are not limited to:

• Exception safety: Does the implementation provide a guarantee that state of the vector will not be modified if an exception is thrown when appending the new element (e.g. rollback semantics)? For example, an exception could be thrown during allocation, copying, insertion, etc.
• Proper use of allocator: Does the implementation correctly use the vector's allocator instead of plain old new based allocator (both may or may not be the same)? Ideally, this will be handled transparently by the vector's resizing code, implementations could certainly differ, however.

Answer 7

template< typename T >
void std::vector<T>::push_back(const T& obj)
{
    this->insert(this->end(),obj);
}