39 | 如何在编译期玩转字符串？

Jun 13, 2022
39 | 如何在编译期玩转字符串？-极客时间

下载APP


关闭
讲堂部落提薪训练营云原生训练营架构实战营企业版极客商城兑换中心 App下载浏览器插件
渠道合作
推荐作者
39 | 如何在编译期玩转字符串？

2022-06-13 吴咏炜来自北京
《现代C++编程实战》
课程介绍

讲述：吴咏炜

时长18:28大小16.87M

你好，我是吴咏炜。
在实际的项目里，我遇到过不少在编译期处理字符串的需求。今天，我们就来把这个问题好好讨论一下。
对象的选择在编译期处理字符串，你是不能使用 std::string 的。原因有以下几个方面：
在 C++20 之前你完全无法在编译期使用 string。而且，对于编译期 string 的支持来得比较晚，只有 MSVC 较早支持，GCC 需要刚出炉不久的 GCC 12，Clang 需要当前（2022 年 6 月）尚未正式发布的 LLVM 15。
到了 C++20，你虽然可以在编译期使用 string，但实际上仍有很多不方便的地方。最明显的，编译期生成的字符串不能在运行期使用。并且，string 不可以声明为 constexpr。
string 不能用作模板参数。
因此我们只能放弃这个看起来最方便的方式，另外探索一条新路。我们的基本操作对象可以是下面这几样：
常字符指针，这是字符串字面量会自然退化成的东西
string_view，C++17 里新增的有力工具，方法和 string 类似，且基本都是 constexpr
array，使用它我们才可以返回全新的字符串
我们的编译期字符串处理，也因此会围绕着这几种类型来进行讨论。
常见操作获取字符串长度一个最最基本的操作，显然就是获取字符串的长度。这里，我们不能使用 C 的 strlen 函数，因为这个函数不是 constexpr。
对于这个操作，我们尝试一下几种不同的实现方式。
首先，我们可以自己实现 strlen 的功能，并把代码写成 constexpr 函数：
namespace strtools {
constexpr size_t
length(const char* str)
{
  size_t count = 0;
  while (*str != '\0') {
    ++str;
    ++count;
  }
  return count;
}
} // namespace strtools
不过，标准库里是不是有现成的编译期获取字符串长度的机制呢？答案是，有。不仅有，还能支持 char、wchar_t 等多种不同字符类型的情况。以 Unix 下最常用的 char 为例，使用跟上面相同的接口，我们可以写出：
constexpr size_t
length(const char* str)
{
  return char_traits<char>::length(
    str);
}
从 C++17 开始，这就是合法的可以在编译期计算字符串长度的代码了。（不过，一些较老的编译器上，使用 char_traits 会有一些问题，如 GCC 8 或更老的版本。）
既然用了 C++17，我们当然也可以试一下 string_view 了：
constexpr size_t
length(string_view sv)
{
  return sv.size();
}
不管使用上面哪一种写法，现在你可以用下面的代码来验证我们确实可以在编译的时候验证字符串的长度：
static_assert(strtools::length("Hi") == 2);
目前看起来，应该是 string_view 实现最方便了。
查找字符查找指定的字符也是一个常用功能。我们不能使用 strchr，但一样，我们有几种不同的实现方式可供选择。使用 char_traits 或 string_view 的代码都非常简单。
这是使用 char_traits 的版本：
constexpr const char*
find(const char* str, char ch)
{
  return char_traits<char>::find(
    str, length(str), ch);
}
这是使用 string_view 的版本：
constexpr string_view::size_type
find(string_view sv, char ch)
{
  return sv.find(ch);
}
这次我就不展示手工的查找代码了。（除非你非得用老的编译器，否则简单为好。）
字符串比较下一个是字符串比较。这个 string_view 完全不需要动手就赢了：string_view 可以直接进行各种标准的比较，不需要写任何的代码。
截取子串看起来使用 string_view 很方便，我们应当尽量使用 string_view，可以少写代码。不过，截取子串这个操作，string_view::substr 够不够用呢？
这个问题，没有实际的使用场景是比较难回答的。我在项目中遇到过的一个实际场景是，__FILE__ 宏可能会携带编译时的完整路径，导致在不同路径下编译会产生不同的二进制输出。而比较理想的解决方式是，通过编译期编程来消除某个前缀或者截取路径的最后部分，让编译的绝对路径不会泄漏出来。
实测结果，string_view::substr 难当此任。对于下面的代码：
puts("/usr/local"sv.substr(5)
       .data());
