Peut set_intersection être utilisé avec hash_set en C ++?

Question

Je calculais intersection, l'union et les différences d'ensembles. J'ai un typedef de mon type de jeu:

typedef set<node_type> node_set;

Quand il est remplacé par

typedef hash_set<node_type> node_set;

Les résultats sont différents. Il est un programme complexe, et avant que je commence le débogage - ce que je fais bien? Lorsque j'utilise des fonctions comme ceci:

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

• devraient-ils travailler en toute transparence à la fois et mis hash_set?

Answer 1

Je ne pense pas.

L'un des pré-condition de set_intersection est:

• [first1, last1) est triés dans l'ordre croissant selon la operator<. C'est, pour chaque paire de itérateurs i et j dans [first1, last1) tels que i précède j, *j < *i est fausse.

Le hash_set (et unordered_set) est non ordonnée, de sorte que la condition ordonnée ne peut pas être satisfait.

Voir TR1 :: unordered_set union et intersection sur la façon de recouper unordered_sets .

Answer 2

Je vais aller sans. Gardez à l'esprit est hash_set ne sera pas la norme C ++ et jamais, il est une extension plus qui est plus pris en charge. Les nouvelles "cartes de hachage" sont appelés unordered_set et unordered_map, disponible en TR1, Boost et C ++ 0x.

La raison pour laquelle il est un pas que set_intersection exige que les données d'entrée à trier. Au contraire, la raison pour laquelle une carte de hachage est si rapide est-il abandonne la commande. Ceci est évidemment plus prononcée sous le nom unordered_set. Ainsi, la condition sine qua non fiable ne peut être satisfaite.

Answer 3

Non, vous ne pouvez pas utiliser set_intersection parce set_intersection exige que les deux ensembles sont commandés (en utilisant le même ordre). ensembles hash ne sont pas commandés en aucune façon. En C ++ 0x, ils seront en fait appelés unordered_set.