Carte d'existence en C ++

Question

Je veux quelque chose comme un std :: map , mais seulement moi veux voir si l'élément existe ou non, je n'ai pas réellement besoin d'une clé ET d'une valeur. Que devrais-je utiliser?

Answer 1

On dirait qu'il vous faut un std :: set .

Answer 2

Si vous voulez le même type de comportement que std :: map , vous voulez alors std :: set .

Si vous mélangez des opérations d'insertion / suppression et d'interrogation, alors std :: set est probablement le meilleur choix. Cependant, si vous pouvez d'abord renseigner l'ensemble, puis le suivre avec les requêtes, il vaut peut-être la peine d'utiliser std :: vector , de le trier, puis d'utiliser une recherche binaire pour vérifier son existence dans le vecteur.

Answer 3

Si vous avez vraiment besoin d'existence, et même pas d'une commande, vous avez besoin d'un unordered_set . Il est disponible auprès de votre fournisseur C ++ 0x ou boost.org favori.

Answer 4

Si vos données sont numériques, vous pouvez utiliser un std :: vector optimisé pour l'espace:

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

Vous devriez probablement consulter stl :: set pour ce dont vous avez besoin. Une stl :: bitset est une autre option.

Cela dépendra de la façon dont vous devez utiliser les informations permettant de définir lequel de ces éléments est le meilleur. Un set est une structure de données triée. Les insertions, recherches et suppressions prennent un temps O (LOG N). Mais si vous avez besoin de parcourir toutes les valeurs que vous avez marquées pour "existence", alors le set est la voie à suivre.

S'il vous suffit de marquer et de rechercher le fait que quelque chose est membre d'un ensemble, le jeu de bits pourrait être préférable pour vous. L'insertion, la recherche et la suppression ne prennent que O (1), mais vous ne pouvez collecter que les valeurs int . Si vous parcourez toutes les valeurs marquées, vous aurez besoin de O (N), car vous devez parcourir l'ensemble pour trouver les membres définis sur true . Vous pouvez l'utiliser conjointement avec un stl :: map pour mapper les valeurs vous avez les valeurs numériques dont bitset a besoin.

Examinez les opérations que vous devez effectuer avec les valeurs de votre ensemble et choisissez le type de structure de données approprié.

Answer 6

Vous pouvez continuer à utiliser std :: map dans le but souhaité.

Pour vérifier si un élément particulier (de type clé) existe ou non dans la carte, vous pouvez utiliser le code suivant:

if (mapObj.count(item) != 0)
{
   // item exists
}

Comme répondu précédemment, std :: set fera également le travail. Fait intéressant, à la fois, set et map sont représentés sous forme d'arbres en interne.

Answer 7

Si la clé est la valeur, vous pouvez également envisager un "filtre de bloom". plutôt qu'un ensemble.