0

I'm getting a compilation error,

required from 'std::pair<std::_Rb_tree_iterator<_Val>, bool> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_insert_unique(_Arg&&) [with _Arg = Solution::EnhancedNode* const&; _Key = Solution::EnhancedNode*; _Val = Solution::EnhancedNode*; _KeyOfValue = std::_Identity<Solution::EnhancedNode*>; _Compare = Solution::EnhancedNodeComparator; _Alloc = std::allocator<Solution::EnhancedNode*>]'

Unfortunately there is no line number, but my removing sections of code, I believe it has something to do with an std::set that I want to apply a custom comparator to:

class EnhancedNode {
public:
    EnhancedNode(TreeNode* node) {
        node_ = node;
        distance_ = numeric_limits<double>::max();
        discarded_ = false;
    }
    TreeNode* node_;
    double distance_;
    bool discarded_;
};
struct EnhancedNodeComparator {
    bool operator() (const EnhancedNode*& a, const EnhancedNode*& b) const {
        return a->distance_ < b->distance_;
    }
};
set<EnhancedNode*, EnhancedNodeComparator> closest_;
set<EnhancedNode*, EnhancedNodeComparator> next_;

Am I doing anything obviously wrong?

Andrew Cheong
  • 29,362
  • 15
  • 90
  • 145

2 Answers2

2

The comparator of std::set should definitely accept references to the const qualified type which is in the set.

What you got wrong is the qualification of the type in the set. It's EnhancedNode*, so qualifying it with const should give EnhancedNode* const. And not const EnhancedNode*.

This is once again a case of leading const being misleading. Change your original comparator, with reference and all, to this:

struct EnhancedNodeComparator {
    bool operator() (EnhancedNode const * const& a, EnhancedNode const * const& b) const {
        return a->distance_ < b->distance_;
    }
};

You can keep the const-qualified pointee, as well. Since C++ explicitly allows it.

The reason that your issue was fixed when you got rid of the reference, is that top-level const is ignored when passing by value. So it didn't matter the the pointer your function received as an argument wasn't const qualified. It was just a copy of the original.

StoryTeller - Unslander Monica
  • 165,132
  • 21
  • 377
  • 458
0

While creating a Minimal, Complete, VerifiableTM example, I was able to solve my problem. I'm posting it anyway because Google surprisingly had zero hits for the first portions of my error in quotes.

Turns out I didn't need the &s in

