Compile-time list in C++

Everything is evaluated in compile-time. You will need a C++14 compiler. The compilation time is quite long, and with a bigger list input, you'll get some error messages like constexpr evaluation hit maximum step limit.

```
#include
#include
#include

template
class List
{
template
friend std::ostream &operator &);
public:
constexpr List();
constexpr List(std::initializer_list);
constexpr T head() const;
constexpr List tail() const;
constexpr List add(T) const;
constexpr List merge(List) const;
constexpr List reverse() const;
template
constexpr List filter(Filter) const;
constexpr List sort() const;
constexpr T sum() const;
private:
int length;
T array[std::numeric_limits::max() >> 2];
};

template
constexpr List::List()
: length {0}
, array {0}
{
}

template
constexpr List::List(std::initializer_list l)
: length {static_cast(l.size())}
, array {0}
{
for (auto it = l.begin(); it != l.end(); ++it)
{
array[it - l.begin()] = *it;
}
}

template
constexpr T List::head() const
{
return array[0];
}

template
constexpr List List::tail() const
{
List l;
l.length = length - 1;
for (int i = 0; i
constexpr List List::add(T t) const
{
List l {*this};
l.array[l.length++] = t;
return l;
}

template
constexpr List List::merge(List l) const
{
for (int i = l.length - 1; i >= 0; --i)
{
l.array[i + length] = l.array[i];
}
for (int i = 0; i
constexpr List List::reverse() const
{
List l;
l.length = length;
for (int i = 0; i
template
constexpr List List::filter(Filter f) const
{
List l;
for (int i {0}; i
struct LT
{
T pivot;
constexpr bool operator()(T t) const
{
return t
struct GE
{
T pivot;
constexpr bool operator()(T t) const
{
return t >= pivot;
}
};

template
constexpr List List::sort() const
{
if (length == 0)
{
return *this;
}
return tail().filter(LT {head()}).sort().add(head())
.merge(tail().filter(GE {head()}).sort());
}

template
constexpr T List::sum() cons

I confess to not being entirely clear as to the purpose of this code. It seems to me that any list known at compile time could more easily and more correctly handled by other forms of preprocessing. With that said, though, here are some comments on this code.

Think about real machines

The code for the List class currently includes this data member:

T array[std::numeric_limits::max() >> 2];

On my machine, this attempts to allocate 2GB on the stack for an int-based List. That's a rather large amount of memory to attempt to allocate for every List! Perhaps this could be trimmed to some reasonable value.

Reduce the number of requirements on template types

The code requires a number of operations on the underlying T type. It requires both = but that requirement can be relaxed somewhat by defining GE's operator like this:

constexpr bool operator()(T t) const {
    return !(t < pivot);
}

Pass const references where practical

Rather than passing by value, it would probably make more sense in the general case to pass by const reference. So for example, the previous function could be written like this instead:

constexpr bool operator()(const T &t) const {
    return !(t < pivot);
}

In fact, one of the only places that can't be treated this way is the argument to merge() which must be passed by value.

Try it with a non-primitive type

Whenver you're creating templated code, carefully consider just how it might be used and what requirements it may demand of the underlying type. One technique I use is to wrap a primitive type inside a goofy minimalistic wrapper for testing:

template 
class Goofy
{
public:
    constexpr Goofy(T n = 0) : num(n) { } 
    constexpr Goofy(const Goofy &g2) : num(g2.num) { }
    constexpr Goofy &operator=(const Goofy &g2) { num = g2.num; return *this; }
    constexpr Goofy &operator+=(const Goofy &g2) { num += g2.num; return *this; }
    constexpr bool operator
constexpr Goofy operator+(const Goofy &g1, const Goofy &g2)
{
    Goofy result(g1);
    result += g2;
    return result;
}

This represents a minimal interface that can then be tested with your template:

int main()
{
  constexpr List> list{0, 5, 8, 13, 1, 7};
  std::cout << list << std::endl;
  std::cout << list.reverse() << std::endl;
  std::cout << list.sort() << std::endl;
  constexpr auto m = list.sum();
  std::cout << m << std::endl;
}

Sample output

{0, 5, 8, 13, 1, 7}
{7, 1, 13, 8, 5, 0}
{0, 1, 5, 7, 8, 13}
34

StackExchange Code Review Q#102495, answer score: 8