hsinewu hsinewu - 2 months ago 14
C++ Question

C++ std:search behavior or restriction

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

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