Можно ли использовать 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 s.

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.