c ++ map find () possibilmente inserire (): come ottimizzare le operazioni?

Question

Sto usando la struttura di dati della mappa STL e al momento il mio codice invoca find () : se la chiave non era precedentemente nella mappa, chiama insert () , altrimenti non fa nulla.

map<Foo*, string>::iterator it;
it = my_map.find(foo_obj);   // 1st lookup

if(it == my_map.end()){
  my_map[foo_obj] = "some value";  // 2nd lookup
}else{
  // ok do nothing.
}

Mi chiedevo se esiste un modo migliore di questo, perché per quanto ne so, in questo caso quando voglio inserire una chiave che non è ancora presente, eseguo 2 ricerche nelle strutture di dati della mappa: una per trova () , uno in inserisci () (che corrisponde all'operatore [] ).

Grazie in anticipo per qualsiasi suggerimento.

Answer 1

Normalmente se fai una ricerca e forse un inserimento, allora vuoi mantenere (e recuperare) il vecchio valore se esiste già. Se vuoi solo sovrascrivere qualsiasi vecchio valore, map [foo_obj] = " un certo valore " lo farà.

Ecco come ottenere il vecchio valore o inserirne uno nuovo se non esistesse, con una ricerca della mappa:

typedef std::map<Foo*,std::string> M;
typedef M::iterator I;
std::pair<I,bool> const& r=my_map.insert(M::value_type(foo_obj,"some value"));
if (r.second) { 
    // value was inserted; now my_map[foo_obj]="some value"
} else {
    // value wasn't inserted because my_map[foo_obj] already existed.
    // note: the old value is available through r.first->second
    // and may not be "some value"
}
// in any case, r.first->second holds the current value of my_map[foo_obj]

Questo è un idioma abbastanza comune che potresti voler usare una funzione di supporto:

template <class M,class Key>
typename M::mapped_type &
get_else_update(M &m,Key const& k,typename M::mapped_type const& v) {
    return m.insert(typename M::value_type(k,v)).first->second;
}

get_else_update(my_map,foo_obj,"some value");

Se si dispone di un calcolo costoso per v si desidera saltare se esiste già (ad esempio memoization), è possibile generalizzare anche questo:

template <class M,class Key,class F>
typename M::mapped_type &
get_else_compute(M &m,Key const& k,F f) {
   typedef typename M::mapped_type V;
   std::pair<typename M::iterator,bool> r=m.insert(typename M::value_type(k,V()));
   V &v=r.first->second;
   if (r.second)
      f(v);
   return v;
}

dove ad esempio

struct F {
  void operator()(std::string &val) const 
  { val=std::string("some value")+" that is expensive to compute"; }
};
get_else_compute(my_map,foo_obj,F());

Se il tipo mappato non è costruibile per impostazione predefinita, imposta F come valore predefinito o aggiungi un altro argomento per get_else_compute.

Answer 2

Esistono due approcci principali. Il primo consiste nell'utilizzare la funzione di inserimento che accetta un tipo di valore e che restituisce un iteratore e un valore booleano che indicano se si è verificato un inserimento e restituisce un iteratore all'elemento esistente con la stessa chiave o all'elemento appena inserito.

map<Foo*, string>::iterator it;
it = my_map.find(foo_obj);   // 1st lookup

my_map.insert( map<Foo*, string>::value_type(foo_obj, "some_value") );

Il vantaggio è che è semplice. Lo svantaggio principale è che si costruisce sempre un nuovo valore per il secondo parametro, indipendentemente dal fatto che sia necessario o meno un inserimento. Nel caso di una stringa questo probabilmente non ha importanza. Se il tuo valore è costoso da costruire, potrebbe essere più dispendioso del necessario.

Un modo per aggirare questo è usare la versione 'suggerimento' di insert.

std::pair< map<foo*, string>::iterator, map<foo*, string>::iterator >
    range = my_map.equal_range(foo_obj);

if (range.first == range.second)
{
    if (range.first != my_map.begin())
        --range.first;

    my_map.insert(range.first, map<Foo*, string>::value_type(foo_obj, "some_value") );
}

L'inserimento è garantito per essere in tempo costante ammortizzato solo se l'elemento viene inserito immediatamente dopo l'iteratore fornito, quindi - , se possibile.

Modifica

Se questa necessità di - sembra strana, lo è. Esiste un difetto aperto (233) nello standard che evidenzia questo problema sebbene la descrizione del problema applicata a map sia più chiara nel problema duplicato 246 .

Answer 3

Nel tuo esempio, vuoi inserire quando non viene trovato. Se la costruzione predefinita e l'impostazione del valore dopo non sono costose, suggerirei una versione più semplice con 1 ricerca:

string& r = my_map[foo_obj];    // only lookup & insert if not existed
if (r == "") r = "some value";  // if default (obj wasn't in map), set value
                                // else existed already, do nothing

Se il tuo esempio dice quello che vuoi veramente, considera di aggiungere quel valore come str Foo :: s invece, hai già l'oggetto, quindi non sarebbero necessarie ricerche, controlla solo se ha default valore per quel membro. E mantieni gli objs nel std :: set . Anche l'estensione della classe FooWithValue2 potrebbe essere più economico dell'uso della mappa .

Ma se unire i dati attraverso la mappa in questo modo è davvero necessario o se si desidera aggiornare solo se esistevano, allora Jonathan ha la risposta.