c++ 如何找到两个STL集合的交集？

wlsrxk51  于 2022-11-27  发布在  其他
关注(0)|答案(6)|浏览(155)

我一直试图在C++中找到两个std：：set之间的交集，但我总是得到一个错误。
我为此创建了一个小样本测试

#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;
}

后一个程序不生成任何输出，但我希望有一个新的集合（我们称之为s3），其值如下：

s3 = [ 1 , 3 ]

相反，我得到的是错误：

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>)’

我从这个错误中了解到，set_intersection中没有接受Rb_tree_const_iterator<int>作为参数的定义。
此外，我假设std::set.begin()方法返回这样一个类型的对象，
在C++中有没有更好的方法来求两个std::set的交集？最好是内置函数？

c++

6条答案

按热度按时间
z6psavjg

z6psavjg1#

您尚未提供set_intersection的输出迭代器

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

通过执行以下操作来解决此问题

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

因为set现在是空的，所以你需要一个std::insert迭代器。我们不能使用std::back_inserter或std::front_inserter，因为set不支持这些操作。

赞(0）分享  回复(0）举报  2022-11-27
z9smfwbn

z9smfwbn2#

请看链接中的示例：http://en.cppreference.com/w/cpp/algorithm/set_intersection
您需要另一个容器来存储交集数据，下面的代码假设可以工作：

std::vector<int> common_data;
set_intersection(s1.begin(),s1.end(),s2.begin(),s2.end(), std::back_inserter(common_data));
赞(0）分享  回复(0）举报  2022-11-27
b1zrtrql

b1zrtrql3#

请参见std::set_intersection。您必须添加一个输出迭代器，在其中存储结果：

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

完整列表请参见Ideone。

赞(0）分享  回复(0）举报  2022-11-27
swvgeqrz

swvgeqrz4#

accepted answer的第一个（投票通过的）注解抱怨现有的std集合操作缺少一个操作符。
一方面，我理解在标准库中缺少这样的操作符。另一方面，如果需要的话，添加它们很容易（为了个人的快乐）。

  • operator *()表示集合的交集
  • operator +()表示集合的并集。

样品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;
}

编译和测试：

$ 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 }

$

我不喜欢的是操作符中返回值的复制。也许，这可以用移动赋值来解决，但这仍然超出了我的技能。
由于我对这些“新的花式”移动语义的知识有限，我担心操作符返回可能导致返回集合的副本。Olaf Dietsche指出这些担心是不必要的，因为std::set已经配备了移动构造函数/赋值。
虽然我相信了他的话，但我在想如何检验一下（比如“自我说服”）。实际上，这很容易。因为模板必须在源代码中提供，所以你可以简单地用调试器单步调试。因此，我在operator *()的return s;处放置了一个断点，并继续单步调试，这将我立即引导到std::set::set(_myt&& _Right)：谢谢Olaf给我的启发。
为了完整性，我还实现了相应的赋值操作符

  • operator *=()表示集合的“破坏性”交集
  • operator +=()表示集合的“破坏性”并集。

样品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;
}

编译和测试：

$ 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 }

$
赞(0）分享  回复(0）举报  2022-11-27
tct7dpnv

tct7dpnv5#

在这里评论一下。我认为是时候在集合接口中增加并集和交集操作了。让我们在未来的标准中提出这个建议。我已经使用标准很长时间了，每次使用集合操作我都希望标准更好。对于一些复杂的集合操作，比如交集，你可以简单地（更容易？）修改下面的代码：

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;
}

复制自http://www.cplusplus.com/reference/algorithm/set_intersection/
例如，如果你的输出是一个集合，你可以输出.insert（* first 1）。此外，你的函数可能不是模板化的。如果你的代码可以比使用std set_intersection函数更短，那么就继续使用它。
如果你想做两个集合的并集，你可以简单地setA.insert（setB.开始（），setB.end（））;这比set_union方法要简单得多。但是，这不适用于vector。

赞(0）分享  回复(0）举报  2022-11-27
e5njpo68

e5njpo686#

为保持界面简单，您可以复制/粘贴此模板：

template<typename Type>
auto setIntersection(set<Type> set0, set<Type> set1)
{
    set<Type> intersection;
    for (auto value : set0)
        if (set1.find(value) != set1.end())
            intersection.insert(value);
    return intersection; 
}

那么在你的情况下

intersection = setIntersection<int>(s1, s2);

或

intersection = setIntersection(s1, s2);
赞(0）分享  回复(0）举报  2022-11-27
我来回答

相关问题

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新问答

    更多
    • 蜀ICP备2022004421号-2 NULL123 https://www.null123.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com