Simulate type deduction on return type using temp. proxy with conversion operator

Question

I have this Haskell-style map higher-order function which already uses template type deduction for a clean syntax on the caller side, except for the result type:

template<class ResultingContainer, class R, class Fn>
ResultingContainer map(const R &range, const Fn &f) {
    ResultingContainer result;
    using value_type = decltype(*std::begin(range));
    for_each(range, [&](const value_type &v){
        result.push_back(f(v));
    });
    return result;
}

_{(I prefer decltype(*std::begin(range)) over R::value_type or some iterator traits, because I use containers which don't provide such an interface: Qt containers.)}

Using this function is simple but not as simple as I want it to be, you all know what I mean:

std::vector<int> result = map<std::vector<int>>(otherVector, someFunction);

Of course, I want it to be:

std::vector<int> result = map(otherVector, someFunction);

If I designed the API in the following way, type deduction would work perfectly. But I don't want it to be like this, as this is C++ standard library style (except the difference between iterator pair / range), but I want it to be "Haskell-style":

std::vector<int> result;
map(otherVector, result, someFunction);

Given the fact that otherVector doesn't necessarily be of the same type as the result (for example, they could be strings and I want their length, so someFunction returns the length of a given string), I can't express the type ResultingContainer only using the already known types (in particular, the input's value type).

If I (and I don't want to) stick to one single type of container, I could express it. But there is one hope left: The compiler already knows what the result should be, unless auto is used for the return type. (And it will be confusing when there are multiple possibilities on the result type, e.g. when used as an argument to an overloaded function).

So I thought about a proxy container, which is the default ResultingContainer (but can be overwritten if the user needs to, that's not my problem). However, with my current knowledge I could only implement some ProxyContainer<T> (with T being the result type of f, the predicate used in map), which temporarily holds all result items. This sounds like unnecessary overhead. However, an implementation could look like:

template<typename T>
class ProxyContainer : public std::vector<T> {
    template<typename FinalContainer>
    operator FinalContainer() const {
        FinalContainer result;
        for (auto x : *this)
            result.push_back(x);
        return result;
    }
};

But this just doesn't feel right.

Can you come up with a better solution?

Answer 1

Here is a generic lazy adaptor implementation, together with some container_traits allowing you to return your data into a std::set or the like.

#include <tuple>
#include <iterator>
#include <utility>
#include <algorithm>

// Standard metaprogramming boilerplate:
template<std::size_t...>
struct seq {};
template<std::size_t max, std::size_t... s>
struct make_seq:make_seq<max-1, max-1, s...> {};
template<std::size_t... s>
struct make_seq<0, s...> {
  typedef seq<s...> type;
};
// helper to make creating a sequence from 0,...,max-1 take less typing:
template<std::size_t max>
using MakeSeq = typename make_seq<max>::type;

// takes a sequence of indexes, a tuple, a Result type, and a Functor, and calls the Functor passing
// in the Result type with the fowarded args in the tuple, as indicated by the sequence of indexes:
template<typename Result, template<typename Result>class Functor, typename... Args, std::size_t... s>
Result apply( seq<s...>, std::tuple<Args...>& args ) {
  return Functor<Result>()(std::forward<Args>(std::get<s>(args))...);
}

// and here it is, a generic lazy evaluator:
template<template<typename Result>class Functor, typename... Args>
struct LazyEvaluation {
  std::tuple<Args...> stored_args;
  LazyEvaluation( Args... args ):stored_args(std::forward<Args>(args)...) {};
  template<typename R>
  operator R() {
    return apply<R, Functor>( MakeSeq<sizeof...(Args)>(), stored_args );
  }
};

// The start of some container traits templates:
template<typename T, typename=void>
struct const_iterator_type:std::false_type {};
template<typename T>
struct const_iterator_type<T, typename std::enable_if<
  std::is_same< typename T::const_iterator, typename T::const_iterator >::value
>::type>:std::true_type {
   typedef typename T::const_iterator const_iterator;
};
template<typename T, size_t n>
struct const_iterator_type< T[n] >:std::true_type {
   typedef T const* const_iterator;
};


template<typename T,typename=void>
struct has_push_back:std::false_type {};
template<typename T>
struct has_push_back<T, typename std::enable_if<
  std::is_same<
     decltype(std::declval<T>().push_back(*std::declval<typename const_iterator_type<T>::const_iterator>())),
     decltype(std::declval<T>().push_back(*std::declval<typename const_iterator_type<T>::const_iterator>()))
  >::value
>::type>:std::true_type{};
template<typename T,typename=void>
struct has_insert:std::false_type {};
template<typename T>
struct has_insert<T, typename std::enable_if<
  std::is_same<
     decltype(std::declval<T>().insert(*std::declval<typename const_iterator_type<T>::const_iterator>())),
     decltype(std::declval<T>().insert(*std::declval<typename const_iterator_type<T>::const_iterator>()))
  >::value
>::type>:std::true_type {};

template<typename Container, typename=void>
struct container_traits;

template<typename Container>
struct container_traits<Container, typename std::enable_if<has_push_back<Container>::value>::type> {
   template<typename V>
   static void add_to_container( Container& c, V&& v ) {
     c.push_back( std::forward<V>(v) );
   }
};
template<typename Container>
struct container_traits<Container, typename std::enable_if<!has_push_back<Container>::value && has_insert<Container>::value>::type> {
   template<typename V>
   static void add_to_container( Container& c, V&& v ) {
     c.insert( std::forward<V>(v) );
   }
};

// supporting emplace_back and emplace is harder, but probably worth it.
// the trick with both of them is that you only know if they exist or are valid
// after you try to call add_to_container with the arguments!  So instead of
// "does it exist", you end up with "can we call emplace_back with these arguments".
// This requires a bit of slight of hand in the template code, as we want to fall back
// on insert and push_back if emplace_back doesn't exist.

// Another improvement to the above might be to have the const_iterator traits class
// fall back on a decltype( std::begin(std::declval<C const>()) ) -- or even better,
// do full ADL with a private namespace and a using std::begin.

// your code, basically verbatim, but uses container_traits to figure out
// how to add an element to the container:
template<class ResultingContainer, class Range, class Fn>
ResultingContainer map_now(const Range &range, const Fn &f) {
  ResultingContainer result;
  using value_type = decltype(*std::begin(range));
  for_each(std::begin(range), std::end(range), [&](const value_type &v){
    container_traits<ResultingContainer>::add_to_container(result, f(v));
  });
  return result;
}

// could make this easier if I could pass in a pointer-to-template-function
// or the equivalent directly.  Know the syntax by any chance?
template<typename Range, typename Fn>
struct map_lazy_helper {
  template<typename ResultingContainer>
  struct Func {
    ResultingContainer operator()(const Range &range, const Fn &f) const {
      return map_now<ResultingContainer>( range, f );
    }
  };
};

// Map lazy is mostly repeating type information:
template<typename Range, typename Fn>
LazyEvaluation<map_lazy_helper<Range, Fn>::template Func, Range, Fn>
map_lazy(Range&&range, Fn&&f) {
  return {std::forward<Range>(range), std::forward<Fn>(f)};
}

#include <iostream>
#include <vector>
#include <set>

int main() {
   std::vector<int> tester {3,2,1};

   std::vector<double> vd = map_lazy( tester, [](int x) { return x*0.5; } );
   std::set<double> sd = map_lazy( tester, [](int x) { return x*0.5; } );
   std::vector<int> vs = map_lazy( tester, [](int x) { return x*2; } );
   for(auto&& x:vd)
     std::cout << x << "\n";
   for(auto&& x:sd)
     std::cout << x << "\n";
   for(auto&& x:vs)
     std::cout << x << "\n";
}

which works as well as you might like. :)

Amusingly, while this answer is huge, 40% of it is a generic "add to container" code that handles set, 10% is metaprogramming boilerplate, 30% is a generic LazyEvaluation, 10% is test code, and only 10% is the code required to actually write map_lazy.

And now that I think about it, what you want is a generic "insert stuff into container" iterator, so you can support writing to a std::array of sufficient size, a std::set, a std::vector or a homebrew container. It should probe for back_insert_iterator, failing that insert_iterator( C.end() ), with specializations for fixed sized containers like std::array (which have a size even when empty!). That would make container_traits even more complex, and it already takes up about half of this post!

Finally, here is an ADL-enabled "does the container support begin":

namespace aux_adl {
  using std::begin; using std::end;
  template<typename C>
  auto adl_begin( C&& c )->decltype( begin(std::forward<C>(c)) );
  template<typename C>
  auto adl_end( C&& c )->decltype( end(std::forward<C>(c)) );
  template<typename C>
  auto adl_cbegin( C const& c )->decltype( begin(c) );
  template<typename C>
  auto adl_cend( C const& c )->decltype( end(c) );
}
template<typename C, typename=void>
struct container_iterator {}
template<typename C>
struct container_iterator<C, std::enable_if<
  std::is_same<
    decltype( adl_aux::adl_begin(std::declval<C>()),
    decltype( adl_aux::adl_end(std::declval<C>())
  >::value
>::type> {
  typedef adl_aux::adl_begin(std::declval<C>()) iterator;
};
template<typename C>
struct container_const_iterator<C, std::enable_if<
  std::is_same<
    decltype( adl_aux::adl_cbegin(std::declval<C>()),
    decltype( adl_aux::adl_cend(std::declval<C>())
  >::value
>::type> {
  typedef adl_aux::adl_cbegin(std::declval<C>()) const_iterator;
};

Note that the adl_end type functions only do proper ADL type lookup, they cannot actually be called.

And yes, it is a hack. And apparently someone is bugging the C++ committee to allow using declarations inside decltype to fix up this hack a tad.

Answer 2

I solved the problem using a "lazy adapter" as Xeo suggested. But instead of using the Boost one, I wrote a very simple one:

template<class R, class Fn>
class MapAdaptor
{
    const R &range;
    const Fn &f;

public:
    MapAdaptor(const R &range, const Fn &f) :
        range(range), f(f)
    {
    }

    template<class ResultingContainer>
    operator ResultingContainer() const {
        ResultingContainer result;
        for(const auto &v : range)
            result.push_back(f(v));
        return result;
    }
};

Then, the actual map function becomes the following:

template<class R, class Fn>
MapAdaptor<R,Fn> map(const R &range, const Fn &f) {
    return MapAdaptor<R,Fn>(range, f);
}

I didn't make the adaptor a range itself yet, but I'll add this functionality, in order to be able to chain / nest operations.