decltype does not resolve nested vectors. How can

Question

I am trying to overload the + operator to deal with nested vectors. I thought the function would call itself until the nested vectors resolve to basic types, but instead I get a huge list of errors when I compile it. My vector operations that I have defined work for basic types, but not a variable amount of nested vectors. The only operation that does work for nested vectors is the << operator.

main.cpp

#include <iostream>
#include <vector>
#include <algorithm>

template<typename T1>
std::ostream& operator<<(std::ostream& stream, std::vector<T1> r){
    if(r.size() == 0){
        return stream;
    }
    else{
        stream << "(";
        for(int i = 0; i < r.size(); i++){
            if(i < (r.size() - 1)){
                stream << r[i] << ", ";
            }
            else{
                stream << r[i] << ")";
            }
        }
    }
    return stream;
};

template<typename T1, typename T2>
auto operator+(const std::vector<T1>& l, const std::vector<T2>& r) 
-> std::vector<decltype((l[0] + r[0]))>{
    typedef decltype((l[0] + r[0])) type;
    std::vector<type> ans;
    if(l.size() == std::max(l.size(),r.size()))
        std::transform(r.begin(), r.end(), l.begin(), std::back_inserter(ans), std::plus<type>());
    else
        std::transform(l.begin(), l.end(), r.begin(), std::back_inserter(ans), std::plus<type>());
    return ans;
};

int main(){

    std::vector<std::vector<int>> vecvec = {{1,2,3},{4,5,6},{7,8,9}};
    std::vector<int> vec = {1,2,3};

    //Both output statements compile
    std::cout << vec    << std::endl;
    std::cout << vecvec << std::endl;

    //Does not compile 
    vecvec = vecvec + vecvec;

    //Does compile
    vec = vec + vec;

    return 0;
} 

Now I am not able to do type promotion with nested vectors. I think I need std::plus T1 or std::plus T2 depending on promotion rules.

template <typename T1, typename T2>
struct Add : std::plus<T1> { };//<- Here

template <typename T1, typename T2>
struct Add<std::vector<T1>, std::vector<T2>>
{   
    auto operator()(const std::vector<T1>& l, const std::vector<T2>& r)
        -> std::vector<decltype(Add<T1,T2>{}(l[0], r[0]))>
    {
        using type = decltype(Add<T1,T2>{}(l[0], r[0]));
        std::vector<type> ans;

        if(l.size() == std::max(l.size(),r.size()))
            std::transform(r.begin(), r.end(), l.begin(), std::back_inserter(ans), Add<T1,T2>{});
        else
            std::transform(l.begin(), l.end(), r.begin(), std::back_inserter(ans), Add<T1,T2>{});
        return ans;
    };
};

template <typename T1, typename T2>
auto operator+(const std::vector<T1>& lhs, const std::vector<T2>& rhs)
    -> decltype(Add<std::vector<T1>, std::vector<T2>>{}(lhs, rhs))
{
    return Add<std::vector<T1>, std::vector<T2>>{}(lhs, rhs);
}

I tried this and got an output of 2 instead of 2.5.

int main(){
    p(int) e = {1};
    p(double) q = {1.5};
    std::cout << (e + q) << std::endl;
    return 0;
}

Answer 1

The problem you're running into has to do with name lookup. You are doing unqualified name lookup on operator+ here:

template<typename T1, typename T2>
auto operator+(const std::vector<T1>& l, const std::vector<T2>& r) 
-> std::vector<decltype((l[0] + r[0]))> {
                        ^^^^^^^^^^^^^

From [basic.scope.pdecl]:

The point of declaration for a name is immediately after its complete declarator (Clause 8) and before its initializer (if any)

And in that function, the "complete declarator" includes the trailing-return-type. So your operator+ template will not be in scope until after the declarator. That is, the {

The other problem is std::plus. std::plus will never find your operator+ since it won't have existed yet at the time that std::plus is defined.

The simplest solution, in C++14, is to drop the trailing return type (it'll be deduced correctly anyway) and to replace std::plus with a simple lambda:

auto plus = [](const type& lhs, const type& rhs) { return lhs + rhs; };

Without C++14, you'll have to forward everything to another function so that name lookup can succeed. You can either use an ADL trick for that, but I think a template is a little easier to understand. Here's a working solution:

template <typename T1, typename T2>
struct Add : std::plus<T1> { };

template <typename T1, typename T2>
struct Add<std::vector<T1>, std::vector<T2>>
{   
    auto operator()(const std::vector<T1>& l, const std::vector<T2>& r)
        -> std::vector<decltype(Add<T1,T2>{}(l[0], r[0]))>
    {
        using type = decltype(Add<T1,T2>{}(l[0], r[0]));
        std::vector<type> ans;

        if(l.size() == std::max(l.size(),r.size()))
            std::transform(r.begin(), r.end(), l.begin(), std::back_inserter(ans), Add<T1,T2>{});
        else
            std::transform(l.begin(), l.end(), r.begin(), std::back_inserter(ans), Add<T1,T2>{});
        return ans;
    };
};

template <typename T1, typename T2>
auto operator+(const std::vector<T1>& lhs, const std::vector<T2>& rhs)
    -> decltype(Add<std::vector<T1>, std::vector<T2>>{}(lhs, rhs))
{
    return Add<std::vector<T1>, std::vector<T2>>{}(lhs, rhs);
}

Answer 2

My other answer on here explains why your approach failed and one possible approach for a solution. I just thought of a much, much simpler one that I thought was worth sharing.

The problem is that you can't use a trailing return type because the function name itself isn't in scope yet, so you can't use recursion in that way. However, there's nothing to stop you from writing a metafunction to determine what the return type should be. That metafunction is very simple:

template <typename T1, typename T2>
struct nested_common_type :std::common_type<T1, T2> { };

template <typename T1, typename T2>
struct nested_common_type<std::vector<T1>, std::vector<T2>> {
    using type = std::vector<typename nested_common_type<T1,T2>::type>;
};

template <typename T1, typename T2>
using vector_common_type_t = std::vector<typename nested_common_type<T1,T2>::type>;

And once we have the return type, we can just write one normal operator+:

template <typename T1, typename T2,
          typename R = vector_common_type_t<T1,T2>>
R operator+(const std::vector<T1>& l, const std::vector<T2>& r)
{
    R ans;
    std::transform(l.begin(),
                   l.begin() + std::min(l.size(), r.size()),
                   r.begin(),
                   std::back_inserter(ans),
                   [](const T1& lhs, const T2& rhs){ return lhs + rhs; });
    return ans;
}