std::map iteration - order differences between Debug and Release builds

Question

Here's a common code pattern I have to 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 have found that the order that the map is processed in (within the for loop) can differ based upon whether the build configuration is Release or Debug. It seems that the compiler optimisation that occurs in Release builds affects this order.

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

This is particularly annoying, as most of the unit tests are run on a Debug build, and often strange order dependency bugs aren't found until the external QA team start testing (because they use a Release build).

Can anyone explain this strange behaviour?

Answer 1

Don't use const char* as the key for maps. That means the map is ordered by the addresses of the strings, not the contents of the strings. Use a std::string as the key type, instead.

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

Answer 2

The definition of map is:
map<Key, Data, Compare, Alloc>

Where the last two template parameters default too:
Compare: less<Key>
Alloc:        allocator<value_type>

When inserting new values into a map. The new value (valueToInsert) is compared against the old values in order (N.B. This is not sequential search, the standard guarantees a max insert complexity of O(log(N)) ) until Compare(value,ValueToInsert) returns true. Because you are using 'const char*' as the key. The Compare Object is using less<const char*> this class just does a < on the two values. So in effect you are comparing the pointer values (not the string) therefore the order is random (as you don't know where the compiler will put strings.

There are two possible solutions:

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

Personally I (like Chris) would just use a std::string because < operator used on strings returns a comparison based on the string content. But for arguments sake we can just define a Compare type.

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;