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

> 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.

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

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.

>>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