Adam Hunyadi Adam Hunyadi - 1 month ago 11
C++ Question

Python-like map in c++

My problem with std:: transform is that I can't both get the begin and the end of a temporary object.

I would like to implement a python-like mapping function in c++ that works on vectors of a type and maps them to another vector (of possibly another type).

This is my approach:

template <class T, class U, class UnaryOperator>
std::vector<T> map(const std::vector<T>& vectorToMap, UnaryOperator operation)
{
std::vector<U> result;
result.reserve(vectorToMap.size());
std::transform(vectorToMap.begin(), vectorToMap.end(),
std::back_inserter(result), [&operation] (U item) { return operation(item); });
return result;
}


And this an example of how I intend to use this (where the return type of filter is the type of its first agurment):

std::vector<std::shared_ptr<Cluster>> getClustersWithLength(const std::vector<Cluster>& clusterCollection, const int& length)
{
return map(filter(clusterCollection, [&length] (Cluster& cluster) {
return cluster.sizeY == length;
}),
[] (const Cluster& cluster) {
return std::make_shared<Cluster>(cluster);
});
}


The error message I get for this code though is:

error: no matching function for call to 'map(std::vector<Cluster>,
ClusterPairFunctions::getClustersWithLength(const
std::vector<Cluster>&, const int&)::<lambda(const Cluster&)>)'

note: candidate: template<class T, class U, class UnaryOperator> std::vector<_RealType> map(const std::vector<_RealType>&, UnaryOperator)
std::vector<T> map(const std::vector<T>& vectorToMap, UnaryOperator operation)
note: couldn't deduce template parameter 'U'


Can you give me some help, how do I fix it? Also, can I somehow use compile-time static assertion to check if the type of operation(T t) is U?

Edit:

Removing U and replacing the declaration of result with
std::vector<typename std::result_of<UnaryFunction(T)>::type> result;
still produces an error:

