Using std::reference_wrapper as the key in a std::map

Question

I have a bunch of objects in a class hierarchy and would like to make a std::map using references to those objects as the keys in the map. Its seems like std::reference_wrapper would be exactly what is needed for this, but I can't seem to make it work. What I've tried so far:

class Object { // base class of my hierarchy
    // most details unimportant
public
    virtual bool operator< (const Object &) const;  // comparison operator
};

std::map<std::reference_wrapper<const Object>, int> table;

auto it = table.find(object);

table[object] = 42;

table[object]++

However, I always get somewhat obscure errors from the compiler:

/usr/include/c++/4.5.3/bits/stl_function.h: In member function ‘bool std::less<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = std::reference_wrapper<const Object>]’:
/usr/include/c++/4.5.3/bits/stl_tree.h:1522:38:   instantiated from ‘std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::find(const _Key&) [with _Key = std::reference_wrapper<const Object>, _Val = std::pair<const std::reference_wrapper<const Object>, int>, _KeyOfValue = std::_Select1st<std::pair<const std::reference_wrapper<const Object>, int> >, _Compare = std::less<std::reference_wrapper<const Object> >, _Alloc = std::allocator<std::pair<const std::reference_wrapper<const Object>, int> >, std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator = std::_Rb_tree_iterator<std::pair<const std::reference_wrapper<const Object>, int> >]’
/usr/include/c++/4.5.3/bits/stl_map.h:697:29:   instantiated from ‘std::map<_Key, _Tp, _Compare, _Alloc>::iterator std::map<_Key, _Tp, _Compare, _Alloc>::find(const key_type&)[with _Key = std::reference_wrapper<const Object>, _Tp = int, _Compare = std::less<std::reference_wrapper<const Object> >, _Alloc = std::allocator<std::pair<const std::reference_wrapper<const Object>, int> >, std::map<_Key, _Tp, _Compare, _Alloc>::iterator = std::_Rb_tree_iterator<std::pair<const std::reference_wrapper<const Object>, int> >, key_type = std::reference_wrapper<const Object>]’
testfile.cpp:39:31:   instantiated from here
/include/c++/4.5.3/bits/stl_function.h:230:22: error: no match for ‘operator<’ in ‘__x < __y’

The error seems to be saying it can't compare two std::reference_wrapper<const Object> objects, but it seems like it should be possible -- std::reference_wrapper has a conversion operator that can implicitly convert it to a T& (const Object & here), and Object has a operator <, so why doesn't it work?

Should it work and this is merely a bug in g++? Or is something else going on?

Answer 1

By default std::map uses std::less<std::reference_wrapper<const Object>> as Compare, but std::reference_wrapper<T> doesn't forward operator<() to the underlying type T.

The simplest and concisest option to solve your problem is to define std::less<const Object> (or std::greater<const Object>) in the map definition like this:

std::map<std::reference_wrapper<const Object>, int, std::less<const Object>> table;

It will work correctly and as expected due to implicit conversion of std::reference_wrapper to T& and implicit constructor of std::reference_wrapper.

Example.

Answer 2

It seems that it would work if you made the comparison operator a free function (that perhaps calls a virtual member function).

If it is a member function, a < b really means a.operator<(b); and implicit conversions are not considered for the left-side argument.