問題タブ [forward-list]

std::forward_listを使いたい

なぜなら：

フォワード リストは、コンテナのどこからでも要素をすばやく挿入および削除できるコンテナです。

しかし、*std::forward_list::push_back* の実装はありません。

それを行う理由が1つまたはまったくない場合でも、サポートを追加する高性能な方法はありますか?

forward_list関数splice_after（参照用）、具体的には、指定されたリンクの関数＃3があります。listが単独でリンクされていることを考慮して、それを実装するにはどうすればよいでしょうか。

演習として、実装するときに、前にノードに到達するまで（に接続できるように）、また前にノードに到達するまで（現在のリストのノードをノードに接続できるように）、リストを繰り返す必要がfirstありましたfirst。前）。これは私にはひどく効率的ではないようで、反復なしでそれを行うためのより良い方法があるかどうか疑問に思っていましたか？lastlastlast

C++11 のノード用のメモリ プールを作成しますforward_list。

BOOST プールメモリを で使用できますstd::forward_listか?

あるリストから別のリストへの範囲のスプライシングは、size()の複雑さを線形にすることを犠牲にして、一定の時間で達成できます。

C++11 では、一定時間であるstd::list必要がある場合に変更されました。size()これにより、たとえば gcc の実装が壊れました。[C++0x] std::list::size complexを参照してください。

range 以外splice()に、以前の C++03 準拠の実装で一定時間にできなかった他の理由はありますか? size() std::list

リスト全体または範囲を線形に接合するのはなぜ std::forward_listですか?

splice_after()、ケース (1) および (3)を参照してください。標準ドラフト N3485の 23.3.4.6 forward_list 操作 [forwardlist.ops] も参照してください。も実装していstd::forward_listませんsize()。

splice_after()forward_list が単独でリンクされたリストであることは知っていますが、一定の時間で範囲を実行できない理由がわかりません。私はおそらくここで些細なことを見逃しています...

編集: OK、少なくとも部分的には私の誤解でした。4 がソース リストに残らないと思っていました。コード：

出力：

[first, last]両方のエンドポイントを含めて range をスプライスしたい。before firstと toの要素へのイテレータがありますlast。私はそれを行うことができましsplice_after()たが、線形時間でしかできませんでした。

このスプライスは一定時間でできると思います。どうすればそれを行うことができstd::forward_listますか?

質問が明確でない場合は、私の問題を示すコード例を次に示します。

ライブワークスペースのコード

出力：

ある時点で、N数値のコレクションがあり、中央値の要素がわかっているとしますM。これで、新しい値 が与えられたXので、 を更新する必要があるかもしれませんM。(むしろ、扱っている数値がすべて一意であると仮定する必要があります。また、すべてのサンプルは連続して受信されるため、同時実行性の問題はありません。)

新しい平均の計算は簡単です。古い平均を取り、 を足しX、 を掛けN、 で割りN + 1ます。(これは、N 個の要素の平均がどのように定義されているかを調べれば明らかです。今のところ、数値についてはあまり心配していません。)

私の質問は次のとおりです。中央値を更新するという問題に、創造的/斬新な（またはおそらく最適な）アプローチを提案できる人はいますか? 以下に例 (私自身の設計の簡単なアイデア) を示し、少し分析します。

このサンプルではstd::forward_list、​​C++ 11 が最近これに遭遇した場所であるため、を使用します。std::forward_list<T> sorted;一般性を失うことなく、これを正しい方法で行っていると仮定します: これまでに 遭遇した要素 (タイプ T) の順序付けられたリストを維持しますT x;。

ところで、誰かがこれのためのより良い（より効率的/エレガントな）方法を持っているかどうか興味があります. 不満は大歓迎です。

Xは の一部になりました。私sortedの考えを簡単に説明すると、次のようになります。

ここで起こる良いこと (多少見づらくない場合) は、次のとおりです。イテレータを 2 回前方に移動するため (そして安全に、2 回の比較の代償を払って追加することもできます)、 にend()到達すると、適切な（中央値）値になります。奇数の要素Mがある場合は、そのサンプルだけです。そうでない場合は、この要素と古い (押し出された) 中央値の平均です。奇数と偶数が入れ替わるため、古いものと新しいもののどちらかMが実際にコレクションに含まれます。この推論は正しいですよね？

私の O(3n) メソッドがゴミだと思うなら、コメントする必要はありません。出発点として提案しているだけです。

要求のリストを実装し、それらを一度に 1 つずつ送信し (スロットリング)、応答を待つ必要があります (常に順番に)。したがって、操作は次のとおりです。

• 挿入 (最後に)
• 削除 (開始時)
• 前に進む (「送信済み」ポインター)

を発見したばかりstd::forward_listで、使おうと思っています。しかし、これが機能するためには、送信されたポインター用の 1 つのイテレーターと挿入用の 1 つのイテレーターを追跡する必要があり、オブジェクトを挿入および削除するときにそれらを壊すことはできません。

直感的には、リンクされたリストの反復子は挿入と削除に対して安定していると思いますが、誰かがこれを確認できますか。また、挿入イテレータをリセットする必要があるリストを空にする場合、特別なケースを作成する必要がありますbefore_beginか?

コードをxlCに移植しています。
forward_list が xlC でサポートされているかどうか疑問に思っていますか?
私はテストプログラムで試しました

g++ では問題なくコンパイルできますが、xlC ではエラーが発生します。
次のコンパイル行を試してみました:
xlC forward_list_test.cpp
xlC -D __IBMCPP_TR1__ forward_list_test.cpp
しかし、エラーは同じです:
"forward_list_test.cpp", 行 1.10: 1540-0836 (S) #include ファイルが見つかりません。

サポートされている場合、コンパイルするために何か追加する必要がありますか?
注：xlC 11を使用