std :: map get value - find vs handcrafted loop

Question

Ho un oggetto std :: map map<string , Property*> _propertyMap, dove string è il nome della proprietà e Property* contiene i valori della proprietà.

Ho bisogno di elaborare i valori delle proprietà e convertirli in un dato specifico Formato- ogni proprietà ha il proprio formato, ad esempio se la mappa inizializzazione è la seguente:.

_propertyMap["id"] = new Property(Property::UUID, "12345678"); 
_propertyMap["name"] = new Property(Property::STRING, "name"); 
.... 

poi "id" vanno trattati differentemente di "name" ecc.

Ciò significa che devo cercare ogni proprietà nella mappa ed elaborare i suoi valori di conseguenza.

Ho pensato a due modi per farlo.

One, utilizzare std::map::find metodo per ottenere una proprietà specifica, come quella:

map<string , Property*>::iterator it1 = _propertyMap.find("id"); 
if(it1 != _propertyMap.end()) 
{ 
    //element found - process id values 
} 
map<string , Property*>::iterator it2 = _propertyMap.find("name"); 
if(it2 != _propertyMap.end()) 
{ 
    //element found - process name values 
} 
.... 

Due, iterare la mappa e per ogni voce di controllare ciò che il nome della proprietà è e procedere di conseguenza:

for (it = _propertyMap.begin(); it != _propertyMap.end(); ++it) 
    { 
     //if it is events - append the values to the matching nodes 
     if (it->first == "id") 
     { 
      //process id values 
     } 
     else if (it->first == "name") 
       { 
        //process name values 
       } 
     ..... 
    } 

Dato che il Time complexity of std::map::find is O(logN), la complessità della prima soluzione è O(NlogN). Non sono sicuro della complessità della seconda soluzione, perché itera la mappa una volta (O(N)), ma esegue molto if-else ogni iterazione. Ho provato a rispondere alle domande comuni su google map::find(), ma non sono riuscito a trovare alcuna informazione utile; molti di questi hanno solo bisogno di ottenere un valore dalla mappa, e quindi lo find() lo fa con una maggiore complessità (O(logN) vs O(N)).

Qual è un approccio migliore? o forse ce n'è un altro a cui non ho pensato?

Inoltre, lo stile del codice parla, quale è il codice più buono e chiaro?

Answer 1

vedo alcuni casi d'uso diversi, a seconda di ciò che avete in mente:

proprietà fisse

(Solo per completezza, credo che non è ciò che si vuole) Se entrambi nome e tipo di possibili proprietà deve essere fissato, la versione migliore è quella di utilizzare una semplice classe/struct, eventualmente utilizzando boost::optional (std::optional con C++ 17) di valori che potrebbero essere presenti o meno

struct Data{ 
    int id = 0; 
    std::string name = ""; 
    boost::optional<int> whatever = boost::none; 
} 

Pro:

• Tutte le "ricerche" sono risolti al momento della compilazione

Contro:

• No flessibilità di espandere in fase di esecuzione

elaborare solo le opzioni specifiche a seconda della loro chiave

Se si desidera elaborare solo un sottoinsieme specifico di o ptions, ma mantieni l'opzione di avere chiavi personalizzate (non elaborate) che i tuoi approcci sembrano adatti.

In questo caso ricordate che usando find in questo modo:

it1 = _propertyMap.find("id"); 

ha complessità O (log N), ma è usato M volte, con M beeing il numero di opzioni elaborati. Questa non è la dimensione della mappa, è il numero di volte in cui si utilizzafind()per ottenere una proprietà specifica. Nel tuo esempio (abbreviato) questo significa una complessità di O (2 * logN), dal momento che si cercano solo 2 chiavi.

Quindi, in pratica, utilizzare gli M-times find() scale migliori del ciclo quando aumenta solo la dimensione della mappa, ma peggio se si aumenta il numero di rilevamenti nello stesso modo. Ma solo la profilazione può dirti qual è la più veloce per la tua taglia e la tua custodia.

