Riko Riko - 9 months ago 61
C++ Question

In C++, do iterator invalidation rules also apply to pointers for all the std containers?

I have a container C of some elements. In my algorithm, these elements need to be split into two sub-groups C1 and C2, where they will be ordered. Now, in order to avoid storing the same data twice, these two subgroups can either be

  1. std::sets of pointers pointing to the elements in the container C, or

  2. std::sets of iterators pointing to the elements in the container C.

I know that it would work well with iterators when following the Invalidation rules, however I will only be using C1 and C2 sets to dereference the actual value and to move the pointer/iterator from C1 to C2 or the other way around, nothing else.

Conceptually, it makes more sense to me to use pointers, but I'm not sure about two things:

Could the use of pointers actually save some memory for some std containers? (since iterators are generalization of pointers)

Do the Invalidation rules also apply for raw pointers for all std containers?

Answer Source

From C++ FAQ:

Important note: Even though a reference is often implemented using an address in the underlying assembly language, please do not think of a reference as a funny looking pointer to an object. A reference is the object. It is not a pointer to the object, nor a copy of the object. It is the object.

Then whatever operation on those container which doesn't invalidate the reference in your linked question will not invalidate pointer even if that operation invalidate the iterator, which is the case of unordered_[multi]{set,map} insertion.