Può essere utilizzato con set_intersection hash_set in C ++?

Question

Sto calcolando intersezione, unione e le differenze di set. Ho un typedef del mio tipo di set:

typedef set<node_type> node_set;

Quando viene sostituito con

typedef hash_set<node_type> node_set;

I risultati sono diversi. Si tratta di un programma complicato, e prima di iniziare il debug - sto facendo bene? Quando uso le funzioni in questo modo:

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

• dovrebbero funzionare senza problemi con entrambe impostate e hash_set?

Answer 1

Non penso così.

Uno dei pre-condizione della set_intersection è:

• [first1, last1) è ordinati in ordine crescente secondo operator<. Cioè, per ogni coppia di iteratori i e j in [first1, last1) tale che precede i j, *j < *i è falsa.

Il hash_set (e unordered_set) è ordinata, quindi la condizione ordinata non possono essere soddisfatte.

tr1 :: unordered_set unione e intersezione su come si intersecano unordered_sets .

Answer 2

ho intenzione di andare con n. Tenete a mente hash_set non è standard C ++ e non lo sarà mai, è un'estensione più vecchio che non è più supportato. Le "mappe hash" più recenti sono chiamati unordered_set e unordered_map, disponibili in TR1, Boost, e C ++ 0x.

Il motivo è un no è che set_intersection richiede i dati di input da ordinare. Al contrario, la ragione per una mappa di hash è così rapido è rinuncia ordinazione. Questo è, ovviamente, più pronunciato sotto il nome unordered_set. Quindi il presupposto non può essere attendibilmente incontrato.

Answer 3

No, non è possibile utilizzare set_intersection perché set_intersection richiede che le due serie sono ordinate (utilizzando lo stesso ordine). set di hash non sono ordinati in alcun modo. In C ++ 0x saranno infatti chiamati unordered_set.