Templated map / multimap function in C++

Question

Assume I have:

std::map<K, V1> m1;
std::multimap<K, V2> m2;

I would like to template by container type and by key/value type. The following isn't working however :/

template <typename T>
void do_something(T var)
{
  // do something
}

template <typename TContainer, typename TKey, typename TVal>
void func(const TContainer<TKey, TVal>& container)
{
  for (typename TContainer<TKey, TVal>::iterator it = container.begin(); it != container.end(); ++it)
  {
    do_something(it->second);
  }
}

And then call it with:

func(m1);
func(m2);

Answer 1

Try this, you don't need to specify that the container is templated on key and value types (note that the code is the same for any of those types), the compiler will generate an error if the passed type does not satisfy the contract. Currently the contract is "has iterator", "has begin", "has end" and "the iterator has second".

template <typename T>
void do_something(T var)  // Also consider "const T&"
{
  // do something
} 

template <typename TContainer>
void func(const TContainer& container)
{
  for (typename TContainer::iterator it = container.begin();
       it != container.end(); ++it)
  {
    do_something(it->second);
  }
}

Answer 2

Can't you just have a single template parameter?

template <typename Container>
void func(const Container & container)
{
    for (typename Container::iterator it = container.begin(); it != container.end(); ++it)
    {
        do_something(it->second);
    }
}

Or better, pass iterators to your function instead of a container:

template <typename ForwardIterator>
void func(ForwardIterator begin, ForwardIterator end)
{
    for (; begin != end; ++begin)
    {
        do_something(begin->second);
    }
}

If you really want a template template parameter, here is the syntax:

template <template <typename, typename> Container, typename TKey, typename TValue>
void func(const Container<TKey, TValue> & container);

However, this won't work for the STL container since they usually have more parameters than it seems; indeed, they often have parameters with default values, such as allocator, so your best bet is to use the idiomatic way of writing generic algorithm described above, i.e. deal with iterators instead of containers.

Answer 3

The reason this doesn't work is that std::map takes four template arguments:

template<class Key,
         class Value,
         class Predicate = std::less<Key>,
         class Allocator = std::allocator<pair<const Key, Value> > >
class map;

While you can omit the last two parameters for instantiating, you have to list them for template matching to work:

template < typename TKey, 
           typename TVal, 
           class TPr, 
           class TAl
           template<typename,typename,class,class> TContainer >
void func(const TContainer<TKey, TVal, TPr, TAl>& container)
{
  for (typename TContainer<TKey, TVal, TPr, TAl>::iterator it = container.begin(); it != container.end(); ++it)
  {
    do_something(it->second);
  }
}

That said, however, I wonder why you are bothering with this. The idiomatic way would be to pass iterators:

template <typename FwdIt>
void func(FwdIt begin, FwdIt end)
{
  while(begin != end) {
    do_something(begin->second);
    ++begin;
  }
}

This also allows you to pass in anything that's compatible:

void f(const std::vector< std::pair<int, std::string> >& v)
{
   func( v.begin(), v.end() );
}

Answer 4

I would definitely suggest the following approach. I dislike templating on the container, for a lot of reasons, so let's template on iterators. A cumbersome, but generic approach is the following:

#include <algorithm>
#include <functional>

// This should be part of the standard, but it isn't.
template <typename Func1, typename Func2>
struct composer :
    std::unary_function
        <
            typename Func2::argument_type,
            typename Func1::result_type
        >
{
    composer(Func1 f1_ = Func1(), Func2 f2_ = Func2())
        : f1(f1_), f2(f2_)
    {}

    typename Func1::result_type 
    operator()(typename Func2::argument_type x)
    { return f1(f2(x)); }

private:
    Func1 f1; Func2 f2;
};


template <typename F1, typename F2>
composer<F1, F2> compose(F1 f1, F2 f2)
{ return composer<F1, F2>(f1, f2); }


template <class C, typename T, T C::*ptr>
struct mem_ptr : std::unary_function<C&, T&>
{ T& operator()(C& x) { return x::*ptr; } };


template <typename Iter>
void func(Iter begin, Iter end)
{
    typedef typename Iter::value_type pair_t;

    typedef mem_ptr
    <
        pair_t,
        pair_t::second_type,
        pair_t::&second
    > second_of;

    std::for_each(begin, end, compose(ptr_fun(do_something), ptr_mem));
}

The utility function compose and the class mem_ptr are stuff which should have been implemented in the standard (they may be in TR1 though). Note that you can template on the type of do_something, and you can even pass do_something as an argument.

Note that ptr_mem can be improved to something you can call like

ptr_mem(pair_t::&second)

but this would involve some more code. There may be some useful things in Boost, but here we can content with a 20-line approach.

Answer 5

Passing iterators, as suggested multiple times, is the standard way, but you might also harness Boost.Range:

#include <boost/range.hpp>

template<typename ForwardReadableRange>
void func(const ForwardReadableRange& range) {
  typedef typename boost::range_iterator<const ForwardReadableRange>::type InputIterator;
  for (InputIterator it = boost::begin(range); it != boost::end(range); ++it) {
    do_something(it->second);
  }
}

template<typename ForwardReadableWriteableRange>
void func(ForwardReadableWriteableRange& range) {
  typedef typename boost::range_iterator<ForwardReadableWriteableRange>::type ForwardIterator;
  for (ForwardIterator it = boost::begin(range); it != boost::end(range); ++it) {
    do_something(it->second);
  }
}

This allows the caller to pass anything that models ForwardReadable(Writeable)Range, e.g. containers or iterator pairs.

Of course this should be replaced by a DoSomethingWithSecond functor and for_each:

template<typename T, typename UnaryOp, typename Result>
struct DoSomethingWithSecond: std::unary_function<T, Result> {
  UnaryOp op;
  explicit DoSomethingWithSecond(UnaryOp op): op(op) { }
  Result operator()(T value) {
    return op(value.second);
  }
};
template<typename T>
void func(T range) {
  boost::for_each(range, DoSomethingWithSecond(do_something));
}