std :: map iteration - Différences d'ordre entre les versions Debug et Release

Question

Voici un modèle de code commun avec lequel je dois travailler:

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

Cependant, j'ai constaté que l'ordre dans lequel la mappe est traitée (dans la boucle for) peut différer selon que la configuration de construction est Release ou Debug. Il semble que l’optimisation du compilateur effectuée dans les versions de Release affecte cet ordre.

Je pensais qu'en utilisant begin() dans la boucle ci-dessus et en incrémentant l'itérateur après chaque appel de méthode, la carte serait traitée dans l'ordre d'initialisation. Cependant, je me souviens aussi d'avoir lu qu'une carte était implémentée comme une table de hachage et que son ordre ne pouvait pas être garanti.

Ceci est particulièrement gênant, car la plupart des tests unitaires sont exécutés sur une version de débogage et que des bogues de dépendance d'ordre étranges ne sont souvent détectés que lorsque l'équipe d'assurance qualité externe commence à tester (car elle utilise une version de version).

Quelqu'un peut-il expliquer cet étrange comportement?

Answer 1

N'utilisez pas const char* comme clé pour les cartes. Cela signifie que la carte est ordonnée par les adresses des chaînes et non par le contenu des chaînes. Utilisez plutôt un std::string comme type de clé.

std::map n'est pas une table de hachage, elle est généralement implémentée sous la forme d'un arbre rouge-noir et certains éléments sont garantis d'être classés (par défaut, < comparaison entre les clés).

Answer 2

La définition de la carte est:
mapper < clé, données, comparer, attribuer >

Où les deux derniers paramètres de modèle sont également définis par défaut:
Comparez: & Nbsp; less & Lt; Key & Gt;
Alloc: & Nbsp; & Nbsp; & Nbsp; & Nbsp; & Nbsp; & Nbsp; & Nbsp; & Nbsp; allocator & Lt; valeur_type < !> gt;

Lors de l'insertion de nouvelles valeurs dans une carte. La nouvelle valeur (valueToInsert) est comparée aux anciennes valeurs dans l’ordre ( NB . Il ne s’agit pas d’une recherche séquentielle, la norme garantit une complexité maximale d’insertion de O (log (N))) jusqu’à ce que Compare (valeur, ValueToInsert) renvoie true. Parce que vous utilisez 'const char *' comme clé. L'objet de comparaison utilise moins & Lt; const char * & Gt; cette classe ne fait qu'un & Lt; sur les deux valeurs. Donc, en fait, vous comparez les valeurs du pointeur (pas la chaîne), donc l'ordre est aléatoire (car vous ne savez pas où le compilateur mettra les chaînes.

Il existe deux solutions possibles:

• Modifiez le type de la clé pour qu'elle compare les valeurs de chaîne.
• Définissez un autre type de comparaison qui répond à vos besoins.

Personnellement, je (comme Chris) utiliserais simplement un std :: string parce que < opérateur utilisé sur les chaînes renvoie une comparaison basée sur le contenu de la chaîne. Mais pour des raisons d’argumentation, nous pouvons simplement définir un type de comparaison.

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

Si vous souhaitez utiliser const char * comme clé de votre carte, définissez également une fonction de comparaison de clé qui utilise strcmp (ou similaire) pour comparer les clés. Ainsi, votre carte sera ordonnée en fonction du contenu de la chaîne plutôt que de la valeur de son pointeur (emplacement en mémoire).