Existenz Karte in C ++

Question

Ich möchte so etwas wie ein std :: map , aber ich nur sehen wollen, ob das Element vorhanden ist oder nicht, muss ich nicht wirklich einen Schlüssel und einen Wert. Was soll ich verwenden?

Answer 1

Sieht aus wie Sie benötigen ein std :: set .

Answer 2

Wenn Sie die gleiche Art von Verhalten als std::map wollen, dann möchten Sie std::set.

Wenn Sie Insert mischen / löschen und Abfrageoperationen, dann ist std::set wahrscheinlich die beste Wahl. Wenn Sie jedoch den ersten Satz füllen und dann mit den Anfragen folgen, könnte es lohnt einen Blick auf std::vector mit, Sortier-, und dann eine binäre Suche auf der Existenz in dem Vektor zu überprüfen.

Answer 3

Wenn Sie wirklich brauchen nur Existenz, und nicht einmal eine Bestellung aufgeben, benötigen Sie einen unordered_set. Es ist erhältlich bei Ihrem Lieblings C ++ 0x-Anbieter oder boost.org .

Answer 4

Wenn Sie Ihre Daten numerische Sie ein std :: vector verwenden können, die für Raum optimiert ist:

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

Sie sollten wahrscheinlich sehen stl::set für das, was Sie brauchen. Ein stl::bitset ist eine weitere Option.

Es wird davon abhängen, wie Sie die Informationen verwenden müssen, was von diesen würde definieren besser ist. A set ist eine sortierte Datenstruktur, Insertion, Deletion finden und nehmen O Zeit (log N). Aber wenn Sie auf iterate über alle Werte, die Sie für „Existenz“ markiert haben, dann ist die set ist der Weg zu gehen.

Wenn Sie nur markieren müssen und Nachschlagen der Tatsache , dass etwas ist Mitglied einer Gruppe, dann könnte die bitset für Sie besser sein. Insertion, finden und löschen Sie nur dauert O (1), aber man kann nur int Werte sammeln. Iterieren über alle markierten Werte nehmen O (N), wie Sie durch den ganzen Satz gehen, müssen die Mitglieder zu finden, die true eingestellt. Sie können es im Konzert mit einem stl :: map aus den Werten zur Karte Sie müssen die Zahlenwerte der bitset muss.

Schauen Sie sich die Vorgänge, die Sie brauchen, um mit den Werten in Ihrem Set auszuführen, und Sie sollten die entsprechende Datenstruktur

wählen können

Answer 6

Sie können halten std :: map für den gewünschten Zweck verwendet wird.

Um zu überprüfen, ob ein bestimmtes Element (Schlüsseltyp) in der Karte vorhanden ist oder nicht, können Sie folgenden Code verwenden:

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

Wie bereits beantwortet, std :: Set wird auch die Arbeit machen. Interessanter beide, Satz und Karte sind wie Bäume intern dargestellt.

Answer 7

Wenn der Schlüssel der Wert ist, dann könnten Sie auch einen „Bloom-Filter“ betrachten, anstatt einen Satz.