Kann set_intersection mit hash_set in C ++ verwendet werden?

Question

Ich Berechnung Schnitt, Vereinigung und Unterschiede von Sätzen. Ich habe einen typedef meiner Settyps:

typedef set<node_type> node_set;

Wenn es ersetzt mit

typedef hash_set<node_type> node_set;

Die Ergebnisse sind unterschiedlich. Es ist ein kompliziertes Programm, und bevor ich das Debuggen starten - bin ich es richtig zu machen? Wenn ich Funktionen wie folgt aus:

set_intersection(v_higher.begin(), v_higher.end(), neighbors[w].begin(), neighbors[w].end(), 
            insert_iterator<node_set>(tmp1, tmp1.begin()));

• sollten sie arbeiten nahtlos mit Satz und hash_set?

Answer 1

Ich glaube nicht, dass so.

Einer der Voraussetzung von set_intersection ist:

• [first1, last1) heißt aufsteigend geordnet nach operator<. Das heißt, für jedes Paar von Iteratoren i und j in [first1, last1) so dass i vorangeht j, *j < *i ist falsch.

Die hash_set (und unordered_set) ist ungeordnet, so dass die bestellte Bedingung nicht erfüllt werden kann.

Siehe tr1 :: unordered_set Vereinigung und Durchschnitt wie unordered_sets schneiden .

Answer 2

Ich werde mit Nein gehen. Denken Sie daran, hash_set nicht Standard C ++ und wird es nie sein, es ist ein älteres Erweiterung, die nicht mehr unterstützt wird. Die neueren "Hash-Karten" sind unordered_set und unordered_map, erhältlich in TR1, Erhöhung genannt, und C ++ 0x.

Der Grund ein, es ist nicht, dass set_intersection erfordert die Eingabedaten sortiert werden. Im Gegensatz dazu ist der Grund, eine Hash-Karte so schnell ist es Bestellung aufgibt. Dies wird offensichtlich mehr unter dem Namen unordered_set ausgesprochen. So ist die Voraussetzung nicht zuverlässig erfüllt werden können.

Answer 3

Nein, Sie können nicht set_intersection verwenden, da set_intersection es erforderlich, dass die beiden Sätze bestellt werden (die gleiche Reihenfolge verwenden). Hash-Sets sind in keiner Weise geordnet. In C ++ 0x werden sie in der Tat genannt unordered_set werden.