时间戳

首页 > 解决方案 > 查找多个向量之间的公共元素（无整数元素）

c++ - 查找多个向量之间的公共元素（无整数元素）

问题描述

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

理想情况下，该函数将一组向量作为参数（要比较的向量数量可以变化）并返回向量的共同值。我确保每个向量中没有重复项，但可能没有共同元素。

例子：

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

返回的共同值：

a

标签： c++arrays

解决方案

正如理查德在评论中提到的，交集可以很容易地用std::set_intersection(). 前提条件是分类容器。

因此，“集合”set_intersection()可以从数学意义上理解——它不限于std::set。std::vector也可以使用排序。

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

QPair定义了operator<可以使用的类型，如果 和 的类型first也second一样。

由于 OP 没有提到哪些类型是QPaired，我选择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）

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

推荐阅读