21

This is very strange for me, i expected it to be a hash table.

I saw 3 reasons in the following answer (which maybe correct but i don't think that they are the real reason). Hash tables v self-balancing search trees

  1. Although hash might be not a trivial operation. I think that for most of the types it is pretty simple.

  2. when you use map you expect something that will give you amortized O(1) insert, delete, find , not log(n).

  3. i agree that trees have better worst case performance.

I think that there is a bigger reason for that, but i can't figure it out. In c# for example Dictionary is a hash table.

Community
  • 1
  • 1
OopsUser
  • 4,642
  • 7
  • 46
  • 71

4 Answers4

26

It's largely a historical accident. The standard containers (along with iterators and algorithms) were one of the very last additions before the feature set of the standard was frozen. As it happened, they didn't have what they considered an adequate definition of a hash-based map at the time, and there wasn't time to add it before features were frozen, so the original specification included only a tree-based map.

C++ 11 added std::unordered_map (as well as std::unordered_set and multi versions of both), which is based on hashing though.

Jerry Coffin
  • 476,176
  • 80
  • 629
  • 1,111
  • 2
    Surely the standard containers had been worked on for years and years in the STL before standardisation. It's hard to see how there was "no time to add it". Granted, the question only then becomes one of why the STL had this property, which gets us no closer to an answer. – Lightness Races in Orbit Mar 26 '14 at 17:08
  • 1
    @LightnessRacesinOrbit: They had been worked on yes--but keep in mind that (in round numbers) only about half of the STL was accepted into the standard. Especially in terms of actual specification, it appears that quite a bit was being written barely in time for inclusion in the standard. – Jerry Coffin Mar 26 '14 at 17:47
22

The reason is that map is explicitly called out as an ordered container. It keeps the elements sorted and allows you to iterate in sorted order in linear time. A hashtable couldn't fulfill those requirements.

In C++11 they added std::unordered_map which is a hashtable implementation.

Mark B
  • 95,107
  • 10
  • 109
  • 188
  • 1
    Not to be insulting, but I really can't figure out why this is getting up-voted at all. I'd read the question as: "why does the standard require that map be ordered?" and this answers: "because the standard requires that map be ordered." It's certainly true that it does, but this does *nothing* to tell *why*. – Jerry Coffin Mar 26 '14 at 15:46
  • 5
    @Jerry Coffin I read (and answered) the question as "why is the implementation of `map` not a hashtable". Perhaps the OP would clarify their *actual* question. – Mark B Mar 26 '14 at 16:13
  • Question clarification would certainly help. I too do not understand what exactly the OP is seeking help with. – CPlusPlus OOA and D Mar 26 '14 at 16:14
  • @MarkB: Yeah--the basic problem with that is that the standard doesn't mandate using a red-black tree (or a tree at all). There are implementations of map that don't use red-black trees. – Jerry Coffin Mar 26 '14 at 16:56
  • 1
    @Jerry Coffin Just for my own information, what non-tree container fulfills the complexity requirements of `map`? (We agree that it doesn't mandate using a red-black tree) – Mark B Mar 26 '14 at 18:29
5

A hash table requires an additional hash function. The current implementation of map which uses a tree can work without an extra hash function by using operator<. Additionally the map allows sorted access to elements, which may be beneficial for some applications. With C++ we now have the hash versions available in form of unordered_set.

Danvil
  • 22,240
  • 19
  • 65
  • 88
  • The copy constructor and assignment operator `=`, as well as the `<` and `==` operators should be defined for the element(s) being stored in the container (e.g. map, vector, list, deque, etc.). Consequently, both copying and comparing are fully supported. – CPlusPlus OOA and D Mar 26 '14 at 15:41
  • 3
    @cplusplus ooa and d Do you have a reference for this? I never heard of `==` being a requirement of any container. – MatthiasB Mar 26 '14 at 15:44
  • 2
    @MatthiasB: I'm reasonably certain it's *not* a requirement for any container (though it is used by a few algorithms, such as `std::find`). Containers that need to compare for equality do it using `<`: (!a – Jerry Coffin Mar 26 '14 at 15:47
  • @MatthiasB Yes, I first learned about the importance of this from this book: [The STL ](http://www.amazon.com/The-STL-Primer-Graham-Glass/dp/0134549767%3FSubscriptionId%3DAKIAIIBINOD46VC3JCLQ%26tag%3Dstackoverfl08-20%26linkCode%3Dxm2%26camp%3D2025%26creative%3D165953%26creativeASIN%3D0134549767) by Graham Glass and Brett Schuchert. Pages 12 through 16 address preparing a class for use in any container. – CPlusPlus OOA and D Mar 26 '14 at 15:53
  • @JerryCoffin On page 16 of the book above, it describes that all other comparison operations for a container are defined by the `<` and `==` operators. The other comparison operators: `!=`, `>`, `<=`, and `>=` can be defined in terms of `<` and `==`. The STL `utility.h` header is indicated as where this automatic implementation is defined. – CPlusPlus OOA and D Mar 26 '14 at 16:01
  • @JerryCoffin @MatthiasB I would not go so far as to say it is _required_ to define the two comparison operators. The book explains it by saying that having all of them present (e.g. copy constructor, `=`, `<`, and `==` ) are suggested for optimal and generic support for any container, especially one which sorts elements (e.g. the associative ones: map, set, multiset, multimap, etc.) – CPlusPlus OOA and D Mar 26 '14 at 16:09
  • The book shows a very short example comparing two different containers by printing the results of `vector1 == vector2` and `vector1 < vector2`. The contents of `vector1` is used to populate `vector2` on the single line where `vector2` is declared. – CPlusPlus OOA and D Mar 26 '14 at 16:19
  • @JerryCoffin Is there some reference material indicating that the recent Standard Library (formerly STL) implementations use the `<` operator to define all other comparison operations? – CPlusPlus OOA and D Mar 26 '14 at 16:22
  • 2
    @GWW `std::map` does *not* use `operator<` directly, there are two indirections at work: I) `std::map` is just a short-hand for `std::map>` and II) the default implementation of `std::less` uses `operator<`. So you could specialize `std::less` for a certain type `X` to use something other than `operator<`, or (more realistically) you could parameterize the map explicitly with a different comparator, for example `std::map>` to store the keys in descending order. – fredoverflow Mar 26 '14 at 17:02
  • @CPlusPlusOOAandD: Most of what's mandated comes from the standard, of course. For example: "The phrase “equivalence of keys” means the equivalence relation imposed by the comparison and not the operator== on keys. That is, two keys k1 and k2 are considered to be equivalent if for the comparison object comp, comp(k1, k2) == false && comp(k2, k1) == false. For any two keys k1 and k2 in the same container, calling comp(k1, k2) shall always return the same value." Normally `comp` will be `std::less`, so `comp(k1, k2)` is equivalent to `k1 < k2`. – Jerry Coffin Mar 26 '14 at 17:11
  • @JerryCoffin When I next have the time, I will run some tests on what occurs if the `<` and/or `==` operators are not present for a user defined map element (e.g. a test object with private and protected data). It will be conducted with the C++11 settings on both the CLang++ 3.3 version supplied by the Xcode Command Line Tools on OS X Mavericks and the C++11 64-bit Windows compiler within C++Builder. I am not too sure how posting the results as a question would be accepted. Any suggestions on a good style and content presentation? – CPlusPlus OOA and D Mar 26 '14 at 17:26
  • 1
    @CPlusPlusOOAandD: I can pretty much predict the results: having/lacking `==` will make no difference. A type that doesn't define `<` simply won't compile unless you also specify something to to the comparison when you (attempt to) instantiate the map. – Jerry Coffin Mar 26 '14 at 17:31
  • @JerryCoffin Very interesting. Maybe later tonight I will try some basic things first and see which compiler messages appear. I might even try the oldest C++ compiler I have to see what it does. Nothing like having more knowledge... – CPlusPlus OOA and D Mar 26 '14 at 17:40
  • The result will be neither surprising nor generally unexpected. This is fairly basic :) – Lightness Races in Orbit Mar 26 '14 at 18:10
2

Simple answer: because a hash table cannot satisfy the complexity requirements of iteration over a std::map.

Why does std::map hold these requirements? Unanswerable question. Historical factors contribute but, overall, that's just the way it is.

Hashes are available as std::unordered_map.

It doesn't really matter what the two are called, or what they're called in some other language.

Lightness Races in Orbit
  • 378,754
  • 76
  • 643
  • 1,055