Find first match in two sorted ranges using STL

user_805659 0
Viewed 67

I have two sorted ranges. I would like to find the first matching element in the ranges, if any.

The operations (on sorted ranges) sections in cppreference do not appear to contain exactly what I want. std::set_intersection is close, but it finds all the matching elements.

Of course I could write my own template algorithm, but it's a bit of a chore to write algorithms up to the STL quality standard.

Another option is to somehow adapt std::set_intersection by using a special output iterator. We could write something like

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

and use it for the output iterator of std::set_intersection. This will waste effort scanning the input ranges past the first match, but it's still O(n) complexity.

However, writing STL-quality iterators is a chore too. I'm not aware of anything in <iterator> that can do this without writing a new iterator class.

If the STL container library included a fixed-size FIFO queue whose push_back is a no-op when full, then we could use a std::back_inserter on a queue of size 1 as the output iterator. But no such container exists.

Is there any elegant way to do this with existing STL tools I'm missing?

std stl c++
1 Answers

This doesn't technically answer the question since you want an STL solution. However, range-v3 has been the basis for a lot of the additions to the STL in C++20, and so I expect this solution to work in a future version, hopefully even in C++23.

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

where rv is just a namespace alias for ranges::views.

In this solution rv::set_intersection is just the lazy version of std::set_intersection. Since only the first element is rv::taken, the remaining matching elements are not computed, which satisfies your requirements. In fact, vec_1 and/or vec_2 can even be infinite ranges.

The only requirement is that there be at least one matching element, or else it invokes undefined behavior.

Here's a demo.

user_83728530
Related