Можно ли использовать set_intersection с hash_set в C++?

Question

Я вычисляю пересечение, объединение и разность множеств.У меня есть typedef моего установленного типа:

typedef set<node_type> node_set;

Когда его заменяют на

typedef hash_set<node_type> node_set;

Результаты разные.Это сложная программа, и прежде чем начать ее отладку, правильно ли я ее делаю?Когда я использую такие функции:

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

• должны ли они беспрепятственно работать как с set, так и с hash_set?

Answer 1

Я так не думаю.

Одно из предварительных условий set_intersection является:

• [first1, last1) является упорядочено в порядке возрастания в соответствии с operator<.То есть для каждой пары итераторов i и j в [first1, last1) такой, что i предшествует j, *j < *i является ложным.

А hash_set (и unordered_set) неупорядочен, поэтому условие упорядоченности не может быть удовлетворено.

Видеть tr1::unordered_set объединение и пересечение о том, как пересекаться unordered_setс.

Answer 2

Я собираюсь пойти без.Иметь ввиду hash_set не является стандартом C++ и никогда им не будет, это старое расширение, которое больше не поддерживается.Новые «хэш-карты» называются unordered_set и unordered_map, доступный в TR1, Boost и C++0x.

Причина, по которой это «нет», заключается в том, что set_intersection требует сортировки входных данных.Напротив, причина, по которой хеш-карта работает так быстро, заключается в том, что она отказывается от упорядочения.Это, очевидно, более выражено под названием unordered_set.Таким образом, это предварительное условие не может быть надежно выполнено.

Answer 3

Нет, вы не можете использовать set_intersection потому что set_intersection требует, чтобы два набора были упорядочены (используя один и тот же порядок).Хэш-наборы никак не упорядочены.В C++0x они фактически будут называться unordered_set.