c++ - 比较函数不适用于 equal_range

Question

我有以下代码，将结构保存到 boost::ptr_vector 容器中。我现在正在尝试通过 equal_range 为这个容器编写一个简单的搜索函数。我选择该函数是因为我想要一个指向序列元素的指针(如果找到)，或指向下限和上限的指针(如果未找到元素):

struct COMP
{
    bool operator()(const merkle_tree_node &LHS, const std::string& query){
        return (LHS.word < query);
    }
};

std::pair<boost::ptr_vector<merkle_tree_node>::iterator,
      boost::ptr_vector<merkle_tree_node>::iterator> 
search_tree(merkle_tree vWords, std::basic_string<char> query, size_t length)
{ 
    return std::equal_range(vWords.begin(), vWords.begin()+(length-1),
         query, 
         COMP());
}

我通过我的主要功能调用它:

std::basic_string<char> QUERY = "SOMETHING";
std::pair<boost::ptr_vector<merkle_tree_node>::iterator,
          boost::ptr_vector<merkle_tree_node>::iterator> result = 
    search_tree(vWords, QUERY, vWords.size());

但是，我遇到了以下似乎无法克服的编译错误:

    In file included from /usr/include/c++/4.8/algorithm:62:0,
                     from vf-merkle.cpp:3:
    /usr/include/c++/4.8/bits/stl_algo.h: In instantiation of ‘std::pair<_FIter, _FIter> std::equal_range(_FIter, _FIter, const _Tp&, _Compare) [with _FIter = boost::void_ptr_iterator<__gnu_cxx::__normal_iterator<void**, std::vector<void*, std::allocator<void*> > >, merkle_tree_node>; _Tp = std::basic_string<char>; _Compare = COMP]’:
    vf-merkle.cpp:111:10:   required from here
    /usr/include/c++/4.8/bits/stl_algo.h:2668:36: error: no match for call to ‘(COMP) (const std::basic_string<char>&, merkle_tree_node&)’
        else if (__comp(__val, *__middle))
                                        ^
    vf-merkle.cpp:98:8: note: candidate is:
     struct COMP
            ^
    vf-merkle.cpp:100:7: note: bool COMP::operator()(const merkle_tree_node&, const string&)
      bool operator()(const merkle_tree_node &LHS, const std::string& query){
           ^
    vf-merkle.cpp:100:7: note:   no known conversion for argument 1 from ‘const std::basic_string<char>’ to ‘const merkle_tree_node&’

有什么想法吗？

Answer 1

简短的回答是，您需要为参数的不同顺序提供两种重载

struct COMP
{
    bool operator()(const merkle_tree_node &LHS, const std::string& query){
        return (LHS.word < query);
    }

   bool operator()(const std::string& query,const merkle_tree_node &RHS){
        return (query < RHS.word);
    }
};

您需要这样做，因为您调用 std::equal_range 时使用类型为 string 的第三个参数，而迭代器指向 merkle_tree_node。这种混合比较情况需要您提供额外的重载来处理 string 是第一个参数或 string 是第二个参数的情况。为了完整起见，您可能需要考虑添加它是 merkle_tree_node 的两个实例的情况。