用STL替换循环中的循环以在两个向量中查找匹配

Question

给定结构：

struct bob
{
    int a {1};
    std::string b{"bob"};
};

std::vector<bob> list1{{1, "a"}, {2, "b"}, {3, "c"}};
std::vector<bob> list2{{1, "x"}, {2, "b"}, {3, "x"}};

我想查找是否存在匹配项。执行此操作的经典方法是循环中的循环 - 类似于：

    for (const auto &item1 : list1)
    {
        for (const auto &item2 : list2)
        {
            std::cout << "loop check: " << item1.a << "," << item1.b << " == "<< item2.a << "," << item2.b << "\n";
            if (item2.a == item1.a && 
                item2.b == item1.b)
            {
                return true;
            }
        }
    }

clangtidy 现代化功能抱怨使用原始循环不是前进的方向，因此我已使用以下方法转换为 STL std::any_of：

    return std::any_of(
        list1.begin(),
        list1.end(),
        [&](const auto &item1)
        {
            return std::any_of(
                list2.begin(),
                list2.end(),
                [&](const auto &item2) {
                    std::cout << "stl check: " << item1.a << "," << item1.b << " == "<< item2.a << "," << item2.b << "\n";
                    return item2.a == item1.a &&
                           item2.b == item1.b;
                });
        });

但我不禁认为这更难阅读并且代码更多等等......

是否有更好的安排或不同的算法能够以更清晰/更具表现力的方式做到这一点？

这是完整的工作示例：https ://godbolt.org/z/e8MYYK5G4

注意：正在使用c++17

Answer 1

我将从定义 的比较开始struct bob，因此其余代码不需要处理其内部细节。如果您使用的是 C++20 或更高版本，则可以使用 spaceship 运算符来执行此操作。否则，您可以改为定义operator<。

struct bob {
    // existing contents of bob ...

    // C++20 or newer:
    // auto operator<=>(bob const &) const = default;

    // C++17 or older:
    bool operator<(bob const &other) const {
        if (a == other.a) return b < other.b;
        return a < other.a;
    }
};

然后我们想要确定一个集合的任何元素是否包含在另一个集合中。就像@chrysante一样，我会先排序然后搜索。但我会使用二分搜索而不是线性搜索。

标准库实际上包含三个不同的函数模板来进行二分搜索。大多数时候，我们想要upper_bound或lower_bound尝试在集合中查找元素的特定位置。但在这种情况下，我们并不关心具体位置——我们只需要一个布尔结果来告诉我们它是否存在。对我们来说幸运的是，事实正是如此std::binary_search。

template <class T, class U>
bool intersects(T const &a, U b) {
    std::sort(std::begin(b), std::end(b));

    return std::any_of(std::begin(a), std::end(a),
        [&](auto const &x) { return std::binary_search(std::begin(b), std::end(b), x); });
}

目前我只定义了一个版本，用于对一个输入的副本进行排序。如果您可以修改原始内容，请改为b通过引用传递。

不过，根据集合的大小以及预期的相交元素数量，这可能不是最有效的方法。std::set_intersection要求我们对两个输入进行排序，然后并行遍历两个输入以找到相交的项。上面的算法的复杂度为 O(M log N)，其中 M 和 N 是两个集合的大小。

std::set_intersection复杂度为 O(M + N)，但还要继续搜索，以找到两个集合之间匹配的所有元素。因此，在任何给定情况下，确切地说哪种速度更快是很难确定的。

一旦我们有了这些，让我们尝试一些测试——一个应该产生积极的结果，另一个应该产生消极的结果：

int main() { 
    std::vector<bob> list1{{1, "a"}, {2, "b"}, {3, "c"}};
    std::vector<bob> list2{{1, "x"}, {2, "b"}, {3, "x"}};
    std::vector<bob> list3{{1, "I don't think so"}, {5, "nope"}, { 17, "no way"}};

    std::cout << "1 and 2 intersect? " << std::boolalpha << intersects(list1, list2) << "\n";
    std::cout << "2 and 3 intersect? " << std::boolalpha << intersects(list2, list3) << "\n";

}

至少对我来说，这会产生我所期望的结果：

1 and 2 intersect? true
2 and 3 intersect? false

Live on Godbolt