c++ - 将迭代器从原始容器镜像到它的拷贝

Question

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

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()指向原始容器的拷贝。

我找到了 this answer ，这似乎有一定的相关性，暗示指向原始容器的 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 或双端队列获得多少)。