查找多个向量之间的公共元素(无整数元素)

Question

是否有一个C++函数可以找到多个向量之间的共同元素？向量元素不是整数(在我的例子中,元素是QPair类型).

该函数理想地具有一组向量作为参数(要比较的向量的数量可以变化)并返回向量的公共值.我确保每个向量中没有重复,但可能没有共同的元素.

例:

vec 1 [a,b]      vec 2 [c,d,a,e,h]     vec 3 [i,j,a]

回报的共同价值:

a

Answer 1

正如理查德在评论中提到的那样,交叉可以轻松完成std::set_intersection().前提条件是分类容器.

因此,set_intersection()可以在数学意义上理解"集合" - 它不限于此std::set.std::vector也可以使用排序.

要排序std::vector,std::sort()可以使用.在这种情况下,前置条件是元素的可能顺序,即为operator<元素类型定义.

QPair定义了一个operator<可以使用的,如果类型first和也可以使用second.

由于OP没有提到这类型QPair编,我选择了std::string和double我的样本isectQPair.cc:

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

#include <QtCore>

int main()
{
  // prepare sample data
  typedef QPair<std::string, double> Pair;
  Pair
    a("Hello", 1.23),
    b("World", 2.34),
    c("Stack", 3.45),
    d("Overflow", 4.56),
    e("C++11", 5.67),
    f("C++14", 6.78),
    g("C++17", 7.89),
    h("C++20", 8.90),
    i("gin hill", 10.1),
    j("scheff", 0.0);
  std::vector<Pair> vec1({ a, b });
  std::vector<Pair> vec2({ c, d, a, e, h });
  std::vector<Pair> vec3({ i, j, a });
  // sort vectors
  std::sort(vec1.begin(), vec1.end());
  std::sort(vec2.begin(), vec2.end());
  std::sort(vec3.begin(), vec3.end());
  // intersect vectors
  std::vector<Pair> isect12;
  std::set_intersection(
    vec1.begin(), vec1.end(), vec2.begin(), vec2.end(),
    std::back_inserter(isect12));
  std::vector<Pair> isect123;
  std::set_intersection(
    isect12.begin(), isect12.end(), vec3.begin(), vec3.end(),
    std::back_inserter(isect123));
  // report
  const size_t n = isect123.size();
  std::cout << "Intersection contains " << n << " elements"
    << (n ? ':' : '.') << '\n';
  for (size_t i = 0; i < n; ++i) {
    const Pair &entry = isect123[i];
    std::cout << (i + 1) << ".: '" << entry.first
      << "', " << entry.second << '\n';
  }
  // done
  return 0;
}

isectQPair.pro:

SOURCES = isectQPair.cc

Qt = core

在Windows 10 上的cygwin上编译和测试:

$ qmake-qt5 isectQPair.pro

$ make

$ ./isectQPair
Intersection contains 1 elements:
1.: 'Hello', 1.23

$

Live Demo on ideone(QPair替换为std::pair)

关于交集的另一个很好的Q/A可以在这里找到:SO:如何在C++中找到两个std :: set的交集？.