Mappa di esistenza in C ++

Question

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?

Answer 1

Sembra che tu abbia bisogno di un std :: set .

Answer 2

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.

Answer 3

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 .

Answer 4

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

Answer 5

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

Answer 6

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.

Answer 7

Se la chiave È il valore, allora potresti anche considerare un filtro "bloom" " piuttosto che un set.