1

I'm using a deque in one of my C++ programs, and was reading the documentation for insert on cppreference.com. Most of it made sense except this bit:

All iterators, including the past-the-end iterator, are invalidated. References are invalidated too, unless pos == begin() or pos == end(), in which case they are not invalidated.

What does this mean? Is this saying that references to the deque itself are invalidated, or references to its elements, or references to the iterators? Or something else entirely?

Here's a link the doc in question: http://en.cppreference.com/w/cpp/container/deque/insert

Baum mit Augen
  • 49,044
  • 25
  • 144
  • 182
Dovahkiin
  • 946
  • 14
  • 25
  • 3
    References to the elements. – Baum mit Augen Jan 17 '17 at 01:04
  • @BaummitAugen How is that possible? C++ references can't be changed once they've been assigned. – Dovahkiin Jan 17 '17 at 01:05
  • [Related](https://stackoverflow.com/questions/913980/confusion-on-iterators-invalidation-in-deque) – Baum mit Augen Jan 17 '17 at 01:06
  • Okay, but if it's simply memory chunks then why does 'insert' invalidate the iterators to the beginning/ end? @BaummitAugen – Dovahkiin Jan 17 '17 at 01:11
  • It creates a space at the insertion point by shuffling the elements towards either the begining or the end which ever is closer. If a new begining or ending block is needed one is created. This will invalidate the begin/end iterators. – Richard Critten Jan 17 '17 at 01:23
  • With a `deque` you can add to the beginning and end without repositioning anything in the middle because of how a `deque` grows. Insert into the middle of a `deque` and things are going to have to move to make room. Once things move, Crom only knows at what the old iterators point. – user4581301 Jan 17 '17 at 01:25

1 Answers1

1

A deque is an object. It is a container, therefore it contains other objects within it's internal storage. Those are elements stored in a deque.

You can access those elements. Accessing an element is basically getting a reference back from the container. If you check it, all of the methods under element access section return a reference type.

You can make a copy of accessed element, but you can store the reference itself. T foo = d.front(); vs T& bar = d.front();. (Let d be some std::deque<T>)

A reference to a deque would be auto& ref_d = &d;. This is something else.

So:

1. What effect does “insert” have on references to deques?

None. references to d are fine.

2. What does this mean?

A deque is designed in such a way that inserting at the beginning or at the end of it does not invalidate the references to the elements which you might have already stored. Though if you insert in the middle, the elements might move in memory. Note that the bar is not touched. Precisely because it cannot be, it gets invalidated. Previously obtained reference (or iterator) doesn't point to anything meaningful anymore, thus dereferencing it is illegal.

3. Is this saying that references to the deque itself are invalidated?

Nope, as in 1.

4. or references to its elements [are invalidated]?

Yes, as in 2.

5. or references to the iterators [are invalidated]?

You again seem to confuse what is what. A reference to an iterator would be std::deque<T>::iterator& iter_ref;, if you obtain an iterator from a deque. E.g. auto iter = d.begin(); and make a reference to it iter_ref = &iter;, an insert doesn't make *iter_ref illegal, it invalidates the iterator, so *iter is illegal (or **ref_iter).

Note: I am not saying that something like std::deque<T>& ref_d or std::deque<T>::iterator& iter_ref make sense, but this is semantical meaning of "reference to a deque" and "reference to an interator".

luk32
  • 15,812
  • 38
  • 62
  • So, if I understand correctly... if you call insert on any position other then the front or end, then the iterators may be invalidated, but inserting at the front or end preserves the validity of the iterators? – Dovahkiin Jan 17 '17 at 02:35
  • Exactly. This is what your quote says: "*All iterators, including the past-the-end iterator, are invalidated. References are invalidated too, unless `pos == begin()` or `pos == end()`, in which case they are not invalidated.*" You just came up with additional terms of "reference to deque" and "reference to iterator" in your question for some reason, and got confused. – luk32 Jan 17 '17 at 02:37
  • But any references to elements that were created before the call to `insert` should still be valid references, correct? – Dovahkiin Jan 17 '17 at 03:04
  • 1
    @Dovahkiin. No. Once `insert` causes elements to be moved all bets are off. Those references may refer to the same place, but they could also refer to wrong element in the `deque`, the not-yet reused leavings of part of the `deque`'s old datastore, another data structure sitting in the space the `deque`'s datastore previously occupied, nothing, or anything in between. While you can make guesses, you can't know in the general sense. Assume they are all timebombs waiting to explode your program and get rid of them. – user4581301 Jan 17 '17 at 18:20