libc++源码分析之std::string

发表于 分类于 本文字数： 2.5k 阅读时长 ≈ 9 分钟

std::string

1
typedef basic_string<char, char_traits<char>, allocator<char> > string;

数据结构

在basic_string实现中，对短字符串进行了优化，长短字符长存储的数据结构是不一样的。

1
2
3
4
5
6
7
8
9
10
11
struct __rep
{
    union
    {
        __long  __l;
        __short __s;
        __raw   __r;
    };
};

__compressed_pair<__rep, allocator_type> __r_;

长字符串

长字符串会根据字符大小动态分配内存，data中存储字符数组的指针，当字符大小超过分配的长度时，会进行扩容。

1
2
3
4
5
6
7
// 总共24个字节
struct __long
{
    size_type __cap_; // 分配的字符数组长度
    size_type __size_; // 字符串长度
    pointer   __data_; // 字符数组指针
};

短字符串

短字符串最多存储22个字符（最后一位为0），所以小于23长度的都是短字符串存储，超过都是长字符串存储。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 23
enum {__min_cap = (sizeof(__long) - 1)/sizeof(value_type) > 2 ?
                  (sizeof(__long) - 1)/sizeof(value_type) : 2};

// 总共24个字节
struct __short
{
    union
    {
        unsigned char __size_; // 字符串长度
        value_type __lx;
    };
    value_type __data_[__min_cap]; // 字符数组
};

长短字符串标记

通过在数据结构的第一个字节插入标记来区分当前是长字符还是短字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#ifdef _LIBCPP_BIG_ENDIAN
    static const size_type __short_mask = 0x80;
    static const size_type __long_mask  = ~(size_type(~0) >> 1);
#else  // _LIBCPP_BIG_ENDIAN
    static const size_type __short_mask = 0x01;
    static const size_type __long_mask  = 0x1ul;
#endif // _LIBCPP_BIG_ENDIAN

