c++ - vector or map, which one to use?

Question

I've heard many people say that if the number of expected elements in the container is relatively small, it is better to use std::vector instead of std::map even if you were to use the container for lookups only and not iterating.

What is the real reason behind this?

Obviously the lookup performance of std::map cannot be worse than std::vector (although it may differ in nanoseconds/microseconds) so does it have something to do with memory usage?

Does std::vector fare any better/worse than std::map in fragmenting the virtual address space?

I am using the STL library that comes along with Visual Studio (i.e. Microsoft's implementation). Does that make any difference compared to other implementations?

Answer 1

I presume you're comparing map<A, B> with vector<pair<A, B> >.

Firstly, finding an item in a very small vector can easily be faster than the same thing in a map, because all the memory in a vector is always contiguous (and so plays more nicely with computers' caches and such things), and the number of comparisons needed to find something in a vector might be about the same as for a map. Finding an element in a map needs fewer operations in the limit of very large containers.

The point where maps become faster than vectors depends on the implementation, on your processor, what data is in the map, and subtle things like what memory is in the processor's cache. Typically, the point where map becomes faster would be about 5-30 elements.

An alternative is to use a hash container. They are often named hash_map or unordered_map. Classes named hash_map are not part of the official standard (and there are a few variants out there); std::tr1::unordered_map is. A hash map is often faster than a normal map for lookups, regardless of how many elements are in it, but whether it is actually faster depends on what the key is, how it is hashed, what values you have to deal with, and how the key is compared in std::map. It doesn't keep things in a specific order like std::map, but you've said that you don't care about that. I'd recommend hash maps particularly if the keys are integers or pointers, because these hash very quickly.