さまざまな std::list オブジェクトを処理するコードがいくつかあり、現在、それらの間でコンテンツを転送する非常に非効率的な方法を使用しています (1 つのリストの任意のセクションを反復処理し、要素を 1 つずつ 2 番目のリストに移動しています)。リスト)。std::list::splice 関数に気付く前に、このコードを少し前に書きました。たとえば、次のようにコードを置き換える予定です。
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"
スプライス機能の複雑さについて質問があります。このソースによると:
http://www.cplusplus.com/reference/stl/list/splice/
スプライスされる最初の要素と最後の要素 (私の例では iterator2 と list2.end() ) の間の範囲で線形の複雑さが必要であり、ソースはこれがイテレータの進行によるものであることを示唆しています。私はこれに耐えることができますが、私は一定の複雑さを望んでいました.
私の仮定 (このソースを見つける前) は、 splice 関数が次のようなことをするというものでした:
- 「x」と「y」の間のリンクを切断します
- "z" と list2.end() の間のリンクを切断します
- "x" と list2.end() の間にリンクを形成する
- 「a」と「b」の間のリンクを切断します
- 「a」と「y」の間にリンクを形成する
- 「y」と「b」の間にリンクを形成する
したがって、両方のリストを完全なチェーンに復元します。
同じ原則が、任意のサイズのリストに適用されます。splice関数がイテレータを進める必要がある場所がどこにあるのかわかりません。これは、仕事をするために必要なすべてのイテレータを提供しているためです。
私の質問は、C++ 仕様はこれをどのように扱っているのでしょうか? スプライスの始点と終点でのみリンクを切断して再形成しますか、それとも各リンクを 1 つずつ進みますか? 後者の場合、前者を提供する他のリスト コンテナ (QT など) はありますか? 私のコードはシミュレーション プログラムの内部ループ内に存在するため、線形の複雑さではなく一定の複雑さを与えることは非常に価値があります。