誰もが知っているわけではない、std :: listの不快な機能

二重リンクリストは、誰もが知っているすべての場所で使用される基本的なデータ構造です。 誰もが理由を知っており、どの場合にベクトルよりも効果的であり、どの演算が線形の複雑さを持ち、どの演算が一定であるか...



ちょっと待ってくださいが、size（）関数の複雑さを知っていますか？

「もちろん私は知っています-O（1）！」多くの人が答えます。

size_type size() const { return _size; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

些細で、効果的で、安全ですね。

私はこの方法でこの機能を実装します、あなたのほとんどは同じことをするでしょう。



ただし、GNU STL実装を書いた人は異なる意見を持っています。





gcc 4.xでのこの関数の実装は次のようになります。

 /** Returns the number of elements in the %list. */ 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; // Thread 1 void thread1_proc () { while (!stop) { std::cout << "List size: " << my_list.size () << std::endl; } } // Thread 2 void thread2_proc () { while (!stop) { int n = rand () my_list.push_back (n); if (n % 2) my_list.pop_front (); } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

最初のスレッドでクラッシュする深刻なリスクがあります。

それはまた

• 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