Pushing a vector element into a vector during extension: vector.push_back (vector [0])

Question

I am making a custom vector class in C ++. I have a question about this code:

vector<T> vec; vec.push_back(one); vec.push_back(two); vec.push_back(vec[0]); 

The definition of push_back is as follows:

  void push_back(const T & v) 

to avoid unnecessary copying. This implementation looks like

  if (size == capacity) { allocate new storage copy old values into new storage // 2 delete old storage fix pointers and counters } // 1 copy v at the end of storage 

The problem arises if we want to click on an element that is already in the vector. And the vector should expand (the size is equal to its capacity). If we do this ( vec.push_back(vec[0]) ), then in // 1 it is already freed. Therefore, we need to have a copy of it. Another alternative is to add it during expansion, somewhere in // 2 , but it does not look pretty.

How do you resolve this?

Answer 1

In some STL implementations that I saw (for example, in the current VS2010), they first check if the pointer to the new data element is in the current degree of the vector buffer.

If so, an index position (not a pointer!) Will be found for the location of the data inside the vector. This will not change even if the base buffer is redistributed. After expanding the buffer (whether it is related to the actual redistribution or not), the data item can be safely copied from the index position.

Another alternative that I told you about is simply to take a local (stack) copy of the data item to be added before the buffer is redistributed, just in case the item is internal to the vector. Obviously, if the data type is very expensive to copy (for example, another vector, maybe?), This might not be a good idea.

Hope this helps.

Answer 2

Another thing to consider is exception safety: what happens if memory is allocated or an object is copied? In this case, you should try to make your class as efficient as possible. Consider the following warranties:

• No guarantee: if something goes wrong, the object may be in an invalid state
• Weak guarantee: if something goes wrong, the object is in undefined, but valid, state
• Strong guarantee: if something goes wrong, the object has not changed
• No-throw guarantee: nothing can go wrong.

You cannot achieve the latter here, since you do not have control over the memory allocator or objects that need to be copied. Nevertheless, a “strong” guarantee is possible using a two-stage approach: do work that may not work “sideways”, so that it does not affect the visible state; as soon as this works, update the persistent state using operations that cannot fail (for example, updating pointers and deleting old memory - if deleting gives a "no-throw" guarantee, which usually should).

Thus, a safer version with exceptions might look something like this:

 if (new_size > capacity) { allocate new storage, controlled by a local smart pointer copy old values copy new values update state, releasing the smart pointer delete old storage } else { copy new values } 

The "else" case here offers only a "weak" guarantee: if any object cannot copy, then some, but not all, of the new data can be copied. Improving this will cost either in terms of complexity (providing a way to “soak” the changes upon failure) and speed and memory (using the redistributable version, is there enough memory or not).

Answer 3

I would postpone deleting the old repository:

 if (size == capacity) { allocate new storage copy old values into new storage fix pointers and counters, but keep one pointer at the old storage } copy v at the end of storage delete old storage