2009-05-20 4 views

Antwort

7

Man kann nur spekulieren, was Ihre wahre Absicht hier ist, also nehme ich an, Sie haben bereits eine Klasse, die Schlüssel und Wert enthält. In diesem Fall ist std :: set mit einem benutzerdefinierten Vergleich möglicherweise eine bessere Wahl als eine std :: map.

Sie müssen dann einen Vergleich bereitstellen, der nur den Schlüsselteil Ihrer Klasse vergleicht, und der Schlüsselteil muss const sein (nicht ändern im Laufe der Zeit), solange das Objekt in der Menge ist. Wie im Kommentar erwähnt, sind die Elemente eines Sets nur als Consts verfügbar. Wenn Sie also den Wert eines solchen Elements ändern wollen, müssen Sie den Schreibzugriff const_cast oder das Member veränderbar deklarieren.

In einer anderen Antwort iain machte einen weiteren sehr guten Vorschlag. Wenn Sie selten in den Container einfügen und meistens auf den Container zugreifen, der nach Elementen sucht, dann ist ein sortierter std :: vector und std :: binary_search eine sehr effektive Alternative zur Menge.

+1

Das Hauptproblem dabei könnte sein, dass set konstante Werte hält, um die Reihenfolge beizubehalten, so dass die CustomPair das zweite Element änderbar haben müsste, und den Vergleich zwingen würde, nur das erste Element zu verwenden. –

+0

@Greg Rogers Danke, fügte der Antwort die Konstanz des Schlüsselteils hinzu. – lothar

+0

Ich weiß nicht, was die Absicht des OP war, aber seine Frage war über die Übergabe von CustomPair <...> als Vorlage Parameter an Std :: Allocator anstelle von Paar <...>. Dies beantwortet die Frage nicht. – Ari

3

Ich würde eher std :: set verwenden.

-2

Ich glaube, Sie können es tun, aber nicht den gewünschten Effekt erhalten, weil die Verwendung von std::allocator wird über rebind<std::pair> getan werden, damit Ihre Auswahl CustomPair überschrieben. In der Tat ist es wahrscheinlich egal, welchen Typ Sie dort eingeben, die STL-Funktionen werden es ignorieren. Zumindest einige von ihnen werden das definitiv tun, aber ich bin mir nicht sicher, ob es alles wird. Streng genommen ist dies mit ziemlicher Sicherheit implementierungsabhängig. Ich weiß nicht, was der Standard sagt.

+1

@Ari-Zuweiser können die interne Implementierung von STL-Containern nicht ändern, sie können nur ändern, wo und wie der Speicher für die internen Daten des Containers zugewiesen wird. – lothar

+0

In der Tat sagt meine Antwort, dass Sie tun können, was das OP buchstäblich verlangt, aber Sie werden nicht den gewünschten Effekt bekommen. Ich habe auch erklärt, wie das möglich ist (kompilieren, aber tut nicht, was Sie denken). Was ist das Problem. – Ari

3

Ich würde entweder einen Satz wie von Lothar beschrieben verwenden oder eine sortierte std::vector wie in "Effective STL" Kapitel 23: "Betrachten Sie ersetzen assoziative Container mit sortierten Vektoren" verwenden.

Die rationale dafür ist, dass ein std::binary_search eines sortierten Vektors mit einem benutzerdefinierten Vergleicher ist fast so schnell und manchmal schneller als eine Map-Lookup und Iteration ist viel schneller. Die Einfügeoperationen sind jedoch teurer (Sie müssen nach jedem Einfügen die Sortierung aufrufen). Viele Karten-Anwendungsfälle werden jedoch sehr selten eingefügt.

Der Vektor wäre mehr Flexibilität als der Satz.

Ich ersetzte eine Karte von 2000 komplexen Objekten (indiziert durch int) mit diesem Ansatz, Iteration und Verarbeitung jedes Objekt in der Karte ging von 50 Sekunden auf weniger als 5 auf einem Server-Klassensystem. Es gab keinen merklichen Unterschied für die Kartensuchzeiten.

+0

+1 für die binäre Suche auf std :: vector – lothar

+1

std :: binary_search() gibt nur zurück, ob der angegebene Wert existiert. Meintest du std :: equal_range()? – bk1e

+0

Danke, ja du bist richtig es ist equal_range – iain