Map or Vector?

I've been contemplating a problem and wondering what's the better container for my particular solution.

In this case, I have a group/list/collection/whatever of objects called Entity. Entities have both a 'Name' property and an 'Update()' function. Simple enough.

I expect to have a maximum of 200 entities in any particular group at any time.

I've been wondering whether or not to use a std::map or a std::vector for hanging on to these Entity's. I want to be able to retrieve an Entity via its name. With map, this is very easy using the [] operator. With vector, I have to do the comarison manually but ultimately it's trivial.

My concern comes with iterating through the entire list of Entity objects to call their update functions. It's simple enough to iterate through each container type but would it be faster to use a vector and iterate using a for loop (e.g., for(int i = 0; i < vector.size(); i++)) or is it ultimately about the same speed using an iterator for map? I could just build a wrapper class to abstract all of that and just test both solutions but I thought I'd ask first.

Iterating on a map or vector are both O(1) in the time taken to advance to the next element, but the map has a larger overhead. Whether you choose map or vector will depend on whether lookup time or iteration time is dominant.

If you keep the vector sorted by Name, you can use binary search to achieve O(log n) lookup (like a map) while retaining the iteration characteristic of a vector. So long as insertions are not frequent, this might be the best solution.

Linear iteration performance, for me, is the deciding factor. Value retrieval speed is much less important as it happens much less frequently yet insertion is something that will also require high speed. As sorting is unimportant I figure a simple push_back() call should do the trick.

Thanks for your reply. I really appreciate your feedback.

>> As sorting is unimportant I figure a simple push_back() call should do the trick.

But sorting is important if you want something better than O(n) lookup by name from the vector.

I would use the map, since it is either better for insertion or better for lookup (depending on whether you keep the vector sorted), but is basically the same for iteration. It is also the more obvious/clear solution.

Another option is unordered_map, which is a hash map. Since the order of iteration is not important (maybe that's what you meant above), you get O(1) lookup and insertion. This is especially good if you know a good maximum so you can define a proper number of buckets.

Of course, in the end if this decision is really going to impact the speed of your application, you really have to test the different options. The actual speeds can vary depending on the library implementation.

I think I stated it incorrectly when I said that insertion time was important. It's not. Searching and insertion are not that important as these function will rarely be used. However, the update() function will be called every program iteration which makes the iteration being fast very important.

Seing as I expect to only ever see no more than 200 objects and possibily capping it at 256, I would imagine that with such a relatively small set of objects to iterate through the solution that I use is less important provided things are clear. Besides, a map provides a lot of the functionality built-in that I would want to use and is going to work the same way no matter which platform it's built on (this is a cross-platform project currently working on Win32, MacOS X and Linux).

Thanks for the suggestion!

>> a map provides a lot of the functionality built-in that I would want to use and is going to work the same way no matter which platform it's built on <<

Technically, all three options (vector, map, unordered_map) will work the same way no matter which platform they're built on, but any of the three could have vastly different speeds depending on the platform and library you use.

Quote:

---

Originally Posted by leeor_net

I think I stated it incorrectly when I said that insertion time was important. It's not. Searching and insertion are not that important as these function will rarely be used. However, the update() function will be called every program iteration which makes the iteration being fast very important.

---

If lookup/insert are not important, use vector. Nothing iterates faster than vector.