c++ - 使用 STL 在两个排序范围内查找第一个匹配项

Question

我有两个排序范围。我想找到范围中的第一个匹配元素(如果有的话)。

cppreference 中的操作(在排序范围内) 部分似乎没有包含我想要的内容。 std::set_intersection很接近，但它找到所有匹配的元素。

当然我可以编写自己的模板算法，但是编写符合 STL 质量标准的算法有点麻烦。

另一种选择是以某种方式适应 std::set_intersection通过使用特殊的输出迭代器。我们可以这样写

template <typename T>
struct OneElementIter
{
    T &operator*() {
        if (full) return dummy;
        full = true;
        return t;
    }
    void operator++() {}
    bool full = false;
    T t;
    T dummy;
};

并将其用于 std::set_intersection 的输出迭代器.这将浪费精力扫描超过第一个匹配项的输入范围，但它仍然是 O(n) 复杂度。

但是，编写 STL 质量的迭代器也是一件苦差事。我不知道 <iterator> 中的任何内容无需编写新的迭代器类即可完成此操作。

如果 STL 容器库包含一个固定大小的 FIFO 队列，其 push_back满时是空操作，那么我们可以使用 std::back_inserter在大小为 1 的队列上作为输出迭代器。但是不存在这样的容器。

有没有什么优雅的方法可以使用我缺少的现有 STL 工具来做到这一点？

Answer 1

这在技术上不能回答问题，因为您需要一个 STL 解决方案。然而，range-v3 一直是 C++20 中对 STL 进行大量添加的基础，因此我希望该解决方案能够在未来的版本中运行，甚至希望在 C++23 中也能运行。

auto first = *std::begin(rv::set_intersection(vec_1, vec_2) | rv::take(1));

其中 rv 只是 ranges::views 的命名空间别名。

在此解决方案中，rv::set_intersection 只是 std::set_intersection 的惰性版本。由于只有第一个元素是rv::taken，其余匹配的元素不计算，满足你的要求。事实上，vec_1 和/或 vec_2 甚至可以是无限范围。

唯一的要求是至少有一个匹配元素，否则它会调用未定义的行为。

这是一个 demo .