c++ - 检查 vector C++ 中的公共(public)成员

Question

验证多个 vector 中是否存在公共(public)成员的最佳方法是什么？ vector 不一定大小相等，它们可能包含自定义数据(例如包含表示二维坐标的两个整数的结构)。

例如:

vec1 = {(1,2); (3,1); (2,2)};
vec2 = {(3,4); (1,2)};

如何验证两个 vector 是否有共同的成员？

请注意，我试图避免低效的方法，例如遍历所有元素并检查相等的数据。

Answer 1

对于非平凡的数据集，最有效的方法可能是对两个 vector 进行排序，然后使用 中定义的 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));

如果您不需要知道哪些元素不同，而只知道公共(public)元素的数量，则使用非标准算法可能会获得更好的性能，因为这样您就可以避免创建公共(public)元素的新拷贝。
无论如何，在我看来，从对两个容器进行排序开始将为您提供具有几十个元素的数据集的最佳性能。

这里尝试编写一个算法，只为您提供匹配元素的计数(未经测试):

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;
        }
    }
}