当给出所有信息时，为什么编译器在编译期间不评估 constexpr 函数？

Question

这个

int main()
{
  std::cout << range(1, 11).reverse().sort().sum() << std::endl;
}

是 main 中的所有内容，正如代码所说，它创建一个从 1 到 10（含）的列表，将其反转，通过排序取消反转，并计算总和。因此输出应该是 55.

该代码更像是一个实验，（滥用）使用 C++14 中 constexpr 的宽松要求。我尽了最大努力创建了一个编译时列表 class，但真的做得还不够。 class虽然不完整，但还是可以模仿很多函数式风格的编程。

据我了解，constexpr 的要求是让编译器在编译时评估事物。所以我认为编译器可以简单地用常量 55 替换我的代码中的所有内容，但事实并非如此。该代码确实具有在编译时获得结果所需的一切。我错过了什么？

根据评论，我尝试使用 static_assert 中的结果来检查问题。 clang 和 gcc 都报错，我也没看懂，而且后者好像坏了...

铿锵

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

完整代码

#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;
}

Answer 1

I did my best to create a compile-time list class

虽然这与编译时列表完全不同 - 值存储在数组中，并且长度在插入期间发生变化。编译时列表将是非类型参数的可变参数模板，或类似于 Boost.MPL Integral Sequence Wrapper，或非类型参数的 Loki 样式递归列表。

您尝试编写的 - 并且 ecatmur 成功 - 编写的是一个运行时列表，有时可以将其删除。

具体来说，在您的代码中，List 成员不是常量； constexpr-runtime-list 解决方案是避免改变成员并跳过其他一些 constexpr 环，而编译时列表解决方案是使 type 的长度（和值）属性.

为了帮助您入门，这里有一个俗气且不完整的可变参数列表，以及您想要的一些算法：

template <int... Values> struct VList {};

template <int X, typename Xs> struct cat;
template <int X, int... Xs> struct cat<X, VList<Xs...>> {
    using result = VList<X, Xs...>;
};
template <typename Xs, int X> struct rcat;
template <int... Xs, int X> struct rcat<VList<Xs...>, X> {
    using result = VList<Xs..., X>;
};
template <typename L> struct reverse;
template <int X> struct reverse<VList<X>> { using result = VList<X>; };
template <int X, int Y> struct reverse<VList<X, Y>> { using result = VList<Y, X>; };
template <int X, int... Xs> struct reverse<VList<X, Xs...>> {
    using result = typename rcat<typename reverse<VList<Xs...>>::result, X>::result;
};
template <int From, int To> struct range;
template <int End> struct range <End,End> { using result = VList<End>; };
template <int From, int To> struct range {
    using result = typename cat<From, typename range<From+1,To>::result>::result;
};

int main()
{
  typename range<1,11>::result l;
  typename reverse<decltype(l)>::result r;
  return sizeof(l) + sizeof(r);
}

注意：

VList 只是一个类型包装器，它的内容无关紧要。我们同样可以使用 std::tuple<std::integral_constant<int, ...>...>
range 应该断言 From<=To，可以允许大步前进等
我们真的不需要中间 reverse 专业
cat真的应该叫push_front什么的，还有rcat、push_back。对于前者，我用 car 开始草图，并决定在上下文中可能故意模糊。此外，这对于递归版本来说更有意义。
X,Xs... 表示法基于 Haskell 的 x:xs 约定。当您将数据类型和算法转换为编译时操作时，函数式语言通常是寻找灵感的好地方。

Answer 2

灵感来自：C++1y/C++14: Assignment to object outside its lifetime is not allowed in a constant expression?

你的Listclass的private成员没有在编译期初始化，所以只能活在运行期，不能活在编译期。如果您进行更改以让它们阅读：

int length = 0;
T array[0x100] = {0};

你更进一步到一个新的编译错误；）。另一种方法是也在 constexpr 构造函数中正确初始化 array：

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

尽管正如 Useless 所提到的，可能 difficult/impossible 根本无法完成您想要的事情。

Answer 3

初始错误是 array 未在您的构造函数中初始化。您可以通过初始化来解决此问题：

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

之后你会运行陷入你使用的<algorithm>函数不是constexpr的问题；您可以通过将标准中的示例定义复制到您的实现中并标记您的副本来解决此问题 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

最后，您使用 lambda 作为过滤谓词（在 sort 中）； lambda 在常量表达式中是非法的。此处的解决方法是手动将 lambda 扩展为函数对象：

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());
}

通过这些更改，您的代码将在 clang 3.7 下编译，但不能在 gcc 5.2.0 下编译。

gcc 5.2.0 有两个错误：

首先，它不喜欢reverse_copy中的组合递减-间接*(--last)；这很容易修复：

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;
}

其次，它不喜欢将指针与array进行比较；但是，可以通过将 array + length 更改为 &array[length].

来满足

Live example 进行了这些更改（适用于 clang 3.7 和 gcc 5.2.0）。

当给出所有信息时，为什么编译器在编译期间不评估 constexpr 函数？

Why isn't the compiler evaluating a constexpr function during compilation when every information is given?

c++

constexpr

c++14