10
\$\begingroup\$

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 <iostream>
#include <limits>
#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[std::numeric_limits<int>::max() >> 2];
};

template<typename T>
constexpr List<T>::List()
: length {0}
, array {0}
{
}

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

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;
  for (int i = 0; i < l.length; ++i)
  {
    l.array[i] = array[i + 1];
  }
  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
{
  for (int i = l.length - 1; i >= 0; --i)
  {
    l.array[i + length] = l.array[i];
  }
  for (int i = 0; i < length; ++i)
  {
    l.array[i] = array[i];
  }
  l.length += length;
  return l;
}

template<typename T>
constexpr List<T> List<T>::reverse() const
{
  List<T> l;
  l.length = length;
  for (int i = 0; i < l.length; ++i)
  {
    l.array[i] = array[length - i - 1];
  }
  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>
struct LT
{
  T pivot;
  constexpr bool operator()(T t) const
  {
    return t < pivot;
  }
};

template<typename T>
struct GE
{
  T pivot;
  constexpr bool operator()(T t) const
  {
    return t >= pivot;
  }
};

template<typename T>
constexpr List<T> List<T>::sort() const
{
  if (length == 0)
  {
    return *this;
  }
  return tail().filter(LT<T> {head()}).sort().add(head())
  .merge(tail().filter(GE<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()
{
  constexpr std::size_t n = range(0, 300).reverse().sort().sum();
  std::cout << n << std::endl;
}
\$\endgroup\$
  • 3
    \$\begingroup\$ You could allow the user of a List to pass the desired size as a second integer template parameter. Using that int max based constant is very inflexible. \$\endgroup\$ – glampert Sep 1 '15 at 19:10
  • 1
    \$\begingroup\$ May I ask why the list size is MAX_INT / 4? Was that an arbitrary choice? \$\endgroup\$ – U007D Jul 9 '16 at 4:34
  • 1
    \$\begingroup\$ yeah...that's a lot of memory to use \$\endgroup\$ – Benjamin Aug 20 '18 at 19:57
7
\$\begingroup\$

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<int>::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 < and >= 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 <typename T>
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<(const Goofy &g2) const { return num < g2.num; }

    friend std::ostream &operator<<(std::ostream &out, const Goofy &g2) {
        return out << g2.num;
    }
private:
    T num;
};

template <typename T>
constexpr Goofy<T> operator+(const Goofy<T> &g1, const Goofy<T> &g2)
{
    Goofy<T> result(g1);
    result += g2;
    return result;
}

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

int main()
{
  constexpr List<Goofy<float>> 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
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.