how to find the intersection of two std::set in C+

问题:

I have been trying to find the intersection between two std::set in C++, but I keep getting an error.

I created a small sample test for this

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

int main() {
  set<int> s1;
  set<int> s2;

  s1.insert(1);
  s1.insert(2);
  s1.insert(3);
  s1.insert(4);

  s2.insert(1);
  s2.insert(6);
  s2.insert(3);
  s2.insert(0);

  set_intersection(s1.begin(),s1.end(),s2.begin(),s2.end());
  return 0;
}

The latter program does not generate any output, but I expect to have a new set (let's call it s3) with the following values:

s3 = [ 1 , 3 ]

Instead I'm getting the error:

test.cpp: In function ‘int main()’:
test.cpp:19: error: no matching function for call to ‘set_intersection(std::_Rb_tree_const_iterator<int>, std::_Rb_tree_const_iterator<int>, std::_Rb_tree_const_iterator<int>, std::_Rb_tree_const_iterator<int>)’

What I understand out of this error, is that there's no definition in set_intersection that accepts Rb_tree_const_iterator<int> as parameter.

Furthermore, I suppose the std::set.begin() method returns an object of such type,

is there a better way to find the intersection of two std::set in C++? Preferably a built-in function?

Thanks a lot!

回答1:

You havent provided an output iterator for set_intersection

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_intersection ( InputIterator1 first1, InputIterator1 last1,
                                InputIterator2 first2, InputIterator2 last2,
                                OutputIterator result );

Fix this by doing something like

...;
set<int> intersect;
set_intersection(s1.begin(),s1.end(),s2.begin(),s2.end(),
                  std::inserter(intersect,intersect.begin()));

You need a std::insert iterator since the set is as of now empty. We cannot use back_ or front_inserter since set doesnt support those operations.

回答2:

Have a look at the sample in the link: http://en.cppreference.com/w/cpp/algorithm/set_intersection

You need another container to store the intersection data, below code suppose to work:

std::vector<int> common_data;
set_intersection(s1.begin(),s1.end(),s2.begin(),s2.end(), std::back_inserter(common_data));

回答3:

See std::set_intersection. You must add an output iterator, where you will store the result:

#include <iterator>
std::vector<int> s3;
set_intersection(s1.begin(),s1.end(),s2.begin(),s2.end(), std::back_inserter(s3));

See Ideone for full listing.

回答4:

Just comment here. I think it is time to add union, intersect operation to the set interface. Let's propose this in the future standards. I have been using the std for a long time, each time I used the set operation I wished the std were better. For some complicated set operation, like intersect, you may simply (easier?) modify the following code:

template <class InputIterator1, class InputIterator2, class OutputIterator>
  OutputIterator set_intersection (InputIterator1 first1, InputIterator1 last1,
                                   InputIterator2 first2, InputIterator2 last2,
                                   OutputIterator result)
{
  while (first1!=last1 && first2!=last2)
  {
    if (*first1<*first2) ++first1;
    else if (*first2<*first1) ++first2;
    else {
      *result = *first1;
      ++result; ++first1; ++first2;
    }
  }
  return result;
}

copied from http://www.cplusplus.com/reference/algorithm/set_intersection/

For example, if your output is a set, you can output.insert(*first1). Furthermore, you function may not be templated.If you code can be shorter than using the std set_intersection function then go ahead with it.

If you want to do a union of two set you can simply setA.insert(setB.begin(), setB.end()); This is much simpler than the set_union method. However, this will not work with vector.

回答5:

The first (well-voted) comment of the accepted answer complains about a missing operator for the existing std set operations.

On one hand, I understand the lack of such operators in the standard library. On the other hand, it is easy to add them (for the personal joy) if desired. I overloaded

• operator *() for intersection of sets
• operator +() for union of sets.

Sample test-set-ops.cc:

#include <algorithm>
#include <iterator>
#include <set>

template <class T, class CMP = std::less<T>, class ALLOC = std::allocator<T> >
std::set<T, CMP, ALLOC> operator * (
  const std::set<T, CMP, ALLOC> &s1, const std::set<T, CMP, ALLOC> &s2)
{
  std::set<T, CMP, ALLOC> s;
  std::set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(),
    std::inserter(s, s.begin()));
  return s;
}

template <class T, class CMP = std::less<T>, class ALLOC = std::allocator<T> >
std::set<T, CMP, ALLOC> operator + (
  const std::set<T, CMP, ALLOC> &s1, const std::set<T, CMP, ALLOC> &s2)
{
  std::set<T, CMP, ALLOC> s;
  std::set_union(s1.begin(), s1.end(), s2.begin(), s2.end(),
    std::inserter(s, s.begin()));
  return s;
}

