是否有标准算法来检查容器 A 是否是容器 B 的超集？

Question

我正在寻找一种标准算法，给定两个容器 A 和 B，两者都没有重复项，如果 A 的所有元素与 B 的元素比较为 true，则返回 true。我使用了 std::all_of 使用谓词检查另一个容器中的成员资格，但我想知道是否有更优雅的解决方案。

Answer 1

是否有STL算法来检查两个容器是否包含相同的元素？

我想你的意思是“比较相等的元素”。一个对象只能是一个容器的元素（至少在所有标准容器的情况下）。

我正在寻找一个 std:: 算法，给定两个容器 A 和 B，如果 A 的所有元素都包含在 B 中，则返回 true。

这个问题与标题中的问题不同。

对于第一个，有std::is_permutation。然而，对于某些容器类型，有更有效的算法。例如，如果容器已排序（例如 std::set），那么您可以简单地比较是否相等。

对于第二个，没有通用算法。如果容器已排序，则可以使用 std::includes。否则，您可以编写一个先排序，然后使用 std::includes 的算法。

我使用了 std::all_of 和一个谓词来检查另一个容器中的成员资格

如果较大的容器具有快速查找（例如无序集），那么这个解决方案很好。

Answer 2

std::includes 会在两个容器都已排序的情况下执行此操作。

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

int main() {

  std::vector< int > A = {1, 2, 3, 4, 7};
  std::vector< int > B = { 1, 2 ,3};
  std::vector< int > C = { 3, 4, 5};

  bool BinA = std::includes(A.begin(), A.end(), B.begin(), B.end());
  bool CinA = std::includes(A.begin(), A.end(), C.begin(), C.end());
  std::cout<< "B in A = " << BinA <<std::endl;
  std::cout<< "C in A = " << CinA <<std::endl;
}

https://godbolt.org/z/dnoM4xPbY

如果它们没有排序，你可以' t/不想对它们进行排序，那么我相信 all_of 方法尽可能高效。
如果性能至关重要，我认为首先排序会更有效，但您应该检查您的特定情况。