stl のサイズの落とし穴

私が昨年入社したとき、会社の基本ライブラリにはLRUCacheがあり、内部の実装はstd::listを使っていました。ただし、std::list を計算する関数は、stl の size() メソッドを直接使用します。その結果、ストレステスト中、パフォーマンスはここで行き詰まりました。
今日、同僚が基本ライブラリで別のキュー実装を発見しました。これも要素数を取得するときに std::list メソッドが使用されていました。
残念ながら、同社の基本ライブラリはヘッダーファイルのみを公開しており、このピットが他の場所に存在するかどうかを一つ一つ確認することは不可能です。

stl の size() メソッドの実装を見てみましょう:

size_type    
  size() const
      { return std::distance(begin(), end()); }

上記のコードの g++ バージョンは 4.2.1 です

明らかに、複雑さは O(N) です。リストに多くの要素がある場合、計算は非常に遅くなります。 したがって、std::list を使用するときは、自分でカウントを維持することを忘れないでください。