è insert() necessario in una mappa o unordered_map?

Question

Vedo un sacco di esempi che aggiungere elementi a una map o unordered_map via operator[], in questo modo:

int main() { 
    unordered_map <string, int> m; 
    m["foo"] = 42; 
    cout << m["foo"] << endl; 
} 

C'è qualche ragione per usare la funzione insert membro? Sembrerebbe che entrambi facciano la stessa cosa.

Answer 1

Non lo sono.

operator[] sovrascriverà il valore per questa chiave, se esiste, mentre insert no.

Nel caso operator[] viene utilizzato per l'inserimento di elementi, si prevede che sia un po 'più lento (vedere il commento di MatthieuM sotto per i dettagli), ma qui non è significativo.

Mentre std::map::insert restituisce std::pair< iterator, bool >, dove .second indica se il valore è inserito o esiste già.

---

Per quanto riguarda il tuo commento: non si possono avere 2 elementi con lo stesso valore di chiave e diverso. Questo non è un multimap.

Se c'è un elemento nella mappa, con la stessa chiave si sta cercando di inserire, quindi:

• operator[] sovrascriverà il valore esistente
• std::map::insert sarà non fare nulla. ^* restituisce un std::pair< iterator, bool >, dove .second sarà false (dicendo "il nuovo elemento non è inserito, in quanto tale chiave esiste già") e il .first punterà all'elemento trovato.

_{^* ho cambiato questo grazie alla nota/osservazione, data da @ luk32; ma scrivendo "non farò nulla", non intendevo letteralmente, intendevo che non cambierebbe il valore dell'elemento esistente}

Answer 2

Beh, io non sono d'accordo con la risposta di Kiril in una certa misura e penso che sia non pieno quindi do il mio.

Secondo cppreferencestd::map::operator[] equivale a una determinata chiamata insert(). Da questo penso anche che abbia torto dicendo che il valore verrà sovrascritto. Dice: "Valore restituito Riferimento al valore mappato del nuovo elemento se non esisteva alcun elemento con chiave chiave, altrimenti viene restituito un riferimento al valore mappato dell'elemento esistente."

Quindi sembra che sia un involucro conveniente. Lo insert(), tuttavia, ha questo vantaggio di essere sovraccaricato, quindi fornisce più funzionalità sotto un unico nome.

Dare un punto a Kiril, che sembrano avere una funzionalità leggermente diversa a prima vista, tuttavia IHMO gli esempi che fornisce non sono equivalenti tra loro.

Pertanto, come esempio/motivo per utilizzare insert Vorrei sottolineare, inserendo più elementi contemporaneamente o utilizzando hint (chiamate 3-6 in here).

Quindi insert() è necessario in una mappa o unordered_map? Direi di si. Inoltre, lo operator[] non è necessario in quanto può essere emulato/implementato utilizzando insert, mentre l'altro modo è impossibile! Fornisce semplicemente più funzionalità. Tuttavia, scrivere cose come (insert(std::make_pair(key, T())).first)->second) (dopo cppreference) sembra ingombrante di [].

Quindi, c'è qualche motivo per utilizzare invece la funzione membro di inserimento? Direi per la sovrapposizione di funzionalità, diavolo no.

Answer 3

L'utilizzo di insert() consente di migliorare le prestazioni in determinate situazioni (in particolare per std::map poiché il tempo di ricerca è O(log(n)) anziché ammortizzato costante). Prendi il seguente esempio comune:

std::map<int, int> stuff; 

// stuff is populated, possibly large: 

auto iterator = stuff.find(27); 

if(stuff.end() != iterator) 
{ 
    // subsequent "find", set to 15 
    iterator->second = 15; 
} 
else 
{ 
    // insert with value of 10 
    stuff[27] = 10; 
} 

Il codice sopra riportato ha consentito di trovare efficacemente l'elemento due volte. Possiamo fare che (leggermente) più efficiente scritto così:

// try to insert 27 -> 10 
auto result = stuff.insert(std::make_pair(27, 10)); 

// already existed 
if(false == result.second) 
{ 
    // update to 15, already exists 
    result.first->second = 15; 
} 

Il codice di cui sopra solo cerca di trovare un elemento, una volta, riducendo la complessità algoritmica. Per operazioni frequenti, questo può migliorare drasticamente le prestazioni.

Answer 4

I due non sono equivalenti. insert non sovrascrive un valore esistente e restituisce un valore pair<iterator, bool>, dove iterator è la posizione della chiave, indipendentemente dal fatto che esistesse o meno. bool indica se l'inserimento si è verificato o meno.

operator[] fa effettivamente un lower_bound sulla chiave. Se il risultato di tale operazione è un iterator con la stessa chiave, restituisce un riferimento al valore. In caso contrario, inserisce un nuovo nodo con un valore predefinito, quindi restituisce un riferimento al valore. Questo è il motivo per cui operator[] è un membro non-const: esso auto-vivifica il valore-chiave se non esiste. Questo potrebbe avere implicazioni sulle prestazioni se il tipo di valore è costoso da costruire.

notare anche in C++ 11, abbiamo un metodo emplace che funziona quasi identico a insert, tranne che costruisce la coppia valore-chiave sul posto da argomenti trasmessi, se si verifica un inserto.