Compile-time equivalent to std::accumulate()
Asked Answered
D

2

7

I tried to code a basic, compile-time version of std::accumulate() by defining a class template that would recursively iterate through a given range and would add the elements at each iteration.

When compiling a test program using gcc 4.8.4 on Ubuntu 14.04, I get the following error:

compile-time-accumulate.cpp: In function ‘int main()’:
compile-time-accumulate.cpp:44:40: error: call to non-constexpr function ‘std::vector<_Tp, _Alloc>::const_iterator std::vector<_Tp, _Alloc>::cbegin() const [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::const_iterator = __gnu_cxx::__normal_iterator<const int*, std::vector<int> >; typename __gnu_cxx::__alloc_traits<typename std::_Vector_base<_Tp, _Alloc>::_Tp_alloc_type>::const_pointer = const int*]’
                               v.cbegin(),
                                        ^
compile-time-accumulate.cpp:46:32: error: ‘class __gnu_cxx::__normal_iterator<const int*, std::vector<int> >’ is not a valid type for a template non-type parameter
                               0>::value;

Here's the code:

Run it online

#include <iostream>
#include <vector>

template
<
    typename     ResultType,
    typename     IteratorType,
    IteratorType Iterator,
    int          RangeLength,
    ResultType   InitialValue
>
struct accumulator
{
    static_assert(RangeLength > 1, "The range length must be > 1");
    static constexpr ResultType value = InitialValue
                                      + accumulator<ResultType,
                                                    IteratorType,
                                                    Iterator + 1,
                                                    RangeLength - 1,
                                                    *Iterator>::value;
};

template
<
    typename     ResultType,
    typename     IteratorType,
    IteratorType Iterator,
    //int          RangeLength,
    ResultType   InitialValue
>
struct accumulator<ResultType, IteratorType, Iterator, 1, InitialValue>
{
    static constexpr ResultType value = InitialValue + *Iterator;
};


int main()
{
    std::vector<int> v = {4,5,6,7};

    const int a = accumulator<int,
                              decltype(v.cbegin()),
                              v.cbegin(),
                              4,
                              0>::value;

    std::cout << a << std::endl;
}

So basically, the standard doesn't allow the use of variables in template arguments, which is what I'm doing here:

const int a = accumulator<int,
                          decltype(v.cbegin()),
                          v.cbegin(),
                          4,
                          0>::value;

Q: What is the proper method for coding a class template (or any other "compile-time" computation mechanism) for achieving a similar result to std::accumulate() ?

(Ideally, one should be able pass custom ranges and binary operations like the real std::accumulate())

EDIT: The std::vector used in the code is just an example. I've also tried std::array and C-style arrays but I still had similar problems.

EDIT2: I don't want to use macros.

EDIT3: I don't want to use external libraries. The goal here is to do a simple, self-contained compile-time computation block. Class template was the my first idea, but I'm open to other suggestions/techniques.

Decorous answered 15/10, 2015 at 20:16 Comment(4)
std::vector storage is allocated during runtime. Thus, is not possible to iterate through a std::vector during compile time.Glomeration
If you used an integer_sequence instead of a vector, I think you could pull this off easier.Intendment
you may iterate over std::array as it's size is known at compile time. You cannot do that for std::vectorSwordfish
There's a set of constexpr containers here; accumulate is also provided.Trichinize
G
6

std::vector's storage is allocated during runtime. Thus, is not possible to iterate through a std::vector during compile time.

Now for std::array and raw arrays. Provided that your std::array variable is a constexpr you could use the following construction to accumulate it:

template<typename T, std::size_t N>
constexpr T compile_time_accumulator(std::array<T, N> const &A, int const i = 0) {
  return (i < N)? A[i] + compile_time_accumulator(A, i + 1) : T(0);
}

LIVE DEMO

And for raw arrays, provided also that they are declared constexpr, the following construction:

template<typename T, std::size_t N>
constexpr T compile_time_accumulator(T const (&A)[N], int const i = 0) {
  return (i < N)? A[i] + compile_time_accumulator(A, i + 1) : T(0);
}

LIVE DEMO

Now in C++14 things about constexpr are more relaxed and you could do the following:

template<typename T, std::size_t N>
constexpr T compile_time_accumulator(T const (&A)[N]) {
  T sum(T(0));

  for(int i = 0; i < N; ++i) {
    sum += A[i];
  }

  return sum;
}

LIVE DEMO

or

template<typename T, std::size_t N>
constexpr T compile_time_accumulator(std::array<T, N> const &A) {
  T sum(T(0));

  for(int i = 0; i < N; ++i) {
    sum += A[i];
  }

  return sum;
}

LIVE DEMO

Glomeration answered 15/10, 2015 at 20:47 Comment(8)
Interesting, I extended your example in order to take custom lambdas, which seems to work well. Thanks!Decorous
@865719 Nice but I would suggest use of std::plus as compile_time_accumulator<int, 4>(v, 0, std::plus<int>(), 42) instead.Glomeration
I agree :) On a related note: after reading a little bit more about constexpr (at least in C++11), it seems that calling std::accumulate() from a constexpr function is legal (cf. this example. However, do we have the guarantee that the constexpr function's code (i.e. ct_std_accumulate_std() in the code example) will be executed at compile time ?Decorous
@865719 sorry to disappoint you but std::accumulate is not constexpr. Thus, your example is not a compile time evaluation but rather a runtime evaluation.Glomeration
@865719 Also constexpr lambdas aren't allowed yet. Must be a gcc bug that accepts them. Clang complains about them. I didn't know also I've made a question here.Glomeration
You're right. I was writing this example when I figured it was weird that gcc compiled the constexpr function while the static_assert() was rejected.Decorous
On a positive note, as long as the custom operator is constexpr it seems that we can work around the lambda limitation :)Decorous
in c++14 error: statement not allowed in constexpr function for(int i = 0; i < N; ++i) { ^Unbolted
T
0

std::vector, as any other memory managing container, is, of course, not iterable during compile time. Given the tag C++11, I suggest using boost.fusion :)

Terrorism answered 15/10, 2015 at 20:23 Comment(0)

© 2022 - 2024 — McMap. All rights reserved.