C++是怎么实现string的

本篇内容主要讲解“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: stringusing 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) {}                pointer _M_p;  // The actual data.    };    _Alloc_hider _M_dataplus;        size_type _M_string_length;    enum { _S_local_capacity = 15 / sizeof(_CharT) };        union {        _CharT _M_local_buf[_S_local_capacity + 1];                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的实现，具体分析可以看下我代码中添加的注释：

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;    }        __try {        while (__beg != __end) {            if (__len == __capacity) {                                __capacity = __len + 1;                pointer __another = _M_create(__capacity, __len);                                this->_S_copy(__another, _M_data(), __len);                                _M_dispose();                                _M_data(__another);                                _M_capacity(__capacity);            }            _M_data()[__len++] = *__beg;            ++__beg;        }    }    __catch(...) {                _M_dispose();        __throw_exception_again;    }        _M_set_length(__len);}

再分析下内部的内存申请函数_M_create：

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) {        if (__capacity > max_size()) std::__throw_length_error(__N("basic_string::_M_create"));        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();    }        return _Alloc_traits::allocate(_M_get_allocator(), __capacity + 1);}

再分析下内部的内存释放函数_M_dispose函数:

void _M_dispose() {    if (!_M_is_local()) _M_destroy(_M_allocated_capacity);}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(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的赋值构造函数：

basic_string& operator=(const basic_string& __str) { return this->assign(__str); }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();                if (__rsize > __capacity) {            size_type __new_capacity = __rsize;            pointer __tmp = _M_create(__new_capacity, __capacity);            _M_dispose();            _M_data(__tmp);            _M_capacity(__new_capacity);        }                if (__rsize) this->_S_copy(_M_data(), __str._M_data(), __rsize);        _M_set_length(__rsize);    }}

再分析下移动构造函数：

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 '\0' in the string.    _M_length(__str.length());    __str._M_data(__str._M_local_data());    __str._M_set_length(0);}

移动赋值函数和移动构造函数类似，就不作过多分析啦。

COW方式下string的实现

先看下部分源代码了解下COW的basic_string的结构：

