将迭代器从原始容器镜像到它的副本

Question

我有一个 class，它是一个容器的委托，并在内部存储一个迭代器到这个容器。

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
    }
};

现在的问题是，如果我尝试编写一个简单的构造函数来如上所述复制容器和迭代器，迭代器在复制的上下文中变得不可用，更具体地说，我稍后在尝试时遇到运行时异常执行比较：

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

我认为这是因为 m_relevantDataStart 仍然是我从中复制的 class 的 m_data 的迭代器，而 m_data.begin() 指向原始副本容器。

我找到了，这似乎有点相关性，暗示指向原始容器的iterator确实无法使用。

我的问题和 TL;DR: 有没有办法将迭代器镜像到原始容器，这样 "mirroring" 的结果将指向相应的元素在复制容器中？

我能想到一个解决方案，它需要确定原始容器中的项目索引（处理 std::list 时的线性复杂度）并在副本容器中推进迭代器，但除非我使用一些随机访问容器而不是 std::list 它似乎效率很低。

也总是可以选择编写自定义容器复制算法，我真的很想避免这种情况。

Answer 1

我看不出有多少方法可以避免从副本的开头开始，并推进迭代器直到到达所需的点（只要您使用 std::list）。

如果您要自己复制列表，则可以将该步骤合并到遍历原始列表中，并在到达原始列表中的迭代器点时保存正确的迭代器。

否则，复制列表，然后在新列表中推进一个迭代器所需的位置数：

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;
    }
}

当然，您可以 "hide" 通过使用 std::distance 找到原始列表中从开始到迭代器的距离，然后 std::advance （或 std::next) 将迭代器移动到新迭代器中那个距离——事实上，对于生产代码，这显然更可取；上面的代码只是展示了实际发生的事情 "under the covers").

虽然这显然具有线性复杂性，但除非您处理真正大列表，否则它可能不会像最初看起来那样增加执行时间.由于您刚刚完成了整个列表的逐个节点副本，原始列表和您刚刚创建的副本的（至少大部分）数据通常都在缓存中，因此遍历它们只会需要从缓存中读取（而复制步骤更有可能必须从主内存中读取大部分数据）。

如果您要处理的列表（甚至可能）足够大，以至于整个内容可能无法放入缓存中，因此第二次遍历不会很便宜，您可以考虑分两部分进行复制，然后拼接在一起：

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);

鉴于 m_list 和 temp 将使用相同的分配器，拼接将具有恒定的复杂度并且迭代器将在整个拼接中保持有效。

当然，如果您要从 list 切换到 vector，这将全部（包括复制和获取正确的迭代器）使用更少的资源（但您没有对你的其他用途说得足够多，可以猜测你在其他地方使用列表而不是 vector 或 deque 可以获得多少）。

将迭代器从原始容器镜像到它的副本

Mirroring iterators from original container to its copy

c++

containers

iterator

copy

copy-constructor