vector or map, which one to use?


Question

I've heard many people saying that if the number of elements expected in the container is relatively small it is better to use std::vector instead of std::map eventhough I use the container for only lookup and not for iterating.

What is the real reason behind this?

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

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

I am using STL library that comes along with Visual Studio (i.e. microsoft implementation) does that make any difference from other implementations?

1
62
3/31/2015 2:34:30 PM

Accepted Answer

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.

63
1/18/2009 7:45:21 AM

Maps are usually implemented as binary search trees, and walking a binary tree always comes with a little overhead (performing comparisons, walking links, etc.) Vectors are basically just arrays. For very small amounts of data, maybe 8 or 12 elements, sometimes it's faster just to do a linear search over an array than to walk a binary search tree.

You can run some timings yourself to see where the break-even point is -- time a search over four elements, then eight, then sixteen, and so on to find the sweet spot for your particular implementation of the STL.

Maps do tend to have a bunch of small allocations all over the heap, whereas vectors are contiguous so the cache-hit rate of vectors can sometimes be a little better in cases where you're iterating over all the elements from front to back.


Licensed under: CC-BY-SA with attribution
Not affiliated with: Stack Overflow
Icon