元のコンテナからそのコピーへのイテレータのミラーリング

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.begin()ポイントのに対し、からコピーされたクラスのm_dataのイテレータであるために生じます。

私は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）の反復子を使用して、新しいものから反復子を移動させることができます。上記のコードは実際に "カバーの下"で起こることを示しています）。

実際に大きなリストを扱っていない限り、これは明らかに線形の複雑さを持っていますが、最初は表示されるほど多くの時間が実行時間に追加されません。リスト全体をノード単位でコピーしただけなので、元のリストと作成したコピーの両方のデータ（通常は少なくとも大部分）は通常キャッシュに格納されるため、キャッシュから読み込む必要があります（コピーするステップでは、メインメモリからほとんどのデータを読み込む必要がありました）。

もしあなたが（潜在的に）十分な大きさでキャッシュ全体に収まらないリストを扱っているなら、2回目の走査は本当に安価ではないでしょうから、その後、一緒に作品を継ぐ：m_listとtempは同じアロケータを使用するであろうことを考えると

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

を、スプライスは、一定の複雑さを持つことになりますし、イテレータはスプライス渡って有効なままになります。

もちろん、listからvectorに切り替えると、これはすべて（コピーと右イテレータの取得の両方）、リソースが大幅に少なくなります（ただし、他の用途については十分に言及していませんベクトルやデキューの代わりにリストを使用することからどれくらいの利益を得られるか）。