We are working on a game project for school in c++.
I'm in charge of the map object, who will contain Entities like bombs, players, walls and boxes.
I have 3 containers in my map:
- A std::list for players (multiple players can stand on a same case).
- A
std::unordered_map<int, std::unordered_map<int, AEntity*> > for walls.
- An other
std::unordered_map<int, std::unordered_map<int, AEntity*> > for bombs+boxes.
The aim is to access an Entity very fast on the map, number of entities can be very high.
That's why I thought about unordered_maps, I planned to use them this way:
Unordered_map A contain:
KEY: y coord of the Entity || VALUE: pointer to unordered_map B
Unordered_map B contain:
KEY: x coord of the entity || VALUE: pointer to the AEntity instance
Question 1:
First, are unordered_maps that fast for this kind of usage? I am very new to unordered_maps.
Question 2:
Second, is this a viable way to add element?
int main(int ac, char **av)
{
std::unordered_map <int, unordered_map <int, char*>> umap;
(umap[4])[2] = "salut";
std::cout << (umap[4])[2] << std::endl;
}
A std::unordered_map is implemented in terms of a hash table, unlike a std::map which is implemented in terms of a tree. This means that for an unordered_map, access is in general O(1) where as for a std::map it is O(log n). There are a great many differences between these, I would suggest looking at a data structures book if you are unaware of the differences, but here are a few:
For std::unordered_map
- Allocates a single contiguous array of memory, you can use
reserve() to prevent resizing at an inopportune moment, however because of the nature of hash tables, this will always allocate more space than you are actually ever going to use
- Calculating the hash is fast, but it could be faster to lookup a few pointers in a
std::map
For std::map
- Dynamically allocates new memory for each element in your map, this can be slow if you are adding millions of elements to the map.
- Deleting elements is also a log n operation, which can be slow if you are doing this often.
- Because it is a tree, it is sorted, so you can traverse elements in order, something that is not possible with an unordered map
There are many others, I suggest looking them up, there are many duplicates of this type of question on stackoverflow already.
As for your seconds question, that is a valid way of adding and accessing an element in an unordered_map. However I would highly recommend using reserve() if you know the number of items you are going to be placing in the map.
Others have already explained unordered_map vs. map, but if it is really speed you're after then I'd suggest using plain arrays (or vectors) instead. You say the number of entities can be "very large", by this I understand you're dealing with dense data (i.e. most of the coordinates contain an entity). An unordered_map is a kind of hashmap, meaning that dense data will fill up the buckets rapidly. Large buckets will reduce speed and increase memory usage, decreasing the advantages of using an unordered_map.
Reverting to arrays will always provide quicker access and insertion of entities, at the cost of some extra RAM. I don't know the range of possible coordinates, but let's say your map ranges from (0,0) - (1024, 1024). Using arrays of pointers for this would only use 1024 x 1024 x 8 bytes = 8MBytes of RAM no matter how much Entities you store in them. I'd have to run some tests to make sure, but I think that if your map is more than 80% filled with Entities, the array approach would actually use less RAM than the unordered_map approach.
To conclude I'd also like to mention that you shouldn't always focus on speed. Optimized C++ code is usually already very fast, and unless you really, really, really need the speed I'd suggest using the simpelest solution rather than the quickest.
The unordered_map containers are faster than map containers when you need to access their key, but are considered to be less efficient when trying to access a subset of their elements. I think that if you were to access the pointers contained in the unordered_map containers directly that it would be less efficient.
http://www.cplusplus.com/reference/unordered_map/unordered_map/
