14 replies to this topic

[freeworld]

brainfart... I've got a vector of structs, that contain a string value. I'd like to be able to look into the vector using the string value as the index like so.

vector<struct> myStructs;
int health = myStructs["health"].value;

is there a container that can already do this for me, or should I just wrap the vector in a class that overrides the [] operator? The other things is, it kinda needs some sort of error checking, there's definitely times were the string won't exist, so returning a blank struct (ie 0) would be prefered.

[D.Chhetri]

Yes you are looking for http://www.cplusplus.com/reference/stl/map/

[freeworld]

Yes you are looking for http://www.cplusplus...erence/stl/map/

ooh, quick question, what happens if I try to push an element onto a map with a key that matchs an already existing element? Do I need to handle these errors on my own or will it ignore the new value?

and what happens if I try to access an element but the key doesn't exist... ie there is no value in the map that has the key "health" but I try to access it anyways?

[boogyman19946]

Both of those questions are thoroughly described in the reference that was linked. Basically, you go to the function you're using to do that and check what the result are and what they mean.

[Matias Goldberg]

The value is overriden. If you want to have more than one element with the same key (the key in this case would be "health") then you're looking into multi_map

Note however, games are performance critical and using strings to address data is very inefficient. And map causes lots of cache misses too. I only use strings (& std::map) to store game's data (i.e. to store it in HDD) and then be processed at loading time. If this is used every frame by every entity in your scene, it may affect your performance seriously.

[boogyman19946]

The value is overriden. If you want to have more than one element with the same key (the key in this case would be "health") then you're looking into multi_map

Are you sure? The reference says it doesn't get modified.

[freeworld]

Both of those questions are thoroughly described in the reference that was linked. Basically, you go to the function you're using to do that and check what the result are and what they mean.

ok it states that if I try to access a key that doesn't exist it creates a new element with that key.... but does map not use push to add elements? do I have to use insert or the [] operator?

The value is overriden. If you want to have more than one element with the same key (the key in this case would be "health") then you're looking into multi_map

Note however, games are performance critical and using strings to address data is very inefficient. And map causes lots of cache misses too. I only use strings (& std::map) to store game's data (i.e. to store it in HDD) and then be processed at loading time. If this is used every frame by every entity in your scene, it may affect your performance seriously.

nothing huge going on here, I wouldn't think I'd have an issue, if each map i no more than 10-15 elements in size and typically only ~5. and access every map anywhere from 150-3K times every second... I wouldn't think I'd notice it at all. The need for the dynamic storage of data based on a name is more important then an extra fps.

Also I don't need to store multiple values with the same name, in fact that should never happen, but there is the chance that I might try to add another value with the same name, I want the enw value to be completely ignored/rejected, not override the old value.

[boogyman19946]

I'm not sure if that's true, but I think map sorts the objects by key so it can find them quicker.

[swiftcoder]

ok it states that if I try to access a key that doesn't exist it creates a new element with that key.... but does map not use push to add elements? do I have to use insert or the [] operator?

If you use operator [] to insert elements, then the new item will overwrite the existing item.

If you instead use the insert() function, it will not replace existing elements, and will return a boolean to indicate success.

You can also use the find() function, to check for an existing item, and then pass the resulting iterator into insert(), which will cut down the cost of performing find+insert.

[Matias Goldberg]

ok it states that if I try to access a key that doesn't exist it creates a new element with that key.... but does map not use push to add elements? do I have to use insert or the [] operator?

These have been said by swiftcoder, but just to clarify:

• Map doesn't have push_back
• myMap["myKey"] = 20 -> creates the entry "myKey" and set it to 20. If "myKey" already existed, it overwrites it's contents.
• int myVal = myMap["myKey"]; ->Watch out when you do that, because if the entry "myKey" didn't exist, you may be reading uninitialized memory (unless the mapped value has a default constructor that sets it's contents to valid values).
• std::map<int>::iterator it = myMap.find( "myKey" ) -> Reads the value at "myKey". If it didn't exist, returns myMap.end() instead (doesn't create a new entry).

nothing huge going on here, I wouldn't think I'd have an issue, if each map i no more than 10-15 elements in size and typically only ~5. and access every map anywhere from 150-3K times every second... I wouldn't think I'd notice it at all. The need for the dynamic storage of data based on a name is more important then an extra fps.

150 is not the same as 3k; and is not the same per frame than per second. Be sure you understand timing. If you access the map 3k in your loop iteration, that's 3k * 60 = 180k per second; which can badly hurt performance since the keys are strings. 3k per second though, is fine.

Also take in mind:

• Map is designed for amortized-time accessing of a large number of elements. That means map is designed to hold like 1.000's or 10.000's of values in the same map. If they're gonna have like 15, may be you should roll your own using a struct and a std::vector with linear search (see std::find). However, if you really access like 3k per second, then may be you just stick to map; it's quicker to code and you won't notice performance problems
• The thing about using strings is that, when used carelesssly can greatly increase the memory size as well as the memory fragmentation, which is the most damaging element to a video game. That's the reason of my warning. Cache misses can also cause surprising slowdowns even of cutting edge CPUs.
• It's rather strange to see someone doing myMap["health"] to store or read a simple common value like health; which seemed like wrong usage to me. May be you were just using as an example only.

Also I don't need to store multiple values with the same name, in fact that should never happen, but there is the chance that I might try to add another value with the same name, I want the enw value to be completely ignored/rejected, not override the old value.

If you stick to map; don't use myMap["key"] = 10; but rather myMap.insert() like swiftcoder suggested.

[iMalc]

Use a map if the contents need to change throughout times when the program is running.
If you add all items at initialisation time and then just perform lookups then using a std::vector of pairs, sorting the container at the end of the initialisation phase, and performing searches using std::lower_bound, is the faster way to go.

[swiftcoder]

If you add all items at initialisation time and then just perform lookups then using a std::vector of pairs, sorting the container at the end of the initialisation phase, and performing searches using std::lower_bound, is the faster way to go.

We are already off-topic for 'For Beginners', but just to be clear, the algorithmic complexity is the same between both approaches, no? The difference is that std::vector will use a contiguous block of memory, and thus hopefully avoid quite a few cache misses (with the implication that a std::map using a block allocator could offer similar performance).

And of course, std::unordered_map is likely to outperform both of these approaches in general.

Edited by swiftcoder, 11 January 2012 - 01:44 PM.
Sorry, brainfart. I meant unordered_map - thanks Alvaro.

[Álvaro]

And of course, std::unordered_set is likely to outperform both of these approaches in general.

I think you mean std::unordered_map, which is what I would have suggested to begin with if I had read this thread earlier.

[Slavik81]

And of course, std::unordered_map is likely to outperform both of these approaches in general.

Isn't unordered_map generally a hash table, while map is a tree? Lookup performance would depend on a number of things. In particular:
1. How many elements there are.
2. The relative computational intensity of the hash function vs. the less-than comparison function.

Given that the OP has a handful of string values in the map, I'd expect the ordered map to be faster. With such a low n, algorithmic complexity is irrelevant and fixed costs dominate.

But it's easy enough to swap one for the other, profile and compare the results.

[Álvaro]

Although there are good reasons to use key/value pairs in C++, this particular usage seems to indicate that the OP wants to have some sort of super-flexible structure, where you can add any fields you want in run time. Although that's a very natural way of doing things in some languages (I seem to remember that's basically what structures are in Perl and PHP), it is not idiomatic in C++ and perhaps you should rethink your design. Of course we would need to know much more about what you are trying to do before we can suggest any design alternatives.