如何找到两个性病的交集::在C ++中设置？(how to find the intersectio

2019-07-03 22:40发布

站内文章 / 前沿技术
38 0 0

我一直在试图找到两个STD之间的交叉::在C ++中设置的，但我不断收到一个错误。

我创建了一个小样本检验这种

#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()方法返回这种类型的对象，

有没有更好的办法找到两只路口std::set在C ++？ 最好内置的功能？

非常感谢！

Answer 1:

您还没有提供一个输出迭代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()));

你需要std::insert迭代器，因为该组是现在空的。 我们不能用back_或front_inserter自组犯规支持这些行动。



Answer 2:

看一看在链接样本： 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));


Answer 3:

见的std :: set_intersection 。 您必须添加一个输出迭代器，在这里您将存储结果： 

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

见Ideone的完整列表。



Answer 4:

只是在这里评论。 我觉得是时候添加的结合，交叉运行到设定界面。 我们提出这在未来的标准。 我一直在使用STD很长一段时间，我用我祝愿STD设置操作比较好各一次。 对于一些复杂的设置操作，如相交，你可以简单地（？更容易）修改下面的代码： 

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/

例如，如果你的输出是一组，你可以output.insert（* first1）。 此外，您功能可能无法templated.If你的代码可以比使用则STD set_intersection功能，用它继续缩短。

如果你想要做两个集的工会，你可以简单地setA.insert（setB.begin（），setB.end（））; 这比set_union方法要简单得多。 但是，这不会与向量工作。



Answer 5:

在第一（精心投票）评论接受的答案抱怨对现有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 }

$

我不喜欢的是返回值在运营商的副本。 可能，这可能使用移动分配来解决，但这仍然是超出了我的能力。

由于我对这些“新奇特”移动语义有限的知识，我担心运营商的回报可能导致返回集的副本。 奥拉夫Dietsche指出，这些担忧是不必要的，因为std::set已经配备了移动构造函数/赋值。

虽然我相信他，我就在想该如何检查出来（对于类似“自我说服”）。 其实，这是很容易的。 作为模板在源代码提供，你可以简单地使用调试器逐步完成。 因此，我放置在一个破发点右return s; 的的operator *()和单步其含铅我马上进入进行std::set::set(_myt&& _Right)等瞧-移动的构造。 谢谢，奥拉夫，为（我的）启示。

为了完整起见，我实现了相应的赋值运算符，以及

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

$


文章来源: how to find the intersection of two std::set in C++?
标签： c++ std stl-algorithm stdset
举报

收藏的人(0)

Ta的文章 更多文章
登录 后发表评论
0条评论
还没有人评论过~