译者：lucasfan，百度 IEG 格斗游戏应用程序合作开发技师
选用 C++ 展开 SDK 合作开发的老师很大免不了碰到TK1偶现的 Crash 难题，而崩盘栈有许多间接 Crash 在 std::string 源代码中，std::string 源代码艰涩艰涩减少了 Debug 的技术难度。在数次与 std::string 的权力斗争中，本栏写作了数个版的 string 同时实现源代码，对关键的同时实现展开预测、并对照其同时实现，期望对诸位老师有协助。
责任编辑将对照下列两个版的 string 源代码同时实现。
string 版情景优点libstd c++ string（gnu4.9）百度外部 Android SDK 常见写时复本（COW）libc++ string百度外部 iOS SDK 常见短数组强化（SSO）；左值复本外部内部结构tpstl string百度暗鞘 string， SDK 外部选用化解跨库难题；缓存池
在 Class 实现中，最关键的是 Class 的表述、缓存内部结构、常见外部内部结构器、= 运算符、析构方式，责任编辑将对四种相同的 string 同时实现展开如是说。
一、libstdc++ string
现阶段子公司的 Android SDK 两极化选用了 gnu4.9 版的 C++ 库。依照工程项目实战经验，Android 网络平台 string 的崩盘率是相比之下少于 iOS 的，因而也是此次如是说的重点工程项目。
1、表述
typedefbasic_string<char> string; template<typename _CharT, typename _Traits = char_traits<_CharT>, typename_Alloc = allocator<_CharT> > class basic_string;能看见 string 只不过是 basic_string<char>，透过 basic_string 能外部内部结构出相同字符串类别的数组类别。比如说 wstring 是 basic_string<wchar_t>。
查阅 basic_string 能辨认出 basic_string 主要包括了四个模版模块，分别是：
_CharT 字符串类型；_Traits 优点类，主要提供 char 优点相关的方式，比如说求数组长度；_Alloc 缓存分配器，主要用于数组的缓存分配。_Traits和 _Alloc` 不是责任编辑如是说的重点工程项目，有兴趣的老师能自己查阅源代码学习。
2、缓存内部结构
透过代码辨认出 std::string 中只主要包括一个成员变量 _M_dataplus。
mutable _Alloc_hider _M_dataplus; struct _Alloc_hider : _Alloc { _Alloc_hider(_CharT* __dat, const_Alloc& __a) _GLIBCXX_NOEXCEPT : _Alloc(__a), _M_p(__dat) { } _CharT* _M_p;// The actual data. };_Alloc_hider 主要包括一个成员变量 _M_p，存储了真实的数组地址。因而在栈上分配一个 string 时，这个栈上的 string 只保存了一个地址。
struct _Rep_base { // 数组的真实长度 size_type _M_length; // 数组的容量 size_type _M_capacity; // 引用计数 _Atomic_word _M_refcount; }; struct _Rep : _Rep_base { /**/ }那么数组的长度信息保存在哪里呢？
只不过在外部内部结构时，string 会在堆上申请一个缓存空间，主要包括了一个 _Rep类别的对象和一个数组缓存。_Rep 就主要包括了数组的长度等信息，具体可看其代码表述。
不过_M_p指向的并不
3、char* 外部内部结构器
std::string str(“hello world”);当用一个 char* 去外部内部结构 std::string 时，即调用了 char* 外部内部结构器。
template<typename _CharT, typename _Traits, typename _Alloc> basic_string<_CharT, _Traits, _Alloc>:: basic_string(const_CharT* __s,const_Alloc& __a) : _M_dataplus(_S_construct(__s, __s ? __s + traits_type::length(__s) : __s + npos, __a), __a) { }char* 外部内部结构器的具体同时实现是空的，初始化是在初始化列表中。 _S_construct 方式返回的数组地址和分配器__a外部内部结构了 _M_dataplus。
_Alloc_hider(_CharT* __dat, const _Alloc& __a) _GLIBCXX_NOEXCEPT : _Alloc(__a), _M_p(__dat) { }_M_dataplus 的类别是 _Alloc_hider ，其外部内部结构器只是简单的地址复本。最主要的是将外部内部结构的地址复本到 _Alloc_hider 中。
template<typename_CharT,typename _Traits, typename _Alloc> template <typename_InIterator> _CharT* basic_string<_CharT, _Traits, _Alloc>:: _S_construct(_InIterator __beg, _InIterator __end,const_Alloc& __a, forward_iterator_tag) {#if _GLIBCXX_FULLY_DYNAMIC_STRING == 0 // 如果数组长度为空，间接返回在std::string静态存储区的空数组 if(__beg == __end && __a == _Alloc())return _S_empty_rep()._M_refdata(); #endif // NB: Not required, but considered best practice. if(__gnu_cxx::__is_null_pointer(__beg) && __beg != __end) __throw_logic_error(__N(“basic_string::_S_construct null not valid”)); // 计算数组长度 const size_type __dnew = static_cast<size_type>(std::distance(__beg, __end)); // Check for out_of_range and length_error exceptions. // _S_create 申请缓存空间，返回的是 _Rep 数据内部结构地址 _Rep* __r = _Rep::_S_create(__dnew, size_type(0), __a); __try // 拷贝数据 { _S_copy_chars(__r->_M_refdata(), __beg, __end); } __catch(…) { // 如果发生异常，_M_destory 销毁分配的数组空间 __r->_M_destroy(__a); __throw_exception_again; } // 设置数组长度，并将引用计数为0(0表示实际的引用个数为1)__r->_M_set_length_and_sharable(__dnew);// 返回数组地址 return __r->_M_refdata(); }_S_construct 展开了缓存空间的申请和数组的复本操作。
依照以上代码综合来看，char* 外部内部结构器只不过是申请了一块缓存并展开了数组的复本操作。
4、复本外部内部结构
std::string orginStr = “hello world”; std::string newStr(orginStr); // 复本外部内部结构复本外部内部结构同样常见，也非常关键。
template<typename _CharT, typename _Traits, typename _Alloc> basic_string<_CharT, _Traits, _Alloc>:: basic_string(const basic_string& __str) : _M_dataplus(__str._M_rep()->_M_grab(_Alloc(__str.get_allocator()), __str.get_allocator()), __str.get_allocator()) { }与 char* 外部内部结构器相同的主要是外部内部结构数组的方式，由_S_construct变为了 __str._M_rep()->_M_grab。
_CharT* _M_grab(const _Alloc& __alloc1, const _Alloc& __alloc2) { return(!_M_is_leaked() && __alloc1 == __alloc2) ? _M_refcopy() : _M_clone(__alloc1); }_M_grab同时实现了：如果数组可共享，展开引用复本，否则展开深度复本。
正常情况下，数组都是可共享的。只有个别情况下不可共享，比如说这个数组正在被写入时就不可被共享。
先看下引用复本的方式同时实现：
_CharT* _M_refcopy() throw() { #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0 if (__builtin_expect(this != &_S_empty_rep(), false)) #endif __gnu_cxx::__atomic_add_dispatch(&this->_M_refcount, 1); return _M_refdata(); }注意 __builtin_expect 只是用于编译器强化的方式，返回值仍然是第一个模块。
在引用复本的方式同时实现 _M_refcopy 中，对数组的引用计数+1，然后间接返回源数组的数组地址。
方式返回后，用源数组的地址外部内部结构新的数组，也是说新的 std::string 外部保存了源数组同样的地址，只是引用计数减少了 1。
再看一下发生间接复本时的代码同时实现。
template<typename _CharT, typename _Traits, typename _Alloc> _CharT* basic_string<_CharT, _Traits, _Alloc>::_Rep:: _M_clone(const _Alloc& __alloc, size_type __res) { // Requested capacity of the clone. constsize_type __requested_cap =this->_M_length + __res; _Rep* __r = _Rep::_S_create(__requested_cap, this->_M_capacity, __alloc);if (this->_M_length) _M_copy(__r->_M_refdata(), _M_refdata(), this->_M_length); __r->_M_set_length_and_sharable(this->_M_length); return __r->_M_refdata(); }_M_clone 的方式也比较容易理解，是展开缓存分配和数组复本，并设置数组长度、引用计数。
5、= 运算符
std::string str1; std::string str2(“hello world”); std1 = str2;// 选用 operator == 运算符的代码同时实现比较简单，都是调用重载了的 assign 方式。
basic_string& operator=(constbasic_string& __str) {return this->assign(__str); } basic_string& operator=(const _CharT* __s) { return this->assign(__s); }assign 同时实现类似，以 assign(const basic_string& __str) 举例。
template<typename _CharT, typename _Traits, typename _Alloc> basic_string<_CharT, _Traits, _Alloc>& basic_string<_CharT, _Traits, _Alloc>:: assign(const basic_string& __str) { if (_M_rep() != __str._M_rep()) { // XXX MT const allocator_type __a = this->get_allocator(); // 调用 _M_grab 对源数组展开复本 _CharT* __tmp = __str._M_rep()->_M_grab(__a, __str.get_allocator()); // 对现有数组的堆上缓存展开析构处理_M_rep()->_M_dispose(__a); _M_data(__tmp); }return *this; }assign 方式外部主要是对源数组展开复本，然后对现在数组的缓存展开了析构处理，并用新的数组地址外部内部结构了当前数组。
void_M_dispose(const _Alloc& __a) _GLIBCXX_NOEXCEPT { #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0 if(__builtin_expect(this != &_S_empty_rep(), false)) #endif { // Be race-detector-friendly. For more info see bits/c++config. _GLIBCXX_SYNCHRONIZATION_HAPPENS_BEFORE(&this->_M_refcount); // __exchange_and_add_dispatch 对 _M_refcount 展开减 1，但会返回 _M_refcount 原来的值 if (__gnu_cxx::__exchange_and_add_dispatch(&this->_M_refcount, -1) <=0) { _GLIBCXX_SYNCHRONIZATION_HAPPENS_AFTER(&this->_M_refcount); // 销毁当前缓存空间_M_destroy(__a); } } }_M_dispose 方式用于析构数组占用的缓存空间。其会判断当前数组的引用计数，如果当前的引用计数 <= 0，才会销毁当前的内容空间，否则只会将引用计数减 1。
6、析构方式
string 的析构方式是调用_M_dispose，如果引用计数 <= 0，才会真正销毁堆上的空间。
~basic_string() _GLIBCXX_NOEXCEPT { _M_rep()–>_M_dispose(this->get_allocator()); }7、COW 优点
gnu libstdc++ 同时实现的 std::string 主要选用了写时复本（COW）优点，用于化解如下难题：
大多数的 string 复本都用于只读每次复本消耗性能但是写时复本的优点导致存在一些难题，主要包括：
存在多线程风险。比如说某个 std::string 透过 COW 展开复本后，一个堆上的数组有可能会被数个线程同时访问，存在有多线程风险。可能减少缓存复本情况。比如说 A 和 B 共享同一段缓存，在多线程环境下同时对 A 和 B 展开写操作，可能会有如下序列：A 写操作，A 复本缓存，B 写操作，B 拷贝缓存，A 对引用计数减一，B 对引用计数减一，加上初始的一次外部内部结构总共三次缓存申请，如果选用全复本的 string，只会发生两次缓存申请。二、libc++ string
现阶段 iOS 网络平台选用的 C++ 版均已经切到了 llvm 同时实现的 libc++。
1、表述
string 的表述也比较简单，主要的同时实现仍然是在 basic_string 中。
template <class _CharT, // for<stdexcept>class _Traits = char_traits<_CharT>, class _Allocator = allocator<_CharT> > class _LIBCPP_TEMPLATE_VIS basic_string; typedef basic_string<char, char_traits<char>, allocator<char> > string;2、缓存内部结构
libc++ string 的缓存内部结构更巧妙一些，针对选用过程中更多的数组都是短数组，且数组经常是入栈申请、出栈销毁的情况。libc++ string 将数组的缓存内部结构分为了长数组模式和短数组模式。
长数组模式下，在栈上保存数组容量、大小和堆上申请的数组地址。短数组模式下，间接将其数据存在栈中，而不去堆中动态申请空间，避免了申请堆空间所需的开销 。string 唯一的成员变量是 __r_，最主要的是保存了一个 __rep。
__rep 是一个联合体类别，能保存 __long 或 __short，而 __raw 只是用于便捷的用数组的方式操作数组。__long 和 __short 分别代表了两种数组模式。
能辨认出，string 巧妙的选用了联合体类别，来保存相同模式的数组。
既然一个空间既能表示长数组又能表示短数组，那么如何判断这个数组到底是长数组还是短数组呢？
libc++ string 是透过一个 bit 标志位来判断的。
长数组 __cap_最后一个字节的末位 bit 固定为 1短数组 __size_ 的末位 bit 固定为 0由于引入了这个标志位：
长数组的容量就必须为偶数（末位只作为标志位，真实容量 = _cap – 1）短数组的长度保存时需要左移一位，而取出是需要右移一位，用于保存末位的 03、char* 外部内部结构器
template <class _CharT, class _Traits, class _Allocator> inline _LIBCPP_INLINE_VISIBILITY basic_string<_CharT, _Traits, _Allocator>::basic_string(const _CharT* __s) { _LIBCPP_ASSERT(__s != nullptr, “basic_string(const char*) detected nullptr”); __init(__s, traits_type::length(__s)); #if _LIBCPP_DEBUG_LEVEL >= 2 __get_db()->__insert_c(this); #endif }libc++ 的 char* 外部内部结构器是主要调用的是 __init 方式。
template <class _CharT, class _Traits, class _Allocator> void basic_string<_CharT, _Traits, _Allocator>::__init(const value_type* __s, size_type __sz) { if(__sz > max_size())this->__throw_length_error(); pointer __p; // <=22 字节的为短数组 if(__sz < __min_cap) {// 设置短数组长度 __set_short_size(__sz); __p = __get_short_pointer(); } else // >=23 的为长数组{// __recommend 获得推荐的容量 size_type __cap = __recommend(__sz); // 分配空间__p = __alloc_traits::allocate(__alloc(), __cap+1); // 设置__rep数据 __set_long_pointer(__p); __set_long_cap(__cap+1); __set_long_size(__sz); }// 复本数据 traits_type::copy(_VSTD::__to_raw_pointer(__p), __s, __sz); // 末尾设置为\0traits_type::assign(__p[__sz], value_type()); }__init 方式主要是针对长短数组，分别同时实现了初始化方式。
短数组，间接选用当前栈上的空间；长数组，申请推荐的容量大小，展开初始化设置。4、左值复本外部内部结构
在如是说复本外部内部结构之前，先回顾一下之前学习的 C++ 知识：左值、左值、转移语义。
左值：非临时变量。如 std::string a，a 为左值；左值：临时的对象，只在当前语句有效。如 std::string()为左值；转移语义能将资源 (堆，系统对象等) 从一个对象转移到另一个对象，这样能够减少不必要的临时对象的创建、复本以及销毁，能够大幅度提高 C++ 应用程序的性能；复本语义&转移语义约等于复本&剪切。C++ 中 & 用于表示左值引用，&& 用于表示左值引用。
如果复本外部内部结构时，源数组是一个左值，将调用左值复本外部内部结构函数。
template <class _CharT, class _Traits, class _Allocator> basic_string<_CharT, _Traits, _Allocator>::basic_string(const basic_string& __str) : __r_(__second_tag(), __alloc_traits::select_on_container_copy_construction(__str.__alloc())) { if (!__str.__is_long()) // 如果为短数组，选用数组（__raw）的方式间接复本__r_.first().__r = __str.__r_.first().__r; else // 如果为长数组，选用__init方式展开缓存复本 __init(_VSTD::__to_raw_pointer(__str.__get_long_pointer()), __str.__get_long_size()); #if _LIBCPP_DEBUG_LEVEL >= 2__get_db()->__insert_c(this); #endif }左值复本外部内部结构函数的源数组如果为
短数组，选用数组（__raw）的方式间接复本；长数组，选用 __init 方式展开缓存复本。5、左值复本外部内部结构
libc++ string 同时实现时就很好的选用了转移语义。如果源数组为左值，能间接将源数组的数据转移到新的数组，而不用重新申请空间。只不过是将源 string 堆上申请的空间间接交给新的 string 管理，源 string 不再管理原来的缓存。
template <class _CharT, class _Traits, class _Allocator> inline _LIBCPP_INLINE_VISIBILITY basic_string<_CharT, _Traits, _Allocator>::basic_string(basic_string&& __str) #if _LIBCPP_STD_VER <= 14_NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)#else _NOEXCEPT #endif // 将源数组的__r_转为左值，并初始化__r_ : __r_(_VSTD::move(__str.__r_)) { // 将源数组置空 __str.__zero(); #if _LIBCPP_DEBUG_LEVEL >= 2 // … #endif }6、析构方式
string 析构时，如果
为长数组，展开堆上缓存的释放为短数组，无需额外操作template <class _CharT, class _Traits, class _Allocator> basic_string<_CharT, _Traits, _Allocator>::~basic_string() { #if _LIBCPP_DEBUG_LEVEL >= 2__get_db()->__erase_c(this); #endif if(__is_long()) __alloc_traits::deallocate(__alloc(), __get_long_pointer(), __get_long_cap()); }三、TPSTL string
Tpstl 是百度自己合作开发一个简化版 STL。主要是为了化解：
当以静态库形式提供基础组件服务时，原生的 stl 代码容易和目标 app 编译产生冲突，透过自同时实现 stl 代码，能有效规避这种难题。std::string 同时实现过于复杂，难定位难题。1、表述
tpstl string 表述比较简单，是 basic_string<char>。
typedef basic_string<char> string;2、缓存内部结构
缓存内部结构主要包括了数组地址和数组的长度。
template <class _Tp>class basic_string{ private: // 数组地址 _Tp* _M_buf; // 数组长度 size_t _M_len; }3、char * 外部内部结构器
basic_string(const _Tp *s) :_M_buf(0), _M_len(0) { assign_str(s); }char* 外部内部结构器中，会首先将 _M_buf 和 _M_len 初始化为空值。然后调用 assign_str 方式。
template <class _Tp> void basic_string<_Tp>::assign_str(const _Tp* s) { // 将原有 _M_buf 析构_M_deallocate(_M_buf); _M_buf =0; _M_len = 0; if (s != 0) { // 取数组长度 size_t len = strlen(s); // 分配缓存空间 _M_buf = _M_allocate(len + 1); if (_M_buf == 0) { __TPSTL_ASSERT(0); return; } // 数组复本 for (size_t i = 0; i < len; i++) { _M_buf[i] = s[i]; } // 末位置 0 _M_buf[len] = 0; _M_len = len; } }assign_str 方式主要是析构原有数组，并申请空间、展开数组复本操作。
需要注意的是，tpstl 并没有间接选用系统的 malloc 和 free 方式，而是选用了自己同时实现的 _M_allocate 和 _M_deallocate 方式。实际上 tpstl 展开缓存申请和释放都是在其缓存池上展开的。
_Tp* _M_allocate(size_t__n) { _Tp* ptr = (_Tp *)__TPSTL_NAMESPACE_EX::allocate_node(sizeof(_Tp) * __n); if (ptr == 0) { __TPSTL_ASSERT(0); return 0; } __TPSTL_LEAK_COUNT_INC(sizeof(_Tp) * __n); return ptr; } void _M_deallocate(_Tp* __p) { if (__p == 0) return; __TPSTL_LEAK_COUNT_DEC(sizeof(_Tp) * (_M_len + 1)); __TPSTL_NAMESPACE_EX::deallocate_node(__p, (_M_len + 1)); }4、复本外部内部结构
tpstl string 的复本外部内部结构也只是选用了 assign_str 方式。并没有做特殊处理。
basic_string(const basic_string<_Tp>& __x) : _M_buf(0), _M_len(0) { assign_str(__x.c_str()); }5、= 运算符
tpstl string 的 = 运算符也是很简单，也只是选用了 assign_str 方式。也并没有做特殊处理。
basic_string<_Tp>&operator=(const basic_string<_Tp>& __x) { if (&__x != this) { assign_str(__x.c_str()); }return *this; }6、析构方式
string 的析构方式调用了 _M_deallocate 方式，实际都是在缓存池上展开的。
~basic_string() {_M_deallocate(_M_buf); }7、缓存池
TPSTL 外部选用了缓存池，其主要目的：
化解缓存碎片难题。由于每次都 malloc ，产生了大量的缓存碎片，透过选用缓存池，每次分配一个较大的缓存，能避免缓存碎片难题。减少 malloc 调用次数，降低性能消耗。每次申请缓存时，均透过缓存池分配，大大减少了 malloc 的次数。缓存池的同时实现原理是：
针对 8、16、24、32…128 字节的 string 分配缓存池，大于 128 的字节间接 malloc。针对相同大小的 string，每次分配一块 1KB 的空间用于缓存分配，分配缓存时间接从缓存池中取。缓存申请和释放达到很大阈值后，可展开缓存重整，回收不用的缓存缓存池针对相同大小的数组，分别分配了相同的缓存池，比如说一个 13 字节的数组，会在 16 字节大小的缓存池上展开分配。
在需要展开缓存分配时，每次分配一块 1KB 的空间用于缓存分配，如果是 16 字节大小的缓存，每个缓存块就能存储 1024/16 个数组（只不过还有一个区域存储公共字段）。
当缓存块中的缓存全部被分配过了，就会再创建一个缓存块，每个缓存块之间透过指针串起来。
如果选用过程中，某个缓存被回收，则会将下一个要被分配空间地址的指向这个缓存。
当缓存申请和释放达到很大阈值时，会展开缓存的重整，释放掉缓存全部被释放的缓存块，节省缓存空间。
四、结语
透过写作主流移动端 SDK 相关的 string 源代码，我们已经基本理解了其外部同时实现的原理。在出现 Crash 难题时，也就能依照栈信息找到具体的排查方向。
后续我会再整理一些 string 源代码崩溃的案例，分享化解难题的思路和方式。
更多干货尽在百度技术，官方QQ交流群已建立，交流讨论可加：711094866 。
