Stroustrup says a map keeps its elements ordered so that an iteration traverses the map in order. Does that mean that a map cannot be implemented as a hash table? Does anyone know how it is usually implemented?
Stroustrup says a map keeps its elements ordered so that an iteration traverses the map in order. Does that mean that a map cannot be implemented as a hash table? Does anyone know how it is usually implemented?
It is generally implemented as a binary tree. It is guaranteed O(log n) lookup rather than the O(1) lookup of a hash map.
If you can find an implementation, you can use unordered_map and other unordered_* containers from TR1 as an almost standard hash map.
Actually, that would be O(1) with a perfect hashing algorithm and a big enough hash table. In practice, it can be anywhere from O(1) to O(log n). (Although hashing may also have a non-constant complexity)
As far as I know a map does not need to keep it's elements ordered. I couldn't find anything about it in the C++ standard either. So you shouldn't really depend on it. (Actually, I sometimes do at an ACM programming contest. I mean, it will always work on the compiler they use... I hope...
Technically worst case for hash map is O(n) if everything hashes to the same bucket. There are certainly various benefits and drawbacks that should be considered.
The standard map container does keep its elements ordered (why else would they call the hashed map unordered?). I'll do a quick check of the standard to see if I can find it.
I think that gives the basic idea.23.1.2 Associative containers
1 Associative containers provide an ability for fast retrieval of data based on keys. The library provides four
basic kinds of associative containers: set, multiset, map and multimap.
2 Each associative container is parameterized on Key and an ordering relation Compare that induces a strict
weak ordering (25.3) on elements of Key. In addition, map and multimap associate an arbitrary type T
with the Key. The object of type Compare is called the comparison object of a container. This comparison
object may be a pointer to function or an object of a type with an appropriate function call operator.
...
9 The fundamental property of iterators of associative containers is that they iterate through the containers in
the non-descending order of keys where non-descending is defined by the comparison that was used to construct
them. For any two dereferenceable iterators i and j such that distance from i to j is positive,
value_comp(*j, *i) == false
Last edited by Daved; 11-06-2008 at 06:04 PM.
Although std::map is not required to be a tree, it does have some pretty stringent requirements placed on it which constrain it to almost certainly be a balanced binary tree.
Initially you might think that you could use a hash table with forward/backward links in the hash nodes to allow in-order traversal, but think of the difficulties when you insert a new node. It is probably impossible to maintain the requirement that insertion be O(log N).
A skip list MIGHT be able to meet the requirements but I have not seen any map implementations using skip lists.
Code://try //{ if (a) do { f( b); } while(1); else do { f(!b); } while(1); //}
Do skip lists have any advantage over trees at all?
All the buzzt!
CornedBee
"There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
- Flon's Law
Code://try //{ if (a) do { f( b); } while(1); else do { f(!b); } while(1); //}
Another thought I had was that if you really wanted a map with O(1) lookup while still matching the other requirements, you could mate a balanced binary tree with a hash table at the expense of increased memory overhead.
In practice the O(1) doesn't really outclass O(log N) until N gets fairly large.
Code://try //{ if (a) do { f( b); } while(1); else do { f(!b); } while(1); //}