Iterator into container which is moved

Question

I've got a class which holds in it a container, and an iterator into that container. How can I correctly implement the move constructor? I seem to recall that by Standard, you can't rely on the iterators remaining valid after moving (which is so silly). Is there some means by which I can "update" the iterator if it was invalidated or something? Or will I have to dynamically allocate the container, move it, and then have the iterators remain valid that way?

Answer 1

Update: Using a std::unique_ptr as a holder for the container is the canonical generic solution - simply don't move the container, just transfer the ownership and swap the iterators. As you already said you can special-case this as an optimization, although I'd expect the generic solution to be also quite efficient and I'd only accept more complexity (aka bug-potential) to the code after proving that it's a real performance win for your use-case.

I'll leave the former answer below for future readers: Read it and the comments to see why other solutions are not really working and in which cases they cause trouble.

---

The obvious way to update the 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 generally linear, but constant when the iterator is a random access iterator.

Since you probably don't want to do that, you have two options which should help: Either default construct the new container and use swap without invalidating the iterators or put the container into a std::unique_ptr and move that instead.

The first approach (swap) requires both instances to have the container instance and this might be a bit larger than the simple, single pointer stored inside a std::unique_ptr. When you move your instances around very often, the std::unique_ptr-based approach seems preferable to me, although each access requires one more pointer indirection. Judge (and measure) for yourself what fits best in your case.

Answer 2

I think the implicit guarantee on iterator invalidation holds for the move ctor. That is, the following should work for all containers but 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))
    {}
};

The complicated initialization via a base class is necessary as move assignment isn't required to move if the allocator doesn't propagate for move-assignment. The check for the iterator is required as the end() iterator may be invalidated; this check has to be performed before the container is moved. If you can ensure however that the allocator propagates (or otherwise the move-assignment doesn't invalidate iterators for your cases), you can use the simpler version below, replacing the swap with a move-assignment.

N.B. The sole purpose of the get_init function is to enable ADL. It is possible that foo_base has a member function end, which would disable ADL. The using-declaration stops unqualified lookup to find a possible member function, therefore ADL is always performed. You could as well use std::end(c) and get rid of get_init, if you're comfortable with losing ADL here.

If it should turn out that there is no such implicit guarantee for the move ctor, there's still the 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, a swap has some requirements, defined in [container.requirements.general]/7+8:

The behavior of a call to a container's swap function is undefined unless the objects being swapped 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 shall be swappable and shall be exchanged by unqualified calls to non-member swap. If allocator_traits<allocator_type>::propagate_on_container_swap::value is true, then the allocators of a and b shall also be exchanged using an unqualified call to non-member swap. Otherwise, they shall not be swapped, and the behavior is undefined unless a.get_allocator() == b.get_allocator().

I.e. both containers should (but not have to) have equal allocators.

Move construction OTOH only requires that no exception is thrown (for allocator-aware containers); the allocator is always moved.