C++的杂七杂八：constexpr与编译期计算

社区（ http://purecpp.org/ ）里有朋友提出了编译期分割字符串的需求，大家在群里进行了热烈的讨论，也做了许多尝试，但并没有得出确定的结果。本文作者试图对C++11/14里的新关键字constexpr进行编译期计算的总结和探讨，并在最后结合constexpr给出C++在编译期分割字符串的方法。

我们先来看一段求阶乘（factorial）的算法：

size_t factorial(size_t n) noexcept {     return (n == 0) ? 1 : n * factorial(n - 1); }

很明显，这是一段运行期算法。程序运行的时候，传递一个值，它可以是一个变量，也可以是一个常量：

int main(void) {     std::cout << factorial(10) << std::endl;     return 0; }

如果程序仅仅像这样传递常量，我们可能会希望能够让它完全在编译的时候就把结果计算出来，那么代码改成这样或许是个不错的选择：

template <size_t N> struct factorial {     enum : size_t { value = N * factorial<N - 1>::value }; };  template <> struct factorial<0> {     enum : size_t { value = 1 }; };  int main(void) {     std::cout << factorial<10>::value << std::endl;     return 0; }

只是用起来会稍显麻烦点，但好处是运行期没有任何时间代价。

像上面这种运用模板的做法，算是最简单的模板元编程了。对C++模板来说，类型和值是同一种东西；同时，又由于C++的模板有了“Pattern Matching”（即特化和偏特化），同时又允许模板的递归结构（见上面factorial中使用factorial的情况），于是C++的模板是图灵完全的一种独立于C++的语言。理论上来说，我们可以利用它在编译期完成所有计算——前提是这些计算的输入都是literal的。

从C++11开始，我们有了constexpr specifier。它可以被用于变量，及函数上，像这样：

template <size_t N> struct t_factorial_ {     enum : size_t { value = N * t_factorial_<N - 1>::value }; };  template <> struct t_factorial_<0> {     enum : size_t { value = 1 }; };  template <size_t N> constexpr auto t_factorial = t_factorial_<N>::value;  int main(void) {     std::cout << t_factorial<10> << std::endl;     return 0; }

当然了，上面更直接的用法是这样：

constexpr size_t c_factorial(size_t n) noexcept {     return (n == 0) ? 1 : n * c_factorial(n - 1); }

在C++11中，constexpr还有诸多限制，但到了C++14，它似乎有点过于强大了。比如我们可以在函数中写多行语句，定义变量，甚至是循环：

// runtime version template <typename T, size_t N> size_t r_count(T&& v, const T(&arr)[N]) noexcept {     size_t r = 0;     for (const auto& a : arr) if (v == a) ++r;     return r; }  // constexpr version template <typename T, size_t N> constexpr size_t c_count(T&& v, const T(&arr)[N]) noexcept {     size_t r = 0;     for (const auto& a : arr) if (v == a) ++r;     return r; }

就如同我们在写的只是一个普通函数，之后在函数的最前面加上constexpr它马上就可以在编译期执行了。

constexpr同样带来了强大的类型计算能力。我们简单的来看个例子，实现一个“types_insert”（Reference： C++的杂七杂八：使用模板元编程操作类型集合 ）：

template <typename...> struct types {};  template <typename T, typename... U> constexpr auto insert(types<U...>) noexcept {     return types<T, U...>{}; }

可以看到，对于这种简单的类型计算，constexpr比模板元的实现要清晰很多。

不过，由于函数模板缺少偏特化，因此需要编译期分支判断的“types_assign”是没办法直接写出来的（在这里无法短路求值的std::conditional并没有什么用）。要知道，函数重载虽然强大，但仅能做编译期类型，而不是数值的Pattern Matching，这点是不如类模板的偏特化/特化的。

不过我们可以利用类模板的偏特化来模拟函数模板的偏特化：

template <int N, typename T> struct impl_ {     constexpr static auto assign(void) noexcept     {         return insert<T>(impl_<N - 1, T>::assign());     } };  template <typename T> struct impl_<0, T> {     constexpr static auto assign(void) noexcept     {         return types<>{};     } };  template <int N, typename T> constexpr auto assign(void) noexcept {     return impl_<N, T>::assign(); }

