验证多个向量中是否有共同成员的最佳方法是什么？向量不一定具有相等的大小，它们可能包含自定义数据（例如包含两个代表2D坐标的整数的结构）。
例如：
vec1 = {(1,2); (3,1); (2,2)};
vec2 = {(3,4); (1,2)};
如何验证两个向量是否具有共同成员？
请注意，我正在尝试避免无缺的方法，例如浏览所有元素并检查相等的数据。
对于非平凡数据集，最有效的方法可能是对两个向量进行排序，然后使用std :: set_intersection函数定义在中，如下所示：
#include <vector>
#include <algorithm>
using namespace std;
typedef vector<pair<int, int>> tPointVector;
tPointVector vec1 {{1,2}, {3,1}, {2,2}};
tPointVector vec2 {{3,4}, {1,2}};
std::sort(begin(vec1), end(vec1));
std::sort(begin(vec2), end(vec2));
tPointVector vec3;
vec3.reserve(std::min(vec1.size(), vec2.size()));
set_intersection(begin(vec1), end(vec1), begin(vec2), end(vec2), back_inserter(vec3));
，如果您不需要知道哪些元素不同，而只有共同元素的数量，则可以通过非标准算法获得更好的性能，因为这样您可以避免创建共同元素的新副本。
无论如何，在我看来，通过对两个容器进行排序，将为您提供最佳的性能，其中包括几十个元素。
这是一个尝试编写算法的尝试，该算法只为您提供匹配元素的计数（未经测试）：
auto it1 = begin(vec1);
auto it2 = begin(vec2);
const auto end1 = end(vec1);
const auto end2 = end(vec2);
sort(it1, end1);
sort(it2, end2);
size_t numCommonElements = 0;
while (it1 != end1 && it2 != end2) {
bool oneIsSmaller = *it1 < *it2;
if (oneIsSmaller) {
it1 = lower_bound(it1, end1, *it2);
} else {
bool twoIsSmaller = *it2 < *it1;
if (twoIsSmaller) {
it2 = lower_bound(it2, end2, *it1);
} else {
// none of the elements is smaller than the other
// so it's a match
++it1;
++it2;
++numCommonElements;
}
}
}
请注意，我正在尝试避免无缺的方法，例如浏览所有元素并检查相等的数据。
您需要至少浏览所有元素一次，我认为您暗示您不想检查所有组合。确实您不想这样做：
对于VEC1中的所有元素，请仔细阅读整个VEC2以检查该元素是否在此处。如果您的向量有大量元素，这将不会有效。
如果您喜欢线性时间解决方案，并且不介意使用额外的内存是您可以做的：
您需要一个哈希功能才能将元素插入unordered_map或unordered_set中 请参阅https://stackoverflow.com/a/13486174/2502814
// next_permutation example
#include <iostream> // std::cout
#include <unordered_set> // std::unordered_set
#include <vector> // std::vector
using namespace std;
namespace std {
template <>
struct hash<pair<int, int>>
{
typedef pair<int, int> argument_type;
typedef std::size_t result_type;
result_type operator()(const pair<int, int> & t) const
{
std::hash<int> int_hash;
return int_hash(t.first + 6495227 * t.second);
}
};
}
int main () {
vector<pair<int, int>> vec1 {{1,2}, {3,1}, {2,2}};
vector<pair<int, int>> vec2 {{3,4}, {1,2}};
// Copy all elements from vec2 into an unordered_set
unordered_set<pair<int, int>> in_vec2;
in_vec2.insert(vec2.begin(),vec2.end());
// Traverse vec1 and check if elements are here
for (auto& e : vec1)
{
if(in_vec2.find(e) != in_vec2.end()) // Searching in an unordered_set is faster than going through all elements of vec2 when vec2 is big.
{
//Here are the elements in common:
cout << "{" << e.first << "," << e.second << "} is in common!" << endl;
}
}
return 0;
}
输出：{1,2}共有！
您可以执行此操作，也可以将VEC1的所有元素复制到unordered_set中，然后将VEC2 traverse vec2复制。根据VEC1和VEC2的尺寸，一种解决方案可能比另一个解决方案更快。请记住，选择较小的向量将其插入Unordered_set也意味着您将使用较少的额外内存。
我相信您使用2D树在2个dimenstions中搜索。您指定的问题的最佳算法将属于几何算法类别。也许此链接对您有用：http：//www.cs.princeton.edu/courses/archive/fall05/cos226/lectures/geosearch.pdf。