Pushing vector member into vector during expand: vector.push_back(vector[0])

Question

I'm doing custom vector class in C++. I have a question about such code:

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

Definition of push_back is as follows:

    void push_back(const T & v)

to avoid unnecessary copying. It's 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 push element that is already in vector AND vector needs to expand (size is equal to its capacity). If we do it (vec.push_back(vec[0])) then at // 1, it is already deallocated. So we need to have a copy of it. Another alternative is adding it during expansion, somewhere at // 2 but this doesn't seem pretty.

How would you resolve this?

Answer 1

In some STL implementations I've seen (like the current VS2010 for instance) they first check whether a pointer to the new data item to be added is within the current extent of the vector buffer.

If so, the index position (not pointer!) to the location of the data within the vector is found. This will not change even if the underlying buffer is reallocated. Once the buffer has been expanded (whether this involves actual reallocation or not) the data item can be safely copied from the index position.

Another alternative, which I think you mentioned, is just to take a local (stack) copy of the data item to be added before the buffer is reallocated, just in case the item is internal to the vector. Obviously, if the data type is very expensive to copy (like another vector maybe??) this might not be a great idea.

Hope this helps.

Answer 2

One further thing to consider is exception safety: what happens if memory allocation, or copying an object, fails? You should try to make your class behave as well as possible in this case. Consider the following guarantees:

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

You can't achieve the last here, since you have no control over the memory allocator or the objects to be copied. However, the "strong" guarantee is possible using a two-stage approach: do the work that can fail "on the side", in a way that doesn't affect the visible state; once this has succeeded, update the persistent state using operations that can't fail (such as updating pointers, and deleting the old memory - if deletion gives the "no-throw" guarantee, which it usually should).

So a more exception safe version 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 only offers the "weak" guarantee: if any object fails to copy, then some, but not all, of the new data may have been copied. Improving that will have a cost, either in terms of complexity (providing a way to "unwind" the changes on failure) or speed and memory (using the reallocating version whether or not there's enough memory already).