比较两个std::矢量/阵列，或者通常比较两个stl连续器

Question

我有两个字符串数组/向量，例如

str1_arr = ["hello","my","dear","world"]
str2_arr = ["dear","my","world","hello"]

单词的位置/顺序不一样。我想知道str1_arr中的每个元素是否都存在于str2_arr中，而不是真正关心它在容器中的位置。

这里和这里很少有讨论，但答案要追溯到2011年。考虑到c++已经取得了很大的进步，想知道是否有更好的方法可以使用std:：算法来实现这一点

感谢

Answer 1

更新

这是一个非修改版本和一个修改版本。Al艰难的排序和复制似乎是一项艰巨的工作，排序的最高复杂度是log(n(*n，包括的只有4*n，加上一些线性ns，这比n^2小得多。(用n近似两个范围的大小/距离，这只是较大范围的大小(

因此，对于大O表示法，该解在O(n*log(n((中，而不是解或std::is_permutation的天真的O(n^2(中(这在结果中也是错误的(。

但我想知道，它仍然是一个相当高的复杂度常数因子，所以我计算了一下：

对于一个只有14个元素大小的容器，即使是最坏的情况，即复制有2n，排序有2(log(n(*n(，包含有2(2n(，也小于原始解决方案的n^2。

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

template<typename Iterator1, typename Iterator2>
bool is_included_general_modifying(Iterator1 begin1, Iterator1 end1, Iterator2 begin2, Iterator2 end2) {
std::sort(begin1, end1);
std::sort(begin2, end2);
return std::includes(begin2, end2, begin1, end1);
}
template<typename Iterator1, typename Iterator2>
bool is_included_general(Iterator1 begin1, Iterator1 end1, Iterator2 begin2, Iterator2 end2) {
const auto first_range_is_sorted = std::is_sorted(begin1, end1);
const auto second_range_is_sorted = std::is_sorted(begin2, end2);
if (first_range_is_sorted && second_range_is_sorted) {
return std::includes(begin2, end2, begin1, end1);
} else if (first_range_is_sorted) {
auto second_range_copy = std::vector<typename std::iterator_traits<Iterator2>::value_type>(begin2, end2);
auto new_begin2 = second_range_copy.begin(), new_end2 = second_range_copy.end();
std::sort(new_begin2, new_end2);
return std::includes(new_begin2, new_end2, begin1, end1);
} else if (second_range_is_sorted) {
auto first_range_copy = std::vector<typename std::iterator_traits<Iterator1>::value_type>(begin1, end1);
auto new_begin1 = first_range_copy.begin(), new_end1 = first_range_copy.end();
std::sort(new_begin1, new_end1);
return std::includes(begin2, end2, new_begin1, new_end1);
}
auto first_range_copy = std::vector<typename std::iterator_traits<Iterator1>::value_type>(begin1, end1);
auto new_begin1 = first_range_copy.begin(), new_end1 = first_range_copy.end();
std::sort(new_begin1, new_end1);
auto second_range_copy = std::vector<typename std::iterator_traits<Iterator2>::value_type>(begin2, end2);
auto new_begin2 = second_range_copy.begin(), new_end2 = second_range_copy.end();
std::sort(new_begin2, new_end2);
return std::includes(new_begin2, new_end2, new_begin1, new_end1);
}
int main() {
std::array<std::string, 4> str1_arr = {"hello", "my", "dear", "world"};
std::vector<std::string> str2_arr = {"additional element", "dear", "my", "world", "hello"};
std::cout << is_included_general(str1_arr.begin(), str1_arr.end(), str2_arr.begin(), str2_arr.end()) << "n";
}

Answer 2

std::vector<std::string> str1_arr{"hello", "my", "dear", "world"};
std::vector<std::string> str2_arr{"dear", "my", "world", "hello"};
assert(std::is_permutation(str1_arr.begin(), str1_arr.end(), 
str2_arr.begin(), str2_arr.end()));

根据C++引用，如果存在使范围[first1, last1)中的元素的排列使得该范围等于范围[first2, last2)，则std::is_permutation(first1, last1, first2, last2)返回true。