Pode set_intersection ser usado com hash_set em C ++?

Question

Eu estou calculando intersecção, união e diferenças de conjuntos. Eu tenho um typedef de meu tipo set:

typedef set<node_type> node_set;

Quando ele é substituído por

typedef hash_set<node_type> node_set;

Os resultados são diferentes. É um programa complicado, e antes de eu começar a depuração - eu estou fazendo a coisa certa? Quando eu usar funções como este:

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

• eles devem trabalhar de forma integrada com os dois set e hash_set?

Answer 1

Eu não penso assim.

Um dos pré-condição de set_intersection é:

• [first1, last1) é ordenada em ordem crescente de acordo com operator<. Ou seja, para cada par de iteradores i e j em [first1, last1) tal que precede i j, *j < *i é falsa.

O hash_set (e unordered_set) é não ordenada, de modo a condição ordenado não pode ser satisfeita.

tr1 :: união unordered_set e intersecção sobre como se cruzam unordered_sets .

Answer 2

Eu estou indo para ir sem. Tenha em mente hash_set não é padrão C ++ e nunca será, é uma extensão mais antigo que já não é suportado. O mais recente "hash de mapas" são chamados unordered_set e unordered_map, disponível em TR1, Boost, e C ++ 0x.

A razão é um não é que set_intersection requer os dados de entrada a ser classificado. Ao contrário, a razão de um mapa de hash é tão rápido é que ele dá-se de encomenda. Isto é, obviamente, mais pronunciada sob o nome unordered_set. Assim, a pré-condição não pode ser cumprida de forma confiável.

Answer 3

Não, você não pode usar set_intersection porque set_intersection requer que os dois conjuntos são ordenados (usando a mesma ordem). conjuntos de hash não são ordenados de forma alguma. Em C ++ 0x eles vão na verdade ser chamado unordered_set.