Reputation: 9173
I have a small working code for finding a range of items that uses a special compare method. But when I try to rewrite it with lower_bound()
and upper_bound()
function, I get a strange error. I have written a small code to show my problem. Here is the code:
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int main() {
string str = "banana";
string keyword = "ana";
int sa_idx[] = {5, 3, 1, 0, 4, 2};
vector<int> sa(sa_idx, sa_idx + sizeof(sa_idx) / sizeof(int) );
auto cmp = [&str] (const int &a, const string &keyword) -> bool
{
return strncmp(str.c_str() + a, keyword.c_str(), keyword.length()) < 0;
};
cout << (upper_bound(sa.begin(), sa.end(), keyword, cmp) -
lower_bound(sa.begin(), sa.end(), keyword, cmp)) << endl;
return 0;
}
As you see, compare function uses keyword and value of sa
array for compare decision. A standard says:
The type Type1 must be such that an object of type ForwardIt can be dereferenced and then implicitly converted to Type1. The type Type2 must be such that an object of type T can be implicitly converted to Type2.
My compare function has int
type for first argument(because of vector<int>
of array) and string
for the second argument type(as type of keyword). But I don't know why I get following error:
In file included from /usr/include/c++/6/bits/stl_algobase.h:71:0,
from /usr/include/c++/6/bits/char_traits.h:39,
from /usr/include/c++/6/ios:40,
from /usr/include/c++/6/ostream:38,
from /usr/include/c++/6/iostream:39,
from prog.cpp:1:
/usr/include/c++/6/bits/predefined_ops.h: In instantiation of ‘bool __gnu_cxx::__ops::_Val_comp_iter<_Compare>::operator()(_Value&, _Iterator) [with _Value = const std::__cxx11::basic_string<char>; _Iterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = main()::<lambda(const int&, const string&)>]’:
/usr/include/c++/6/bits/stl_algo.h:2049:14: required from ‘_ForwardIterator std::__upper_bound(_ForwardIterator, _ForwardIterator, const _Tp&, _Compare) [with _ForwardIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Tp = std::__cxx11::basic_string<char>; _Compare = __gnu_cxx::__ops::_Val_comp_iter<main()::<lambda(const int&, const string&)> >]’
/usr/include/c++/6/bits/stl_algo.h:2114:32: required from ‘_FIter std::upper_bound(_FIter, _FIter, const _Tp&, _Compare) [with _FIter = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Tp = std::__cxx11::basic_string<char>; _Compare = main()::<lambda(const int&, const string&)>]’
prog.cpp:19:57: required from here
/usr/include/c++/6/bits/predefined_ops.h:173:11: error: no match for call to ‘(main()::<lambda(const int&, const string&)>) (const std::__cxx11::basic_string<char>&, int&)’
{ return bool(_M_comp(__val, *__it)); }
^~~~~~~~~~~~~~~~~~~~~~~~~~~
prog.cpp:14:61: note: candidate: main()::<lambda(const int&, const string&)>
auto cmp = [&str] (const int &a, const string &keyword) -> bool
^~~~
prog.cpp:14:61: note: no known conversion for argument 1 from ‘const std::__cxx11::basic_string<char>’ to ‘const int&’
Have I missed something super obvious? Because it seems compiler looks for string
as first argument of compare function.
Upvotes: 3
Views: 1320
Reputation: 181027
Your problem here is that std::uppper_bound
requires the cmp
be of the signature
bool(T, decltype(*Iterator))
std::lower_bound
has the opposite requirement though and wants
bool(decltype(*Iterator), T)
so you can't use the same comparator with both functions. There are other ways to modify the code but just adding a second comparator like
auto cmp1 = [&str](const string &keyword, const int &a) -> bool
{
return strncmp(keyword.c_str(), str.c_str() + a, keyword.length()) < 0;
};
auto cmp2 = [&str] (const int &a, const string &keyword) -> bool
{
return strncmp(str.c_str() + a, keyword.c_str(), keyword.length()) < 0;
};
cout << (upper_bound(sa.begin(), sa.end(), keyword, cmp1) -
lower_bound(sa.begin(), sa.end(), keyword, cmp2)) << endl;
allows the code to compile.
Upvotes: 9