// sample code to check them out:

#include <iostream>

using namespace std;

template <class T>
ostream& operator << (ostream &out, const set<T> &values)
{
  const char *sep = " ";
  for (const T &value : values) {
    out << sep << value; sep = ", ";
  }
  return out;
}

int main()
{
  set<int> s1 { 1, 2, 3, 4 };
  cout << "s1: {" << s1 << " }" << endl;
  set<int> s2 { 0, 1, 3, 6 };
  cout << "s2: {" << s2 << " }" << endl;
  cout << "I: {" << s1 * s2 << " }" << endl;
  cout << "U: {" << s1 + s2 << " }" << endl;
  return 0;
}

Compiled and tested:

$ g++ -std=c++11 -o test-set-ops test-set-ops.cc 

$ ./test-set-ops     
s1: { 1, 2, 3, 4 }
s2: { 0, 1, 3, 6 }
I: { 1, 3 }
U: { 0, 1, 2, 3, 4, 6 }

$ 

What I don't like is the copy of return values in the operators. May be, this could be solved using move assignment but this is still beyond my skills.

Due to my limited knowledge about these "new fancy" move semantics, I was concerned about the operator returns which might cause copies of the returned sets. Olaf Dietsche pointed out that these concerns are unnecessary as std::set is already equipped with move constructor/assignment.

Although I believed him, I was thinking how to check this out (for something like "self-convincing"). Actually, it is quite easy. As templates has to be provided in source code, you can simply step through with the debugger. Thus, I placed a break point right at the return s; of the operator *() and proceeded with single-step which leaded me immediately into std::set::set(_myt&& _Right): et voilà – the move constructor. Thanks, Olaf, for the (my) enlightment.

For the sake of completeness, I implemented the corresponding assignment operators as well

• operator *=() for "destructive" intersection of sets
• operator +=() for "destructive" union of sets.

Sample test-set-assign-ops.cc:

#include <iterator>
#include <set>

template <class T, class CMP = std::less<T>, class ALLOC = std::allocator<T> >
std::set<T, CMP, ALLOC>& operator *= (
  std::set<T, CMP, ALLOC> &s1, const std::set<T, CMP, ALLOC> &s2)
{
  auto iter1 = s1.begin();
  for (auto iter2 = s2.begin(); iter1 != s1.end() && iter2 != s2.end();) {
    if (*iter1 < *iter2) iter1 = s1.erase(iter1);
    else {
      if (!(*iter2 < *iter1)) ++iter1;
      ++iter2;
    }
  }
  while (iter1 != s1.end()) iter1 = s1.erase(iter1);
  return s1;
}

template <class T, class CMP = std::less<T>, class ALLOC = std::allocator<T> >
std::set<T, CMP, ALLOC>& operator += (
  std::set<T, CMP, ALLOC> &s1, const std::set<T, CMP, ALLOC> &s2)
{
  s1.insert(s2.begin(), s2.end());
  return s1;
}

// sample code to check them out:

#include <iostream>

using namespace std;

template <class T>
ostream& operator << (ostream &out, const set<T> &values)
{
  const char *sep = " ";
  for (const T &value : values) {
    out << sep << value; sep = ", ";
  }
  return out;
}

int main()
{
  set<int> s1 { 1, 2, 3, 4 };
  cout << "s1: {" << s1 << " }" << endl;
  set<int> s2 { 0, 1, 3, 6 };
  cout << "s2: {" << s2 << " }" << endl;
  set<int> s1I = s1;
  s1I *= s2;
  cout << "s1I: {" << s1I << " }" << endl;
  set<int> s2I = s2;
  s2I *= s1;
  cout << "s2I: {" << s2I << " }" << endl;
  set<int> s1U = s1;
  s1U += s2;
  cout << "s1U: {" << s1U << " }" << endl;
  set<int> s2U = s2;
  s2U += s1;
  cout << "s2U: {" << s2U << " }" << endl;
  return 0;
}

Compiled and tested:

$ g++ -std=c++11 -o test-set-assign-ops test-set-assign-ops.cc 

$ ./test-set-assign-ops
s1: { 1, 2, 3, 4 }
s2: { 0, 1, 3, 6 }
s1I: { 1, 3 }
s2I: { 1, 3 }
s1U: { 0, 1, 2, 3, 4, 6 }
s2U: { 0, 1, 2, 3, 4, 6 }

$