template <typename _CharT, typename _Traits, typename _Alloc>class basic_string {   private:    struct _Rep_base {                size_type _M_length;                size_type _M_capacity;                _Atomic_word _M_refcount;    };        struct _Rep : _Rep_base {        // Types:        typedef typename _Alloc::template rebind<char>::other _Raw_bytes_alloc;        static const size_type _S_max_size;        static const _CharT _S_terminal;  // \0        static size_type _S_empty_rep_storage[];  // 这里大小不是0，稍后分析        static _Rep& _S_empty_rep() _GLIBCXX_NOEXCEPT {            // NB: Mild hack to avoid strict-aliasing warnings.  Note that            // _S_empty_rep_storage is never modified and the punning should            // be reasonably safe in this case.            void* __p = reinterpret_cast<void*>(&_S_empty_rep_storage);            return *reinterpret_cast<_Rep*>(__p);        }    };    // Use empty-base optimization: http://www.cantrip.org/emptyopt.html    struct _Alloc_hider : _Alloc {        _Alloc_hider(_CharT* __dat, const _Alloc& __a) _GLIBCXX_NOEXCEPT : _Alloc(__a), _M_p(__dat) {}        _CharT* _M_p;  // The actual data，这里的_M_p指向存储实际数据的对象地址    };   public:    static const size_type npos = static_cast<size_type>(-1);  // 0xFFFFFFFF   private:        mutable _Alloc_hider _M_dataplus;};

具体分析可以看代码中注释，可以分析出COW的string结构如图：

前面程序喵分析过深拷贝方式下string的局部内存为_M_local_buf，那COW下string的_S_empty_rep_storage是什么样子呢？直接看源代码：

// Linker sets _S_empty_rep_storage to all 0s (one reference, empty string)// at static init time (before static ctors are run).template <typename _CharT, typename _Traits, typename _Alloc>typename basic_string<_CharT, _Traits, _Alloc>::size_type basic_string<_CharT, _Traits, _Alloc>::_Rep::    _S_empty_rep_storage[(sizeof(_Rep_base) + sizeof(_CharT) + sizeof(size_type) - 1) / sizeof(size_type)];

再分析下构造函数：

template <typename _CharT, typename _Traits, typename _Alloc>basic_string<_CharT, _Traits, _Alloc>::basic_string(const _CharT* __s, size_type __n, const _Alloc& __a)    : _M_dataplus(_S_construct(__s, __s + __n, __a), __a) {}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,                                                            input_iterator_tag) {#if _GLIBCXX_FULLY_DYNAMIC_STRING == 0    if (__beg == __end && __a == _Alloc()) return _S_empty_rep()._M_refdata();#endif    // Avoid reallocation for common case.    _CharT __buf[128];    size_type __len = 0;    while (__beg != __end && __len < sizeof(__buf) / sizeof(_CharT)) {        __buf[__len++] = *__beg;        ++__beg;    }        _Rep* __r = _Rep::_S_create(__len, size_type(0), __a);        _M_copy(__r->_M_refdata(), __buf, __len);    __try {                while (__beg != __end) {            if (__len == __r->_M_capacity) {                // Allocate more space.                _Rep* __another = _Rep::_S_create(__len + 1, __len, __a);                _M_copy(__another->_M_refdata(), __r->_M_refdata(), __len);                __r->_M_destroy(__a);                __r = __another;            }            __r->_M_refdata()[__len++] = *__beg;            ++__beg;        }    }    __catch(...) {        __r->_M_destroy(__a);        __throw_exception_again;    }        __r->_M_set_length_and_sharable(__len);    return __r->_M_refdata();}

再看下string内部_M_create是如何申请内存的

template <typename _CharT, typename _Traits, typename _Alloc>typename basic_string<_CharT, _Traits, _Alloc>::_Rep* basic_string<_CharT, _Traits, _Alloc>::_Rep::_S_create(    size_type __capacity, size_type __old_capacity, const _Alloc& __alloc) {    if (__capacity > _S_max_size) __throw_length_error(__N("basic_string::_S_create"));        const size_type __pagesize = 4096;    const size_type __malloc_header_size = 4 * sizeof(void*);        if (__capacity > __old_capacity && __capacity < 2 * __old_capacity) __capacity = 2 * __old_capacity;        size_type __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);        const size_type __adj_size = __size + __malloc_header_size;    if (__adj_size > __pagesize && __capacity > __old_capacity) {        const size_type __extra = __pagesize - __adj_size % __pagesize;        __capacity += __extra / sizeof(_CharT);        // Never allocate a string bigger than _S_max_size.        if (__capacity > _S_max_size) __capacity = _S_max_size;        __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);    }    // NB: Might throw, but no worries about a leak, mate: _Rep()    // does not throw.    void* __place = _Raw_bytes_alloc(__alloc).allocate(__size);        _Rep* __p = new (__place) _Rep;    __p->_M_capacity = __capacity;        __p->_M_set_sharable();    return __p;}

这里有关于malloc的知识点可以看我之前写的文章，前面Rep有个_M_set_length_and_sharable方法，看下它的源码：

void _M_set_length_and_sharable(size_type __n) _GLIBCXX_NOEXCEPT {#if _GLIBCXX_FULLY_DYNAMIC_STRING == 0    if (__builtin_expect(this != &_S_empty_rep(), false))#endif    {        this->_M_set_sharable();  // One reference.        this->_M_length = __n;        traits_type::assign(this->_M_refdata()[__n], _S_terminal);    }}void _M_set_sharable() _GLIBCXX_NOEXCEPT { this->_M_refcount = 0; }

COW版本主要就是为了避免过多的拷贝，这里看下string的拷贝构造函数：

basic_string(const basic_string& __str, const _Alloc& __a)    : _M_dataplus(__str._M_rep()->_M_grab(__a, __str.get_allocator()), __a) {}_Rep* _M_rep() const _GLIBCXX_NOEXCEPT { return &((reinterpret_cast<_Rep*>(_M_data()))[-1]); }_CharT* _M_grab(const _Alloc& __alloc1, const _Alloc& __alloc2) {    return (!_M_is_leaked() && __alloc1 == __alloc2) ? _M_refcopy() : _M_clone(__alloc1);}bool _M_is_leaked() const _GLIBCXX_NOEXCEPT {#if defined(__GTHREADS)    // _M_refcount is mutated concurrently by _M_refcopy/_M_dispose,    // so we need to use an atomic load. However, _M_is_leaked    // predicate does not change concurrently (i.e. the string is either    // leaked or not), so a relaxed load is enough.    return __atomic_load_n(&this->_M_refcount, __ATOMIC_RELAXED) < 0;#else    return this->_M_refcount < 0;#endif}_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();}  // XXX MTtemplate <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();}

再分析下string的析构函数：

~basic_string() _GLIBCXX_NOEXCEPT { _M_rep()->_M_dispose(this->get_allocator()); }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);        if (__gnu_cxx::__exchange_and_add_dispatch(&this->_M_refcount, -1) <= 0) {            _GLIBCXX_SYNCHRONIZATION_HAPPENS_AFTER(&this->_M_refcount);            _M_destroy(__a);        }    }}  // XXX MTtemplate <typename _CharT, typename _Traits, typename _Alloc>void basic_string<_CharT, _Traits, _Alloc>::_Rep::_M_destroy(const _Alloc& __a) throw() {    const size_type __size = sizeof(_Rep_base) + (this->_M_capacity + 1) * sizeof(_CharT);    _Raw_bytes_alloc(__a).deallocate(reinterpret_cast<char*>(this), __size);}

data()和c_str()的区别

我们以前学习工作过程中都知道str有data和c_str函数，看资料都说它们的区别是一个带\0结束符，一个不带。 这里看下源码：

const _CharT* c_str() const _GLIBCXX_NOEXCEPT { return _M_data(); }const _CharT* data() const _GLIBCXX_NOEXCEPT { return _M_data(); }

这里可以看见它俩没有任何区别，因为\0结束符其实在最开始构造string对象的时候就已经添加啦。

to_string是怎么实现的

这里直接看代码：

inline string to_string(int __val) {    return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, 4 * sizeof(int), "%d", __val);}inline string to_string(unsigned __val) {    return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, 4 * sizeof(unsigned), "%u", __val);}inline string to_string(long __val) {    return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, 4 * sizeof(long), "%ld", __val);}template <typename _String, typename _CharT = typename _String::value_type>_String __to_xstring(int (*__convf)(_CharT*, std::size_t, const _CharT*, __builtin_va_list), std::size_t __n,                     const _CharT* __fmt, ...) {    // XXX Eventually the result should be constructed in-place in    // the __cxx11 string, likely with the help of internal hooks.    _CharT* __s = static_cast<_CharT*>(__builtin_alloca(sizeof(_CharT) * __n));    __builtin_va_list __args;    __builtin_va_start(__args, __fmt);    const int __len = __convf(__s, __n, __fmt, __args);    __builtin_va_end(__args);    return _String(__s, __s + __len);}

这里可以看出所有的数值类型转string，都是通过vsnprintf来实现，具体vsnprintf是什么这里就不过多介绍啦，读者可以自行查找下相关用法哈。

到此，相信大家对“C++是怎么实现string的”有了更深的了解，不妨来实际操作一番吧！这里是编程网网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！