Std :: map iteration - the order of differences between the Debug and Release assemblies

Question

Here is a general code template that I should work with:

class foo { public: void InitMap(); void InvokeMethodsInMap(); static void abcMethod(); static void defMethod(); private: typedef std::map<const char*, pMethod> TMyMap; TMyMap m_MyMap; } void foo::InitMap() { m_MyMap["abc"] = &foo::abcMethod; m_MyMap["def"] = &foo::defMethod; } void foo::InvokeMethodsInMap() { for (TMyMap::const_iterator it = m_MyMap.begin(); it != m_MyMap.end(); it++) { (*it->second)(it->first); } } 

However, I found that the processing order of the map (inside the for loop) may vary depending on whether the assembly configuration is Release or Debug. It seems that the compiler optimizations that occur in Release builds affect this order.

I thought that using begin() in the loop above and incrementing the iterator after each method call, it processes the map in the initialization order. However, I also remember that the map is implemented as a hash table, and the order cannot be guaranteed.

This is particularly annoying since most unit tests run in the Debug assembly, and often strange order dependency errors are not detected until the external QA team starts testing (because they use the Release assembly).

Can anyone explain this weird behavior?

Answer 1

Do not use const char* as a key for maps. This means that the map is ordered by line address, not by line content. Instead, use std::string as the key type.

std::map not a hash table, it is usually implemented as a red-black tree, and elements are guaranteed to be ordered by some criteria (by default < comparison between keys).

Answer 2

Map Definition: map <Key, Data, Compare, Alloc>

If both last template parameters are also default:
For comparison: less <& Key GT;
Alloc: & Distributor l; value_type>

When entering new values ​​into the map. The new value (valueToInsert) is compared with the old values ​​in order ( NB This is not a sequential search, the standard guarantees the maximum complexity of inserting O (log (N)) until Compare (value, ValueToInsert) returns true. Because you are using 'const char *' as the key. The Compare object uses less <const char *> , this class simply executes <on two values. This way you are comparing the values ​​of the pointer (not the string), so the order is random (since you don't know where the compiler will put the strings.

There are two possible solutions:

• Change the key type so that it compares string values.
• Define another type of comparison that does what you need.

Personally, I (like Chris) just used std :: string because the <statement used for strings returns a comparison based on the contents of the string. But for arguments, we can simply determine the type of comparison.

 struct StringLess { bool operator()(const char* const& left,const char* const& right) const { return strcmp(left,right) < 0; } }; /// typedef std::map<const char*, int,StringLess> TMyMap; 

Answer 3

If you want to use const char * as a key for your card, also set up a key comparison function that uses strcmp (or similar) to compare keys. This way, your map will be ordered by the contents of the string, not the value of the string pointer (i.e., by location in memory).