来源：腾讯技术工程
作者：lucasfan，腾讯 IEG 游戏客户端开发工程师
使用 C++ 进行 SDK 开发的同学一定少不了遇到现网偶现的 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、定义
typedef basic_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指向的并不是_Rep数据结构的起始地址，而是字符串的起始地址。由于 _Rep数据结构的大小是已知的，因此可以通过字符串的起始地址减 _Rep 的大小，就可以获取 _Rep 对象的地址。
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.
const size_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=(const basic_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 将字符串的内存结构分为了长字符串模式和短字符串模式。
长字符串模式下，在栈上保存字符串容量、大小和堆上申请的字符串地址。
短字符串模式下，直接将其数据存在栈中，而不去堆中动态申请空间，避免了申请堆空间所需的开销 。
万字详文：三个版本的C++ string 源码实现对比
struct __long // 24字节
{
// 字符串容量
size_type __cap_;
// 字符串实际大小
size_type __size_;
// 字符串指针
pointer __data_;
};
// __min_cap = 24-1（long类型的大小减一个字节的大小，1个字节用于存储短字符串的实际大小）
enum {__min_cap = (sizeof(__long) - 1)/sizeof(value_type) > 2 ?
(sizeof(__long) - 1)/sizeof(value_type) : 2};
struct __short // 24字节
{
union
{
unsigned char __size_;
value_type __lx;
};
value_type __data_[__min_cap];
};
union __ulx{__long __lx; __short __lxx;};
enum {__n_words = sizeof(__ulx) / sizeof(size_type)};
struct __raw // 24字节
{
size_type __words[__n_words];
};
// 最关键的联合体类型
struct __rep
{
union
{
__long __l;
__short __s;
__raw __r;
};
};
// 唯一的成员变量
__compressed_pair<__rep, allocator_type> __r_;
string 唯一的成员变量就是 __r_，最主要的是保存了一个 __rep。
__rep 是一个联合体类型，可以保存 __long 或 __short，而 __raw 只是用于便捷的用数组的方式操作字符串。__long 和 __short 分别代表了两种字符串模式。
可以发现，string 巧妙的使用了联合体类型，来保存不同模式的字符串。
既然一个空间既可以表示长字符串又可以表示短字符串，那么如何判断这个字符串到底是长字符串还是短字符串呢？
libc++ string 是通过一个 bit 标志位来判断的。
长字符串 __cap_最后一个字节的末位 bit 固定为 1
短字符串 __size_ 的末位 bit 固定为 0
由于引入了这个标志位：
长字符串的容量就必须为偶数（末位只作为标志位，真实容量 = _cap - 1）
短字符串的长度保存时需要左移一位，而取出是需要右移一位，用于保存末位的 0
3、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);
// 末尾设置为\0
traits_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 = s;
}
// 末位置 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 问题时，也就可以根据堆栈信息找到具体的排查方向。
/3 
