CODEWITHSUNDEEP
c++dictionaryvector
Fabian
Fabian

Reputation: 4211

At what size is map better than vector?

I have a collection of objects, each of which has an identifier (string). Now I wonder whether I should store them as a vector or a map, so either std::vector<cObject> or std::map<std::string,cObject>. Each name can only be used once, so I need to check the vector/map for occurrences of a given name. Using a map, I would use find() which scales logarithmically, while for a vector, I would iterate and test oObject.name == newname until I find the name or arrive at the end, which scales linearly. A downside of the map is that the name is stored twice, once inside the object and once as the key.

While for large vectors/maps, a map would always win, I wonder at which point this is the case, since a map seems to be overkill if I only have up to 10 objects to store.

This leads to my question: At which point does a map become advantageous (regarding performance) compared to a plain vector? Should I already consider using maps if the expected number of objects is about 10, 100, 1000 or even larger? I admit that this question is rather vague, but I hope to get some advice anyway, to get a feeling when to use which container.

Upvotes: 1

Views: 1070

Answers (3)

Slava
Slava

Reputation: 44238

Using a map, I would use find() which scales logarithmically, while for a vector, I would iterate and test oObject.name == newname until I find the name or arrive at the end, which scales linearly.

Not quite true, you can keep your objects in the vector sorted and use std::binary_searchwith logarythmic complexity.

A downside of the map is that the name is stored twice, once inside the object and once as the key.

You can use std::set with custom comparator so you will not have to store key separately.

In general Knuth said "premature optimization is root of all evil". Make your program readable, use what's easier (std::map or std::unordered_map I guess) and later if you have performance issue with this container optimize it. Encapsulating this container in some class could be helpful, so later you can replace implementation transparently for the rest of your code.

Upvotes: 1

Rahul Tripathi
Rahul Tripathi

Reputation: 172378

It is hard to predict the size at which map is advantageous then vector. But there are few points which you can consider:

  1. Maps are basically implemented as binary tree whereas vectors are implemented as arrays. So it is compartively easier to iterate through array for lets says when there are 10 to 12 elements as it would be a liner search.
  2. The point that maps are faster than the vectors depends on the implementation on the processor and also what data you are trying to store in it. My best guess is that maps would be faster will be for 5-20 elements.(But it is just a guess I would suggest you to create a benchmark for yourself)
  3. "By default, use vector when you need a container" - Bjarne Stroustrup.

You may also find this C++ Containers Cheat Sheet useful

Upvotes: 3

Peter
Peter

Reputation: 36597

That depends on how the vector and map are implemented, and what operations your code does on them (e.g. adding elements to the middle or end, removing elements, adding and removing repeatedly, etc). You would need to test and profile your code. Even them, the answer would depend on the host system (e.g. caching, pipelining, etc).

Incidentally, if you keep a vector sorted, finding an element also scales logarithmically (e.g. using binary search). Your basis of comparison (vector linear, map logarithmic) is therefore flawed.

Upvotes: 1

Related Questions