我们在编译器的汇编输出里会看到这样的代码（参见 https://godbolt.org/z/1dssd96vz）：
.LC0:
        .string "/usr/local"
        …
        mov     edi, OFFSET FLAT:.LC0+5
        call    puts
我们得另外想办法……
下面我们来试试 array。很容易会想到类似下面这样的代码：
constexpr auto
substr(string_view sv,
       size_t offset, size_t count)
{
  array<char, count + 1> result{};
  copy_n(&sv[offset], count,
         result.data());
  return result;
}
代码的意图应该很容易读懂：根据要求的大小生成一个全新的字符数组并清零（C++20 之前不允许 constexpr 变量不立即初始化）；拷贝所需的内容；然后返回。可惜，这个代码没法通过编译……
它里面有好几个问题：
函数参数不是编译期常量，不能用在模板参数里
copy_n 在 C++20 之前不是 constexpr，不能用于编译期编程
第二个问题好解决，手写个循环就行。我们重点来看一下第一个问题。
一个 constexpr 函数可以在编译期求值，也可以在运行期求值，所以函数的参数全部不被视作编译期常量，不能用到模板参数等要求编译期常量的地方。
更进一步，这个问题到了 C++20 的 consteval 函数，仍然没有解决。其主要原因是，如果我们允许函数的参数当作编译期常量来用的话，那我们就能写出一个函数，它的入参的不同的值（相同类型），能够产生不同类型的返回值。例如（当前为不合法代码）：
consteval auto make_constant(int n)
{
  return integral_constant<int, n>{};
}
这在目前的类型系统里是无法接受的，我们仍需确保函数的返回值有唯一类型。要想在函数里用作模板参数的值，就必须以模板参数的形式来传递给函数模板（而不是作为非模板函数的普通参数）——这种情况下，每一个不同的模板参数就意味着一个不同的模板特化，不是同一个函数，这样就没有上面这个函数返回值类型不唯一这个问题。
顺便说一句，有一个标准提案 P1045 试图解决这个问题 [1]，但后来迟迟没有进展。由于存在一些绕过的方案（下面会讨论），目前我们仍能实现需要的效果。
回到 substr 函数，我们需要把长度变成模板参数。下面是修改的结果：
template <size_t Count>
constexpr auto
substr(string_view sv,
       size_t offset = 0)
{
  array<char, Count + 1> result{};
  for (size_t i = 0; i < Count;
       ++i) {
    result[i] = sv[offset + i];
  }
  return result;
}
这回，代码确实可以工作了。对于 puts(substr<5>("/usr/local", 5).data());，现在编译器生成的结果里不再有 "/usr/" 了。
不过，很遗憾，这回我们见到了抽象对编译器的挑战：在当前 Godbolt 上最新版本的 GCC（12.1）和 MSVC（19.32）下，这个版本的 substr 没有生成最优的输出，我在老版本的编译器上也多多少少遇到了一些兼容性问题。因此，纯粹从实际的角度，我推荐下面这个不使用 string_view 的版本：
template <size_t Count>
constexpr auto
substr(const char* str,
       size_t offset = 0)
{
  array<char, Count + 1> result{};
  for (size_t i = 0; i < Count;
       ++i) {
    result[i] = str[offset + i];
  }
  return result;
}
如果有兴趣的话，你可以自行比较一下这两个不同版本代码生成的汇编：
https://godbolt.org/z/zT8s1aEYo
https://godbolt.org/z/qGPevxP98
只有 Clang 对于这两个版本生成了完全相同的高效汇编代码：
        mov     word ptr [rsp + 4], 108
        mov     dword ptr [rsp], 1633906540
        mov     rdi, rsp
        call    puts