src/ClusterPairFunctions.cc: In function 'std::vector<std::shared_ptr<Cluster> > ClusterPairFunctions::getClustersWithLength(const std::vector<Cluster>&, const int&)':
src/ClusterPairFunctions.cc:130:14: error: could not convert 'map(const std::vector<_RealType>&, UnaryFunction) [with T = Cluster; UnaryFunction = ClusterPairFunctions::getClustersWithLength(const std::vector<Cluster>&, const int&)::<lambda(const Cluster&)>]((<lambda closure object>ClusterPairFunctions::getClustersWithLength(const std::vector<Cluster>&, const int&)::<lambda(const Cluster&)>{}, ClusterPairFunctions::getClustersWithLength(const std::vector<Cluster>&, const int&)::<lambda(const Cluster&)>()))' from 'std::vector<Cluster>' to 'std::vector<std::shared_ptr<Cluster> >'
return (map(filter(clusterCollection, [&length] (Cluster& cluster) {
In file included from src/../interface/ClusterPairFunctions.h:5:0,
from src/ClusterPairFunctions.cc:1:
src/../interface/../../../interface/HelperFunctionsCommon.h: In instantiation of 'std::vector<_RealType> filter(const std::vector<_RealType>&, UnaryPredicate) [with T = Cluster; UnaryPredicate = ClusterPairFunctions::getClustersWithLength(const std::vector<Cluster>&, const int&)::<lambda(Cluster&)>]':
src/ClusterPairFunctions.cc:132:4: required from here
src/../interface/../../../interface/HelperFunctionsCommon.h:52:15: error: no match for call to '(ClusterPairFunctions::getClustersWithLength(const std::vector<Cluster>&, const int&)::<lambda(Cluster&)>) (const Cluster&)'
if(predicate(*it)) result.push_back(*it);
^
src/ClusterPairFunctions.cc:130:68: note: candidate: ClusterPairFunctions::getClustersWithLength(const std::vector<Cluster>&, const int&)::<lambda(Cluster&)> <near match>
return (map(filter(clusterCollection, [&length] (Cluster& cluster) {
^
src/ClusterPairFunctions.cc:130:68: note: conversion of argument 1 would be ill-formed:
In file included from src/../interface/ClusterPairFunctions.h:5:0,
from src/ClusterPairFunctions.cc:1:
src/../interface/../../../interface/HelperFunctionsCommon.h:52:15: error: binding 'const Cluster' to reference of type 'Cluster&' discards qualifiers
if(predicate(*it)) result.push_back(*it);
^
src/../interface/../../../interface/HelperFunctionsCommon.h: In instantiation of 'std::vector<_RealType> map(const std::vector<_RealType>&, UnaryFunction) [with T = Cluster; UnaryFunction = ClusterPairFunctions::getClustersWithLength(const std::vector<Cluster>&, const int&)::<lambda(const Cluster&)>]':
src/ClusterPairFunctions.cc:135:4: required from here
src/../interface/../../../interface/HelperFunctionsCommon.h:64:9: error: could not convert 'result' from 'std::vector<std::shared_ptr<Cluster> >' to 'std::vector<Cluster>'
return result;

Answer

Here is your code made a touch more generic:

template <template<class...>class Z=std::vector, class C, class UnaryOperator>
auto fmap(C&& c_in, UnaryOperator&& operation)
{
  using dC = std::decay_t<C>;
  using T_in = dC::reference;
  using T_out = std::decay_t< std::result_of_t< UnaryOperator&(T_in) > >;
  using R = Z<T_out>;
  R result;
  result.reserve(vectorToMap.size());
  using std::begin; using std::end;
  std::transform(
    begin(cin), end(cin),
    std::back_inserter(result),
    [&] (auto&& item) { return operation(declype(item)(item)); }
  );
  return result;
}

To make the above work in C++11, you'll have to add trailing return type -> decltype(complex expression) and replace the nice std::decay_t<whatever> with typename std::decay<whatever>::type or write your own aliases.

These steps:

  using dC = std::decay<C>;
  using T_in = dC::reference;
  using T_out = std::decay_t< std::result_of_t< UnaryOperator&(T_in) > >;
  using R = Z<T_out>;

need to be moved to a helper type

template<template<class...>class Z, class C, class Op>
struct calculate_return_type {
  using dC = typename std::decay<C>::type;
  using T_in = typename dC::reference;
  using T_out = typename std::decay< typename std::result_of< Op&(T_in) >::type >::type;
  using R = Z<T_out>;
};

giving us this:

template <template<class...>class Z=std::vector, class C, class UnaryOperator>
auto fmap(C&& c_in, UnaryOperator&& operation)
-> typename calculate_return_type<Z, C, UnaryOperator>::R
{
  using R = typename calculate_return_type<Z, C, UnaryOperator>::R;
  R result;
  result.reserve(c_in.size());
  using T_in = typename calculate_return_type<Z, C, UnaryOperator>::T_in;

  using std::begin; using std::end;
  std::transform(
    begin(c_in), end(c_in),
    std::back_inserter(result),
    [&] (T_in item) { return operation(decltype(item)(item)); }
  );
  return result;
}

but really, it is 2016, do attempt to upgrade to C++14.

Live example


In C++14, I find curry-style works well

template<class Z, class T>
struct rebind_helper;
template<template<class...>class Z, class T_in, class...Ts, class T_out>
struct rebind_helper<Z<T_in,Ts...>, T_out> {
  using type=Z<T_out, Ts...>;
};
template<class Z, class T>
using rebind=typename rebind_helper<Z,T>::type;

template<class Op>
auto fmap( Op&& op ) {
  return [op = std::forward<Op>(op)](auto&& c) {
    using dC = std::decay_t<decltype(c)>;
    using T_in = dC::reference;
    using T_out = std::decay_t< std::result_of_t< UnaryOperator&(T_in) > >;
    using R=rebind< dC, T_out >;
    R result;
    result.reserve(vectorToMap.size());
    using std::begin; using std::end;
    std::transform(
      begin(cin), end(cin),
      std::back_inserter(result),
      [&] (auto&& item) { return operation(declype(item)(item)); }
    );
    return result;
  };
}

both of these need a "reserve if possible" function (which does SFINAE to detect if .reserve exists, and if so reserves; otherwise, doesn't bother).

The second looks like:

auto fmap_to_double = fmap( [](auto in){ return (double)in; } );

which can then be passed a container and it remaps its elements to double.

auto double_vector = fmap_to_double( int_vector );

On the other hand, maybe always producing vectors might be a worthwhile simplification. However, always only consuming vectors seems pointless.