std::forward_listを使いたい
なぜなら：
フォワード リストは、コンテナのどこからでも要素をすばやく挿入および削除できるコンテナです。
しかし、*std::forward_list::push_back* の実装はありません。
それを行う理由が1つまたはまったくない場合でも、サポートを追加する高性能な方法はありますか?
18095 次
5 に答える
31
ほとんどすべての状況で反対を推奨するのとstd::forward_list同じように、反対をお勧めします。std::list個人的には、リンク リストが最適なデータ構造であるコードの状況を見つけたことはありません。
C++ では、デフォルトの go-to データ コレクションはstd::vector. push_backそれが本当に必要な場合は、効率的です。その1つの操作の抽象的な大規模な複雑さの測定値だけを見ると、技術的には途中からの効率的な削除と挿入が得られません。しかし、現実の世界では、途中での挿入と削除でもstd::vectorまだ勝ちます。
例として、Bjarne Stroustrup は 100,000 要素std::listとstd::vector. 彼はそれぞれの要素を検索して削除しました。次に、挿入ポイントを見つけて、真ん中に挿入します。彼は でバイナリ検索を使用することもできましたがstd::vector、比較を「より公正」にすることはしませんでした。
結果は、が強いはずstd::vectorのこの状況でも、の強い勝利を示しています。すべてのオブジェクトがメモリ内でどれだけ離れているかによりstd::list、単にトラバースするのに非常に時間がかかります。これは、最新のプロセッサにとっておそらく最も重要なことです。std::liststd::list
この 2 番目のリンクstd::listは、要素のサイズが大きい場合など、 を使用する可能性のある状況を示していることに注意してください。ただし、特定の順序で多くの要素があり、一部を削除する必要がある状況にありました。
これらの要素はどの組み込み型よりも大きくはありませんでしたが、巨大ではなく、32 ビット コンピューターではそれぞれ 20 ～ 30 バイトでした)。要素の数が多かったので、データ構造全体が数百 MiB になりました。データ コレクションは、現在知られている情報に基づいて理論的に有効である可能性のある一連の値でした。アルゴリズムはすべての要素を反復処理し、新しい情報に基づいて有効でなくなった要素を削除しました。パスごとに残りの要素の約 80% が削除された可能性があります。
私の最初の実装は、std::vector横断しながら無効な要素を削除するという単純なアプローチでした。これは小さなテスト データ セットでは機能しましたが、実際に実行しようとすると遅すぎて役に立ちませんでした。コンテナーを に切り替えましたstd::listが、同じアルゴリズムを使用したため、パフォーマンスが大幅に向上しました。ただし、それでも遅すぎて役に立ちませんでした。勝利の変更は に戻すことでしたstd::vectorが、悪い要素をその場で削除する代わりに、新しい を作成し、std::vector良いとわかった要素はすべてその中に入れstd::vector、関数の最後で単純に古いものを破棄して新しいものを使用します。これにより、オリジナルよりstd::vectorも速度が向上しましたstd::list。std::liststd::vector実装であり、これは便利なだけの速さでした。
于 2012-07-07T14:51:32.727 に答える
22
std::forward_list高速挿入と削除をサポートしますが、最後までたどることはできません。を実装する.push_backには、最初にリストの最後に到達する必要があります。これは O(N) であり、まったく高速ではありません。これがおそらく実装されていない理由です。
.before_beginN回インクリメントすることで、最後の要素へのイテレータを見つけることができます
auto before_end = slist.before_begin();
for (auto& _ : slist)
++ before_end;
次に、.insert_afteror.emplace_afterを使用して要素を挿入します。
slist.insert_after(before_end, 1234);
于 2012-01-05T12:32:15.413 に答える
6
std::forward_list のポイントは、std::list の超簡素化バージョンであるため、最後の要素に反復子を格納しません。必要な場合は、次のように自分で維持する必要があります。
forward_list<int> a;
auto it = a.before_begin();
for(int i = 0; i < 10; ++i)
it = a.insert_after(it, i);
于 2012-07-07T13:17:16.993 に答える
5
push_backリストはリストの後ろを追跡せず、前だけを追跡するため、ありません。
最後の要素への反復子を維持し、リストが空かどうかに応じて、またはpush_backいずれかを使用して実装するリストの周りにラッパーを書くことができます。より複雑な操作 (および など)をサポートする場合、これはかなり複雑になります。insert_afterpush_frontsortsplice_after
あるいは、高速である必要がない場合はpush_back、線形時間で実行するのが簡単です。
メモリが非常に逼迫していない限り、最善の解決策は を使用することlistです。これは と同じパフォーマンス特性を持ち、双方向であり、と同様forward_listにサポートします。コストは、要素ごとの追加のポインターです。push_backpush_front
于 2012-01-05T12:35:46.917 に答える
3
残念ながら、コメントを追加することはできません (評判が悪い) が、 forward_list と list の利点の 1 つは、挿入と削除の操作が反復子を無効にしないことです。個々の要素を繰り返し処理しながら要素のコレクションが成長するアプリケーションがありました。イテレータの無効化がないため、セグメント スキャンを実装できました (リストの先頭をセグメントの先頭として、最後のセグメントの先頭を末尾として)。
于 2016-09-21T21:22:55.803 に答える