C ++で独自の双方向リンクリストを実装することから何かを学ぶことの学術的側面とは別に、std::listが既に存在する場合に、独自の双方向リンクリストを実装することの実際の利点はありますか? 特定のタスクのために自分で物事をより効率的にすることはできますか、または std::list は長年にわたって非常に洗練されているため、ほとんどの場合、二重リンクリストの最適な実装になっていますか?
5 に答える
7
std::list が既に存在する場合、独自の二重リンク リストを実装する実際の利点はありますか?
おそらくそうではありません。
特定のタスクを自分で効率化できるか、
たぶん - タスクによって異なります。たとえば、単方向にリンクされたリストのみが必要な場合があります。これは、より高速になる可能性があります。
または std::list は何年にもわたって洗練されてきたので、ほとんどの場合、二重にリンクされたリストの最適な実装ですか?
おそらく。
これらすべてに対する最良の答えは、おそらく「機能しなくなるまでは標準の実装を使用し、それに対してどうするかを考え出す」ことです。
于 2013-10-09T17:16:23.353 に答える
2
「 C++ で双方向リンク リストを実装する必要があるのはなぜですか?」
あなたはしません。二重にリンクされたリストが必要な場合でも、車輪の再発明を避け、既存の実装を使用します。
于 2013-10-09T17:16:34.937 に答える
2
その質問をしなければならない場合、答えはノーです。
于 2013-10-09T17:17:27.970 に答える
0
std::listはい、特定のタスクよりも双方向リストの方が効率的である可能性があります。にはアルゴリズムの複雑さのトレードオフがstd::listあり、タスクは逆の決定から利益を得る可能性があります。
具体的にstd::listは、C++11 では必須であり、C++03 では推奨される定数時間size()です。つまり、要素の数をオブジェクトに格納する必要があります。
これは、両方のサイズを更新するために、あるリストから別のリストに移動された要素の数をカウントする必要があるため、4 引数バージョンの はsplice()必然的に線形の複雑さを持つことを意味します (ただし、ソース リストが後で空になるなどの特殊なケースは除きます)。スプライス、または 2 つのリストが同じオブジェクトである)。
ただし、多くのスプライシングを行っている場合は、これらを逆にすることを好むかもしれません-定数時間splice()とsize()、最悪の場合は線形時間の関数(リストでスプライスが行われた場合)前回サイズが更新されたときよりも最近）。
偶然にも、GNU の実装はstd::listこの選択を行い、C++11 準拠のために変更する必要がありました。したがって、これが必要な場合でも、必ずしも自分で完全に実装する必要はありません。古い GNU コードを取り除き、有効なユーザー コードになるように名前を変更するだけです。
于 2013-10-09T18:46:48.667 に答える