c++ - C++ STL セットの実装

Question

C++ セットが、バイナリ ツリーによって提供される O(log n) と比較して O(1) の平均ケース複雑度を提供できるハッシュセットとしてではなく、バイナリ ツリーとして実装されるのはなぜですか?

Answer 1

C++ セットはT's 比較演算子によって順序付けられるため、予測可能な方法でメンバーを反復処理できます。セットで行うことは要素の挿入、メンバーシップのテスト、および/または削除だけであることがわかっている場合std::unordered_set、ハッシュセットを実装する は C++11 以降そのために存在します。

Answer 2

John Nagle によると、2006 年のcomp.lang.c++.moderatedへの投稿から:

実際の理由は、仕様のハッシュ テーブルの部分を書いていた人が時間内に書き終えなかったことです。それで全部です。

標準化プロセスはそのようなものです。