processo tutte le opzioni a seconda del tipo

Dal momento che la tua mappa assomiglia molto i tasti possono essere personalizzati, ma i tipi sono da un piccolo sottoinsieme, si consideri il ciclo sulla mappa e utilizzando i tipi invece dei nomi per determinare come elaborarli. Qualcosa di simile a questo:

for (it = _propertyMap.begin(); it != _propertyMap.end(); ++it) 
{ 
    if (it->first.type() == Property::UUID) 
    { 
     //process UUID values 
    } 
    else if (it->first.type() == Property::STRING) 
    { 
     //process STRING values 
    } 
    ..... 
} 

Questo ha il vantaggio, che non hai bisogno di alcuna informazione su ciò che le chiavi della vostra carta sono davvero, solo che tipo è in grado di memorizzare.

Answer 2

Supponiamo di avere una mappa di proprietà N e stiamo cercando un sottoinsieme di proprietà P. Ecco un'analisi di massima, non conoscendo la distribuzione statistica delle chiavi:

• Nell'approccio mappa pura si cerca P volte con una complessità di O (log (n)), che è O (p * log (n))

• Nell'approccio incatenato si attraversa una volta la mappa. Quello è O (N).Ma non dovresti dimenticare che una catena se-allora è anche un (hiden) traversale della lista di elementi P. Quindi per ognuno degli elementi N stai facendo una ricerca di potenzialmente fino a elementi P. In modo che tu abbia qui una complessità di O (p * n).

Ciò significa che l'approccio della mappa sorpasserà il tuo attraversamento e il divario di prestazioni aumenterà in modo significativo con n. Ovviamente questo non tiene conto della funzione chiamata overhead nella mappa che non si ha nella catena if. Quindi, se P e N sono piccoli, il tuo approccio potrebbe ancora reggere il confronto teorico.

Che cosa si potrebbe eventualmente fare per aumentare ulteriormente peformance potrebbe essere quella di utilizzare un unordered_map, che è O (1) in complessità, ridurre il problema della complessità O (P).

Answer 3

C'è un'altra opzione che combina il meglio di entrambi. Data una funzione come questa (che è un adattamento di std::set_intersection):

template<class InputIt1, class InputIt2, 
     class Function, class Compare> 
void match(InputIt1 first1, InputIt1 last1, 
      InputIt2 first2, InputIt2 last2, 
      Function f, Compare comp) 
{ 
    while (first1 != last1 && first2 != last2) { 
     if (comp(*first1,*first2)) { 
      ++first1; 
     } else { 
      if (!comp(*first2,*first1)) { 
       f(*first1++,*first2); 
      } 
      ++first2; 
     } 
    } 
} 

È possibile utilizzarlo per elaborare tutte le proprietà a O (N + M) di tempo. Ecco un esempio:

#include <map> 
#include <string> 
#include <functional> 
#include <cassert> 

using std::map; 
using std::string; 
using std::function; 

struct Property { 
    enum Type { UUID, STRING }; 
    Type type; 
    string value; 
}; 

int main() 
{ 
    map<string,Property> properties; 
    map<string,function<void(Property&)>> processors; 

    properties["id"] = Property{Property::UUID,"12345678"}; 
    properties["name"] = Property{Property::STRING,"name"}; 

    bool id_found = false; 
    bool name_found = false; 

    processors["id"] = [&](Property&){ id_found = true; }; 
    processors["name"] = [&](Property&){ name_found = true; }; 

    match(
     properties.begin(),properties.end(), 
     processors.begin(),processors.end(), 
     [](auto &a,auto &b){ b.second(a.second); }, 
     [](auto &a,auto &b) { return a.first < b.first; } 
    ); 

    assert(id_found && name_found); 
} 

La mappa processors può essere costruito separatamente e riutilizzato per ridurre l'overhead.