boost::unordered_set intersection using templates

Question

I wrote this function to do unordered_set intersection using templates. I have seen this answer but I thought that it was overkill. I would like the method to take in 2 sets and return a set.

class SetUtilites{
public:
 template<typename Type>
 static boost::unordered_set<Type> intersection(const boost::unordered_set<Type> &set1, const boost::unordered_set<Type> &set2){
 if(set1.size() < set2.size()){
 boost::unordered_set<Type> iSet;
 boost::unordered_set<Type>::iterator it;
 for(it = set1.begin(); it != set1.end();++it){
 if(set2.find(*it) != set2.end()){
 iSet.insert(*it);
 }
 }
 return iSet;
 }else{
 return intersection(set2,set1);
 }
 }
};

Answer 1

• SetUtilites is misspelled; it should be SetUtilities.

• For better readability, consider doing something about this long line:

  static boost::unordered_set<Type> intersection(const boost::unordered_set<Type> &set1, const boost::unordered_set<Type> &set2)
  

  You could shorten the types as such via typedef, but it may not help very much, or it may even make things uglier. You could also wrap the line in some way. Choose whichever works best.

• Do you even need a class for this? It just contains one function and no data members, so it's not really doing anything relevant as one. Instead, just make this a free function (non-member function) and put it into a namespace with a similar name as the class.

• The name iSet sort of sounds like Hungarian notation, although it appears to be a shortened form of intersectionSet. If you still don't want to call it something that lengthy, you could rename it to something like finalSet, indicating that it will be returned from the function.

Answer 2

Bug

When your sets are of equal size you well end up in an endless recursion. Instead of if(set1.size() < set2.size()) you should use if(set1.size() <= set2.size()) (after all it does not make much sense to swap if the sets are of equal size).

Use C++11 loops ...

With C++11 I would advise you to use range based for:

for(auto const &element: set1)

To avoid having to deal with the element type and with iterators.

... or an alternative

I assume you are not using C++11 or you would have taken std::unordered_set instead of the boost one.

Even without C++11 there is BOOST_FOREACH which you could use:

BOOST_FOREACH(Type const &element, set1)

Use easier to understand functions

Furthermore I would suggest to use the count function so you don't have to compare iterators:

if(set2.count(element) > 0)
 iSet.insert(element);

Wrap Up

Finally I would avoid the vertical whitespace that does not add clarity which makes the resulting code (with additions from Jamal's answer):

template<typename Type>
static boost::unordered_set<Type> intersection(const boost::unordered_set<Type> &set1, const boost::unordered_set<Type> &set2){
 if(set1.size() <= set2.size()){
 boost::unordered_set<Type> iSet;
 for(auto const &element : set1){
 if(set2.count(element) > 0) {
 iSet.insert(element);
 }
 }
 return iSet;
 }else{
 return intersection(set2,set1);
 }
}

• pbible: Thanks for bug fix. I would guess that count is more expensive than find, no? Comparing against end is common in stl I believe. Your solution is great, but I do not wish to use c++11 features.
• Nobody moving away from SE: I would say count is internally implemented as end-comparison. End-comparison is a common idiom but still harder to read than count (I believe). In any case it is longer code so it offers more space for errors. Regerding C++11: You can simply transform the C++11 for to BOOST_FOREACH as I have written and the code should work the same. Explicit iterator loops always have the problem of being very verbose and doing potentially other things than looping over all elements. A foreach does communicate more clearly what it does.
• pbible: I agree with the for each point. It is much clearer. I feel a little funny about using count with set because the semantics clash. What I really want would be hasKey or hasElement O(1) of course. I could make another function for that and make it clearer.