mapa existência em C ++

Question

Eu quero algo como um std :: map , mas eu só quero ver se o item existe ou não, eu realmente não precisa de uma chave e um valor. O que devo usar?

Answer 1

Parece que você precisa de um std :: set .

Answer 2

Se você quiser o mesmo tipo de comportamento como std::map, então você quer std::set.

Se você está misturando as operações de inserção / exclusão e consulta, em seguida, std::set é provavelmente a melhor escolha. No entanto, se você pode preencher o conjunto de primeiro e depois segui-lo com as consultas, pode valer a pena olhar para usando std::vector, classificando-o, e em seguida, usando uma pesquisa binária para verificar a existência no vector.

Answer 3

Se você realmente só precisa de existência, e nem mesmo uma ordem, você precisa de um unordered_set. Ele está disponível a partir do C ++ 0x favorito fornecedor ou boost.org .

Answer 4

Se os seus dados é numérica você pode usar um std :: vector que é otimizada para o espaço:

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

Você provavelmente deve olhar em stl::set para o que você precisa. A stl::bitset é outra opção.

Ele vai depender de como você precisa usar as informações que iria definir qual delas é a melhor. Um set é uma estrutura de dados classificados, inserção, deleção e encontrar tomada O (N log N) tempo. Mas se você precisa iterate sobre todos os valores que você marcou para a "existência", então o set é o caminho a percorrer.

Se você só precisa de marca e procurar o fato que algo é um membro de um conjunto, em seguida, o bitset poderia ser melhor para você. Inserção, encontrar e apagar só leva O (1), mas você pode apenas valores int cobrar. Iteração sobre todos os valores marcados levará O (N), como você precisa passar por todo o conjunto para encontrar os membros que estão definidos para true. Você pode usá-lo em conjunto com um stl :: mapear para mapear a partir dos valores você tem que os valores numéricos do bitset necessita.

Olhe para as operações que você precisa executar com os valores no seu conjunto e você deve ser capaz de escolher a estrutura de dados apropriado

Answer 6

Você pode continuar usando std :: map para a finalidade desejada.

Para verificar se um item específico (do tipo chave) existe no mapa ou não, você pode usar o seguinte código:

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

Como respondidas anteriormente, std :: set irá fazer o trabalho bem. Curiosamente ambos, conjunto e mapa são representados como árvores internamente.

Answer 7

Se a chave é o valor, em seguida, você pode também considerar um "filtro bloom" em vez de um conjunto.