This
int main()
{
std::cout << range(1, 11).reverse().sort().sum() << std::endl;
}
is everything in main, and as the code says, it creates a list from 1 to 10 inclusive, reverses it, un-reverses it by sorting, and calculates the sum. The output should thus be 55.
The code is rather an experiment, (ab)using the relaxed requirements of constexpr in C++14. I did my best to create a compile-time list class, but really couldn't go far enough. The class is incomplete, but it still can imitate a lot of functional style programming.
As far as I understand, the requirements of constexpr are there to let the compiler evaluate things in compile-time. So I thought the compiler can simply replace everything with a constant 55 for my code, but it didn't. The code really has everything it needs to get the result in compile-time. What am I missing?
From the comments, I tried to check the problem by using the result in static_assert. clang and gcc both gives me an error, but I failed to understand either, and the latter seems to be broken...
clang
a.cpp:142:17: error: static_assert expression is not an integral constant expression
static_assert(range(1, 11).reverse().sort().sum() == 55, "");
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cpp:60:23: note: assignment to object outside its lifetime is not allowed in a constant
expression
l.array[l.length++] = t;
^
a.cpp:134:9: note: in call to '&l->add(1)'
l = l.add(a);
^
a.cpp:142:17: note: in call to 'range(1, 11, 1)'
static_assert(range(1, 11).reverse().sort().sum() == 55, "");
^
1 error generated.
gcc
main.cpp: In function 'int main()':
main.cpp:142:3: error: non-constant condition for static assertion
static_assert(range(1, 11).reverse().sort().sum() == 55, "");
^
main.cpp:142:38: error: 'constexpr List<T> List<T>::reverse() const [with T = int]' called in a constant expression
static_assert(range(1, 11).reverse().sort().sum() == 55, "");
^
main.cpp:74:19: note: 'constexpr List<T> List<T>::reverse() const [with T = int]' is not usable as a constexpr function because:
constexpr List<T> List<T>::reverse() const
^
main.cpp:74:19: sorry, unimplemented: unexpected AST of kind result_decl
main.cpp:74: confused by earlier errors, bailing out
full code
#include <cstdint>
#include <iostream>
#include <limits>
#include <algorithm>
#include <initializer_list>
template<typename T>
class List
{
template<typename T2>
friend std::ostream &operator<<(std::ostream &, const List<T2> &);
public:
constexpr List();
constexpr List(std::initializer_list<T>);
constexpr T head() const;
constexpr List<T> tail() const;
constexpr List<T> add(T) const;
constexpr List<T> merge(List<T>) const;
constexpr List<T> reverse() const;
template<typename Filter>
constexpr List<T> filter(Filter) const;
constexpr List<T> sort() const;
constexpr T sum() const;
private:
int length;
T array[0x100];
};
template<typename T>
constexpr List<T>::List()
: length(0)
{
}
template<typename T>
constexpr List<T>::List(std::initializer_list<T> l)
: length {static_cast<int>(l.size())}
{
std::copy(l.begin(), l.end(), array);
}
template<typename T>
constexpr T List<T>::head() const
{
return array[0];
}
template<typename T>
constexpr List<T> List<T>::tail() const
{
List<T> l;
l.length = length - 1;
std::copy_n(array + 1, l.length, l.array);
return l;
}
template<typename T>
constexpr List<T> List<T>::add(T t) const
{
List<T> l {*this};
l.array[l.length++] = t;
return l;
}
template<typename T>
constexpr List<T> List<T>::merge(List<T> l) const
{
std::copy_backward(l.array, l.array + l.length, l.array + l.length + length);
std::copy_n(array, length, l.array);
l.length += length;
return l;
}
template<typename T>
constexpr List<T> List<T>::reverse() const
{
List<T> l;
l.length = length;
std::reverse_copy(array, array + length, l.array);
return l;
}
template<typename T>
template<typename Filter>
constexpr List<T> List<T>::filter(Filter f) const
{
List<T> l;
for (int i {0}; i < length; ++i)
{
if (f(array[i]))
{
l = l.add(array[i]);
}
}
return l;
}
template<typename T>
constexpr List<T> List<T>::sort() const
{
if (length == 0)
{
return *this;
}
return tail().filter([&](T t) {return t < head();}).sort().add(head())
.merge(tail().filter([&](T t) {return t >= head();}).sort());
}
template<typename T>
constexpr T List<T>::sum() const
{
if (length == 0)
{
return T {};
}
return head() + tail().sum();
}
template<typename T>
std::ostream &operator<<(std::ostream &os, const List<T> &l)
{
os << '{';
for (int i {0}; i < l.length - 1; ++i)
{
os << l.array[i] << ", ";
}
return os << l.array[l.length - 1] << '}';
}
inline constexpr List<int> range(int a, int b, int c = 1)
{
List<int> l;
while (a < b)
{
l = l.add(a);
a += c;
}
return l;
}
int main()
{
static_assert(range(1, 11).reverse().sort().sum(), "");
std::cout << range(1, 11).reverse().sort().sum() << std::endl;
}
The initial error is that array is not initialized in your constructor. You can fix this by initializing it:
template<typename T>
constexpr List<T>::List()
: length(0)
, array{}
{
}
After that, you will run into the problem that the <algorithm> functions you use are not constexpr; you can fix this by copying the example definitions from the standard into your implementation and marking your copies constexpr:
template<class BidirIt, class OutputIt>
constexpr OutputIt reverse_copy(BidirIt first, BidirIt last, OutputIt d_first)
{
while (first != last) {
*(d_first++) = *(--last);
}
return d_first;
}
// etcetera
Finally, you're using lambdas as filter predicates (in sort); lambdas are illegal in a constant-expression. The fix here is to expand the lambdas by hand into function objects:
template<typename T>
constexpr List<T> List<T>::sort() const
{
if (length == 0)
{
return *this;
}
T pivot = head();
struct Lt { T pivot; constexpr bool operator()(T t) const { return t < pivot; } };
struct Ge { T pivot; constexpr bool operator()(T t) const { return t >= pivot; } };
return tail().filter(Lt{pivot}).sort().add(pivot)
.merge(tail().filter(Ge{pivot}).sort());
}
With these changes your code will compile under clang 3.7, though not gcc 5.2.0.
gcc 5.2.0 has two bugs:
First, it doesn't like the combined decrement-indirection *(--last) in reverse_copy; this is easily fixed:
template<class BidirIt, class OutputIt>
constexpr OutputIt reverse_copy(BidirIt first, BidirIt last, OutputIt d_first)
{
while (first != last) {
--last;
*(d_first++) = *last;
}
return d_first;
}
Second, it doesn't like comparing pointers into array; however, it can be satisfied by changing array + length to &array[length].
Live example with these changes (works with clang 3.7 and gcc 5.2.0).