Find in a map using the base class with a boost::shared_ptr

Question

I'm looking for a way to find an element inside a map using the base class (the code bellow is just a basic example):

#include <map>
#include <boost/shared_ptr.hpp>

class Base {
public:
    Base(int v) : id(v) {};
    int id;  
};

class Derived : public Base {
public:
    Derived(int v) : Base(v) {};
};


int main()
{
    std::map<boost::shared_ptr<Derived>, double> m;
    m.insert(std::make_pair(boost::shared_ptr<Derived>(new Derived(1)), 10));
    m.insert(std::make_pair(boost::shared_ptr<Derived>(new Derived(2)), 20));

    auto b1 = boost::shared_ptr<Base>(new Base(1));
    m.find(b1);

    return 0;
}

Basically, I want to compare the id attribute. The errors returned by the compiler are the following:

main.cpp: In function 'int main()':
main.cpp:35:14: error: no matching function for call to 'std::map<boost::shared_ptr<Derived>, double>::find(boost::shared_ptr<Base>&)'
     m.find(b1);
              ^
main.cpp:35:14: note: candidates are:
In file included from /usr/include/c++/4.8/map:61:0,
                 from main.cpp:1:
/usr/include/c++/4.8/bits/stl_map.h:820:7: note: std::map<_Key, _Tp, _Compare, _Alloc>::iterator std::map<_Key, _Tp, _Compare, _Alloc>::find(const key_type&) [with _Key = boost::shared_ptr<Derived> _Tp = double; _Compare = std::less<boost::shared_ptr<Derived> > _Alloc = std::allocator<std::pair<const boost::shared_ptr<Derived>, double> > std::map<_Key, _Tp, _Compare, _Alloc>::iterator = std::_Rb_tree_iterator<std::pair<const boost::shared_ptr<Derived>, double> > std::map<_Key, _Tp, _Compare, _Alloc>::key_type = boost::shared_ptr<Derived>]
       find(const key_type& __x)
       ^
/usr/include/c++/4.8/bits/stl_map.h:820:7: note:   no known conversion for argument 1 from 'boost::shared_ptr<Base>' to 'const key_type& {aka const boost::shared_ptr<Derived>&}'
/usr/include/c++/4.8/bits/stl_map.h:835:7: note: std::map<_Key, _Tp, _Compare, _Alloc>::const_iterator std::map<_Key, _Tp, _Compare, _Alloc>::find(const key_type&) const [with _Key = boost::shared_ptr<Derived> _Tp = double; _Compare = std::less<boost::shared_ptr<Derived> > _Alloc = std::allocator<std::pair<const boost::shared_ptr<Derived>, double> > std::map<_Key, _Tp, _Compare, _Alloc>::const_iterator = std::_Rb_tree_const_iterator<std::pair<const boost::shared_ptr<Derived>, double> > std::map<_Key, _Tp, _Compare, _Alloc>::key_type = boost::shared_ptr<Derived>]
       find(const key_type& __x) const
       ^
/usr/include/c++/4.8/bits/stl_map.h:835:7: note:   no known conversion for argument 1 from 'boost::shared_ptr<Base>' to 'const key_type& {aka const boost::shared_ptr<Derived>&}'

Answer 1

If you want to use your map for lookup by id, you need to pass in an appropriate comparison function so that the map sorts its keys by id instead of the default operator < (which, I believe, compares ownership block addresses with boost::shared_ptr arguments).

So change the map like this:

struct Less_id
{
  bool operator() (const boost::shared_ptr<Derived> &lhs, const boost::shared_ptr<Derived> &rhs) const
  {
    return lhs->id < rhs->id;
  }
};

typedef std::map<boost::shared_ptr<Derived>, double, Less_id> Map;

Map m;

This will sort the map accordingly, but still not allow lookup by Base pointer. To do that, you can write your own function above std::lower_bound:

Map::const_iterator find_base(const Map &map, const boost::shared_ptr<Base> &base)
{
  auto it = std::lower_bound(
    map.begin(), map.end(), base,
    [](const Map::value_type &lhs, const boost::shared_ptr<Base> &rhs)
    { return lhs.first->id < rhs->id; }
  );
  if (it != map.end() && it->first->id == base->id)
    return it;
  else
    return map.end();
}

std::lower_bound() is used to keep the logarithmic complexity std::map::find() offers.

Live example