Qual è la differenza tra il set <pair> e la mappa in C++?

Question

Ci sono due modi in cui posso facilmente creare una chiave, attribuzione di valore in C++ STL: mappe e insiemi di coppie. Per esempio, potrei avere

map<key_class,value_class> 

o

set<pair<key_class,value_class> > 

In termini di algoritmo di complessità e stile di codifica, quali sono le differenze tra questi usi?

Answer 1

Set elementi non possono essere modificati mentre sono nel set. iterator e set sono equivalenti. Pertanto, con set<pair<key_class,value_class> >, non è possibile modificare il valore value_class sul posto. È necessario rimuovere il vecchio valore dal set e aggiungere il nuovo valore. Tuttavia, se value_class è un puntatore, questo non impedisce di modificare l'oggetto a cui punta.

Con map<key_class,value_class>, è possibile modificare il value_class sul posto, assumendo che si disponga di un riferimento non costante alla mappa.

Answer 2

La differenza di base è che per il set la chiave è la coppia, mentre per la mappa la chiave è key_class - questo fa apparire le cose da key_class, che è quello che vuoi fare con le mappe, difficile per il set.

Entrambi sono in genere implementati con la stessa struttura di dati (di solito un albero binario bilanciato rosso-nero), quindi la complessità per i due dovrebbe essere la stessa.

Answer 3

Sono semanticamente diversi. Considerare:

#include <set> 
#include <map> 
#include <utility> 
#include <iostream> 

using namespace std; 

int main() { 
    pair<int, int> p1(1, 1); 
    pair<int, int> p2(1, 2); 
    set< pair<int, int> > s; 
    s.insert(p1); 
    s.insert(p2); 
    map<int, int> m; 
    m.insert(p1); 
    m.insert(p2); 
    cout << "Set size = " << s.size() << endl; 
    cout << "Map size = " << m.size() << endl; 
} 

http://ideone.com/cZ8Vjr

uscita:

Set dimensione size = 2
Mappa = 1

Answer 4

map<key_class,value_class> fascicolerà su key_class e consentire non duplicati di key_class.
set<pair<key_class,value_class> > fascicolerà su key_class e poi value_class se le istanze key_class sono uguali, e consentirà più valori per key_class

Answer 5

std::map funge da struttura dati associativa. In altre parole, ti permette di interrogare e modificare i valori usando la sua chiave associata.

A std::set<pair<K,V> > È possibile eseguire un std::set<pair<K,V> >, ma è necessario scrivere codice aggiuntivo per la query utilizzando una chiave e un altro codice per modificare il valore (ad esempio, rimuovere la coppia precedente e inserirne un'altra con la stessa chiave e una diversa valore). Devi anche assicurarti che non ci siano più di due valori con la stessa chiave (hai indovinato, più codice).

In altre parole, è possibile provare a clacson un std::set per funzionare come un std::map, ma non c'è motivo.

Answer 6

Per comprendere la complessità algoritmica, è necessario innanzitutto comprendere l'implementazione.

std :: map è implementato utilizzando RB-tree dove come hash_map vengono implementate utilizzando le matrici dell'elenco collegato. std :: map fornisce O (log (n)) per l'operazione insert/delete/search, hash_map è O (1) è best case e o (n) nel peggiore dei casi, a seconda delle collisioni hash.

Answer 7

Visualizzazione che differenza semantica Philipp menzionato dopo passo attraverso il codice, si noti come carta chiave è un int const e come p2 non è stato inserito nella m: