Don't understand iterator, reference and pointer invalidation, an example

Question

I've read a lot of posts abut reference, pointers and iterators invalidation. For instance I've read that insertion invalidates all reference to the elements of a deque, then why in the following code I don't have errors?

#include <deque>

int main()
{
    std::deque<int> v1 = { 1, 3, 4, 5, 7, 8, 9, 1, 3, 4 };
    int& a = v1[6];
    std::deque<int>::iterator it = v1.insert(v1.begin() + 2, 3);
    int c = a;
    return a;
}

When I run this I get 9 as result, so "a" is still referring to the right element. In general I didn't manage to get invalidation errors. I tried different containers and even with pointers and iterators.

In general, provoking undefined behavior does not necessarily mean that it stings you in a simple example like this. — Enlico, Feb 16 '20 at 20:57
Sometimes, [when demons fly out of your nose](http://www.catb.org/jargon/html/N/nasal-demons.html) you don't notice it. It doesn't mean that demons didn't fly of your nose, it just they didn't cause any harm. This time. — Sam Varshavchik, Feb 16 '20 at 21:12
Dereferencing an invalidated iterator may cause undefined behaviour, but if they tell me that references to a deque are always invalidated when inserting an element( unless you use push.front()), I think that that reference ("a") have to be invalid.. I think the problem may be in the definition of invalidation.. I read somewhere that an invalid iterator points to junk data, so why would that reference give me the right value? — Peanojr, Feb 16 '20 at 21:27
Dereferencing an invalid iterator *always* causes undefined behavior. But UB can do anything, including *not* crashing. — HolyBlackCat, Feb 16 '20 at 21:40
@Peanojr, yes, the problem is the definition. _Invalid_ iterator/reference/whatever means that you cannot use it safely, that it **can** cause crash/wrong result/my house bombed, not that using it will certainly cause crash/wrong result/my house bombed. — Enlico, Feb 16 '20 at 21:45
@Peanojr, try the following: get a pointer to [6] before you do the insertion; then get a pointer to [7] after you do the insertion - both pointed, validly, at the element with the value 9 when you got them. Then print the values of the pointers, not the values of the data they are pointing to, the pointers themselves. Do they match? If no, the old pointer is no longer valid, it just happens to point to an address that happens to contain the value you are looking for. — DeducibleSteak, Feb 16 '20 at 21:53

Enlico · Answer 1 · 2020-02-16T21:42:51.013

The following code, on my system, shows the effect of the undefined behavior.

#include <deque>
#include <iostream>

int main()
{
    std::deque<int> v1 = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    for (auto e : v1) std::cout << e << ' ';
    std::cout << std::endl;
    int& a = v1[1];
    int& b = v1[2];
    int& c = v1[3];
    std::cout << a << ' ' << b << ' ' << c << std::endl;
    std::deque<int>::iterator it = v1.insert(v1.begin() + 2, -1);
    for (auto e : v1) std::cout << e << ' ';
    std::cout << std::endl;
    v1[7] = -3;
    std::cout << a << ' ' << b << ' ' << c << std::endl;
    return a;
}

Its output for me is:

1 2 3 4 5 6 7 8 9 10 
2 3 4
1 2 -1 3 4 5 6 7 8 9 10 
-1 3 4

If the references a, b, and c, were still valid, the last line should have been

2 3 4

Please, do not deduce from this that a has been invalidated while b and c are still valid. They're all invalid.

Try it out, maybe you are "lucky" and it shows the same to you. If it doesn't, play around with the number of elements in the containar and a few insertions. At some point maybe you'll see something strange as in my case.

Addendum

The ways std::deques can be implemented all makes the invalidation mechanism a bit more complex than what happens for the "simpler" std::vector. And you also have less ways to check if something is actually going to suffer from the effect of undefined behavior. With std::vector, for instance, you can tell if undefined behavior will sting you upon a push_back; indeed, you have the member function capacity, which tells if the container has already enough space to accomodate a bigger size required by the insertion of further elements by means of push_back. For instance if size gives 8, and capacity gives 10, you can push_back two more elements "safely". If you push one more, the array will have to be reallocated.

DeducibleSteak · Answer 2 · 2020-02-16T21:29:01.823

Sometimes, an operation that could invalidate something, doesn't.

I'm not familiar enough with std::deque implementation to comment, but if you did push_back on a std::vector, for example, you might get all your iterators, references and pointers to elements of the vector invalidated, for example, because std::vector needed to allocate more memory to accomodate the new element, and ended up moving all the data to a new location, where that memory was available.

Or, you might get nothing invalidated, because the vector had enough space to just construct a new element in place, or was lucky enough to get enough new memory at the end of its current memory location, and did not have to move anything, while still having changed size.

Usually, the documentation carefully documents what operations can invalidate what. For example, search for "invalidate" in https://en.cppreference.com/w/cpp/container/deque .

Additionally, particular implementations of the standard data structures might be even safer than the standard guarantees - but relying on that will make your code highly non-portable, and potentially introduce hidden bugs when the unspoken safety guarantees change: everything will seem to work just fine until it doesn't.

The only safe thing to do is to read the specification carefully and never rely on something not getting invalidated when it does not guarantee that.

Also, as Enrico pointed out, you might get cases where your references/pointers/iterators get invalidated, but reading from them yields a value that looks fine, so such a simple method for testing if something has been invalidated will not do.

Don't understand iterator, reference and pointer invalidation, an example

2 Answers2