如果你不明白为什么有 108 和 1633906540 这两个数字的话，提醒你一下，这两个数字的十六进制表示分别是 0x6C 和 0x61636F6C。查一下 ASCII 表你就应该可以明白了。
既然我们在接口里不用 string_view，参数里的 offset 就变得很鸡肋了。因此，下面我们不再使用 offset 这个参数，并把函数名更改为 copy_str：
template <size_t Count>
constexpr auto
copy_str(const char* str)
{
  array<char, Count + 1> result{};
  for (size_t i = 0; i < Count;
       ++i) {
    result[i] = str[i];
  }
  return result;
}
编译期传参问题不过，当你想把上面这些编译期函数组合起来的话，你会发现仍然缺了点什么。比如，如果你想把 "/usr/local" 这样的路径自动去掉第一段，得到 "local"，你可能会试图写出下面这样的代码：
constexpr auto
remove_head(const char* path)
{
  if (*path == '/') {
    ++path;
  }
  auto start = find(path, '/');
  if (start == nullptr) {
    return copy_str<length(path)>(
      path);
  } else {
    return copy_str<length(
      start + 1)>(start + 1);
  }
}
它的问题仍然是，没法通过编译。并且，你有没有注意到，这个代码恰恰违反了我上面提到过的，一个函数的返回类型需要一致这个约束。
对于这个问题，我目前一般采用 Michael Park 描述的一个解法，用 lambda 表达式来对“编译期参数”进行封装 [2]。为了方便使用，我定义了三个宏：
#define CARG typename
#define CARG_WRAP(x) [] { return (x); }
#define CARG_UNWRAP(x) (x)()
“CARG”的意思是“constexpr argument”，代表编译期常量参数。对应于之前那个不能编译的 make_constant 函数，我们现在可以用下面的函数模板来代替：
template <CARG Int>
constexpr auto
make_constant(Int cn)
{
  constexpr int n = CARG_UNWRAP(cn);
  return integral_constant<int,
                           n>{};
}
很容易验证它能够正常工作：
auto result =
  make_constant(CARG_WRAP(2));
static_assert(
  std::is_same_v<
    integral_constant<int, 2>,
    decltype(result)>);
稍微解释一下。在模板参数里，我用 CARG 代替 typename，这只是为了代码的可读性，表示这个模板参数实质上是编译期常量的类型封装。Int 就是这个特殊类型的名称。这个类型我们在实例化函数模板的时候不提供，而是让编译器自己进行推导。调用的时候（make_constant(CARG_WRAP(2))）实际提供的是一个 lambda 表达式（[] { return (2); }），里面封装了我们需要的常量。在实际使用的时候，再使用 CARG_UNWRAP 来进行求值（[] { return (2); }()），重新得回常量值。
现在我们可以改写 remove_head 函数了：
template <CARG Str>
constexpr auto
remove_head(Str cpath)
{
  constexpr auto path =
    CARG_UNWRAP(cpath);
  constexpr int skip =
    (*path == '/') ? 1 : 0;
  constexpr auto pos = path + skip;
  constexpr auto start =
    find(pos, '/');
  if constexpr (start == nullptr) {
    return copy_str<length(pos)>(
      pos);
  } else {
    return copy_str<length(
      start + 1)>(start + 1);
  }
}
这个函数跟之前的版本结构相似，但细节上有了很多改变。为了把结果作为模板参数传递给 copy_str，我们不得不一路使用 constexpr，为此还必须放弃可变性，写出非常具有函数式编程风格的代码。
最终效果如何呢？我们在 main 函数里只放下面这一条语句试试：
puts(strtools::remove_head(
       CARG_WRAP("/usr/local"))
       .data());
