Come posso lasciare che il compilatore deduca il tipo di ritorno di un modello?

Question

Vengo da Haskell e attualmente sto lavorando con C++ 11 per vedere cosa può fare. Uno dei miei giocattoli è un piccolo modello che tenta di imitare la funzione Haskell map, vale a dire accetta un contenitore di valori di X e una funzione che associa uno X a un Y e produce un contenitore di valori di Y. So che potrei facilmente farlo usando std::transform, ma questo rovinerebbe il divertimento.

In questo momento, il mio modello assomiglia a questo:

template <typename T, typename U> 
void myMap(const T &input, 
      U &output, 
      std::function<typename U::value_type (typename T::value_type)> f); 

Ora, la mia qustion è: è possibile regolare la firma in modo che invece di prendere il contenitore di uscita per riferimento (secondo argomento) io cedo un nuovo contenitore tramite il valore di ritorno e tuttavia il compilatore può dedurre il tipo di reso? Qualcosa di simile

template <typename T, typename U> 
U myMap(const T &input, 
     std::function<typename U::value_type (typename T::value_type)> f); 

purtroppo non può essere chiamato come

std::vector<int> x = { 1, 2, 3, 4 }; 
std::list<bool> y = myMap(x, [](int x) { return x % 2 == 0; }); 

... almeno Clang non riesce a dedurre il tipo di ritorno qui.

Un'idea che avevo era che dato che il tipo di contenitore di input e il tipo di funzione sono noti, è possibile costruire il tipo di output da quello. Cioè qualcosa come

template <typename C, typename T, typename U> 
C<U> myMap(const C<T> &input, 
      std::function<U (T)> f); 

... ma ahimè C<U> non sembra nemmeno di essere sintassi valida. Mi chiedo se ho solo bisogno della giusta polvere fata decltype come nel caso this question.

Answer 1

Probabilmente si sta cercando questa sintassi

#include <algorithm> 
#include <functional> 
#include <type_traits> 
#include <list> 

template 
    < 
     template<typename, typename...> class Container, 
     typename InType, 
     typename FuncType, 
     typename... Rest 
    > 
auto myMap (const Container<InType, Rest...>& container, 
      FuncType func) -> 
       Container<decltype(func(std::declval<InType>())), Rest...> 
{ 
    Container<decltype(func(std::declval<InType>())), Rest...> result; 
    std::transform(std::begin(container), 
        std::end(container), 
        std::back_inserter(result), 
        func); 
    return result; 
} 

anche se io non mi consiglia di utilizzare questo tipo di codice in qualsiasi progetto reale.

Answer 2

