C++17剖析：string在Modern C++中的实现

概述

gcc 8.2提供了两个版本的std::string：一个是基于copy on write的，另一个直接字符串拷贝的。前者针对c++11以前的，那时候没有移动构造，一切以效率为先，需要使用cow这种奇技淫巧。后者针对c++11，也就是_glibcxx_use_cxx11_abi宏被设置为非零时会被用到，并没有cow的功能，更简单，用户可以在必要时使用移动构造。如果不使用移动构造，字符串的频繁拷贝将会是异常灾难，这一点，在我的项目中已经踩过坑。
本文主要研究modern c++中的string实现，因为使用c++11以后的标准都使用它。

数据组织：16字节的栈上存储，如果超出16字节则在堆上分配

数据的组织很简单，如果字符串长度不超过15字节（加上后缀0一共16字节），则在栈上保存，否则会在堆上分配内存。

      // use empty-base optimization: http://www.cantrip.org/emptyopt.html
      struct _alloc_hider : allocator_type // todo check __is_final
      {
#if __cplusplus < 201103l
        _alloc_hider(pointer __dat, const _alloc& __a = _alloc())
        : allocator_type(__a), _m_p(__dat) { }
#else
        _alloc_hider(pointer __dat, const _alloc& __a)
        : allocator_type(__a), _m_p(__dat) { }

        _alloc_hider(pointer __dat, _alloc&& __a = _alloc())
        : allocator_type(std::move(__a)), _m_p(__dat) { }
#endif

        pointer _m_p; // the actual data.
      };

      _alloc_hider      _m_dataplus;       ////数据指针，指向本地或者堆内存
      size_type         _m_string_length;  ////实际长度，如果大于_s_local_capacity则是堆内存，否则，是栈内存

      enum { _s_local_capacity = 15 / sizeof(_chart) };

      ////注意这是union，16字节的栈内存和整个堆的容量(capacity)共用一块存储
      union
      {
        _chart           _m_local_buf[_s_local_capacity + 1];
        size_type        _m_allocated_capacity;
      };

里面那个union挺有意思，如果_m_string_length>=_s_local_capacity，那么_m_allocated_capacity保存了整块缓冲区的大小（注意不是字符串的大小）；如果_m_string_length<_s_local_capacity则_m_dataplus._m_p指针指向_m_local_buf这块栈上内存区。union的特性是全部元素共用一块空间，根据程序的语义只使用其中一个变量，在这里_m_local_buf有效的时候_m_allocated_capacity无效，反之亦然，巧妙地运用空间，减少内存浪费。

对象的构造：第一组，不带参数的构造函数（默认构造函数）

• 始化长度为0，数据指针指向栈内存_m_local_buf，包括以下函数：
  • basic_string()
  • basic_string(const _alloc& __a)

对象的构造：第二组，根据字符串构造

• 调用_m_construct()构造对象，也就是把字符串拷贝一个（而不是增加引用计数）；关于_m_construct()的细节，在下面会分析。包括以下函数：
• 2.1 基于basic_string构建字符串拷贝
  • basic_string(const basic_string& __str)：拷贝__str的完整字符串；
  • basic_string(const basic_string& __str, const _alloc& __a)：同上，指定构造器；
  • basic_string(const basic_string& __str, size_type __pos, const _alloc& __a = _alloc())：拷贝__str从__pos位置到末尾的所有字符；
  • basic_string(const basic_string& __str, size_type __pos, size_type __n)：拷贝__str从__pos位置开始的n个字符（或者到末尾）；
  • basic_string(const basic_string& __str, size_type __pos, size_type __n, const _alloc& __a)：同上，指定构造器；
• 2.2 基于指针构建字符串拷贝，指针可以是字符串指针，也可以是其他指针，只要编译器不抱怨
  • basic_string(const _chart* __s, const _alloc& __a = _alloc())：拷贝__s的全部字符串，构造时会计算__s的长度，使用char_traits<char>::length()内联函数；
  • basic_string(const _chart* __s, size_type __n, const _alloc& __a = _alloc())：拷贝__s字符串的前__n个字符，不检测越界问题，留给调用方保证；
  • basic_string(const _tp& __t, size_type __pos, size_type __n, const _alloc& __a = _alloc())：这个比上面两个构造函数更加宽泛，可以是任意数据指针，编译器会对数据能否正确转换进行检测（warnning或者error）；
• 2.3 其他
  • basic_string(initializer_list<_chart> __l, const _alloc& __a = _alloc())：使用初始化列表构造；
  • basic_string(size_type __n, _chart __c, const _alloc& __a = _alloc())：以n个相同的字符填充缓冲区：调用_m_construct()初始化缓冲区并填充字符。

对象的构造：第三组：移动构造函数

• 对于栈上保存的字符串，会拷贝到目标字符串（最多16bytes）；如果是堆上分配的字符串，则把指针转到目标字符串。完成这些拷贝和转移后，右值字符串回归到默认构造的状态（长度为0，字符串指针指向栈缓冲区的起始位置）；
  • basic_string(basic_string&& __str)
  • basic_string(basic_string&& __str, const _alloc& __a)

对象的构造：第四组：基于迭代器构造

• 调用_m_construct()，根据迭代器的类型进行分类处理：
  • basic_string(_inputiterator __beg, _inputiterator __end, const _alloc& __a = _alloc())：把迭代器区间内的数据（允许不是char/wchar_t，只要编译器不抱怨）；

对象的构造：第五组：根据std::string_view构造