struct EnhancedNodeComparator {
    bool operator() (const EnhancedNode*& a, const EnhancedNode*& b) const {

I found this out by compiling on a different compiler, http://cpp.sh,

#include <limits>
#include <set>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class EnhancedNode {
public:
    EnhancedNode(TreeNode* node) {
        node_ = node;
        distance_ = numeric_limits<double>::max();
        discarded_ = false;
    }
    TreeNode* node_;
    double distance_;
    bool discarded_;
};
struct EnhancedNodeComparator {
    bool operator() (const EnhancedNode*& a, const EnhancedNode*& b) const {
        return a->distance_ < b->distance_;
    }
};

int main()
{
    set<EnhancedNode*, EnhancedNodeComparator> closest_;
    closest_.insert(new EnhancedNode(new TreeNode(1)));
    return 0;
}

and getting a more helpful error:

In file included from /usr/include/c++/4.9/set:60:0,
                 from 3:
/usr/include/c++/4.9/bits/stl_tree.h: In instantiation of 'std::pair<std::_Rb_tree_node_base*, std::_Rb_tree_node_base*> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_get_insert_unique_pos(const key_type&) [with _Key = EnhancedNode*; _Val = EnhancedNode*; _KeyOfValue = std::_Identity<EnhancedNode*>; _Compare = EnhancedNodeComparator; _Alloc = std::allocator<EnhancedNode*>; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::key_type = EnhancedNode*]':
/usr/include/c++/4.9/bits/stl_tree.h:1498:47:   required from 'std::pair<std::_Rb_tree_iterator<_Val>, bool> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_insert_unique(_Arg&&) [with _Arg = EnhancedNode*; _Key = EnhancedNode*; _Val = EnhancedNode*; _KeyOfValue = std::_Identity<EnhancedNode*>; _Compare = EnhancedNodeComparator; _Alloc = std::allocator<EnhancedNode*>]'
/usr/include/c++/4.9/bits/stl_set.h:511:40:   required from 'std::pair<typename std::_Rb_tree<_Key, _Key, std::_Identity<_Key>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator, bool> std::set<_Key, _Compare, _Alloc>::insert(std::set<_Key, _Compare, _Alloc>::value_type&&) [with _Key = EnhancedNode*; _Compare = EnhancedNodeComparator; _Alloc = std::allocator<EnhancedNode*>; typename std::_Rb_tree<_Key, _Key, std::_Identity<_Key>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator = std::_Rb_tree_const_iterator<EnhancedNode*>; std::set<_Key, _Compare, _Alloc>::value_type = EnhancedNode*]'
33:54:   required from here
/usr/include/c++/4.9/bits/stl_tree.h:1445:11: error: no match for call to '(EnhancedNodeComparator) (EnhancedNode* const&, EnhancedNode* const&)'
    __comp = _M_impl._M_key_compare(__k, _S_key(__x));
           ^
24:8: note: candidate is:
25:10: note: bool EnhancedNodeComparator::operator()(const EnhancedNode*&, const EnhancedNode*&) const
25:10: note:   no known conversion for argument 1 from 'const key_type {aka EnhancedNode* const}' to 'const EnhancedNode*&'
In file included from /usr/include/c++/4.9/set:60:0,
                 from 3:
/usr/include/c++/4.9/bits/stl_tree.h:1456:7: error: no match for call to '(EnhancedNodeComparator) (EnhancedNode* const&, EnhancedNode* const&)'
       if (_M_impl._M_key_compare(_S_key(__j._M_node), __k))
       ^
24:8: note: candidate is:
25:10: note: bool EnhancedNodeComparator::operator()(const EnhancedNode*&, const EnhancedNode*&) const
25:10: note:   no known conversion for argument 1 from 'EnhancedNode* const' to 'const EnhancedNode*&'
In file included from /usr/include/c++/4.9/set:60:0,
                 from 3:
/usr/include/c++/4.9/bits/stl_tree.h: In instantiation of 'std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_insert_(std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Base_ptr, std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Base_ptr, _Arg&&) [with _Arg = EnhancedNode*; _Key = EnhancedNode*; _Val = EnhancedNode*; _KeyOfValue = std::_Identity<EnhancedNode*>; _Compare = EnhancedNodeComparator; _Alloc = std::allocator<EnhancedNode*>; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator = std::_Rb_tree_iterator<EnhancedNode*>; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Base_ptr = std::_Rb_tree_node_base*]':
/usr/include/c++/4.9/bits/stl_tree.h:1502:38:   required from 'std::pair<std::_Rb_tree_iterator<_Val>, bool> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_insert_unique(_Arg&&) [with _Arg = EnhancedNode*; _Key = EnhancedNode*; _Val = EnhancedNode*; _KeyOfValue = std::_Identity<EnhancedNode*>; _Compare = EnhancedNodeComparator; _Alloc = std::allocator<EnhancedNode*>]'
/usr/include/c++/4.9/bits/stl_set.h:511:40:   required from 'std::pair<typename std::_Rb_tree<_Key, _Key, std::_Identity<_Key>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator, bool> std::set<_Key, _Compare, _Alloc>::insert(std::set<_Key, _Compare, _Alloc>::value_type&&) [with _Key = EnhancedNode*; _Compare = EnhancedNodeComparator; _Alloc = std::allocator<EnhancedNode*>; typename std::_Rb_tree<_Key, _Key, std::_Identity<_Key>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator = std::_Rb_tree_const_iterator<EnhancedNode*>; std::set<_Key, _Compare, _Alloc>::value_type = EnhancedNode*]'
33:54:   required from here
/usr/include/c++/4.9/bits/stl_tree.h:1140:8: error: no match for call to '(EnhancedNodeComparator) (EnhancedNode*&, EnhancedNode* const&)'
        || _M_impl._M_key_compare(_KeyOfValue()(__v),
        ^
24:8: note: candidate is:
25:10: note: bool EnhancedNodeComparator::operator()(const EnhancedNode*&, const EnhancedNode*&) const
25:10: note:   no known conversion for argument 1 from 'EnhancedNode*' to 'const EnhancedNode*&'

I don't really understand why this is so. All the examples for custom comparators for std::set I found online seemed to add &. If someone could explain as an answer, I would select it as the complete answer.

Andrew Cheong
  • 29,362
  • 15
  • 90
  • 145