Thread: How do maps keep elements ordered?

  1. #1
    Registered User
    Join Date
    Oct 2008
    Posts
    55

    How do maps keep elements ordered?

    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?

  2. #2
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    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.

  3. #3
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    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...

  4. #4
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    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.

    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
    I think that gives the basic idea.
    Last edited by Daved; 11-06-2008 at 06:04 PM.

  5. #5
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by nucleon View Post
    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?
    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);
    //}

  6. #6
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    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

  7. #7
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by CornedBee View Post
    Do skip lists have any advantage over trees at all?
    The only advantage I can think of is that the insertion/deletion logic might be a bit easier to grasp, as opposed to tree rotations and other balancing operations. But the difference in difficulty is subjective.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  8. #8
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    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);
    //}

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. using realloc for a dynamically growing array
    By broli86 in forum C Programming
    Replies: 10
    Last Post: 06-27-2008, 05:37 AM
  2. Randomly rearranging the elements in a vector
    By Signifier in forum C++ Programming
    Replies: 11
    Last Post: 08-01-2007, 12:21 PM
  3. way to check 3 elements of array and set 4th
    By Syneris in forum C++ Programming
    Replies: 3
    Last Post: 01-09-2006, 11:30 AM
  4. Replies: 2
    Last Post: 08-03-2003, 10:01 AM
  5. Array elements values not being assigned
    By Sardien in forum C Programming
    Replies: 4
    Last Post: 02-11-2002, 01:45 PM