Constraints on template types

Question

Suppose, I want to implement a generic higher-order Map function in C++. Map should take a container and a transformation function and return a container of the same type, but possibly with different type of items.

Let's take vector for instance:

template <typename InT, typename OutT, typename Tr>
vector<OutT> Map(vector<InT> cont, Tr tr)
{
    OutCont out(cont.size());
    auto oit = out.begin();
    for (auto it = cont.cbegin(); it != cont.cend(); ++it, ++ot)
    {
        *oit = tr(*it);
    }
}

which I want to use like this:

vector<int> v(10);
std::iota(v.begin(), v.end(), 0);
auto x = Map(v, [](int x) -> int {return x * 2;});

This fails in VC++ 2012, giving me the following error:

error C2783: 'std::vector<OutT> Map(std::vector<_Ty>,Tr)' : could not deduce template argument for 'OutT'   

It seems to me that the compiler has all the necessary information, because I explicitly defined the return type in the lambda. Is there a way around this?

The above example uses vector. Is there a way to use a generic type, so that the input and output types are the same? For instance if I have an input container defined as vector<string> and the transformation function tr(string a) -> int, then my goal is to make the compiler to figure out the output type to be vector<int>. Here's the pseudo-code for what I want to achieve:

template <typename Cont<InT>, typename Cont<OutT>, typename Tr<InT, OutT>>
Cont<OutT> Map(Cont<InT> cont, Tr<InT, OutT> tr)
{
    // Implementation
}

Answer 1

You may write something like:

template <typename InT, typename Tr>
auto Map(std::vector<InT> cont, Tr tr) -> std::vector<decltype(tr(cont[0]))>
{
    std::vector<decltype(tr(cont[0]))> out(cont.size());
    auto oit = out.begin();
    for (auto it = cont.cbegin(); it != cont.cend(); ++it, ++oit)
    {
        *oit = tr(*it);
    }
    return out;
}

Out type is deduced.

[Edit] For a more generic function with more container:

template <template<typename, typename...> class Container, typename InT, typename Tr, typename... Args>
auto Map(const Container<InT, Args...>& cont, Tr tr) -> Container<decltype(tr(cont[0])), Args...>
{
    Container<decltype(tr(cont[0])), Args...> out(cont.size());
    auto oit = out.begin();
    for (auto it = cont.cbegin(); it != cont.cend(); ++it, ++oit)
    {
        *oit = tr(*it);
    }
    return out;
}

Notice the typename... needed because std::vector can also take allocator