4

これは、私が使用しなければならない一般的なコードパターンです。

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 ループ内で) マップが処理される順序は、ビルド構成がリリースかデバッグかによって異なる場合があることがわかりました。リリース ビルドで発生するコンパイラの最適化がこの順序に影響しているようです。

begin()上記のループで使用し、各メソッド呼び出しの後に反復子をインクリメントすることで、初期化順にマップを処理すると考えました。ただし、マップはハッシュ テーブルとして実装され、順序が保証されないことも読んだことを覚えています。

ほとんどの単体テストはデバッグ ビルドで実行され、多くの場合、外部の QA チームがテストを開始するまで (リリース ビルドを使用しているため)、奇妙な順序依存関係のバグが検出されないため、これは特に厄介です。

誰かがこの奇妙な振る舞いを説明できますか?

4

3 に答える 3

16

const char*マップのキーとして使用しないでください。つまり、マップは文字列の内容ではなく、文字列のアドレスによって順序付けられます。std::string代わりに、キー タイプとしてaを使用します。

std::mapハッシュテーブルではなく、通常は赤黒木として実装され、要素はいくつかの基準 (デフォルトで<はキー間の比較) によって順序付けられることが保証されています。

于 2008-09-26T01:30:41.910 に答える
10

map の定義は次のとおりです:
map<Key, Data, Compare, Alloc>

最後の 2 つのテンプレート パラメータもデフォルトです:
Compare: less<Key>
Alloc: allocator<value_type>

新しい値をマップに挿入するとき。新しい値 (valueToInsert) は、Compare(value,ValueToInsert) が true を返すまで、順番に古い値と比較されます ( NBこれはシーケンシャル検索ではありません。標準では O(log(N)) の最大挿入複雑度が保証されています)。「const char*」をキーとして使用しているためです。Compare オブジェクトはless<const char*>を使用しています。このクラスは 2 つの値に対して < を実行するだけです。したがって、実質的には（文字列ではなく）ポインター値を比較しているため、順序はランダムです（コンパイラーが文字列を配置する場所がわからないため）。

考えられる解決策は 2 つあります。

  • 文字列値を比較するようにキーのタイプを変更します。
  • 必要なことを行う別の比較タイプを定義します。

個人的には (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;
于 2008-09-26T02:49:49.037 に答える
3

const char * をマップのキーとして使用する場合は、strcmp (または同様のもの) を使用してキーを比較するキー比較関数も設定します。そうすれば、マップは、文字列のポインター値 (つまり、メモリ内の場所) ではなく、文字列の内容によって順序付けられます。

于 2008-09-26T02:56:09.567 に答える