Mirroring iterators from original container to its copy

Question

I have a class that is a delegate to a container and internally stores an iterator to this container.

class A {
public:
    list<int> m_data;
    list<int>::iterator m_relevantDataStart;

    A(const A & cpy) {
        m_data = cpy.m_data;
        m_relevantDataStart = cpy.m_relevantDataStart; //<--- UNWISE
    }
};

Now the problem is that if I try to write a simple constructor for copying both container and iterator as depicted above, the iterator becomes unusable in the context of the copy, more specifically, I later encounter a runtime exception when trying to perform comparison:

`if(m_relevantDataStart == m_data.begin())` - Expression: list iterators incompatible

This I presume arises because the m_relevantDataStart is still an iterator of m_data of the class I copied from, whereas m_data.begin() points to a copy of the original container.

I found this answer, which appears to be of some relevance, implying that the iterator pointing to the original container would indeed be unusable.

My question and TL;DR: Is there a way to mirror an iterator to original container such that the result of this "mirroring" would point to the corresponding element in the copy container?

I could think of one solution which would require determining items index in the original container (linear complexity when dealing with std::list) and advancing an iterator in the copy container, but unless I used some random-access container instead of std::list it appears to be quite inefficient.

There's also always the option of writing a custom container copying algorithm, which I would really like to avoid.

Answer 1

I don't see much way to avoid starting at the beginning of the copy, and advancing an iterator until you get to the desired point (as long as you use std::list).

If you were to copy the list on your own, you could incorporate that step into walking through the original list, and just save the correct iterator when you get to the point of the iterator into the original list.

Otherwise, copy the list, then advance an iterator in the new list the required number of places:

A(const A & cpy) {
    m_data = cpy.m_data;
    auto walker = cpy.m_data.begin();
    m_relevantDataStart = m_data.begin();
    while (walker != cpy.m_relevantDataStart) {
        ++walker;
        ++m_relevantDataStart;
    }
}

Of course, you could "hide" the complexity a little by using std::distance to find the distance from the beginning to the iterator in the original list, then std::advance (or std::next) to move the iterator in the new one that distance--in fact, for production code, that's clearly preferable; the code above is just showing what's actually going to happen "under the covers").

While this obviously does have linear complexity, unless you're dealing with really large lists, it probably won't add nearly as much to execution time as it might initially appear. Since you've just done a node-by-node copy of the entire list, (at least most of) the data for both the original list and the copy you just created will normally be in the cache, so walking through them will only need to read from the cache (whereas the copying step was much more likely to have to read most of the data from main memory).

If you're dealing with lists that are (even potentially) large enough that the whole thing might not fit in cache, so the second traversal wouldn't be really cheap, you might consider doing the copying in two pieces, then splice the pieces together:

auto m_data = std::list(cpy.m_data.begin(), cpy.m_relevantDataStart);
auto temp = std::list(cpy.m_relevantDataStart, cpy.m_data.end());
m_relevantDataStart = temp.begin();
m_data.splice(m_data.end(), temp);

Given that m_list and temp would use the same allocator, the splice will have constant complexity and the iterator will remain valid across the splice.

Of course, if you were to switch from list to vector, this would all (both the copying and getting the right iterator) use a lot less resources (but you haven't said enough about your other uses to guess about how much you might gain elsewhere from using a list instead of vector or deque).