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

Question

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

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仍然是m_data我从中复制的类的迭代器，而m_data.begin()指向原始容器的副本。

我找到了这个答案，似乎有一定意义，这意味着iterator指向原始容器确实是不可用的。

我的问题和TL; DR：有没有办法将迭代器镜像到原始容器，以使此“镜像”的结果指向副本容器中的相应元素？

我可以想到一种解决方案，该解决方案需要确定原始容器中的项目索引（处理时的线性复杂度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;
    }
}

当然，您可以通过std::distance在原始列表中查找从起点到迭代器的距离，然后std::advance（或std::next）将迭代器移动到新的那个距离中，从而稍微“隐藏”复杂度-实际上，是为了生产代码，这显然是可取的；上面的代码仅显示了“幕后”实际发生的情况。）

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

如果要处理的列表足够大（甚至可能）以至于整个列表可能都不适合缓存，那么第二遍遍并不是很便宜，您可以考虑分两部分进行复制，然后将这些部分拼接起来一起：

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或双端队列）。