C++ std:search behavior or restriction

Question

I'm studying std::search (to determine if duplicates exist between std::set), but I don't understand the output.

#include <iostream>
#include <set>
#include <algorithm>
using namespace std;

int main()
{
    set<int> a{9,10,11,12};
    set<int> b{11,12,13};
    auto it = search(a.begin(), a.end(), b.begin(), b.end());

    if (it != a.end())
        cout << "Common is " << *it << endl;
    else
        cout << "Oops " << *it << endl;
    return 0;
}

So I expect *it would be 11, but it turns out it!=a.end() fails and *it prints some irrelevant value (4 here), and I think I might have messed up.

However, when I assign b to {11,12}, everything works as expected and printed out "Common is 11". After some more tries, I can no longer read the pattern.

I don't know if std::search have this kind of restriction, and I can't find answers to it. I'm so confused.

Answer 1

If you read the documentation, you'll notice that search() is looking for an entire subsequence.

So here:

set<int> a{9,10,11,12};
set<int> b{11,12,13};
auto it = search(a.begin(), a.end(), b.begin(), b.end());

we're not looking for any of 11, 12, 13 in a. We're looking for all of them, in order. Since they're not all present in order (a doesn't have 13), you get a.end(). Note that dereferencing the end iterator, as you're doing in your Oops case, is undefined behavior.

However, when I assign b to {11,12}, everything works as expected

Yes, because now that entire sequence appears in a.

---

If you want to find any of the elements, just use find_if:

auto it = find_if(a.begin(), a.end(), [&](int i){ return b.count(i); });