STL のハッシュと二分木
http://www.kt.rim.or.jp/~kbk/zakkicho/08/zakkicho0804a.html#D20080408-2
詳しくは後で書くかもだけど、とりあえず SGI のページを見るに hash_set は Hashed Associative Container であり(ちなみに set は Sorted Associative Container)、その説明には
A Hashed Associative Container is an Associative Container whose implementation is a hash table. [1] The elements of a Hashed Associative Container are not guaranteed to be in any meaningful order; in particular, they are not sorted.
なんてのっけから書いてあるわけですから(強調は引用者)、 hash_set が順序を保持しなければならないというのは間違いですよ。
実際、ハッシュ表は探索木のようなものと違ってデータが全順序である必要がないことが重要だと思うわけですよ。