Returning a template of templates

This code does not automatically infer the return type correctly (a design aspect of C++):

开发者_开发问答template < typename Container,
           typename UnaryOp>
Container
mymap(Container c, UnaryOp op)
{
    typedef typename Container::value_type ResultType
    Container<ResultType> result;
    for(Container::iterator i = c.begin();
        i != c.end();
        i++)
    {
        result.push_back(op(*i));
    }

    return result;
}

What I would like to do is have something like this happen:

vector<string> bar;
bar.push_back("1");
bar.push_back("2");
bar.push_back("3");    
vector<int> foomatic;
foomatic = mymap(bar, [] (string s)->int {return atoi(s.c_str());});
//foomatic now is equal to {1,2,3}

I was figuring that Container would be inferred to be vector, and ResultType would be inferred to be int.

After the question changed:

You are using the same type, Container, for input and output. But your input and output types are distinct: your input is vector<string>, whereas your output is vector<int>. No wonder that C++ refuses to compile this.

Your problem is now to deduce the return type from the input types. Generally, C++ cannot do that. It’s as simple as that: overload resolution and template resolution only happens based on the input arguments, never on the return type (in some cases elaborate tricks involving proxy objects and implicit casts can be used to work around this but let’s not go there).

The simplest and most idiomatic solution is just to specify the return element type manually when calling the function, as in:

foomatic = mymap<int>(bar, [] (string s)->int {return atoi(s.c_str());});

This requires that the return element type be put first in the template argument list:

template <
    typename ResultType,
    template<typename> class Container,
    typename InputType,
    typename UnaryOp>
Container<ResultType> mymap(Container<InputType> c, UnaryOp op) { ... }

However, that does not work because std::vector does not fit the declaration of template<typename> class. Why? Simple reason: because it has more than just one template argument. In particular, the standard says that it has at least one extra template argument to specify the allocator.

Solution: declare the template argument as template<typename, typename> class, right?

No. Now, this does work for some standard library implementations. But besides the mandated two template arguments, the containers may have additional template arguments that take default values (this is often used to pass policy classes to a container, for example; the allocator is already such a policy class).

This is a fundamental problem: we cannot declare Container so that it conforms to all possible type signatures of containers in C++. So this solution, too, is a no-go.

The best solution is unfortunately more complicated, we need to rebind the container type explicitly. This we can do via an extra metafunction:

template <typename C, typename T>
struct rebind;

We need to partially specialize this metafunction for each possible number of template parameters. For example, to make it work with the minimal std::vector, we’d need the following partial specialization:

template <
    template <typename, typename> class C,
    typename Old,
    typename New,
    typename A>
struct rebind<C<Old, A>, New> {
    typedef typename A::template rebind<New> Rebound;
    typedef C<New, typename Rebound::other> type;
};

This looks daunting. What it does is take an existing std::vector<foo> and a type bar and rewrite it to a std::vector<bar>. The tricky part is that we also need to rewrite the allocator type. This is done via the rather complicated Rebound declaration.

Now we can write your function, and invoke it:

template <
    typename ResultType,
    typename C,
    typename UnaryOp>
typename rebind<C, ResultType>::type
mymap(C const& c, UnaryOp op)
{
    typename rebind<C, ResultType>::type result;
    for(typename C::const_iterator i = c.begin();
        i != c.end();
        i++)
    {
        result.push_back(op(*i));
    }

    return result;
}

int main() {
    vector<string> bar;
    bar.push_back("1");
    bar.push_back("2");
    bar.push_back("3");
    vector<int> foomatic =
        mymap<int>(bar, [] (string s)->int {return atoi(s.c_str());});
}

Piece of cake. A really, really, complicated cake.

Answer to old question:

If you have a template parameter that is itself a class template, you need to declare it as such:

template <
    template<typename> class Container,
    typename ResultType,
    typename UnaryOp>
Container<ResultType> mymap(Container<ResultType> c, UnaryOp op) { ... }

The template<typename> class Container mimics the class template declaration syntax and tells the compiler that “Container is a class template that expects a single template argument.”

But libraries usually avoid these nested template declarations and instead rely on traits/metafunctions to communicate such information. That is, it would usually be written as follows:

template <typename Container, typename UnaryOp>
Container mymap(Container c, UnaryOp op) {
    typedef typename Container::value_type ResultType;
}

(The typename in the typedef is necessary because the name is a dependent name and C++ cannot figure out that this it names a type.)

This example mimics the standard library convention of having a typedef value_type inside each container for its associated value type. Other libraries may follow different schemas. For example, I am contributing to a library that uses external metafunctions that work as follows:

template <typename Container, typename UnaryOp>
Container mymap(Container c, UnaryOp op) {
    typedef typename Value<Container>::Type ResultType;
}

The idea is the same, the only difference is that Container::value_type has been “outsourced” to an independent type.

You need something along the lines of:

template<typename Container, typename UnaryOp>
auto mymap(Container c, UnaryOp op) -> Container::rebind<decltype(op(*c.begin()))>
{
    typedef typename Container::value_type InputType;
    typedef decltype( op( InputType() ) ) ResultType;
    typedef typename Container::rebind<ResultType> ResultContainer;

    // ...
}

You can use a trick known as auto_cast, which we will rewrite a little bit to be specific to containers.

template<typename container> struct auto_cast_container {
    container c;
    template<typename out_type> operator out_type() {
        return out_type(c.begin(), c.end());
    }
};

template<typename Container, typename UnaryOperator>
auto 
mymap(const Container& c, UnaryOperator op)
-> auto_cast_container<std::vector<decltype(op(*c.begin()))>> {
    std::vector<decltype(op(*c.begin()))> retval;
    std::for_each(c.begin(), c.end(), [&](decltype(*c.begin())& ref) {
        retval.push_back(op(ref));
    });
    auto_cast_container<std::vector<decltype(op(*c.begin()))>> return_value;
    return_value.c = std::move(retval);
    return return_value;
}

Effectively, the templated conversion operator allows for conversion to any type which will accept the begin/end constructor. This means that you can map from a vector to a list, if you like, and it can also map pairs into associative containers and back again, should you need it. If you're hunting for efficiency this can be tuned further but I left that out for clarity.

Edit: Konrad's comment pointed out a couple of logical flaws. I also improved the safety and transparency of the system by using decltype in all appropriate cases.