下面是 GCC 在 x86-64 上优化编译输出的汇编（参见 https://godbolt.org/z/M1v1ba3PE）：
main:
        sub     rsp, 24
        mov     eax, DWORD PTR .LC0[rip]
        lea     rdi, [rsp+8]
        mov     DWORD PTR [rsp+8], eax
        mov     eax, 108
        mov     WORD PTR [rsp+12], ax
        call    puts
        xor     eax, eax
        add     rsp, 24
        ret
.LC0:
        .byte   108
        .byte   111
        .byte   99
        .byte   97
可以看到，编译器会把 "local" 对应的 ASCII 码填到栈上，把使用的栈空间的起始地址赋给 rdi 寄存器，然后调用 puts 函数。输出中完全看不到 "/usr/" 的影子了。事实上，上面那条 puts 语句跟 puts(substr<5>("/usr/local", 5).data()); 的输出结果没有区别。
Godbolt 上的版本是使用 char_traits 的简洁版本，适用于较新的编译器。特别地，GCC 8 就无法正常工作了。而 GitHub 上的代码库采用了手写的 strtools::length 和 strtools::find，在 GCC 7 下依然能够工作。
这里再提醒一句，编译期产生的字符 array 是可以安全地自由传递和存储的，但从 array 里用 data() 方法取得的指针不是。取得指针立即用来调用其他函数是可以的（像上面的 puts），因为 array 的生命周期会延续到这条语句执行结束；但直接把这个指针存下来，则会导致悬挂指针，是一种未定义行为。
字符串模板参数上面我们已经在参数传递中把字符串变成了类型（lambda 表达式），但不像整数和 integral_constant，这两者之间没有一一对应关系。这在很多时候是不方便的：对于两个 integral_constant，我们可以直接使用 is_same 来判断它们是否相同；对于传递字符串的 lambda 表达式，我们可没法这么用——两个 lambda 表达式的类型永远不同。
C++ 里是不允许直接使用字符串字面量作为非类型模板参数的，因为字符串在不同的翻译单元可能会重复出现，而且字符串也没有合适的比较语义——比较两个字符串只是两个指针的比较而已，不能达到用户一般期望的效果。要使用字符串字面量作为模板参数，我们需要找到方法，把字符串当成一系列的字符传给模板进行处理。我们有两种可用的方法：
GCC 的非标准扩展，可以用在 GCC 和 Clang 编译器中（支持 C++17）
C++20 的标准方法，可以用在任何支持 C++20 的编译器中（包含 GCC）
下面我们分别来看一下。
GCC 扩展GCC 有一个根据标准提案实现的扩展 [3]，使得我们可以把字符串当成模板参数来使用，编译器会把字符串展开成一系列的字符，结果就完全落入了标准 C++ 的范畴。这样的代码在 GCC 和 Clang 下都能够工作，但如果你打开 -Wpedantic 开关的话，编译器会对这种用法告警，告诉你这不是标准 C++。
下面是一个示例：
template <char... Cs>
struct compile_time_string {
  static constexpr char value[]{
    Cs..., '\0'};
};
template <typename T, T... Cs>
constexpr compile_time_string<Cs...>
operator""_cts()
{
  return {};
}
类模板的定义是标准 C++，使我们可以声明出 compile_time_string<'H', 'i'> 这样的类型，同时，取这个类型的 value 成员我们即可得到 "Hi" 这样一个字符串。GCC 的扩展是在字面量运算符上——我们现在可以写出 "Hi"_cts 来得到一个 compile_time_string<'H', 'i'> 类型的对象。
使用上面的定义，下面的代码会合法通过编译：
constexpr auto a = "Hi"_cts;
constexpr auto b = "Hi"_cts;
static_assert(
  is_same_v<decltype(a),
            decltype(b)>);
