std :: map iteration - 调试和发布版本之间的顺序差异

Question

这是我必须使用的常见代码模式:

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);
    }
}

但是,我发现处理映射的顺序(在for循环中)可能因构建配置是Release还是Debug而有所不同.似乎发布版本中发生的编译器优化会影响此顺序.

我认为通过begin()在上面的循环中使用,并在每次方法调用后递增迭代器,它将按初始化顺序处理映射.但是,我还记得读过地图是作为哈希表实现的,并且无法保证顺序.

这尤其令人讨厌,因为大多数单元测试都是在Debug构建上运行的,并且在外部QA团队开始测试之前通常不会发现奇怪的顺序依赖性错误(因为它们使用了Release版本).

谁能解释这种奇怪的行为？

Answer 1

不要const char*用作地图的关键.这意味着地图按字符串的地址排序,而不是字符串的内容.std::string而是使用a 作为键类型.

std::map它不是哈希表,它通常实现为红黑树,并且保证元素按某些条件排序(默认情况下,<键之间的比较).

Answer 2

map的定义是:
map <Key,Data,Compare,Alloc>

最后两个模板参数也默认:
比较:less <Key>
Alloc:allocator <value_type>

将新值插入地图时.新值(valueToInsert)按顺序与旧值进行比较(NB这不是顺序搜索,标准保证O(log(N))的最大插入复杂度,直到Compare(value,ValueToInsert)返回true.因为你使用'const char*'作为关键.Compare Object使用less <const char*>这个类只对两个值执行<.所以实际上你是在比较指针值(而不是字符串)因此顺序是随机的(因为你不知道编译器将字符串放在何处).

有两种可能的解决方案:

• 更改密钥的类型,以便比较字符串值.
• 定义另一个满足您需要的比较类型.

我个人(像Chris)只会使用std :: string,因为在字符串上使用的<运算符会返回基于字符串内容的比较.但为了论证,我们可以定义一个Compare类型.

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;