Mirroring iterators from original container to copy
I have a class that is a delegate in a container and internally stores an iterator in that 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 to copy both the container and the iterator as shown above, the iterator becomes unusable in the context of the copy, more specifically, I later run into a runtime exception when trying to do the comparison:
`if(m_relevantDataStart == m_data.begin())` - Expression: list iterators incompatible
I assume this is because it m_relevantDataStart
is still an iterator m_data
for class I, but rather m_data.begin()
points to a copy of the original container.
I found this answer , which seems to have some value, implying that iterator
pointing to the original container would indeed be unusable.
My question and TL; DR: Is there a way to mirror the iterator in the source container so that the result of this "mirroring" points to the corresponding item in the copy container?
I could think of one solution that would require determining the index of the items in the original container (linear complexity when working with std::list
) and advancing the iterator in the copy container, but if I didn't use a random access container instead it std::list
seems quite inefficient.
It is also always possible to write your own container copying algorithm, which I would really like to avoid.
source to share
I don't see much of a way to avoid starting at the beginning of the copy and advancing the iterator until you reach the point you want (as long as you are using std::list
).
If you needed to copy the list yourself, you can include this step in traversing the original list and just keep the correct iterator when you go to the point of the iterator in the original list.
Otherwise, copy the list, then move the iterator in the new list as many places as needed:
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 can "hide" the complexity a bit, using std::distance
to find the distance from the start to the iterator in the original list, then std::advance
(or std::next
) to move the iterator to a new one, which distance is actually, for production code, which is clearly preferable; the code above just shows what will actually happen "under the covers").
While this obviously has linear complexity, unless you are dealing with really large lists, it probably won't add nearly as much runtime as it might seem. Since you've just finished a copy of the entire list (at least most of it), both the original list and the copy you just created tend to be in the cache, so walking through them will only need to read from the cache (at that time as a copy step, you will most likely have to read most of the data from main memory).
If you are dealing with lists that are (even potentially) large enough that the whole thing would not fit in the cache so that the second workaround would not be really cheap, you might consider copying in two, then splicing 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
both temp
will use the same allocator, the splicing will have constant complexity, and the iterator will remain valid in the splice.
Of course, if you were to switch from list
to vector
, this whole thing (both copying and getting the correct iterator) would use a lot less resources (but you haven't said enough about your other purposes to know how much you could get elsewhere from using a list instead of vector or deque).
source to share