std :: list :: spliceと他のリストコンテナの複雑さ

Question

私はさまざまなstd :: listオブジェクトを扱うコードをいくつか持っていますが、現在は非常に非効率的な方法でそれらの間でコンテンツを転送しています（ 1つのリストの任意のセクション、およびその要素を1つずつ第2のリストに移動する）。

list<string> list1, list2; 

list1.push_back("a"); 
list1.push_back("b"); 
list1.push_back("c"); // list1: "a", "b", "c" 

list<string>::iterator iterator1 = list1.begin(); 
iterator1++: // points to "b" 

list2.push_back("x"); 
list2.push_back("y"); 
list2.push_back("z"); // list2: "x", "y", "z" 

list<string>::iterator iterator2 = list2.begin(); 
iterator2++; // points to "y" 

list1.splice(iterator1, list2, iterator2, list2.end()); 

// list1: "a", "y", "z", "b", "c" 
// list2: "x" 

私はの複雑さに関する質問がある：私は今と私のコードを置き換えるつもりはstd ::リスト::スプライス機能、を知っていた前に、私には、例えば、いくつかの時間前にこのコードを書きましたスプライス機能それは（私の例では）iterator2とlist2.end（）にスプライシングされている最初と最後の要素の間の範囲で線形複雑度を有するべきである

http://www.cplusplus.com/reference/stl/list/splice/

、ソースは、このことを示唆している：このソースによれば、イテレーターの進歩によるものです。私はこれで生きることができますが、私は一定の複雑さを望んでいました。

私の仮定（私はこのソースを見つける前）であった。このような何かスプライス機能することを：「x」および「y」との間のリンクを切断

1. を
2. 「Z」との間のリンクを切断そしてlist2.end（）
3. フォーム（ "X" とlist2.end間のリンク）
4. "a" および "Y" との間のリンクを形成する "a" および "b"
5. との間のリンクを切断します
6. "y"と "b"の間のリンクを形成する

こうして両方のリストを復元してチェーンを完成させます。

同じ原則が任意のサイズのリストに適用されます。スプライス関数がイテレータを進める必要がある場所がわかりません。イテレータの仕事をするために必要なイテレータをすべて提供しているからです。

私の質問は、どのようにC + +の仕様はこれを扱うのですか？スプライスの開始点と終了点でのみリンクを壊して再形成するのですか、それとも各リンクを1つずつ進めますか？後者の場合、他のリストコンテナ（QTなど）が前者を提供していますか？私のコードはシミュレーションプログラムの内部ループの内部にあるので、線形の複雑さよりもむしろ一定にすることは非常に貴重です。

Answer 1

これは、C++ 11の標準化中に非常に懸念されるトピックでした。問題は、リストを含むすべての標準コンテナにも一定時間sizeの操作があることです。

C++ 11より前の多くの実装では、異なるリスト間の直線時間がsizeであり、spliceは一定時間でした。 C++ 11では、sizeが定数であり、spliceが線形である必要があります。

スプライシングされた範囲の長さが1つずつカウントされない場合、コンテナはいくつの要素が削除されて追加されたかを把握することができず、sizeを呼び出す必要がありますこの情報をO（N）時間に回復する - スプライスされた部分だけでなく、シーケンス全体のうちのより大きなNを使用する。

O（1）sizeを必要としない限り、非標準のlistコンテナは、引数が正しいため、コンテナは希望の操作を提供できます。

他のライブラリについては...私は気づいていませんが、ブーストはに1つあります。あなたが自分で書く方法をはっきりと理解しているので、そうすることは、Qtのような大きなライブラリと競合するよりも、あまり努力する必要はありません。

スレッドの安全性が必要ない場合は、std::listのラッパーを実装できます。この場合、各コンテナはシングルトンリストのサブレンジのみを所有します。これにより、標準インタフェースを複製する際のプログラミング作業の大半が省略されます。