How can I use Boost.Bind on compound types?

Question

I have std::map<int, std::pair<short, float> >, and I need to find the minimal short in this map. How can I use boost::bind with std::min_element() for this?

boost::lambda?

Hid

Answer 1

The map iterator will give you a pair where first is the int key and second is the map's pair value, so if you had an iterator it, you'd want the minimum of all the it->second.first values. The min_element function expects a comparison function for its third argument, so you need to build a comparison function that projects second.first of its two arguments.

We'll start with some typedefs to make the code more readable:

typedef std::pair<short, float> val_type;
typedef std::map<int, val_type> map_type;
map_type m;

We're going to use Boost.Lambda for its overloaded operators, allowing us to use operator<. Boost.Bind can bind member variables as well as member functions, so we'll take advantage of that, too.

#include <boost/bind.hpp>
#include <boost/lambda/lambda.hpp>
using boost::bind;

// Comparison is (_1.second.first < _2.second.first)
std::cout <<
  std::min_element(m.begin(), m.end(),
    bind(&val_type::first, bind(&map_type::iterator::value_type::second, _1))
    <
    bind(&val_type::first, bind(&map_type::iterator::value_type::second, _2))
  )->second.first;

That will also work with boost::lambda::bind.

Pyrolysis

Answer 2

min_element(map.begin(), map.end(),
            compose2(less<short>(),
                     compose1(select1st<pair<short, float> >(),
                              select2nd<map<int, pair<short, float>
                                           >::value_type>()),
                     compose1(select1st<pair<short, float> >(),
                              select2nd<map<int, pair<short, float>
                                           >::value_type>()))
           ).second.first;

(Of course, somebody's going to complain that this is an abuse of STL and that these are extensions not in the C++ standard…)

Azotobacter

Well, I would complain about nonstandard extensions, but as far as "STL abuse" goes I think it's perfectly fine :) +1. Luckily the nonstandard bits are easy to write yourself. – Levee

Answer 3

bind cannot do this by itself, because first and second are exposed as fields, not methods (so you can't get away with something like mem_fun).

You could do this using your own functor of course though:

template <typename F, typename S>
struct select_first : std::binary_function<std::pair<F, S>&, F&>
{
    F& operator()(std::pair<F, S>& toConvert)
    {
        return toConvert.first;
    }
};

Levee

Also known as select1st in some C++ libraries. – Azotobacter

@ephemient: True -- wasn't aware that it was already included with SGI's STL. In that case I would recommend leaving the name this way because SGI's supports any pair-like interface, while this one only works with std::pair. – Levee