29

さまざまな 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 関数が次のようなことをするというものでした:

  1. 「x」と「y」の間のリンクを切断します
  2. "z" と list2.end() の間のリンクを切断します
  3. "x" と list2.end() の間にリンクを形成する
  4. 「a」と「b」の間のリンクを切断します
  5. 「a」と「y」の間にリンクを形成する
  6. 「y」と「b」の間にリンクを形成する

したがって、両方のリストを完全なチェーンに復元します。

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

私の質問は、C++ 仕様はこれをどのように扱っているのでしょうか? スプライスの始点と終点でのみリンクを切断して再形成しますか、それとも各リンクを 1 つずつ進みますか? 後者の場合、前者を提供する他のリスト コンテナ (QT など) はありますか? 私のコードはシミュレーション プログラムの内部ループ内に存在するため、線形の複雑さではなく一定の複雑さを与えることは非常に価値があります。

4

1 に答える 1

33

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

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

問題は、スプライスされた範囲の長さが 1 つずつカウントされない場合、コンテナーは削除および追加された要素の数を追跡できず、次の呼び出しでsizeこの情報を O で回復する必要があることです。 (N) 時間 — つなぎ合わせた部分だけでなく、シーケンス全体のより大きい N を使用します。

listO(1) を必要としない限りsize、引数は正しいため、非標準のコンテナーは目的の操作を提供できます。

他のライブラリについては…私は知りませんが、Boost にはあるはずです。(確認したところ、そうではないので、誰か始めてください!) 自分で作成する方法を明確に理解しているので、Qt のような大規模なライブラリと競合するよりも簡単に作成できる可能性があります。

スレッド セーフが必要ない場合は、std::list各コンテナーがシングルトン リストのサブ範囲のみを所有するラッパーを実装できます。これにより、標準インターフェースを複製する際のプログラミング作業のほとんどが不要になります。

于 2012-04-13T03:30:49.127 に答える