std :: map iteration - differenze di ordine tra build di debug e release

Question

Ecco un modello di codice comune con cui devo lavorare:

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

Tuttavia, ho scoperto che l ' ordine in cui viene elaborata la mappa (all'interno del ciclo for) può differire in base al fatto che la configurazione della build sia Rilascio o Debug. Sembra che l'ottimizzazione del compilatore che si verifica nelle build di rilascio influisca su questo ordine.

Ho pensato che usando begin() nel loop sopra e incrementando l'iteratore dopo ogni chiamata di metodo, avrebbe elaborato la mappa in ordine di inizializzazione. Tuttavia, ricordo anche di aver letto che una mappa è implementata come una tabella hash e che l'ordine non può essere garantito.

Ciò è particolarmente fastidioso, poiché la maggior parte dei test unitari vengono eseguiti su una build di debug e spesso non vengono trovati strani bachi di dipendenza dell'ordine fino a quando il team di QA esterno inizia il test (perché usano una build di rilascio).

Qualcuno può spiegare questo strano comportamento?

Answer 1

Non utilizzare const char* come chiave per le mappe. Ciò significa che la mappa è ordinata dagli indirizzi delle stringhe, non dal contenuto delle stringhe. Utilizzare invece std::string come tipo di chiave.

std::map non è una tabella hash, di solito è implementata come un albero rosso-nero e gli elementi sono garantiti per essere ordinati secondo alcuni criteri (per impostazione predefinita, < confronto tra chiavi).

Answer 2

La definizione di mappa è:
map < Key, Data, Compare, Alloc >

Dove sono predefiniti anche gli ultimi due parametri del modello:
Confronto: &; &; & Nbsp meno lt chiave gt;
Alloc: &; &; &; &; &; &; &; &; & Nbsp nbsp nbsp nbsp nbsp nbsp nbsp nbsp allocatore lt; value_type < !> gt;

Quando si inseriscono nuovi valori in una mappa. Il nuovo valore (valueToInsert) viene confrontato con i vecchi valori nell'ordine ( NB Questa non è una ricerca sequenziale, lo standard garantisce una complessità di inserimento massima di O (log (N)) fino a Confronto (valore, ValueToInsert) restituisce true. Perché stai usando 'const char *' come chiave. L'oggetto Confronta utilizza less & Lt; const char * & Gt; questa classe fa solo un & Lt; sui due valori. Quindi in effetti stai confrontando i valori del puntatore (non la stringa) quindi l'ordine è casuale (poiché non sai dove il compilatore inserirà le stringhe.

Esistono due possibili soluzioni:

• Cambia il tipo di chiave in modo che confronti i valori di stringa.
• Definisci un altro tipo di confronto che fa quello che ti serve.

Personalmente io (come Chris) userei solo una stringa std :: string perché < l'operatore utilizzato sulle stringhe restituisce un confronto basato sul contenuto della stringa. Ma per amor di argomenti possiamo semplicemente definire un tipo di confronto.

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

Se si desidera utilizzare const char * come chiave per la propria mappa, impostare anche una funzione di confronto dei tasti che utilizza strcmp (o simile) per confrontare i tasti. In questo modo la tua mappa verrà ordinata in base al contenuto della stringa, piuttosto che al valore del puntatore della stringa (cioè posizione nella memoria).