how is push_back implemented in STL vector?

问题:

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?

回答1:

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

回答2:

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

回答3:

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.

回答4:

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.

回答5:

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

回答6:

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.

回答7:

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.

回答8:

Like so:

void push_back(T const& param)
{
  vector temp(rbegin(), rend());
  temp.push_front(param);
  *this = vector(temp.rbegin(), temp.rend());
}

回答9:

If size < capasity, then everything seems to be ok, you just insert en element in vector, the complexity accures when size == capasity.

It is easy to explaint on words that you have to allocate a new array twice larger then existing one and copy all those elements in new alocated memory and after delete the old one and insert the new element in new array. But here are some key moments which I consider your interviewer expects you to mention.

1. The elements in std::vector are not kept in one array, so the data member of std::vector[1000] is not a int* of lenght 1000. The elements are kept in blocks of memory, thus you must consider it when copying.

2. Secondly, the standard stl vector requires "give me a copyable object and I can insert it", which means that requierment on std::vector is that sometype only has to have a copy_constructer (not operator = ). So when you are alocating a new memory of type sometype, you must consider that sometyme may not have a default copy constructer. In common implementations, this is done by placement new operator to avoid the call of copy constructors.