Mapa de existencia en C++

Question

quiero algo como un std::mapa, pero solo quiero ver si el elemento existe o no, en realidad no necesito una clave Y un valor.¿Qué debo usar?

Answer 1

Parece que necesitas un estándar::conjunto.

Answer 2

Si quieres el mismo tipo de comportamiento que std::map, entonces quieres std::set.

Si está mezclando operaciones de inserción/eliminación y consulta, entonces std::set es probablemente la mejor opción.Sin embargo, si puede completar el conjunto primero y luego seguirlo con las consultas, podría valer la pena considerar el uso std::vector, clasificándolo y luego usando una búsqueda binaria para verificar su existencia en el vector.

Answer 3

Si realmente necesitas sólo existencia, y ni siquiera un orden, necesitas una unordered_set.Está disponible en su proveedor favorito de C++ 0x o impulso.org.

Answer 4

Si sus datos son numéricos, puede usar un std::vector que está optimizado para el espacio:

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

Probablemente deberías mirar stl::set para lo que necesitas.A stl::bitset es otra opción.

Dependerá de cómo necesites utilizar la información que definiría cuál de estos es mejor.A set es una estructura de datos ordenada, la inserción, búsqueda y eliminación toman O (LOG N) tiempo.Pero si necesitas iterar sobre todos los valores que ha marcado para "existencia", entonces el set es el camino a seguir.

Si sólo necesita marcar y buscar el hecho que algo es miembro de un conjunto entonces el bitset podría ser mejor para ti.Insertar, buscar y eliminar solo requiere O(1), pero solo puedes recopilar int valores.Iterar sobre todos los valores marcados tomará O(N) ya que necesita recorrer todo el conjunto para encontrar los miembros que están configurados para true.Puedes usarlo junto con un stl::mapa para asignar los valores que tiene a los valores numéricos, bitset necesidades.

Mire las operaciones que necesita realizar con los valores de su conjunto y debería poder elegir la estructura de datos adecuada.

Answer 6

Puede seguir usando std::map para el propósito deseado.

Para verificar si un elemento particular (de tipo clave) existe en el mapa o no, puede usar el siguiente código:

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

Como respondimos anteriormente, std::set también hará el trabajo.Curiosamente, tanto el conjunto como el mapa están representados internamente como árboles.

Answer 7

Si la clave ES el valor, entonces también podría considerar un "filtro de floración" en lugar de un conjunto.