本篇内容主要讲解“C++是怎么实现string的”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“C++是怎么实现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>文件中有如下代码:
// file: string using string = basic_string<char>;
这里可以看到string其实真实的样子是basic_string,这里可以看下basic_string真实的结构:
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的结构如图:
看下面代码:
string str;
这段代码会调用普通构造函数,对应的源码实现如下:
basic_string() : _M_dataplus(_M_local_data()) { _M_set_length(0); }
而_M_local_data()的实现如下:
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时,构造函数如下:
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的实现,具体分析可以看下我代码中添加的注释:
/*** * _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:
/** * @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函数:
/** * 如果当前指向的是本地内存那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的拷贝构造函数:
/** * 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的赋值构造函数:
/** * 赋值构造函数,调用了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); } }
再分析下移动构造函数:
/** * 移动构造函数,其实就是把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 '