Sum of vector of vectors of vectors ... of integers

Question

I'm trying to sum all the elements of a vector of vectors of vectors ... of integers: something like a std::vector<std::vector<std::vector<std::vector<int>>>> where there's no need to every layer have the same size.

I would like to accomplish it using template, so I did it:

namespace nn
{
    template < class T >
    int sumAllElements(std::vector<T> v)
    {
        int size = v.size();
        int output = 0;

        for ( int i = 0 ; i < size ; i++ )
        {
                                                //should call the function below 
            output += sumAllElements( v[ i ] ); //or this function, depending in 
                                                //which "layer" we are
        }

        return output;
    }

    int sumAllElements(std::vector<int> v)
    {
        int size = v.size();
        int output = 0;

        for ( int i = 0 ; i < size ; i++ )
        {
            output += v[ i ]; //we've reached the bottomest layer,
                              //so just sum everybory
        }

        return output;
    }
}

BUT, this is happening:

CMakeFiles\test.dir/objects.a(main.cpp.obj): In function `main':
D:/test/main.cpp:49: undefined reference to `int nn::sumAllElements<std::vector<int, std::allocator<int> > >(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >)'
collect2.exe: error: ld returned 1 exit status
mingw32-make.exe[3]: *** [CMakeFiles\test\build.make:141: test.exe] Error 1
mingw32-make.exe[2]: *** [CMakeFiles\Makefile2:67: CMakeFiles/test.dir/all] Error 2
mingw32-make.exe[1]: *** [CMakeFiles\Makefile2:79: CMakeFiles/test.dir/rule] Error 2
mingw32-make.exe: *** [Makefile:117: test] Error 2

I really don't know why...

Thanks in advance.

Not sure why this was downvoted. Name lookup in templates is non-trivial. — MSalters, Nov 07 '17 at 18:48
What about writing `int sumAllElements(int x)` instead of a `vector` and just `return x`? — zahir, Nov 07 '17 at 21:10
Given your last comments, this is related: https://stackoverflow.com/questions/495021/why-can-templates-only-be-implemented-in-the-header-file — Bob__, Nov 08 '17 at 09:11

score 2 · Answer 1 · answered Nov 07 '17 at 18:48

2

You can't call a function that hasn't been declared yet. Templates can sometimes make that problem go away, but not always. And this is one of the cases where you simple need a declaration of int sumAllElements(std::vector<int> v) prior to template < class T > int sumAllElements(std::vector<T> v)

answered Nov 07 '17 at 18:48

MSalters

173,980
10
155
350

Well, I just tried it, but didn't work: got the same error. – griloHBG Nov 07 '17 at 19:07
1

@HenriqueGarcia Give also the standard library a try, it's full of useful algorithms: https://ideone.com/VU8X8A – Bob__ Nov 07 '17 at 20:13
@Bob__, thanks. Indeed you're right. And I also realized that the (worst) problem is about how I organized the project, wich is in a comment of the accepted question. – griloHBG Nov 07 '17 at 23:35

kshanholtzer · Accepted Answer · 2017-11-07T19:42:02.000

2

Reading your error message. It looks like your functions are in a separate compilation unit from main.cpp. If your functions are in a .h file, #include the header file in main.cpp.

I would suggest using the template specialization declaration:

template<>
int sumAllElements(std::vector<int> v)
{
 ...   
}

Another, unrelated suggestion, would be to pass the vectors by const reference. Currently, you are passing them by value which could be costly if the vectors are large.

edited Nov 07 '17 at 19:42

answered Nov 07 '17 at 19:31

kshanholtzer

71
5

As you said, the problem was where I placed the function. I have a .h with the namespace nn with its functions sumAllElements and the declaration of a class; a .cpp with the definition of the class's methods and the namespace method (which are both of the sumAllElements forms); main.cpp, where I included the .h, but seems the sumAllElements can't be found... And I don't understand why... If I put these functions inside main.cpp, it works (just like @Bob__ did). – griloHBG Nov 07 '17 at 23:43
1

@HenriqueGarcia the `template<>` is template specialization. This means you are defining an explicit implementation for the `std::vector` type. I don't know why it is not compiling with the functions defined in a .h file. You would have to show all of your code and state which files they are in. – kshanholtzer Nov 08 '17 at 11:22

bolov · Answer 3 · 2017-11-07T21:39:02.697

You can use SFINAE to enable/disable the specialization that is needed:

template <class T, std::enable_if_t<std::is_arithmetic<T>::value, int> = 0>
auto sum_all(const std::vector<T>& v)
{
    T sum = 0;

    for (auto& e : v)
    {
        sum += e;
    }

    return sum;
}

template <class T, std::enable_if_t<!std::is_arithmetic<T>::value, int> = 0>
auto sum_all(const std::vector<T>& nested_v)
{
    decltype(sum_all(nested_v[0])) sum = 0;

    for (auto& e : nested_v)
    {
        sum += sum_all(e);
    }

    return sum;
}

See it on coliru

With C++17 you can have just one function (neat!):

template <class T>
auto sum_all(const std::vector<T>& nested_v)
{
    innermost_type_t<T> sum = 0;

    for (auto& e : nested_v)
    {
        if constexpr(std::is_arithmetic<T>::value)
            sum += e;
        else
            sum += sum_all(e);
    }

    return sum;
}

With innermost_type_t defined as:

template <class T> struct innermost_type
{
    using type = T;
};

template <class T> struct innermost_type<std::vector<T>>
{
    using type = typename innermost_type<T>::type;
};

template <class T>
using innermost_type_t = typename innermost_type<T>::type;

H%lly sh!t! hahahah Good to know. Thanks :) – griloHBG Nov 07 '17 at 23:45 — griloHBG, Nov 07 '17 at 23:45

Sum of vector of vectors of vectors ... of integers

3 Answers3