C++ STL set implementation

Question

Why is the C++ set implemented as a binary tree instead of as a hashset, which can provide average case complexity of O(1) as compared to the O(log n) provided by a binary tree?

Answer 1

Because C++ sets are ordered by the T's comparison operator, which makes it possible to iterate over the members in a predictable way. If you know that all you will do with the set is insert, test membership, and/or remove elements, then std::unordered_set, which implements a hashset, exists for that since C++11.

Answer 2

According to John Nagle, from a 2006 posting to comp.lang.c++.moderated:

The actual reason is that the person who was writing the hash table part of the spec didn't finish it in time. That's all.

Standardization processes are like that.