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?

Answer 1

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.

Answer 2

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.

Answer 3

If you're doing all your insertions at once then doing lots of lookups, you can use a vector and sort it when you're through inserting; then use lower_bound to do a quick lookup. It might be faster than using a map, even for large numbers of items.

Answer 4

I think you should use the container that fits the data first and foremost. std::vector is used in situations where you would use an array in C or pre-STL C++: you want a contiguous block of memory to store values with fast constant time look-up. std::map should be used to map keys to values. The primary overlap here is a vector vs a map with a size_t as the key. In that case there are two concerns: are the indexes continuous? If not, you will probably be wasting memory with a vector. Second, what look-up time do you want? A vector has constant time lookup, while std::map is usually implemented as a RB tree, which has a O(log n) look-up time, and even a hash map (such as TR1 unordered_map) usually has a worse complexity, because the index (or a hash thereof) will be mapped to a bucket that can contain multiple values.

If were aiming at a vector with pairs: you could the elements of the vector and use find to find elements. But this is a binary search, and will practically be as fast as a std::map.

Anyway, try to model the data in the obvious manner. Premature optimization often doesn't help much.

Answer 5

"By default, use vector when you need a container" - Bjarne Stroustrup.

Otherwise, I find this little flow chart to be of very good help:

http://www.linuxsoftware.co.nz/containerchoice.png

Answer 6

Another way to look at this, is if we're talking about small containers, then neither one is going to take very long to look up. Unless you're searching through this container on a very tight loop, the difference in time will probably be negligible.

In that case, I would look for which container more closely matches what you want to do. If you're looking for a particular value, map's built-in find() method will be a lot easier (and less complex to use) than creating a for loop and iterating over a vector.

You're time is probably worth a lot more than a few nano-seconds here and there.