Iterator to the container that moves

Question

I have a class that contains a container in it and an iterator into this container. How can I implement the move constructor correctly? I seem to remember that by standard, you cannot rely on iterators that remain valid after the move (which is so stupid). Are there any ways in which I can “update” an iterator if it was invalidated or something else? Or will I have to dynamically allocate the container, move it, and then the iterators remain valid this way?

Answer 1

Update: Using std::unique_ptr as a holder for a container is a canonical general solution - just don't move the container, just transfer ownership and replace the iterators. As you said, this may be a special case as an optimization, although I would expect that the general solution would also be quite efficient, and I would only take more complexity (a mistake) into the code, proving that this is a real performance gain for your use case .

I will leave the previous answer below for future readers: read it and comments to find out why other solutions really do not work, and in which cases they cause problems.

---

The obvious way to update an iterator would be:

 Container c = ...; Container::iterator it = ...; const auto d = std::distance( c.begin(), it ); Container n = std::move(c); it = n.begin(); std::advance( it, d ); 

which is usually linear but constant when the iterator is a random access iterator.

Since you probably don't want to do this, you have two options that should help: either construct a new container by default, or use swap without invalidating the iterators or putting the container in std::unique_ptr and move it instead.

The first approach ( swap ) requires that both instances have an instance of the container, and this may be a little more than a simple, single pointer stored inside std::unique_ptr . When moving instances very often, an approach based on std::unique_ptr seems to be preferable to me, although for each access one more direction of the pointer is required. Judge (and measure) for yourself what is best in your case.

Answer 2

I think that an implicit iterator invalidity guarantee is fulfilled for moving ctor. That is, for all containers, the following should work: std::array :

 template<class Container> struct foo_base { Container c; Container::iterator i; foo_base(foo_base&& rhs, bool is_end) : c( std::move(rhs.c) ) , i( get_init(is_end, rhs.i) ) {} Container::iterator get_init(bool is_end, Container::iterator ri) { using std::end; // enable ADL return is_end ? end(c) : ri; } }; template<class Container> struct foo : private foo_base<Container> { foo(foo&& rhs) : foo_base(std::move(rhs), rhs.i == end(rhs.c)) {} }; 

Sophisticated initialization using the base class is necessary because destination transfer is not required for movement unless the allocator is distributed for transfer destination. An iterator check is required because the end() iterator may not be valid; this check must be performed before moving the container. If you can guarantee that the allocator is distributed (or else the redirection assignment does not invalidate the iterators for your cases), you can use the simpler version below by replacing swap with the move assignment.

NB The only purpose of the get_init function is to enable ADL. It is possible that foo_base has an end member function that disables ADL. The use-declaration stops the unqualified search to find a possible member function, so ADL is always executed. You can also use std::end(c) and get rid of get_init if you are comfortable playing ADL here.

If it turns out that there is no such implicit guarantee to move ctor, there is still an explicit guarantee for swap . For this you can use:

 template<class Container> struct foo { Container c; Container::iterator i; foo(foo&& rhs) { using std::end; // enable ADL bool const is_end = (rhs.i == end(rhs.c)); c.swap( rhs.c ); i = get_init(is_end, rhs.i); } Container::iterator get_init(bool is_end, Container::iterator ri) { using std::end; // enable ADL return is_end ? end(c) : ri; } }; 

However, the swap has some requirements defined in [container.requirements.general] / 7 + 8:

The behavior of calling the container function swap undefined if only the objects to be exchanged have allocators that compare equal or allocator_traits<allocator_type>::propagate_on_container_swap::value is true [...] Any Compare , Pred or Hash objects belonging to a and b must be replaceable and must be replaced by unqualified non-member swap calls. If allocator_traits<allocator_type>::propagate_on_container_swap::value true , then allocators a and b must also be exchanged using an unqualified non-member swap call. Otherwise, they cannot be exchanged, and the behavior is undefined, if only a.get_allocator() == b.get_allocator() .

those. both containers should (but should not) have equal dispensers.

Moving the OTOH design only requires that no exception be thrown (for containers intended for dispensers); the distributor always moves.