required from 'std::pair<std::_Rb_tree_iterator<_Val>, bool> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_insert_unique

Question

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?

Answer 1

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.