• 可以轻量级使用std::string_view构造一个std::string，同样是使用字符串拷贝
  • basic_string(const _tp& __t, const _alloc& __a = _alloc())：需要__t是std::string_view类型，取整个std::string_view字符串构建std::string；
  • basic_string(const _tp& __t, size_type __pos, size_type __n, const _alloc& __a = _alloc())：需要__t是std::string_view类型，并且取它的字符串一部分构建新的字符串，调用上面的构造函数完成构造。
  • basic_string(__sv_wrapper __svw, const _alloc& __a)：允许某个类型，如果可以转换成std::string_view，则使用此构造函数，类似于basic_string(sv.data(), sv.size(), alloc)。

对象的构造：第六组：赋值

• 调用assign()函数，进而调用_m_assign()系列函数，这部分下面会详细分析
  • operator=(const basic_string& __str) ：代码相对比较复杂，其实就是字符串拷贝，没有cow。
  • operator=(const _chart* __s)：同上
  • operator=(_chart __c)：只插入一个字符

先谈谈构造时的调用流程

上面大部分版本的构造函数都是给定一个起始区间，调用_m_construct(_initerator __beg, _initerator __end)函数。下面分析这个函数的来龙去脉。

• _m_construct(_initerator __beg, _initerator __end)：根据std::__is_integer<_initerator>::__type分析这个“迭代器”是否数值类型；
  • 如果是数值类型，则表示调用方是basic_string(size_type __n, _chart __c)这一组的函数，那么就调用_m_construct_aux(_integer __beg, _integer __end, std::__true_type)去生成，最终调用_m_construct(size_type __req, _chart __c)函数；
  • 如果不是数值类型，则表示调用方是上面第二组的调用方式，则调用_m_construct_aux(_integer __beg, _integer __end, std::__true_type)，继而调用_m_construct(_initerator __beg, _initerator __end)函数；

现在回到_m_construct()函数

_m_construct()函数执行字符串的实际构造操作。它按照迭代器/参数的类型，有两种实现：

• _m_construct(size_type __req, _chart __c)：实现的算法很简单，申请一段__req的内存空间（如果小于15字节则直接写在栈上），并拷贝__req个__c字符；
• _m_construct(_initerator __beg, _initerator __end, std::forward_iterator_tag)：只有当迭代器类型是forward_iterator或者比它更宽的迭代器时使用，它会根据迭代器之间的长度来确定字符串的长度，并逐字符拷贝。关于迭代器的“更宽”，可以参考。
• _m_construct(_initerator __beg, _initerator __end, std::input_iterator_tag)：用于input_iterator迭代器，如输入迭代器等。这个构造比较低效，每次输入一个字符，会检测是否达到缓冲区的末尾，如果是，则把缓冲区的大小加1，重新分配空间并拷贝字符串。
• 讲完了

字符串赋值专用的_m_assign()函数

• 赋值类的函数都会在预分配足够内存后，调用_m_assign()函数，该函数的逻辑很简单，只是单纯的字符串拷贝，拷贝到需要的位置。

结论：std::string在程序在使用的注意事项（划重点）

• 两个字符串连接：根据std::string的实现代码，字符串的连接一定会引起内存的重新分配和字符串拷贝。很遗憾，c++没有使用c的realloc()函数。如果使用realloc()函数，有可能在扩大内存的同时，不需要拷贝字符串（也就是原来分配的内存区域末尾还有足够的字符串）。c++很单纯地分配一块新内存，再把就内存拷贝过去。这一点在效率上会比较低下。个人认为解决办法是，使用std::deque代替std::string。在字符串不断变动的时候，字符数组可以写入std::deque，因为它的插入、追加操作比std::string高效。等字符串稳定后，再使用basic_string(_inputiterator __beg, _inputiterator __end)构造函数生成std::string。
  • google的提供了一个可用的办法：也就是先计算多个字符串的长度，预分配一大块内存来存放，然后分别拷贝字符串，这样避免反复分配内存和拷贝字符串，请参考。但是这种方法只适用于已知固定个数的字符串连接。
  • 有人测试出c++拼接字符串的比较中，std::string::append和operator+的效率是最高的，同样的代码，我用c++98和c++11、c++17分别测试过，o3级别优化，最终结果类似。代码和测试结果见。
• 字符串的赋值：c++11下，因为有移动构造，所以std::string的复杂性比之前的版本有所降低，但是如果直接使用赋值，而不使用移动赋值，效率反而较“史前”版本慢，因为c++11以前，使用基于引用计数的cow，拷贝更加轻量级，而c++11出现以后，移动赋值成为提升效率几乎唯一的途径了，因此c++11以后的程序尽可能使用移动赋值。
• 另外，字符串的中间插入，也是需要重新分配内存，并完整拷贝整个字符串，这一点需要在使用中注意。
• 如果只是需要字符串的只读操作，可以使用std::string_view代替。
• 最后说一个地方，虽然比较少用，就是基于std::input_iterator的构造，它每次重新分配内存只会分配“刚刚适合需要的大小”，而不会如std::vector那样分配2倍，所以将会有频繁分配内存和拷贝的操作。解决的办法还是用std::deque，等字符足够之后再写入std::string。
• 总结上述几条：任何对已有字符串的插入、追加操作，都很可能造成内存的重新分配和整个字符串拷贝，这种重新分配和拷贝，并不是realloc()，而是new+memcpy，这是必须注意的。解决的办法，一是使用reserver()函数申请足够的内存，二是使用std::deque临时代替。