Inserting into vector by reference to element of same vector

Question

I was wondering if someone more experienced might be able to clarify if this is a buggy operation to do on a vector:

std::vector<int> v{1, 2, 3, 4, 5};
v.insert(v.begin() + 1, v[0]);

The reason I ask is because the element to insert is a reference to the 0th element in the vector. If the insertion forces the vector to resize (because its capacity is full), then the reference to v[0] would be invalidated, and the code might insert an incorrect value. Here is some pseudo-code that might demonstrate:

template <typename T>
void vector_insert_method(Iterator pos, const T& value) {
    if capacity full:
        reallocate array and copy over element
        // if value was reference to elem in this vector,
        // that reference might be invalidated


    insert element

    ++size
}

This issue might be more realistic on a concurrent system.

A similar, and related question is what happens if you try inserting an element that comes after the position you are trying to insert. For example, doing something like v.insert(v.begin(), v[2]) because the standard points out that references to elements after the insertion point are invalidated. Is this guaranteed to work?

Answer 1

The original question asked ...

[..] whether this is a buggy operation to do on a vector:

v.insert(v.begin(), v[0]);
//              ^^^ no + 1 here!

Probably yes, it could be undefined behavior. Quoting N3337 ("almost C++11" AFAIK):

[..] If no reallocation happens, all the iterators and references before the insertion point remain valid. [..]

§23.3.6.5/1

While this is not the clear wording one is used to when reading the standard, I'd interpret this as: iterators and references to and after the insertion point are invalidated.

Thus, the reference to v[0] is invalidated by the call(*) to insert. Even if no reallocation happens, insert has to shift all elements to higher indices (so v[0] is re-positioned to v[1]).

Assuming the element type is not trivially destructible, then no matter how that re-positioning is done (either via moving or copying), after v[1] has been assigned / constructed from v[0], the destructor of v[0] needs to be called (and its lifetime ended) before a new object (the one you want to insert) can be placed in the memory location of v[0]. Thus, here your reference turns into a dangling reference, which leads to undefined behavior when it's used directly afterwards to construct the new v[0]. No, as far as I can see, this issue could be circumvented by having std::vector::insert() not construct the new object but rather assign the new object to the "old" one. I'm not sure whether there's a requirement for std::vector to behave that way, though its element type having to be CopyInsertable gives a hint that this might be the case.

UPDATE: I've played around with the code provided in the other answer, adding some print debugging. This showed not what I was expecting (destructing one element and then accessing it) but still shows that the standard library implementation (used here by ideone) does not conform to the standard: It invalidates references to elements before the point of insertion even if the capacity is large enough. That way it circumvents above issues (but breaks the standard ... so).

(*): One could argue about when that invalidation happens. The best answer to that question is IMO that the reference is valid right before calling the insert function, and is invalid (for sure) after returning from that function. The exact point of invalidation is unspecified.

---

The edited question asked the same question but with a extremely important modification:

v.insert(v.begin() + 1, v[0]);
//                ^^^^^

Now this is a completely different situation. The reference to v[0] will not necessarily be invalidated by the call to insert because the point of insertion is "behind" v[0]. The only issue that may arise is if the std::vector has to reallocate its internal buffer, but in that case the following sequence of operations should guarantee correct behavior:

1. Allocate new memory of larger capacity
2. Construct new element at it's correct index in the newly allocated memory region.
3. Copy/Move elements from old (too small) memory to the newly allocated memory region.
4. Free old memory.

Answer 2

Ok so following a lot of looking around, it seems like the standard library is under obligation to make this work. The idea being that since the standard does not explicitly say this shouldn't work, so it must work.

Andrew Koenig wrote a bit about it here and proposes a solution where new memory is allocated, the elements moved over, and only then will the old memory be deallocated.

There are also other discussion here and here (#526).

As for the second case, it seems like the standard library (clang on MacOS) also accounts for the situation where you try to insert a reference to an element in the vector that is positioned after the point where you are trying to insert. To test this I wrote a wrapper class for ints called Integer that behaves exactly like an int except the destructor sets it's internal value to -5. So we should see a -5 inserted instead of the actual value if the std::vector insert doesn't account for the situation.

#include <vector>
#include <iostream>


using std::cout;    using std::endl;
using std::ostream; using std::vector;


class Integer {

public:
    Integer() {
        x = -1;     // default value
    }

    ~Integer() {
        x = -5;     // destructed value. Not 0 so we can clearly see it
    }

    Integer(int r) {
        x = r;
    }

    Integer(const Integer& other) {
        x = other.x;
    }

    Integer operator=(const Integer& other) {
        x = other.x;
        return *this;
    }

    operator int() const{
        return x;
    }

    friend ostream& operator<<(ostream& os, const Integer& thing) {
        os << thing.x;
        return os;
    }

private:
    int x;
};


ostream& operator<<(ostream& os, const vector<Integer> &v) {
    std::copy(v.begin(), v.end(), std::ostream_iterator<Integer>(os, ", "));
    return os;
}

int main() {
    std::vector<Integer> ret {18, 7, 4, 24,11};
    cout << "Before: " << ret << endl;
    ret.insert(ret.begin(), ret[1]);
    cout << "After: " <<  ret << endl;
    return 0;
}

This gives us the correct output:

Before: 18, 7, 4, 24, 11, 
After: 7, 18, 7, 4, 24, 11,