string不是std的成员_C++ string 源码实现对比
作者：lucasfan，腾讯 IEG 游戏客户端开发工程师
使用 C++ 进行 SDK 开发的同学一定少不了遇到现网偶现的 Crash 问题，而崩溃堆栈有很多直接 Crash 在 std::string 源码中，std::string 源码晦涩难懂增加了 Debug 的难度。在多次与 std::string 的斗争中，笔者阅读了多个版本的 string 实现源码，对重要的实现进行分析、并对比其实现，希望对各位同学有帮助。
本文将对比以下几个版本的 string 源码实现。
string 版本场景特性libstdc++ string（gnu4.9）腾讯内部 Android SDK 常用写时拷贝（COW）libc++ string腾讯内部 iOS SDK 常用短字符串优化（SSO）；右值拷贝构造tpstl string腾讯自研 string， SDK 内部使用解决跨库问题；内存池
在 Class 实现中，最重要的就是 Class 的定义、内存结构、常用构造器、= 操作符、析构方法，本文将对三种不同的 string 实现进行介绍。
- C++ string 源码实现对比
- 一、libstdc++ string
- 二、libc++ string
- 三、TPSTL 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 将字符串的内存结构分为了长字符串模式和短字符串模式。
- 长字符串模式下，在栈上保存字符串容量、大小和堆上申请的字符串地址。
- 短字符串模式下，直接将其数据存在栈中，而不去堆中动态申请空间，避免了申请堆空间所需的开销 。
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[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 。