但是说实话，我并不喜欢这样，这种写法丧失了函数模板的简洁性。一般来说，大家也不会用constexpr做太复杂的类型计算，这里反而用模板元来做会更加清晰些。从上面可以看出来，在做类型计算的时候，return返回的数值并不是我们需要的，而类型结果一般会用decltype取出来。在这种情况下，不使用constexpr，仅用普通函数都是可以的。

真正让人眼前一亮的，应该还是上面c_count的写法。利用模板元做数值计算其实是它的短板。撰写复杂不说，还有不少的局限性。

比如c_count可以这样用：

template <size_t N> struct Foo { enum : size_t { value = N }; };  int main(void) {     std::cout << Foo<c_count(',', "1, 2, 3, 4, 5, 6, 7, 8, 9, 0")>::value << std::endl;     return 0; }

而模板元对string literal这类数值做计算是比较麻烦的，template non-type arguments被限制为常整数（包括枚举），或指向外部链接对象的指针（严格来说不止这这些。Reference：Template parameters and template arguments）。

理论上来说，如果constexpr发挥作用，运行时是没有性能损耗的。我们用一个例子来测试下实际的效果：

// https://github.com/mutouyun/capo/blob/master/capo/stopwatch.hpp #include "stopwatch.hpp"  size_t r_fib(size_t n) noexcept {     if (n == 0) return 0;     if (n == 1) return 1;     return r_fib(n - 1) + r_fib(n - 2); }  constexpr size_t c_fib(size_t n) noexcept {     if (n == 0) return 0;     if (n == 1) return 1;     return c_fib(n - 1) + c_fib(n - 2); }  template <size_t N> struct t_fib_ { enum : size_t { value = t_fib_<N - 1>::value + t_fib_<N - 2>::value }; }; template <> struct t_fib_<0> { enum : size_t { value = 0 }; }; template <> struct t_fib_<1> { enum : size_t { value = 1 }; }; template <size_t N> constexpr auto t_fib = t_fib_<N>::value;  ////////////////////////////////////////////////////////////////  int main(void) {     constexpr size_t n = 40;     capo::stopwatch<> sw;      sw.start();     size_t r1 = r_fib(n);     std::cout << r1 << ": " << sw.elapsed<std::chrono::milliseconds>() << "ms" << std::endl;      sw.start();     size_t r2 = c_fib(n);     std::cout << r2 << ": " << sw.elapsed<std::chrono::milliseconds>() << "ms" << std::endl;      sw.start();     size_t r3 = t_fib<n>;     std::cout << r3 << ": " << sw.elapsed<std::chrono::milliseconds>() << "ms" << std::endl;      return 0; }

g++ -v：version 5.3.1 20160413 (Ubuntu 5.3.1-14ubuntu2)

编译命令行：g++ -std=c++14 -O3 -I. ./test.cpp

测试结果：

引用

测试结果并不理想。按理来说，c_fib应该和t_fib一样不需要任何时间才对。下面我们尝试修改一下c_fib的测试case：

sw.start(); const size_t r2 = c_fib(n); std::cout << r2 << ": " << sw.elapsed<std::chrono::milliseconds>() << "ms" << std::endl;

我们可以看到，马上，测试的结果发生了变化，耗时变为0ms。

从实测上来看，除了const之外，如果把r2改为static变量（定义时马上初始化，因此c_fib只会被调用一次。若是定义后再对static变量赋值，则结果和普通变量一样），或constexpr变量，或者不要r2，直接将r_fib(n)放在std::cout后面输出结果，在这些情况都会触发constexpr的编译期计算。

当然了，如果像这样写：

template <size_t N> struct Foo { enum : size_t { value = N }; };  size_t xx = Foo<c_fib(40)>::value;

或者这样写：

char cc[c_fib(n)];

是一定会触发编译期计算的。

constexpr并不会尽可能的让expressions在编译期执行，只是表示expressions能在编译期执行。至于真正执行的时机是编译期还是运行期，依赖编译器自己的选择。见 constexpr specifier (since C++11) ：

