读完本文相信您可以回答以下问题:
▼ string的常见的实现方式有几种?
▼ string类的内部结构是什么样子?
▼ string内部使用的内存是如何分配管理的?
▼ string是如何拷贝构造,如何析构的,有引用计数的概念吗?
▼ string的data()和c_str()函数有什么区别?
▼ std::to_string()是如何实现的?
常见的string实现方式有两种,一种是深拷贝的方式,一种是COW(copy on write)写时拷贝方式,以前多数使用COW方式,但由于目前多线程使用越来越多,COW技术在多线程中会有额外的性能恶化,所以现在多数使用深拷贝的方式,但了解COW的技术实现还是很有必要的。
这里会对这两种方式都进行源码分析,正文内容较少,更多内容都在源码的注释中。
string的内容主要在gcc源码的三个文件中:<string>、<basic_string.h>、<basic_string.tcc>
在分析前先介绍下string或者C stl中几个基本的概念:
- size: 表示真实数据的大小,一般resize函数改变的就是这个值。
- capacity:表示内部实际已经分配的内存大小,capacity一定大于等于size,当size超过这个容量时会触发重新分配机制,一般reserve函数改变的就是这个值。
深拷贝下string的实现
<string>文件中有如下代码:
代码语言:javascript复制// file: string
using string = basic_string<char>;
这里可以看到string其实真实的样子是basic_string,这里可以看下basic_string真实的结构:
代码语言:javascript复制template <typename _CharT, typename _Traits, typename _Alloc>
class basic_string {
// Use empty-base optimization: http://www.cantrip.org/emptyopt.html
struct _Alloc_hider : allocator_type // TODO check __is_final
{
_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) {}
/**
* _M_p指向实际的数据
*/
pointer _M_p; // The actual data.
};
_Alloc_hider _M_dataplus;
/**
* 真实数据的长度,等价于前面介绍的STL中的size
*/
size_type _M_string_length;
enum { _S_local_capacity = 15 / sizeof(_CharT) };
/**
* 这里有个小技巧,用了union
* 因为使用_M_local_buf时候不需要关注_M_allocated_capacity
* 使用_M_allocated_capacity时就不需要关注_M_local_buf
* 继续向下看完您就会明白。
*/
union {
_CharT _M_local_buf[_S_local_capacity 1];
/**
* 内部已经分配的内存的大小,等价于前面介绍的STL中的capacity
*/
size_type _M_allocated_capacity;
};
};
从这里可以看见整个basic_string的结构如图:
看下面代码:
代码语言:javascript复制string str;
这段代码会调用普通构造函数,对应的源码实现如下:
代码语言:javascript复制basic_string() : _M_dataplus(_M_local_data()) { _M_set_length(0); }
而_M_local_data()的实现如下:
代码语言:javascript复制const_pointer _M_local_data() const {
return std::pointer_traits<const_pointer>::pointer_to(*_M_local_buf);
}
这里可以看见M_dataplus表示实际存放数据的地方,当string是空的时候,其实就是指向M_local_buf,且_M_string_length是0。
当由char*构造string时,构造函数如下:
代码语言:javascript复制basic_string(const _CharT* __s, size_type __n, const _Alloc& __a = _Alloc()) : _M_dataplus(_M_local_data(), __a) {
_M_construct(__s, __s __n);
}
首先让M_dataplus指向local_buf,再看下M_construct的实现,具体分析可以看下我代码中添加的注释:
代码语言:javascript复制/***
* _M_construct有很多种不同的实现,不同的迭代器类型有不同的优化实现,
* 这里我们只需要关注一种即可,整体思路是相同的。
*/
template <typename _CharT, typename _Traits, typename _Alloc>
template <typename _InIterator>
void basic_string<_CharT, _Traits, _Alloc>::_M_construct(_InIterator __beg, _InIterator __end,
std::input_iterator_tag) {
size_type __len = 0;
size_type __capacity = size_type(_S_local_capacity);
// 现在__capacity是15,注意这个值等会可能会改变
while (__beg != __end && __len < __capacity) {
_M_data()[__len ] = *__beg;
__beg;
}
/** 现在_M_data()指向的是_M_local_buf
* 上面最多会拷贝_S_local_capacity即15个字节,继续往下看,
* 当超过_S_local_capacity时会重新申请一块堆内存,_M_data()会去指向这块新内存
*/
__try {
while (__beg != __end) {
if (__len == __capacity) {
/**
* 就是在这里,当string内capacity不够容纳len个字符时,会使用_M_create去扩容
* 这里你可能会有疑惑,貌似每次while循环都会去重新使用_M_create来申请多一个字节的内存
* 但其实不是,_M_create的第一个参数的传递方式是引用传递,__capacity会在内部被修改,稍后会分析
*/
__capacity = __len 1;
pointer __another = _M_create(__capacity, __len);
/**
* 把旧数据拷贝到新的内存区域,_M_data()指向的是旧数据,__another指向的是新申请的内存
*/
this->_S_copy(__another, _M_data(), __len);
/**
* __M_dispose()
* 释放_M_data()指向的旧数据内存,如果是_M_local_buf则不需要释放,稍后分析
*/
_M_dispose();
/**
* _M_data()
* 内部的指向内存的指针指向这块新申请的内存__another,它的实现其实就是
* void _M_data(pointer __p) { _M_dataplus._M_p = __p; }
*/
_M_data(__another);
/**
* _M_allocated_capacity设置为__capacity
* 实现为 void _M_capacity(size_type __capacity) { _M_allocated_capacity = __capacity; }
*/
_M_capacity(__capacity);
}
_M_data()[__len ] = *__beg;
__beg;
}
}
__catch(...) {
/**
* 异常发生时,避免内存泄漏,会释放掉内部申请的内存
*/
_M_dispose();
__throw_exception_again;
}
/**
* 最后设置string的长度为__len
* 实现为void _M_length(size_type __length) { _M_string_length = __length; }
*/
_M_set_length(__len);
}
再分析下内部的内存申请函数_M_create:
代码语言:javascript复制/**
* @brief _M_create表示申请新内存
* @param __capacity 想要申请的内存大小,注意这里参数传递方式是引用传递,内部会改变其值
* @param __old_capacity 以前的内存大小
*/
template <typename _CharT, typename _Traits, typename _Alloc>
typename basic_string<_CharT, _Traits, _Alloc>::pointer basic_string<_CharT, _Traits, _Alloc>::_M_create(
size_type& __capacity, size_type __old_capacity) {
/**
* max_size()表示标准库容器规定的一次性可以分配到最大内存大小
* 当想要申请的内存大小最大规定长度时,会抛出异常
*/
if (__capacity > max_size()) std::__throw_length_error(__N("basic_string::_M_create"));
/**
* 这里就是常见的STL动态扩容机制,其实常见的就是申请为__old_capacity的2倍大小的内存,最大只能申请max_size()
* 注释只是说了常见的内存分配大小思想,不全是下面代码的意思,具体可以直接看下面这几行代码哈
*/
if (__capacity > __old_capacity && __capacity < 2 * __old_capacity) {
__capacity = 2 * __old_capacity;
// Never allocate a string bigger than max_size.
if (__capacity > max_size()) __capacity = max_size();
}
/**
* 使用内存分配子去分配__capacity 1大小的内存, 1是为了多存储个
*/
return _Alloc_traits::allocate(_M_get_allocator(), __capacity 1);
}
再分析下内部的内存释放函数_M_dispose函数:
代码语言:javascript复制/**
* 如果当前指向的是本地内存那15个字节,则不需要释放
* 如果不是,则需要使用_M_destroy去释放其指向的内存
*/
void _M_dispose() {
if (!_M_is_local()) _M_destroy(_M_allocated_capacity);
}
/**
* 判断下当前内部指向的是不是本地内存
* _M_local_data()即返回_M_local_buf的地址
*/
bool _M_is_local() const { return _M_data() == _M_local_data(); }
void _M_destroy(size_type __size) throw() {
_Alloc_traits::deallocate(_M_get_allocator(), _M_data(), __size 1);
}
再分析下basic_string的拷贝构造函数:
代码语言:javascript复制/**
* basic_string的拷贝构造函数
* 其实就是每次都做一次深拷贝
*/
basic_string(const basic_string& __str)
: _M_dataplus(_M_local_data(), _Alloc_traits::_S_select_on_copy(__str._M_get_allocator())) {
_M_construct(__str._M_data(), __str._M_data() __str.length());
}
再分析下basic_string的赋值构造函数:
代码语言:javascript复制/**
* 赋值构造函数,调用了assign函数
*/
basic_string& operator=(const basic_string& __str) { return this->assign(__str); }
/**
* 调用了_M_assign函数
*/
basic_string& assign(const basic_string& __str) {
this->_M_assign(__str);
return *this;
}
/**
* 赋值的核心函数
*/
template <typename _CharT, typename _Traits, typename _Alloc>
void basic_string<_CharT, _Traits, _Alloc>::_M_assign(const basic_string& __str) {
if (this != &__str) {
const size_type __rsize = __str.length();
const size_type __capacity = capacity();
/**
* 如果capacity不够用,需要进行重新分配
*/
if (__rsize > __capacity) {
size_type __new_capacity = __rsize;
pointer __tmp = _M_create(__new_capacity, __capacity);
_M_dispose();
_M_data(__tmp);
_M_capacity(__new_capacity);
}
/**
* 将__str指向的内存拷贝到当前对象指向的内存上
*/
if (__rsize) this->_S_copy(_M_data(), __str._M_data(), __rsize);
_M_set_length(__rsize);
}
}
再分析下移动构造函数:
代码语言:javascript复制/**
* 移动构造函数,其实就是把src指向的内存移动到了dst种
*/
basic_string(basic_string&& __str) noexcept : _M_dataplus(_M_local_data(), std::move(__str._M_get_allocator())) {
if (__str._M_is_local()) {
traits_type::copy(_M_local_buf, __str._M_local_buf, _S_local_capacity 1);
} else {
_M_data(__str._M_data());
_M_capacity(__str._M_allocated_capacity);
}
// Must use _M_length() here not _M_set_length() because
// basic_stringbuf relies on writing into unallocated capacity so
// we mess up the contents if we put a '