std::map speed?

This is a discussion on std::map speed? within the C++ Programming forums, part of the General Programming Boards category; I think that std::map is a hashtable, right? So it should be fast returning a value from a key. Last ...

  1. #1
    Registered User
    Join Date
    Jun 2002
    Posts
    132

    std::map speed?

    I think that std::map is a hashtable, right? So it should be fast returning a value from a key. Last time I tested it, I remember myself changing to vector cause map was too slow. Was I wrong?
    I found hash_map, but it exists in the stdext namespace. In which header is that class declared?

    Thanks
    Y3K Network http://www.y3knetwork.com
    Bringing the software of the future on the net.

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,452
    > I think that std::map is a hashtable, right?
    http://www.sgi.com/tech/stl/complexity.html
    Who knows.

    http://www.sgi.com/tech/stl/Map.html
    -> http://www.sgi.com/tech/stl/PairAsso...Container.html
    -> http://www.sgi.com/tech/stl/AssociativeContainer.html
    The last one has some complexity guarantees, but the derived containers have other contraints. These derived containers have no such guarantees.

    > So it should be fast returning a value from a key.
    When it comes to O(n) type things, speed is relative rather than absolute. Each has an implicit constant built in to the calculation. Two implementations of the STL may have O(nlogn) performance in the map, but one could be so much better than the other.

    For example, although quicksort is O(nlogn), and bubblesort is O(n*n), the advantage is obvious for large n, since no matter how big the constant is, the value of the terms will dominate.
    For small n however, the larger constant of quicksort (choosing pivots, recursion) could lose out to the simple bubblesort.

    > I remember myself changing to vector cause map was too slow. Was I wrong?
    If you didn't need a map, why did you choose a map?
    The onus is still on the developer to make the right algorithmic and data structure choices. The STL won't protect you from dumb design decisions.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    Jun 2002
    Posts
    132
    I see.

    But who said that I didn't need a map? Vector was just a small replacement, with a name in the structure.

    Anyway thanks
    Y3K Network http://www.y3knetwork.com
    Bringing the software of the future on the net.

  4. #4
    Registered User
    Join Date
    Aug 2003
    Posts
    470
    std::map is typically a red-black tree, and unless if your dataset is over something like 15 a sequential search might be faster. The hash table has not been standardized yet into the stl.

  5. #5
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Location
    Mt. Prospect, IL
    Posts
    2,572
    >>std::map is typically a red-black tree

    I think it is based on a RB tree as well...just like std set... so the RBtree runtimes apply

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. I am very new . . . :(
    By Eternalglory47 in forum C++ Programming
    Replies: 6
    Last Post: 09-05-2008, 11:29 AM
  2. std::map question.
    By Raigne in forum C++ Programming
    Replies: 7
    Last Post: 03-19-2008, 12:29 PM
  3. Flight Simulator Wind Speed!!
    By Dilmerv in forum C++ Programming
    Replies: 6
    Last Post: 03-19-2006, 11:40 PM
  4. Replies: 6
    Last Post: 01-08-2006, 01:49 PM
  5. increased net speed
    By PING in forum A Brief History of Cprogramming.com
    Replies: 20
    Last Post: 03-29-2005, 06:05 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21