代码之家 › 专栏 › 技术社区 › Afshin

对两种不同类型使用下界/上界

c++

Afshin · 技术社区 · 6 年前

我有一个小的工作代码,用于查找一系列使用特殊比较方法的项。但是当我试着用 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;
}

如您所见,compare函数使用关键字和 sa 比较决策的数组。A standard 说:

类型Type1必须使类型为ForwardIt的对象必须使T类型的对象可以隐式转换为类型2。

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

我错过了什么特别明显的东西吗?因为编译器似乎在寻找 一串

1 回复 | 直到 6 年前

NathanOliver 6 年前

你的问题是 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;

允许代码编译。