Come ho detto prima, ho fatto questo prima di tutto ma non riesce a lavorare con std::basic_string<T,U> (e std::set e gli amici a causa dell'uso di std::back_inserter), perché sarà solo rebind per std::basic_string<stuff,U> piuttosto che un contenitore sottostante Si noti tuttavia che sarebbe facile estenderlo per lavorare con un caso specializzato di std::basic_string<T, U>.

La prima cosa che ho fatto è stato definire una e una metafunction function_traitsRebind che rebind tipi da Container<T> a Container<U> dove U è il tipo di risultato della funzione essere passato e T è il tipo di originale. Il tipo di risultato si trova attraverso la meta funzione function_traits. È possibile vedere il codice completamente funzionante di seguito:

#include <type_traits> 
#include <algorithm> 

/* Helpers */ 
template<typename T> 
using Type = typename T::type; 

template<typename T> 
using Unqualified = Type<std::remove_reference<Type<std::remove_cv<T>>>>; 

template<typename Specialization, typename Target> 
struct rebind {}; 

/* Sensible default: assume first parameter is for the target */ 
template<template<typename...> class Cont, typename T, typename... Ts, typename Target> 
struct rebind<Cont<T, Ts...>, Target> { 
    using type = Cont<Target, Ts...>; 
}; 

/* Special-case */ 
template<typename Old, std::size_t N, typename Target> 
struct rebind<std::array<Old, N>, Target> { 
    using type = std::array<Target, N>; 
}; 

template<typename Specialization, typename Target> 
using Rebind = Type<rebind<Specialization, Target>>; 

#include <tuple> 

template<typename T> 
struct function_traits : public function_traits<decltype(&T::operator())> {}; 

template<typename T, typename R, typename... Args> 
struct function_traits<R(T::*)(Args...) const> { 

    static constexpr size_t args = sizeof...(Args); 

    using result_type = R; 
    template<size_t i> 
    struct arg { 
     using type = typename std::tuple_element<i,std::tuple<Args...>>::type; 
    }; 
}; 

template<typename T> 
using Resultant = typename function_traits<T>::result_type; 

template<class Cont, typename Map> 
auto map(const Cont& cont, Map&& mapped) -> Rebind<Cont, Resultant<Unqualified<Map>>> { 
    Rebind<Cont, Resultant<Unqualified<Map>>> result; 
    auto result_iterator = std::back_inserter(result); 
    for(const auto& elem : cont) { 
     *result_iterator = mapped(elem); 
    } 
    return result; 
} 

#include <iostream> 

int main() { 
    auto i = map(std::vector<int>{1,2,3,4,5,6}, [](int x) { return x % 2 == 0; }); 
    for(auto&& j : i) { 
     std::cout << j << ' '; 
    } 
} 

uscita:

0 1 0 1 0 1 

Live version su Coliru

Answer 3

Utilizzare la nuova sintassi dichiarazione di funzione in C++ 11.

template <typename T> 
auto myMap(const T &input, 
      std::function<typename U::value_type (typename T::value_type)> f) -> decltype(...); 

Dove "..." è sostituito da una singola istruzione che il compilatore può quindi valutare da un tipo. La parte difficile è definire il tipo di ritorno in una singola istruzione, anche se proveniente da Haskell è probabile che lo si possa capire.

Con le dichiarazioni di funzione normale non è possibile per il compilatore dedurre i tipi di ritorno dagli argomenti, poiché gli argomenti non sono ancora stati analizzati. Con questa nuova sintassi è possibile utilizzare gli argomenti per dichiarare il tipo restituito.

Il seguente è un caso in cui è possibile dedurre dal compilatore il tipo di ritorno di una funzione banale che non è possibile in C++ 98.

template <typename T1, typename T2> 
auto add(T1 t1, T2 t2) -> decltype(t1+t2) 
{ return t1 + t2; } 

In C++ 14 stanno aggiungendo alcune regole per consentire al compilatore di dedurre automagically il tipo di ritorno senza dover avere il costrutto decltype.

Answer 4

La risposta di n.m. è quella che vedrei come risposta a destra, ma non penso che l'impatto del template annidato sull'usabilità valga la correttezza.

Ecco la mia prova a esso:

template <typename T, typename F, typename C = 
     std::vector<typename std::result_of<F(typename T::value_type)>::type>> 
C myMap(const T &input, F f) { 
    C ret; 
    for (const auto& x : input) { 
     ret.push_back(f(x)); 
    } 
    return ret; 
} 

Questo illustra due differenze con il tuo codice originale - uno, non ha specificato std :: funzione, come quella classe introduce in testa che è raramente necessario - il modello dedurrà il tipo di lambda inesprimibile nel tuo esempio bene. Due, ho specificato std :: vector invece di std :: list come tipo di ritorno predefinito (il tuo elenco di esempio usato). il vettore è il contenitore C++ preferito: utilizzalo a meno che tu non abbia una ragione schiacciante per utilizzare un contenitore diverso supportato da un benchmark.

Uno dei punti deboli del mio approccio sopra può essere difficile o impossibile elencare i tipi dedotti che sono gli argomenti precedenti del modello. Il modo più semplice per risolvere questo a mio parere è un argomento suggerimento:

template <class T> struct hint {}; 

template <typename T, typename F, typename C> 
C myMap(const T& input, F f, hint<C> h) { 
    return myMap<T, F, C>(input, f); 
} 

Naturalmente, a questo punto si potrebbe anche prendere il contenitore di output come input.