引用

The constexpr specifier declares that it is possible to evaluate the value of the function or variable at compile time. Such variables and functions can then be used where only compile time constant expressions are allowed (provided that appropriate function arguments are given).

另外，需要注意的一点是，函数的参数不能被定义为constexpr。也就是说，我们不能在编译期使用constexpr函数的参数，哪怕我们给它传递的参数确实是一个literal：

constexpr size_t test(size_t n) noexcept {     return Foo<n>::value; // error: ‘n’ is not a constant expression }  const size_t xx = test(123);

自然，这样也是不行的：

constexpr size_t cube(size_t n) noexcept {     constexpr size_t cp = c_power(n, 3); // error: ‘n’ is not a constant expression     return cp; }

简单来说：

• 除了语法上的必须之外（比如在模板参数上使用函数），constexpr函数是否在编译期执行，取决于编译器的选择；
• 不论该函数是否在编译期执行，constexpr函数里，参数都只是普通的变量。

C++这样设计估计是考虑到constexpr函数需要同时具备编译期和运行期执行的能力吧。如果我们需要在constexpr函数内使用编译期参数，只能使用template non-type arguments了。

constexpr可以用在构造函数上，这样定义的类可以用来定义constexpr对象，像这样：

struct Foo {     int i_ = 0;     constexpr Foo(void) noexcept {} };  template <int> struct Bar {};  constexpr Foo foo; Bar<foo.i_>{};

于是，我们可以先尝试定义一个编译期的string：

namespace literal {  template <size_t N> class string {     char str_[N] = {};  public:     constexpr string(void) noexcept = default;      constexpr string(const char* str, size_t n) noexcept     {         for (size_t i = 0; i < std::min(N, n); ++i)             str_[i] = str[i];     }      template <size_t N_>     constexpr string(const char(& str)[N_]) noexcept         : string{ str, N_ }     {}      constexpr auto operator[](size_t n) const noexcept     {         if (n >= N) return '/0';         return str_[n];     }      constexpr size_t size(void) const noexcept     {         return N;     }      constexpr size_t length(void) const noexcept     {         size_t r = 0;         for (; r < N; ++r)             if (str_[r] == '/0') break;         return r;     }      constexpr auto begin(void) const noexcept     {         return str_;     }      constexpr auto end(void) const noexcept     {         return str_ + length();     }      constexpr const char* c_str(void) const noexcept     {         return str_;     }      constexpr size_t count(char c) const noexcept     {         size_t r = 0;         for (size_t i = 0; i < length(); ++i)             if (c == str_[i]) ++r;         return r;     }      static const size_t npos = -1;      constexpr string substr(size_t pos, size_t len = -1) const noexcept     {         return { str_ + pos, std::min(length() - pos, len) };     }      constexpr size_t find(char c, size_t pos = 0) const noexcept     {         for (size_t i = pos; i < length(); ++i)             if (c == str_[i]) return i;         return npos;     } };  } // namespace literal

我们注意到，以上两个类的内部全部使用数组，而不是指针来存储内容，这是因为想要对象能够在编译期被定义出来，C++要求其不能有non-trivial destructor，因此对象自身是不能动态分配内存的。如果我们使用指针，就只能由外部预先传递一块足够大的内存块供我们使用了。

实际上，由于我们只考虑对象在编译期时的初始化和计算，因此拷贝的开销不需要太在意。

接下来，我们可以实现split了：

namespace literal {  template <size_t M, size_t N> class string_array {     typedef string<N> string_t;     string_t arr_[M];      template <size_t M_, size_t N_>     friend constexpr string_array<M_, N_> split(char, const char(&)[N_]) noexcept;      // ... };  template <size_t M, size_t N> constexpr string_array<M, N> split(char delimiter, const char(& str)[N]) noexcept {     string_array<M, N> r;     auto s = make(str);     size_t start = 0, end = s.find(delimiter);     for (size_t i = 0; i < M; ++i)     {         r.arr_[i] = s.substr(start, end - start);         if (end == string<N>::npos) break;         start = end + 1;         end = s.find(delimiter, start);     }     return r; }  } // namespace literal  #define LITERAL_SPLIT(C, S) literal::split<literal::make(S).count(C) + 1>(C, S)  int main(void) {     constexpr auto arr = LITERAL_SPLIT(',', "1,2,3,4,5");     for (auto& s: arr)         std::cout << s.c_str() << std::endl;      return 0; }

到此为止，一个编译期的字符串split函数就完成了，输入参数为字符数组，输出为literal::string_array。我们还可以为literal::string_array添加to_array等函数，让它支持转换为std::array。

注意，以上代码仅在g++ 5.3.1上编译通过，VS2015由于不支持C++14的constexpr，因此无法编译这些代码。

上文第2节，我提到了可以使用constexpr做简单的类型计算来代替模板元。在不需要数值特化做分支判断的情况下，constexpr函数会比模板元简洁很多。接下来，我们尝试改写一下上一节的split，仅使用C++11标准下的constexpr，并通过类型计算来实现编译期的字符串分割。

想要通过类型计算，而不是数值计算来处理字符串是比较麻烦的。我们首先要尝试把字符串类型化。但是在C++中，string literal是不能作为模板参数的，因此我们把字符串字面量转换成一个个的char，然后将这些char作为模板参数传递进去。

//////////////////////////////////////////////////////////////// // Define the literal string & helper types  template <char...> struct literal_string { static const char to_string[]; };  template <char... S> const char literal_string<S...>::to_string[] = { S... };  template <class... LS> struct literal_array { static const std::array<std::string, sizeof...(LS)> to_array; };  template <class... LS> const std::array<std::string, sizeof...(LS)> literal_array<LS...>::to_array = { LS::to_string... };

这里我在literal_array里直接使用了std::array，配合std::string来存储结果。自然，也可以使用普通的char数组来存储。

麻烦的是，我们如何把一个字符串字面量转换成literal_string

literal_string<"123"[0], "123"[1], "123"[2]>{};

可以注意到，这里需要我们对字符串的字符计数，然后顺次将此字符串展开到模板参数上。

宏元是没办法对字符串的内容做分析的；而我们可以使用编译期技巧得到字符个数，宏也没有办法利用这个编译期数值去做计算。

这里我们有一个简单而暴力的解决方法，就是始终让宏嵌套计算到最后一层，并提供一个at函数，当计数的个数超出字符串长度的时候返回’/0’：

#define CAPO_PP_MAX_                        256 #define CAPO_PP_VA_(...)                    __VA_ARGS__ /* Try to expand __VA_ARGS__ */ #define CAPO_PP_PROXY_(F, ...)              CAPO_PP_VA_(F(__VA_ARGS__))  #define CAPO_PP_REPEAT_0_(F1, F2, ...) #define CAPO_PP_REPEAT_1_(F1, F2, ...)      CAPO_PP_VA_(F1(1, __VA_ARGS__)) #define CAPO_PP_REPEAT_2_(F1, F2, ...)      CAPO_PP_REPEAT_1_(F1, F2, __VA_ARGS__) CAPO_PP_VA_(F2(2, __VA_ARGS__)) ...... #define CAPO_PP_REPEAT_256_(F1, F2, ...)    CAPO_PP_REPEAT_255_(F1, F2, __VA_ARGS__) CAPO_PP_VA_(F2(256, __VA_ARGS__))  /* CAPO_PP_REPEAT(5, f, data) --> f(1, data) f(2, data) f(3, data) f(4, data) f(5, data) */  #define CAPO_PP_REPEAT_P_(F, ...)           CAPO_PP_VA_(F(__VA_ARGS__)) #define CAPO_PP_REPEATEX_(N, F1, F2, ...)   CAPO_PP_REPEAT_P_(CAPO_PP_JOIN_(CAPO_PP_REPEAT_, CAPO_PP_JOIN_(N, _)), F1, F2, __VA_ARGS__) #define CAPO_PP_REPEATEX_MAX_(F1, F2, ...)  CAPO_PP_REPEATEX_(CAPO_PP_MAX_, F1, F2, __VA_ARGS__) #define CAPO_PP_REPEAT_(N, F, ...)          CAPO_PP_REPEATEX_(N, F, F, __VA_ARGS__) #define CAPO_PP_REPEAT_MAX_(F, ...)         CAPO_PP_REPEATEX_MAX_(F, F, __VA_ARGS__)  //////////////////////////////////////////////////////////////////////////  /* at */  template <size_t N> constexpr auto at(size_t n, const char(&str)[N]) noexcept {     return (n < N) ? str[n] : '/0'; }  //////////////////////////////////////////////////////////////// // Preprocessor  #define LITERAL_C(N, STR)       , at(N, STR) #define LITERAL_S(STR)          literal_string<at(0, STR) CAPO_PP_REPEAT_MAX_(LITERAL_C, STR)>{} 这样，我们调用LITERAL_S("123")，就可以得到literal_string<'1', '2', '3', '/0', ...>。迈出了第一步以后，后面的类型计算我们就轻车熟路了： //////////////////////////////////////////////////////////////// // Operations  /* link */  template <char... S1, char... S2> constexpr auto link(literal_string<S1...>, literal_string<S2...>) noexcept {     return literal_string<S1..., S2...>{}; }  template <typename... LS1, typename... LS2> constexpr auto link(literal_array<LS1...>, literal_array<LS2...>) noexcept {     return literal_array<LS1..., LS2...>{}; }  /* insert */  template <bool Valid, char C, char... S> constexpr auto insert(literal_string<S...>) noexcept {     return typename std::conditional<Valid, literal_string<C, S...>, literal_string<S...>>::type{}; }  /* remove */  template <char V> constexpr auto remove(literal_string<>) noexcept {     return literal_string<>{}; }  template <char V, char C, char... S> constexpr auto remove(literal_string<C, S...>) noexcept {     return insert<V != C, C>(remove<V>(literal_string<S...>{})); }  /* replace */  template <char V1, char V2> constexpr auto replace(literal_string<>) noexcept {     return literal_string<>{}; }  template <char V1, char V2, char C, char... S> constexpr auto replace(literal_string<C, S...>) noexcept {     return insert<true, (V1 == C) ? V2 : C>(replace<V1, V2>(literal_string<S...>{})); }  /* count */  template <char V> constexpr size_t count(literal_string<>) noexcept {     return 0; }  template <char V, char C, char... S> constexpr size_t count(literal_string<C, S...>) noexcept {     return ((V == C) ? 1 : 0) + count<V>(literal_string<S...>{}); }  /* find */  constexpr size_t npos = static_cast<size_t>(-1);  template <char V, size_t N = 0> constexpr size_t find(literal_string<>) noexcept {     return npos; }  template <char V, size_t N = 0, char C, char... S> constexpr size_t find(literal_string<C, S...>) noexcept {     return (V == C) ? N : find<V, N + 1>(literal_string<S...>{}); }  /* substr */  template <size_t B, size_t E = npos, size_t N = 0> constexpr auto substr(literal_string<>) noexcept {     return literal_string<>{}; }  template <size_t B, size_t E = npos, size_t N = 0, char C, char... S> constexpr auto substr(literal_string<C, S...>) noexcept {     return insert<(B <= N) && (N < E), C>(substr<B, E, N + 1>(literal_string<S...>{})); }

使用方法：

auto arr = LITERAL_SPLIT(',', "1,2,3,4,5,6,7,8,9,0"); // std::array<std::string, 10>

以上代码在g++ 5.3.1及VS2015上编译通过（VS2015里宏不能嵌套这么深，需要调整CAPO_PP_MAX_的值）。

这个split对比上一节实现的最大的好处是，支持运行期无损耗的把字符串字面量拆分，并放入std::string的std::array中。

第5节代码下载： An example for spliting a string literal in compile-time 。

作者简介：

张轶，珠海市云创科技研发中心高级软件工程师，资深C++爱好者。熟练使用C++，有8年以上开发经验，擅长泛型/模板元编程。致力于在实际项目中应用和推广现代C++ 。