CODEWITHSUNDEEP
c++booststd
shblsh
shblsh

Reputation: 81

Comparison function not working for equal_range

I have the following piece of code, which saves structs into a boost::ptr_vector container. I am trying now to write a simple search function for this container via equal_range. I chose that function because I want a pointer to the element of the sequence (if it is found), or pointers to the lower and upper bound (if the element is not found):

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

Which I am calling via my main function as such: 

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

However, I am getting the following compilation error which I just can't seem to overcome:

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

Any ideas?

Upvotes: 0

Views: 817

Answers (2)

Dave S
Dave S

Reputation: 21123

The short answer, is you need to provide both overloads for different orderings of the arguments

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

You need to do this because you are calling std::equal_range with the third argument of type string, while the iterators point to merkle_tree_node. This mixed comparison case requires you to provide additional overloads to handle the case where the string is the first argument, or when the string is the second argument. For completeness, you might want to consider adding the case where it's two instances of merkle_tree_node.

Upvotes: 1

Vlad from Moscow
Vlad from Moscow

Reputation: 311146

You call algorithm std:;equal_range passing to it std:;string as the third argument instead of an iterator, So your using of the algorithm is invalid. Read the description of std::equal_range before using it.

Upvotes: 0

Related Questions