2

I am calculating intersection, union and differences of sets. I have a typedef of my set type:

typedef set<node_type> node_set;

When it is replaced with 

typedef hash_set<node_type> node_set;

The results are different. It's a complicated program, and before I start debugging - am I doing it right? When I use functions like this:

set_intersection(v_higher.begin(), v_higher.end(), neighbors[w].begin(), neighbors[w].end(), 
            insert_iterator<node_set>(tmp1, tmp1.begin()));
  • should they work seamlessly with both set and hash_set?
R S
  • 11,359
  • 10
  • 43
  • 50

3 Answers3

5

I don't think so.

One of the pre-condition of set_intersection is:

  • [first1, last1) is ordered in ascending order according to operator<. That is, for every pair of iterators i and j in [first1, last1) such that i precedes j, *j < *i is false.

The hash_set (and unordered_set) is unordered, so the ordered condition cannot be satisfied.

See tr1::unordered_set union and intersection on how to intersect unordered_sets.

Community
  • 1
  • 1
kennytm
  • 510,854
  • 105
  • 1,084
  • 1,005
1

I'm going to go with no. Keep in mind hash_set isn't standard C++ and never will be, it's an older extension that's no longer supported. The newer "hash maps" are called unordered_set and unordered_map, available in TR1, Boost, and C++0x.

The reason it's a no is that set_intersection requires the input data to be sorted. Contrarily, the reason a hash map is so quick is it gives up ordering. This is obviously more pronounced under the name unordered_set. So the precondition cannot be reliably met.

GManNickG
  • 494,350
  • 52
  • 494
  • 543
0

No, you can't use set_intersection because set_intersection requires that the two sets are ordered (using the same ordering). Hash sets aren't ordered in any way. In C++0x they will in fact be called unordered_set.

Peter Alexander
  • 53,344
  • 14
  • 119
  • 168