c++ - 将 lower_bound/upper_bound 与 2 种不同类型一起使用

Question

我有一个小的工作代码，用于查找使用特殊比较方法的一系列项目。但是当我尝试用 lower_bound() 重写它时和 upper_bound()功能，我得到一个奇怪的错误。我写了一个小代码来显示我的问题。这是代码:

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

如您所见，比较函数使用 sa 的关键字和值用于比较决定的数组。 standard说:

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.

我的比较函数有 int第一个参数的类型(因为数组的 vector<int>)和 string对于第二个参数类型(作为关键字的类型)。但我不知道为什么会出现以下错误:

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&’

我是不是漏掉了一些非常明显的东西？因为编译器似乎在寻找 string作为比较函数的第一个参数。

Answer 1

你的问题是 std::uppper_bound 要求 cmp 是签名

bool(T, decltype(*Iterator))

std::lower_bound 有相反的要求并且想要

bool(decltype(*Iterator), T)

因此您不能对两个函数使用同一个比较器。还有其他方法可以修改代码，但只需添加第二个比较器，如

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;

允许代码编译。