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

Question

我遇到编译错误，

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*>]'

不幸的是没有行号，但我删除了代码部分，我相信它与我想应用自定义比较器的 std::set 有关：

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_;

我做错了什么吗？

Answer 1

在创建一个最小的、完整的、可验证的^TM 示例时，我能够解决我的问题。无论如何我都会发布它，因为 Google 令人惊讶的是，我在引号中的错误的第一部分的命中率为零。

原来我不需要

中的 &

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

我通过在不同的编译器上编译发现了这一点，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;
}

并得到更有用的错误：

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*&'

我真的不明白为什么会这样。我在网上找到的 std::set 的自定义比较器的所有示例似乎都添加了 &。如果有人可以解释为答案，我会 select 它作为完整答案。

Answer 2

std::set 的比较器绝对应该接受对集合中的 const 限定类型的引用。

你搞错的是集合中类型的限定。它是 EnhancedNode*，所以用 const 限定它应该给出 EnhancedNode* const。而不是 const EnhancedNode*。

这又是一个前导常量误导的案例。将你原来的比较器，连同参考和全部，改成这样：

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

您也可以保留 const 限定的指针对象。 .

删除引用后问题得到解决的原因是按值传递时。因此，您的函数作为参数收到的指针不是 const 限定的并不重要。这只是原件的副本。

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

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

c++

compiler-errors

comparator

stdset