例如,我有两个字符串数组/vector
str1_arr = ["hello","my","dear","world"]
str2_arr = ["dear","my","world","hello"]
单词的位置/顺序不一样。我想知道 str1_arr 中的每个元素是否存在于 str2_arr 中,而不是真正关心它在容器中的位置。
讨论很少here和 here但答案可以追溯到 2011 年。鉴于 c++ 已经取得了很大进步,想知道是否有更好的方法使用 std::algorithms 来完成它
谢谢
最佳答案
更新
好吧,这是一个非修改版本和一个修改版本。 Al tough sorting and copying 看起来工作量很大,最复杂的是排序的log(n) * n,而include也就是4 * n,再加上一些线性的ns,比n^2少了很多. (用 n 来近似两个范围的大小/距离,这只是较大范围的大小)
因此对于大 O 表示法,此解决方案的复杂度为 O(n *log(n)) 而不是原始 for 或 std::is_permutation
的 O(n^2) (这在结果中也是错误的)。
但我想知道,它仍然是复杂度的一个相当高的常数因子,所以我计算了:
即使是最坏的情况,也就是复制 2 n,排序 2(log(n) * n) 和包含 2(2n),也小于天真的解决方案的 n^2,因为大小为 14 elements 的容器.
#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";
}
关于c++ - 比较两个 std::vectors/arrays 或者通常比较两个 STL 容器,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58538091/