二重リンクリストは、誰もが知っているすべての場所で使用される基本的なデータ構造です。 誰もが理由を知っており、どの場合にベクトルよりも効果的であり、どの演算が線形の複雑さを持ち、どの演算が一定であるか...
ちょっと待ってくださいが、size（）関数の複雑さを知っていますか？
「もちろん私は知っています-O（1）！」多くの人が答えます。
size_type size() const { return _size; }
些細で、効果的で、安全ですね。
私はこの方法でこの機能を実装します、あなたのほとんどは同じことをするでしょう。
ただし、GNU STL実装を書いた人は異なる意見を持っています。
gcc 4.xでのこの関数の実装は次のようになります。
size_type size() const { return std::distance(begin(), end()); }
あなたが私を信じていないなら、あなたのディストリビューションをチェックしてください。
ここで何が見えますか？ サイズを取得するなどの簡単な操作を実行するために、リストではカウントを伴う完全なパスを実行します！
これは、この関数をループに入れてリストを調べた場合、アルゴリズムの複雑さが自動的にN倍になることを意味します。
for (std::list <int>::const_iterator I = my_list.begin (); I != my_list.end (); ++I) { if (*I > my_list.size ()) { std::cout << "Haha! "<< *I << std::endl; } }
一見明らかなO（N）の代わりに、ここでO（N ^ 2）を取得します。 リストに100個のアイテムがあると便利です。 しかし、1,000,000の場合はどうでしょうか？
また、マルチスレッド環境ではsize（）の呼び出しが安全でないことも意味します。
std::list <int> my_list;
最初のスレッドでクラッシュする深刻なリスクがあります。
それはまた
- 2つのリストを比較するには、簡単なサイズ比較で90％のケースをカットするのではなく、常にフルパスを実行する必要があります。
- 効率の悪いサイズ変更。 ここには2つのケースがあります
1.サイズの縮小。 リストのサイズがわかっている場合（O（1）で読むことができます）、末尾からいくつかの要素を削除するか、先頭からいくつかを残すかによって、最初からパッセージを開始するか、最後からパッセージを開始するかを決定できます。 GNU実装では、これは不可能です。
2.サイズの増加。 リストのサイズがわかっている場合は、不足している要素を追加するだけで十分です。 GNUの実装では、常にリストで完全なパスを実行する必要があります。
- おそらく知っている他の何か、教えてください。
では、GNUプログラマーがこの方法でリストを実装したのはなぜですか？
_size内部変数を維持する必要がないため、スプライスをO（1）で実装できます。そうしないと、O（N）が最悪の場合になります。
spliceは、あるリストから別のリストに連続した要素を転送する操作です。 リストの新しいサイズを数える必要がないので、あるノードから別のノードにポインターを「切り替える」だけで十分です。 一定時間。
_size内部変数があるため、転送する要素の数を計算し、両方のリストでそれに応じて更新する必要があります。
これがその理由です。 ところで、この操作はどのくらいの頻度で使用しますか？ そして、上記のすべて？
一般的に、注意してください。 また、他のSTL実装では、変数_sizeはO（1）に対しても適切に機能することに注意してください。 異なるプラットフォームで異なるSTL実装を使用してプロジェクトを構築する場合は、2回注意してください。
私はこれにお辞儀をします。 金曜日の植物の記事でごめんなさい。
UPD新しいC ++ 11標準では、すべてのSTLコンテナのサイズがO（1）で機能する必要があり、これは非常に優れています。
ただし、GNU STL実装に変更を加える試みは、これまでのところバイナリ互換性の問題のために失敗しています。 詳細はこちらgcc.gnu.org/bugzilla/show_bug.cgi?id=49561