ext::hash_set vs. std::set

I don't know about the containers in ext:: since they're proprietary (your vendor may be able to give you more information), but from the names I would assume they provide unordered associative containers. That means they could give O(1) performance for insertions and retrievals where the standard associative containers give O(log n) performance, but do not provide ordered sequential traversal. You would likely also need to provide a good hashing function.

It's also possible that a poor hashing function could resul in a degenerate unordered associative container with O(n^2) performance in insertions and finds. This is never possible with a standard associative container.

A hash table is different from a self-balancing binary search tree.

Take a data structures class to find out how.

Quote:

Original post by loufoque A hash table is different from a self-balancing binary search tree. Take a data structures class to find out how.

I took a data structures class, unfortunately sets were the one type they neglected to cover, which is why I wanted more info on the differences between them. I assumed a std::set was hashed and unordered, which is why I was curious about the differences. Now I know sets are a binary tree.

It is not specified as such, but there is no known alternative given the complexity requirements.

I think most implementations are red-black trees, but AVL or splay trees would be fine too.

You may want to read wikipedia for further information, it should have some stuff on data structures.