STLport, IIRC, always had them. If you picked a specific STL instead of using the c++stdlib bundled with your compiler, you could generally always have hash tables with iterator semantics. But <map> was usually the right choice; even apart from worst-case behavior, you'd always end up needing not just to look things up, but to traverse the collection.

That's true, I remember using <hash_map> back in 2003 or so for something, but since then reverted back to just using <map> and the vanilla C++ stdlib which has always met my requirements and performance needs.

Though, nowadays, I sometimes find myself using tbb::concurrent_unordered_map and tbb::concurrent_hash_map, not to mention tbb::concurrent_queue.