std::map insert o std::map find?

Question

Supponendo una mappa in cui si desidera preservare le voci esistenti.Nel 20% dei casi, la voce che stai inserendo è un nuovo dato.C'è un vantaggio nel fare std::map::find quindi std::map::insert utilizzando l'iteratore restituito?Oppure è più rapido tentare l'inserimento e quindi agire in base al fatto che l'iteratore indichi o meno che il record è stato o meno inserito?

Answer 1

La risposta è che non fai nessuna delle due cose.Invece vuoi fare qualcosa suggerito dal punto 24 di STL efficace di Scott Meyers:

typedef map<int, int> MapType;    // Your map type may vary, just change the typedef

MapType mymap;
// Add elements to map here
int k = 4;   // assume we're searching for keys equal to 4
int v = 0;   // assume we want the value 0 associated with the key of 4

MapType::iterator lb = mymap.lower_bound(k);

if(lb != mymap.end() && !(mymap.key_comp()(k, lb->first)))
{
    // key already exists
    // update lb->second if you care to
}
else
{
    // the key does not exist in the map
    // add it to the map
    mymap.insert(lb, MapType::value_type(k, v));    // Use lb as a hint to insert,
                                                    // so it can avoid another lookup
}

Answer 2

La risposta a questa domanda dipende anche da quanto è costoso creare il tipo di valore che stai memorizzando nella mappa:

typedef std::map <int, int> MapOfInts;
typedef std::pair <MapOfInts::iterator, bool> IResult;

void foo (MapOfInts & m, int k, int v) {
  IResult ir = m.insert (std::make_pair (k, v));
  if (ir.second) {
    // insertion took place (ie. new entry)
  }
  else if ( replaceEntry ( ir.first->first ) ) {
    ir.second->second = v;
  }
}

Per un tipo di valore come int, quanto sopra sarà più efficiente di una ricerca seguita da un inserimento (in assenza di ottimizzazioni del compilatore).Come già detto, questo accade perché la ricerca sulla mappa avviene una sola volta.

Tuttavia, la chiamata a insert richiede che tu abbia già costruito il nuovo "valore":

class LargeDataType { /* ... */ };
typedef std::map <int, LargeDataType> MapOfLargeDataType;
typedef std::pair <MapOfLargeDataType::iterator, bool> IResult;

void foo (MapOfLargeDataType & m, int k) {

  // This call is more expensive than a find through the map:
  LargeDataType const & v = VeryExpensiveCall ( /* ... */ );

  IResult ir = m.insert (std::make_pair (k, v));
  if (ir.second) {
    // insertion took place (ie. new entry)
  }
  else if ( replaceEntry ( ir.first->first ) ) {
    ir.second->second = v;
  }
}

Per chiamare "insert" stiamo pagando la chiamata costosa per costruire il nostro tipo di valore - e da quello che hai detto nella domanda non utilizzerai questo nuovo valore il 20% delle volte.Nel caso precedente, se la modifica del tipo di valore della mappa non è un'opzione, è più efficiente eseguire prima la ricerca per verificare se è necessario costruire l'elemento.

In alternativa, il tipo di valore della mappa può essere modificato per memorizzare gli handle sui dati utilizzando il tipo di puntatore intelligente preferito.La chiamata a insert utilizza un puntatore nullo (molto economico da costruire) e solo se necessario viene costruito il nuovo tipo di dati.

Answer 3

Non ci sarà quasi alcuna differenza di velocità tra i 2, find restituirà un iteratore, insert farà lo stesso e cercherà comunque nella mappa per determinare se la voce esiste già.

COSÌ..dipende dalle preferenze personali.Provo sempre a inserire e quindi aggiornare se necessario, ma ad alcune persone non piace gestire la coppia restituita.

Answer 4

Penserei che se esegui una ricerca e poi inserisci, il costo aggiuntivo sarebbe quando non trovi la chiave e esegui l'inserimento dopo.È un po' come sfogliare i libri in ordine alfabetico e non trovare il libro, poi sfogliarli di nuovo per vedere dove inserirlo.Dipende da come gestirai le chiavi e se cambiano costantemente.Ora c'è una certa flessibilità nel senso che se non lo trovi, puoi effettuare il log, l'eccezione, fare quello che vuoi...

Answer 5

Mi sono perso con la risposta in alto.

Find restituisce map.end() se non trova nulla, il che significa che stai aggiungendo nuove cose

iter = map.find();
if (iter == map.end()) {
  map.insert(..) or map[key] = value
} else {
  // do nothing. You said you did not want to effect existing stuff.
}

è due volte più lento di

map.insert

per qualsiasi elemento non già presente nella mappa poiché dovrà cercare due volte.Una volta per vedere se c'è, un'altra per trovare il posto dove mettere la cosa nuova.

Answer 6

Se sei preoccupato per l'efficienza, potresti voler dare un'occhiata hash_map<>.

Tipicamente map<> è implementato come un albero binario.A seconda delle tue esigenze, una hash_map potrebbe essere più efficiente.

Answer 7

Non mi sembra di avere abbastanza punti per lasciare un commento, ma la risposta spuntata mi sembra prolissa: se consideri che insert restituisce comunque l'iteratore, perché andare a cercare lower_bound, quando puoi semplicemente usare l'iteratore restituito.Strano.

Answer 8

Qualsiasi risposta sull'efficienza dipenderà dall'esatta implementazione del tuo STL.L’unico modo per saperlo con certezza è confrontarlo in entrambi i modi.Immagino che difficilmente la differenza sia significativa, quindi decidi in base allo stile che preferisci.

Answer 9

map[tasto] - lascia che stl lo risolva.Questo significa comunicare la tua intenzione nel modo più efficace.

Sì, abbastanza giusto.

Se esegui una ricerca e poi un inserimento stai eseguendo 2 x O(log N) quando ottieni un errore poiché la ricerca ti consente solo di sapere se devi inserire non dove dovrebbe andare l'inserimento (lower_bound potrebbe aiutarti lì) .Semplicemente un inserto diretto e poi esaminare il risultato è la strada che seguirei.