50

I recently discovered that the implementation of the hash map in C++ will be called unordered_map.

When I looked up why they weren't just using hash_map, I discovered that apparently there are compatibility issues with the implementation of hash_map that unordered_map resolves (more about it here).

That wiki page doesn't give much more information so I wondering if anyone knew some of the issues with hash_map that unordered_map resolves.

cbuchart
  • 10,847
  • 9
  • 53
  • 93
kidnamedlox
  • 806
  • 1
  • 7
  • 14

1 Answers1

82

Since there was no hash table defined in the C++ standard library, different implementors of the standard libraries would provide a non-standard hash table often named hash_map. Because these implementations were not written following a standard they all had subtle differences in functionality and performance guarantees.

Starting with C++11 a hash table implementation has been added to the C++ standard library standard. It was decided to use an alternate name for the class to prevent collisions with these non-standard implementations and to prevent inadvertent use of the new class by developers who had hash_table in their code.

The chosen alternate name is unordered_map which really is more descriptive as it hints at the class's map interface and the unordered nature of its elements.

rubenvb
  • 74,642
  • 33
  • 187
  • 332
Stef
  • 6,729
  • 4
  • 34
  • 26
  • 5
    And this is one of the things that show that the `std` namespace didn't quite do what they had hoped. Not that I know what would have reasonably prevented the problem. – Michael Burr Oct 29 '09 at 20:22
  • MSVC had stdext for their Standard extension libraries. – Puppy Nov 04 '10 at 17:45
  • 9
    @MichaelBurr How has `namespace std` failed here? None of the non-standard `hash_map`s are in that namespace (legally, at least), so I don't quite understand that statement by @Stef... Is there a source for that? – rubenvb Jul 22 '14 at 07:22
  • 3
    @rubenvb From the [C++ Standards Committee Papers](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1456.html): "since several vendors have defined classes in namespace std with the hash_* names, defining a standard class with that name would introduce a nasty backward compatibility problem". – pera Sep 03 '17 at 02:33
  • While it makes sense as an more interface-level name it still requires you to have a `std::hash` function for the key type. `unordered_map` gives the illusion that you can just throw in any custom type without needing to do anything else – Jimmy T. Sep 02 '22 at 08:24