C++20上面的方法虽然简单有效，但在 C++ 标准委员会没能获得共识从而进入标准。不过，到了 C++20，我们可以在模板参数中使用更多的非类型模板参数的类型了（这句话确实有点拗口）[4]。特别是，用户定义的字面类型也在其中（可参考第 15 讲）。
下面是一个示例：
template <size_t N>
struct compile_time_string {
  constexpr compile_time_string(
    const char (&str)[N])
  {
    copy_n(str, N, value);
  }
  char value[N]{};
};
template <compile_time_string cts>
constexpr auto operator""_cts()
{
  return cts;
}
同样，前面的那个类模板没啥特别，但允许这个 compile_time_string 用作模板参数，以及字符串字面量运算符模板 [5]，就是 C++20 的改进了。我们现在同样可以写出 "Hi"_cts 来生成一个 compile_time_string 的对象。不过，需要注意的是，这个对象的类型是 compile_time_string<3>，因此 "Hi"_cts 和 "Ha"_cts 属于同一类型——这就和 GCC 扩展的结果很不同了。
不过，重点在于我们已经可以使用 compile_time_string 作为模板参数，所以，我们再小小地包一层就可以了：
template <compile_time_string cts>
struct cts_wrapper {
  static constexpr compile_time_string
    str{cts};
};
对应于前面的编译期字符串类型比较，我们现在需要这样写：
auto a = cts_wrapper<"Hi"_cts>{};
auto b = cts_wrapper<"Hi"_cts>{};
static_assert(
  is_same_v<decltype(a),
            decltype(b)>);
甚至进一步简化成（通过非 explicit 的构造）：
auto a = cts_wrapper<"Hi">{};
auto b = cts_wrapper<"Hi">{};
static_assert(
  is_same_v<decltype(a),
            decltype(b)>);
接口统一前面 GCC 和 C++20 的写法不一致，在实际项目里会带来一些困扰。因此，在实际项目里，我会使用宏，使得实际使用这些功能的代码是统一的。具体细节你可以参考 GitHub 上的代码库。在使用这些宏定义之后，现在我们可以这样写：
using t1 = decltype(CTS_STRING(Hi));
using t2 = decltype(CTS_STRING(Hi));
using t3 = decltype(CTS_STRING(Ha));
static_assert(is_same_v<t1, t2>);
static_assert(!is_same_v<t1, t3>);
puts(CTS_GET_VALUE(CTS_STRING(Hi)));
有了这样的基础之后，我们就可以在编译期玩很多花样，得到一些之前无法完成的效果。
内容小结本讲我们讨论了在编译期处理字符串的一些技巧。利用这些技巧，我们能够在编译而非执行代码时对字符串进行处理，从而把一些处理提前，消除运行期的开销。
课后思考请尝试一下，你能不能实现我文中提到的需求，在编译期把一个文件名去掉前面的路径部分，只留下最后的名称？
期待你的分享，如有任何疑问，欢迎留言讨论！
参考资料[1] David Stone, “constexpr function parameters”. https://wg21.link/p1045r1
[2] Michael Park, “constexpr function parameters”. https://mpark.github.io/programming/2017/05/26/constexpr-function-parameters/
[3] Richard Smith, “Literal operator templates for strings”. http://wg21.link/n3599
[4] cppreference.com, “Template parameters and template arguments”. https://en.cppreference.com/w/cpp/language/template_parameters
[4a] cppreference.com, “模板形参与模板实参”. https://zh.cppreference.com/w/cpp/language/template_parameters
[5] cppreference.com, “User-defined literals”. https://en.cppreference.com/w/cpp/language/user_literal
[5a] cppreference.com, “用户定义字面量”. https://zh.cppreference.com/w/cpp/language/user_literal
分享给需要的人，Ta购买本课程，你将得18元
生成海报并分享
赞 0
提建议
38 | 折叠表达式：高效的编译期展开
40 | 如何在编译期遍历数据？
 写留言
精选留言(2)

行大运
2023-01-24 来自广东
什么时候出一个完整的C++20专栏！
作者回复: 目前没有计划……
piboye
2022-09-06 来自上海
c++20 字符串处理，可以超越c了
作者回复: C++ 字符串处理有哪里不如 C？
共 4 条评论