在小端环境下，对于短字符，会把size字段的最低位标记为0（通过左移）。大端环境下，由于短字符的size最大为22，所以最高位一定是0.
```c++
    _LIBCPP_INLINE_VISIBILITY
    void __set_short_size(size_type __s) _NOEXCEPT
#   ifdef _LIBCPP_BIG_ENDIAN
        {__r_.first().__s.__size_ = (unsigned char)(__s);}
#   else
        {__r_.first().__s.__size_ = (unsigned char)(__s << 1);}
#   endif

对于长字符，其分配的内存大小都是经过字节对齐的，所以其最低位一定是0，通过把cap字段的最低位标记为1（大端环境下是把最高位标记为1），来标记是长字符。

1
2
3
_LIBCPP_INLINE_VISIBILITY
void __set_long_cap(size_type __s) _NOEXCEPT
    {__r_.first().__l.__cap_  = __long_mask | __s;}

所以判断是否是长字符，只需要判断其第一个字节的最低位是否是1即可。

1
2
3
_LIBCPP_INLINE_VISIBILITY
bool __is_long() const _NOEXCEPT
    {return bool(__r_.first().__s.__size_ & __short_mask);}

构造函数

basic_string提供了多种构造，可以方便的创建。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
basic_string() noexcept;
explicit basic_string(const allocator_type& a);
basic_string(const basic_string& str);
basic_string(basic_string&& str) noexcept;
basic_string(const basic_string& str, size_type pos, const allocator_type& a = allocator_type());
basic_string(const basic_string& str, size_type pos, size_type n, const Allocator& a = Allocator());
template<class T> basic_string(const T& t, size_type pos, size_type n, const Allocator& a = Allocator()); // C++17
template <class T> explicit basic_string(const T& t, const Allocator& a = Allocator()); // C++17
basic_string(const value_type* s, const allocator_type& a = allocator_type());
basic_string(const value_type* s, size_type n, const allocator_type& a = allocator_type());
basic_string(size_type n, value_type c, const allocator_type& a = allocator_type());
template<class InputIterator> basic_string(InputIterator begin, InputIterator end, const allocator_type& a = allocator_type());
basic_string(initializer_list<value_type>, const Allocator& = Allocator());
basic_string(const basic_string&, const Allocator&);
basic_string(basic_string&&, const Allocator&);

init

一个string构造初始化流程基本如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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;
    if (__sz < __min_cap)
    {
        // 如果当前初始化的字符长度小于23，则判定为短字符
        __set_short_size(__sz); // 存储字符长度（不包含尾部的0）
        __p = __get_short_pointer(); // 获取存储数据的字符数组
    }
    else
    {
        size_type __cap = __recommend(__sz); // 根据字符长度进行字节对齐，返回结果会-1
        __p = __alloc_traits::allocate(__alloc(), __cap+1); // 分配内存
        __set_long_pointer(__p); // 存储指针
        __set_long_cap(__cap+1); // 存储分配大小
        __set_long_size(__sz); // 存储字符长度
    }
    traits_type::copy(_VSTD::__to_address(__p), __s, __sz); // 字符拷贝
    traits_type::assign(__p[__sz], value_type()); // 尾部插0
}

append

通过+=操作符进行字符串加操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
template <class _CharT, class _Traits, class _Allocator>
basic_string<_CharT, _Traits, _Allocator>&
basic_string<_CharT, _Traits, _Allocator>::append(const value_type* __s, size_type __n)
{
    _LIBCPP_ASSERT(__n == 0 || __s != nullptr, "string::append received nullptr");
    size_type __cap = capacity();
    size_type __sz = size();
    if (__cap - __sz >= __n)
    {
        // 如果追加后的字符长度小于当前分配的长度，则直接拷贝
        if (__n)
        {
            value_type* __p = _VSTD::__to_address(__get_pointer()); // 获取字符数组
            traits_type::copy(__p + __sz, __s, __n); // 拷贝
            __sz += __n;
            __set_size(__sz); // 更新字符长度
            traits_type::assign(__p[__sz], value_type()); // 尾部插0
        }
    }
    else
        __grow_by_and_replace(__cap, __sz + __n - __cap, __sz, __sz, 0, __n, __s); // 长度不够，扩容
    return *this;
}

数据扩容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
template <class _CharT, class _Traits, class _Allocator>
void
basic_string<_CharT, _Traits, _Allocator>::__grow_by_and_replace
    (size_type __old_cap, size_type __delta_cap, size_type __old_sz,
     size_type __n_copy,  size_type __n_del,     size_type __n_add, const value_type* __p_new_stuff)
{
    size_type __ms = max_size();
    if (__delta_cap > __ms - __old_cap - 1)
        this->__throw_length_error();
    pointer __old_p = __get_pointer();
    // 扩容最小扩大一倍，如果不够，则根据需要大小来扩容
    size_type __cap = __old_cap < __ms / 2 - __alignment ?
                          __recommend(_VSTD::max(__old_cap + __delta_cap, 2 * __old_cap)) :
                          __ms - 1;
    pointer __p = __alloc_traits::allocate(__alloc(), __cap+1); // 重新分配内存
    __invalidate_all_iterators();
    if (__n_copy != 0)
        traits_type::copy(_VSTD::__to_address(__p),
                          _VSTD::__to_address(__old_p), __n_copy); // 将已有数据拷贝到新分配内存上
    if (__n_add != 0)
        traits_type::copy(_VSTD::__to_address(__p) + __n_copy, __p_new_stuff, __n_add); // 将新数据拷贝到新分配内存上
    size_type __sec_cp_sz = __old_sz - __n_del - __n_copy;
    if (__sec_cp_sz != 0)
        traits_type::copy(_VSTD::__to_address(__p) + __n_copy + __n_add,
                          _VSTD::__to_address(__old_p) + __n_copy + __n_del, __sec_cp_sz); // 将部分数据移动到新分配数据后面，insert pos情况下
    if (__old_cap+1 != __min_cap)
        __alloc_traits::deallocate(__alloc(), __old_p, __old_cap+1); // 如果已有数据是长字符，则需要销毁之前分配的内存
    __set_long_pointer(__p); // 需要扩容的一定是长字符
    __set_long_cap(__cap+1);
    __old_sz = __n_copy + __n_add + __sec_cp_sz;
    __set_long_size(__old_sz);
    traits_type::assign(__p[__old_sz], value_type()); // 尾部插0
}

resize

设置字符长度，设置的是size长度。

1
2
3
_LIBCPP_INLINE_VISIBILITY void resize(size_type __n) {
    resize(__n, value_type());
}
1
2
3
4
5
6
7
8
9
10
template <class _CharT, class _Traits, class _Allocator>
void
basic_string<_CharT, _Traits, _Allocator>::resize(size_type __n, value_type __c)
{
    size_type __sz = size();
    if (__n > __sz)
        append(__n - __sz, __c); // 如果resize的长度超过已有字符长度，则向当前字符后面追加超过长度的0字符
    else
        __erase_to_end(__n); // 如果resize的长度小于已有字符长度，则将n位置置位0，更新字符长度
}

reserve

设置分配内存大小，设置的是cap大小，size不会变。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template <class _CharT, class _Traits, class _Allocator>
void
basic_string<_CharT, _Traits, _Allocator>::reserve(size_type __requested_capacity)
{
    if (__requested_capacity > max_size())
        this->__throw_length_error();

#if _LIBCPP_STD_VER > 17
    // Reserve never shrinks as of C++20.
    if (__requested_capacity <= capacity()) return;
#endif

    size_type __target_capacity = _VSTD::max(__requested_capacity, size());
    __target_capacity = __recommend(__target_capacity);
    if (__target_capacity == capacity()) return;

    __shrink_or_extend(__target_capacity); // 对于长字符，重新分配内存，将已有字符拷贝到新内存
}

clear

清空字符长度，并不会销毁内存

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template <class _CharT, class _Traits, class _Allocator>
inline
void
basic_string<_CharT, _Traits, _Allocator>::clear() _NOEXCEPT
{
    __invalidate_all_iterators();
    // 将字符数组第一个设置为0，并将字符长度设置为0
    if (__is_long())
    {
        traits_type::assign(*__get_long_pointer(), value_type());
        __set_long_size(0);
    }
    else
    {
        traits_type::assign(*__get_short_pointer(), value_type());
        __set_short_size(0);
    }
}

operator[]

1
2
3
4
5
6
7
8
template <class _CharT, class _Traits, class _Allocator>
inline
typename basic_string<_CharT, _Traits, _Allocator>::reference
basic_string<_CharT, _Traits, _Allocator>::operator[](size_type __pos) _NOEXCEPT
{
    _LIBCPP_ASSERT(__pos <= size(), "string index out of bounds");
    return *(__get_pointer() + __pos);
}

at

at多了一个越界的检查，会抛出异常，里面也是调用[]操作符

1
2
3
4
5
6
7
8
template <class _CharT, class _Traits, class _Allocator>
typename basic_string<_CharT, _Traits, _Allocator>::reference
basic_string<_CharT, _Traits, _Allocator>::at(size_type __n)
{
    if (__n >= size())
        this->__throw_out_of_range();
    return (*this)[__n];
}

insert

在指定位置插入新字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
template <class _CharT, class _Traits, class _Allocator>
basic_string<_CharT, _Traits, _Allocator>&
basic_string<_CharT, _Traits, _Allocator>::insert(size_type __pos, const value_type* __s, size_type __n)
{
    _LIBCPP_ASSERT(__n == 0 || __s != nullptr, "string::insert received nullptr");
    size_type __sz = size();
    if (__pos > __sz)
        this->__throw_out_of_range();
    size_type __cap = capacity();
    if (__cap - __sz >= __n)
    {
        // 如果分配的内存大小够用
        if (__n)
        {
            value_type* __p = _VSTD::__to_address(__get_pointer());
            size_type __n_move = __sz - __pos;
            if (__n_move != 0)
            {
                if (__p + __pos <= __s && __s < __p + __sz)
                    __s += __n;
                traits_type::move(__p + __pos + __n, __p + __pos, __n_move); // 将pos后面的字符移动到后面，空出n个字符位置
            }
            traits_type::move(__p + __pos, __s, __n); // 将新字符插入到指定位置
            __sz += __n;
            __set_size(__sz); // 更新字符长度
            traits_type::assign(__p[__sz], value_type()); // 尾部插0
        }
    }
    else
        __grow_by_and_replace(__cap, __sz + __n - __cap, __sz, __pos, 0, __n, __s); // 扩容
    return *this;
}

erase

删除指定位置后面的指定长度的数据，只是改变了size，并没有销毁内存

1
2
3
4
5
6
7
8
9
10
11
12
template <class _CharT, class _Traits, class _Allocator>
basic_string<_CharT, _Traits, _Allocator>&
basic_string<_CharT, _Traits, _Allocator>::erase(size_type __pos,
                                                 size_type __n) {
  if (__pos > size()) this->__throw_out_of_range();
  if (__n == npos) {
    __erase_to_end(__pos); // 默认删除指定位置后面所有数据
  } else {
    __erase_external_with_move(__pos, __n); // 删除指定位置后面n个数据，pos+n后面的数据会移动到pos位置
  }
  return *this;
}

replace

pos到pos+n1位置的数据用s到s+n2的数据来替换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
template <class _CharT, class _Traits, class _Allocator>
basic_string<_CharT, _Traits, _Allocator>&
basic_string<_CharT, _Traits, _Allocator>::replace(size_type __pos, size_type __n1, const value_type* __s, size_type __n2)
    _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
{
    _LIBCPP_ASSERT(__n2 == 0 || __s != nullptr, "string::replace received nullptr");
    size_type __sz = size();
    if (__pos > __sz)
        this->__throw_out_of_range();
    __n1 = _VSTD::min(__n1, __sz - __pos);
    size_type __cap = capacity();
    if (__cap - __sz + __n1 >= __n2)
    {
        value_type* __p = _VSTD::__to_address(__get_pointer());
        if (__n1 != __n2)
        {
            size_type __n_move = __sz - __pos - __n1;
            if (__n_move != 0)
            {   // 如果 pos + n1后面还有数据
                if (__n1 > __n2)
                {   // 如果n1大于n2，直接将n2放入到n1，再将n1后面的数据移动到n2后面
                    traits_type::move(__p + __pos, __s, __n2); // 移动[s,s+n2]的数据到[p,p+n2]
                    traits_type::move(__p + __pos + __n2, __p + __pos + __n1, __n_move); // 移动[pos,n1]后面的数据到[p+p2, n_move]
                    goto __finish;
                }
                if (__p + __pos < __s && __s < __p + __sz)
                {   // 如果n1小于n2，需要先将n1后面的数据向后移动，才能放得下n2
                    if (__p + __pos + __n1 <= __s)
                        __s += __n2 - __n1;
                    else // __p + __pos < __s < __p + __pos + __n1
                    {
                        traits_type::move(__p + __pos, __s, __n1);
                        __pos += __n1;
                        __s += __n2;
                        __n2 -= __n1;
                        __n1 = 0;
                    }
                }
                traits_type::move(__p + __pos + __n2, __p + __pos + __n1, __n_move);
            }
        }
        traits_type::move(__p + __pos, __s, __n2);
__finish:
// __sz += __n2 - __n1; in this and the below function below can cause unsigned
// integer overflow, but this is a safe operation, so we disable the check.
        __sz += __n2 - __n1;
        __set_size(__sz);
        __invalidate_iterators_past(__sz);
        traits_type::assign(__p[__sz], value_type());
    }
    else
        __grow_by_and_replace(__cap, __sz - __n1 + __n2 - __cap, __sz, __pos, __n1, __n2, __s); // 扩容
    return *this;
}

substr

会重新拷贝一份数据

1
2
3
4
5
6
7
template <class _CharT, class _Traits, class _Allocator>
inline
basic_string<_CharT, _Traits, _Allocator>
basic_string<_CharT, _Traits, _Allocator>::substr(size_type __pos, size_type __n) const
{
    return basic_string(*this, __pos, __n, __alloc());
}

operator std::string_view

支持隐式转换为std::string_view

1
2
3
4
_LIBCPP_INLINE_VISIBILITY
operator __self_view() const _NOEXCEPT { 
    return __self_view(data(), size()); 
}

std::string_view

string_view是一个轻量级的字符串类，相比string每次都会拷贝数据，在string_view中只会存储数据的指针。string_view相比较char*提供了很多字符操作，也就是说如果想要使用string里面的字符操作函数，但是又不想到拷贝一份数据，可以使用string_view。

1
typedef basic_string_view<char>     string_view;

数据结构

1
2
3
private:
    const   value_type* __data; // 字符数组的指针
    size_type           __size; // 字符数组的长度

构造函数

string_view的构造只是简单的记录了外部传入的字符数组的指针和长度，并不会和string一样自身拷贝一份。string对象可以隐式转换为string_view，所以可以直接将string对象作为参数进行构造。

1
2
3
4
5
6
constexpr basic_string_view() noexcept;
constexpr basic_string_view(const basic_string_view&) noexcept = default;
basic_string_view& operator=(const basic_string_view&) noexcept = default;
template<class Allocator>
constexpr basic_string_view(const charT* str);
constexpr basic_string_view(const charT* str, size_type len);
1
2
3
4
5
6
7
_LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY
basic_string_view(const _CharT* __s, size_type __len) _NOEXCEPT
    : __data(__s), __size(__len) {}

_LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY
basic_string_view(const _CharT* __s)
    : __data(__s), __size(_VSTD::__char_traits_length_checked<_Traits>(__s)) {}

substr

string_view的substr并不会重新拷贝一份

1
2
3
4
5
6
7
_LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY
basic_string_view substr(size_type __pos = 0, size_type __n = npos) const
{
    return __pos > size()
        ? (__throw_out_of_range("string_view::substr"), basic_string_view())
        : basic_string_view(data() + __pos, _VSTD::min(__n, size() - __pos));
}