1

Answering How to self-copy a vector? has got me a bit confused about iterator invalidation. Some literature says "if you use insert, push_back, etc. consider all iterators invalid". Thats clear, it might cause the vector to grow which invalidates iterators. What about the special case where I know there is going to be enough room?

first try:

myvec.reserve(myvec.size()*3);  //does this protect me from iterator invalidation?
vector<string>::iterator it = myvec.end();    
myvec.insert(myvec.end(), myvec.begin(), it);
myvec.insert(myvec.end(), myvec.begin(), it);

After some excellent answers second try:

auto size = myvec.size();
myvec.reserve(size*3);  //does this protect me from iterator invalidation?  
myvec.insert(myvec.end(), myvec.begin(), myvec.begin()+size);
myvec.insert(myvec.end(), myvec.begin(), myvec.begin()+size);

After more excellent answers third try:

auto size = myvec.size();
myvec.reserve(size*3);  //does this protect me from iterator invalidation?  
back_insert_iterator< vector<string> > back_it (myvec);
copy (myvec.begin(),myvec.begin()+size,back_it);
copy (myvec.begin(),myvec.begin()+size,back_it);

This quote from Josuttis' "C++ Standard Library Reference":

Inserting or removing elements invalidates references, pointers, and iterators that refer to the following element. If an insertion causes reallocation, it invalidates all references, iterators, and pointers.

suggests that my code is safe and defined behavior. Is there a passage in the standard which guaranties this?

Community
  • 1
  • 1
odinthenerd
  • 5,422
  • 1
  • 32
  • 61
  • Just for those that want to keep up the searching: yes there is somewhere a passage, I just don't have it at hand. It says almost exactly the same as the josuttis book. – PlasmaHH Feb 11 '13 at 21:10
  • I don't have the standard handy, but the next best thing, [cppreference.com](http://en.cppreference.com/w/cpp/container/vector/insert) points out the following concerning `std::vector::insert()` : *"Causes reallocation if the new size() is greater than the old capacity().If the new size() is greater than capacity(), all iterators and references are invalidated. Otherwise, only the iterators and references after the added element are invalidated."* I would consult the standard, but unlike other sites, cppreference is maintained by contributors that live, breathe, and die by the standard. – WhozCraig Feb 11 '13 at 21:13

3 Answers3

7

The past-the-end iterator is always a bit special. I'd be careful. The standard says this (23.3.6.5):

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

The key here is "before the insertion point". Since your original it is not before the insertion point (since it is the insertion point), I wouldn't bank on it remaining valid.

Kerrek SB
  • 464,522
  • 92
  • 875
  • 1,084
  • wow you just blew my mind, since it points to the old end which is a theoretical value past then end of course it can be invalidated. +1 I will fix my code to omit this error. – odinthenerd Feb 11 '13 at 21:15
  • +1 thanks for looking this up. I really need to get a copy of the standard on my work-comp. – WhozCraig Feb 11 '13 at 21:17
  • 1
    @WhozCraig: Just a draft but good for most purposes: http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2012/n3485.pdf – Benjamin Lindley Feb 11 '13 at 21:18
  • @PorkyBrain: I had a [similar situation](http://stackoverflow.com/q/6230350/596781) once :-) – Kerrek SB Feb 11 '13 at 21:39
2

Although it is true that insertions into a vector won't cause reallocation as long as the capacity is not exceeded, and won't invalidate iterators to elements before the insertion point (which is arguably the case of end(), as @KerrekSB pointed out), Table 100 of the C++11 Standard (Paragraph 23.2.3) specifies the following precondition for the a.insert(p,i,j) function for sequence containers:

[...] pre: i and j are not iterators into a. [...]

In your case, they clearly are, which makes me think that program has Undefined Behavior.

Andy Prowl
  • 124,023
  • 23
  • 387
  • 451
  • this is pretty much the essence of the question ;) Does the standard just say that because insert might cause a grow? Maybe but on the other hand that is not going to stand up to a language lawyer... – odinthenerd Feb 11 '13 at 21:22
  • @PorkyBrain: It does not matter *why* the standard states it. The fact that it does states it as a precondition is enough: an implementation is allowed to do anything if you violate it – Andy Prowl Feb 11 '13 at 21:23
0

Iterators should not be invalidated mid function. The idea that memory may be relocated doesn't hold up, because you cannot use realloc on objects with non-trivial constructors. Even if construction was a not an issue, it would still have to copy the initial sequence twice in the worst case, negating any benefits in the average case.

Point being, it doesn't make sense to implement it that way; an alloc, copy, free is almost certainly done, regardless of what the standard says.

This is safe because v.begin() and v.end() are always current.

v.insert(v.end(), v.begin(), v.end());
v.insert(v.end(), v.begin(), v.end());

This is not.

vector<foo>::iterator i = v.begin();
vector<foo>::iterator j = v.end();
v.insert(v.end(), i, j);
v.insert(v.end(), i, j);

However, self insertion can be wonky. Try the following under GCC. The self insertion gives an incorrect result only if enough memory is available (not sure if this is a bug).

int main()
{
    int position = 1, first = 2, last = 3;
    // enforce error condition.
    assert(position < first);
    int size = 8;
    // sanity check.
    assert(first < last && last <= size);

    std::vector<int> right, wrong;
    // force resize during insertion.
    right.reserve(size);
    // avoid resize during insertion.
    wrong.reserve(size + (last - first));

    for ( int i = 0; i < size; i++ )
     {
       right.push_back(i);
       wrong.push_back(i);
     }

    std::vector<int>::iterator i;
    i = right.begin();
    right.insert(i + position, i + first, i + last);
    i = wrong.begin();
    wrong.insert(i + position, i + first, i + last);

    assert(right == wrong);
    return 0;
}

Note: The above opinion applies to vector specifically, not containers in general. Also, the suggestion that the above behavior may be a bug has nothing to do with the standard, rather the ease of implementing a robust self insertion for vector.

Johnny Cage
  • 41
  • 1
  • 4