Domanda
Voglio qualcosa come un std :: map , ma solo io voglio vedere se l'articolo esiste o no, in realtà non ho bisogno di una chiave E di un valore. Cosa dovrei usare?
Soluzione
Sembra che tu abbia bisogno di un std :: set .
Altri suggerimenti
Se vuoi lo stesso tipo di comportamento di std :: map
, allora vuoi std :: set
.
Se si stanno combinando operazioni di inserimento / eliminazione e query, allora std :: set
è probabilmente la scelta migliore. Tuttavia, se è possibile popolare prima il set e quindi seguirlo con le query, potrebbe valere la pena guardare std :: vector
, ordinarlo e quindi utilizzare una ricerca binaria per verificare l'esistenza in il vettore.
Se hai davvero bisogno solo dell'esistenza e nemmeno di un ordine, hai bisogno di un unordered_set
. È disponibile presso il tuo fornitore C ++ 0x preferito o boost.org .
Se i tuoi dati sono numerici puoi usare uno std :: vector che è ottimizzato per lo spazio:
D:\Temp>type vectorbool.cpp
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<bool> vb(10);
vb[5] = true;
for (vector<bool>::const_iterator ci = vb.begin(); ci != vb.end(); ++ci) {
cout << *ci << endl;
}
}
D:\Temp>cl /nologo /W4 /EHsc vectorbool.cpp
vectorbool.cpp
D:\Temp>vectorbool.exe
0
0
0
0
0
1
0
0
0
0
Probabilmente dovresti guardare stl :: set
per quello che ti serve. Un stl :: bitset
è un'altra opzione.
Dipenderà da come è necessario utilizzare le informazioni che definirebbero quale di queste è migliore. Un set
è una struttura di dati ordinata, l'inserimento, la ricerca e l'eliminazione impiegano il tempo O (LOG N). Ma se devi iterare su tutti i valori che hai contrassegnato per " esistenza " quindi il set
è la strada da percorrere.
Se hai solo bisogno di contrassegnare e cercare il fatto che qualcosa è un membro di un set, il bitset
potrebbe essere migliore per te. Inserimento, trova ed elimina richiede solo O (1), ma puoi raccogliere solo valori int
. L'iterazione su tutti i valori contrassegnati richiederà O (N) in quanto è necessario scorrere l'intero set per trovare i membri impostati su true
. Puoi usarlo in concerto con una stl :: map per mappare dai valori hai i valori numerici di cui bitset
ha bisogno.
Guarda le operazioni che devi eseguire con i valori nel tuo set e dovresti essere in grado di scegliere la struttura dati appropriata
Puoi continuare a usare std :: map per lo scopo desiderato.
Per verificare se un particolare elemento (di tipo chiave) esiste nella mappa o no, puoi usare il seguente codice:
if (mapObj.count(item) != 0)
{
// item exists
}
Come spiegato in precedenza, anche std :: set farà il lavoro. È interessante notare che sia set che map sono rappresentati internamente come alberi.
Se la chiave È il valore, allora potresti anche considerare un filtro "bloom" " piuttosto che un set.