Vector or map, which one to use?

Question

I heard a lot of people say that if the number of elements expected in the container is relatively small, it is better to use std::vector instead of std::map , although I use the container only for searching, and not for iteration.

What is the real reason for this?

Obviously, map search performance cannot be worse than that of a vector (although it can be in nanoseconds / microseconds), so does this have anything to do with memory usage?

Is there really any other tariff / worse than a card when fragmenting a virtual address space?

I use the STL library that comes with Visual Studio (i.e. the Microsoft implementation), does this make any difference from other implementations?

Answer 1

I assume that you are comparing map<A, B> with vector<pair<A, B> > .

Firstly, finding an element in a very small vector can easily be faster than the same thing in the map, because all the memory in the vector is always contiguous (and therefore plays more beautifully with computer caches, etc.), and the number of comparisons required to search for something in the vector may be about the same as for the map. Finding an item on a map requires fewer operations within very large containers.

The point where cards become faster than vectors depends on the implementation, on your processor, on the data on the card, and on subtle things like memory in the processor cache. As a rule, the point where the map becomes faster will be about 5-30 elements.

An alternative is to use a hash container. They are often called hash_map or unordered_map . Classes named hash_map not part of the official standard (and there are several options); std::tr1::unordered_map is. A hash map is often faster than a regular search map, no matter how many elements it contains, but whether it depends on speed, it depends on what the key is, how it is hashed, what values ​​you have in mind and how the key is compared in std :: map. It does not save things in a specific order, like std :: map, but you said that you do not care. I would recommend hash maps, especially if the keys are integer or index, because these hashes are very fast.

Answer 2

Maps are usually implemented as binary search trees, and when walking the binary tree always comes with little overhead (making comparisons, walking links, etc.). Vectors are mostly arrays. For a very small amount of data, maybe 8 or 12 elements, it is sometimes faster to perform a linear search through an array than to walk through a binary search tree.

You can run some timings yourself to find out where the break-even point is the search time for four elements, then eight, then sixteen, etc., to find a sweet spot for your specific STL implementation.

Maps tend to have a bunch of small distributions across the heap, while vectors are contiguous, so the hit rate in a vector of vectors can be slightly better when you repeat all the elements from front to back.

Answer 3

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

Otherwise, I find this small flowchart very useful:

http://homepages.e3.net.nz/~djm/cppcontainers.html

Answer 4

If you do all your inserts at once, and then do a lot of searches, you can use the vector and sort it when you insert; then use lower_bound for a quick search. This can be faster than using a map even for a large number of items.

Answer 5

I think you should use a container that matches the data first. std :: vector is used in situations where you must use an array in C or pre-STL C ++: you want a contiguous block of memory to store values ​​with fast, constant time lookups. std :: map should be used to map keys to values. The primary overlap here is a vector against the map with size_t as the key. In this case, there are two problems: are the indices continuous? If not, you are likely to waste memory on a vector. Secondly, what search time do you want? A vector has a constant time search, while std :: map is usually implemented as an RB tree that has an O (log n) search time, and even a hash map (e.g. TR1 unordered_map) usually has worse complexity because the index (or its hash) will be mapped to a bucket that may contain multiple values.

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

In any case, try to model the data in an obvious way. Premature optimization often does not help.

Answer 6

Another way to look at this, if we are talking about small containers, then none of them will take a long time to look at. Unless you look for this container on a very narrow loop, the time difference is likely to be negligible.

In this case, I would see which container more closely matches what you want to do. If you are looking for a specific value, the find () built-in method will be much simpler (and less difficult to use) than creating a for loop and iterating over a vector.

Time probably costs a lot more than a few nanoseconds here and there.

Answer 7

Mostly maps are used for searching.

But sometimes std::vector can be used instead of std::map even for searching.

If there are very few elements in your key-value pairs, you can go for an iterative search using the key, even in std::vector<std::pair<x,y>> .

This is because hashing takes time, especially for hash strings and other operations on the map, such as storing data on the heap.

You would see a better difference in std :: map if you have more elements that you should look for, and also when you want to often search the list of elements that you have.