std::string底层原理分析

std::string底层原理分析

参考链接：https://blog.csdn.net/yolan2626/article/details/105705571

  std::string作为我们经常使用的一种STL容器，我们是否某个时刻有想过它的底层到底是如何实现的？其实在std::string的历史中，出现过几种不同的方式。

  可以从一个简单的问题来弹错，一个std::string对象占据的内存空间有多大？即sizeof(std::string)的值为多大？如果我们在不同的编译器（VC++、GNU、Clang++）上去测试，可能会发现其值是不同的；即使是GNU，不同的版本，获取的值也不同。

  虽然历史上的实现有多种，但基本上有三种方式：

• Eager Copy（深拷贝）
• COW（Copy-On-Write 写时复制）：14.04版本的Ubuntu
• SSO（Short String Optimization - 短字符串优化）：小于15个字节，栈区存放字符串；大于15个字节，栈区存放指针，指针指向堆区（堆区存放数据）。

Eager Copy（深拷贝）

  最简单的莫过于深拷贝。即无论什么情况下，都采用拷贝字符串内容的方式解决。这种实现方式，在需要对字符串进行频繁复制而又并不改变字符串内容时，效率比较低下。所以需要对其实现进行优化，之后便出现了下面的COW的实现方式。

COW（Copy-On-Write 写时复制）

  当两个std::string发生复制构造或者赋值时，不会复制字符串内容，而是增加一个引用计数，然后字符串指针进行浅拷贝，其执行效率为O(1)，只有当需要修改其中一个字符串内容时，才执行真正的复制。

  实现方式有下面两种：

  第一种：

std::string的数据成员就是:
class string 
{
private:
	Allocator _allocator;
	size_t size;
	size_t capacity;
	char * pointer;
};
1
2
3
4
5
6
7
8
9

  第二种：

  此时，std::string的数据成员只有一个：

class string {
private:
	char * _pointer;
};
1
2
3
4

  问我了实现的简单，在GNU4.8.4中，采用的第二种方式。从上面的实现我们看到引用计数并没有与std::string的数据成员放在一起，为什么呢？

  当执行复制构造或者赋值时，引用计数加1，std::string对象之间共享字符串内容。

  当std::string对象销毁时，并不直接释放字符串所在的空间，而是先将引用计数减1，知道引用计数为0时，才真正释放字符串内容所在的空间。

  既然涉及到引用计数，那么在多线程环境下，涉及到修改引用计数的操作时，是否是线程安全的呢？为了解决这个问题，GNU4.8.4在实现过程中，采用原子操作。

SSO（Short String Optimization）短字符串优化

  目前，在VC++、GNU5.x.x以上，Clang++上，std::string实现均采用SSO实现。

  通常来说，一个程序里用到的字符串大部分都很短小，而在64位机器上，一个char*指针就占用了8个字节，所以SSO就出现了，其核心思想就是：发生拷贝时要复制一个指针，对于小字符串来说，为啥不能复制整个字符串呢？说不定还没有复制一个指针的代价大。其实现示意图如下：

  std::string的数据成员：

class string 
{
	union Buffer
	{
		char * _pointer;
		char _local[16];
	}; 
	
	Buffer _buffer;
	size_t _size;
	size_t _capacity;
};
1
2
3
4
5
6
7
8
9
10
11
12

  当字符串的长度小于等于15个字节时，buffer直接存放整个字符串；当字符串大于15个字节时，buffer存放的就是一个指针，该指针指向一个堆区空间。这样做的好处就是，当字符串较小时，直接拷贝字符串，放在std::string内部（比如可能buffer只有4个字节大小，而64位机器一个指针8个字节，那么明显直接存放整个字符串开销更小）不用获取堆空间，开销小。

最佳策略

  以上三种方式，都不能解决所有可能遇到的字符串问题，各有所长，有各有缺陷。综合考虑所有情况之后，facebook开源的folly库中，实现了一个fbstring，它根据字符串的不同长度使用不同的拷贝策略，最终每个fbstring对象占据的空间大小都是24个字节。

1. 很短的（0~22）字符串用SSO，23字节表示字符串（包括’\0’），1字节表示长度。
2. 中等长度的（23~255）字符串用 eager copy，8字节字符串指针，8字节size， 8字节capacity。
3. 很长的（大于255）字符串用COW，8字节指针（字符串和引用计数），8字节 size，8字节capacity。

线程安全性

  两个线程同时对同一个字符串进行操作的话，是不可能线程安全的，出于性能考虑，C++并没有为string实现线程安全， 毕竟不是所有程序都要用到多线程。

  但是两个线程同时对独立的两个string操作时，必须是安全的。COW技术实现这一点是通过原子变量对引用计数进行+1或-1操作。

  CPU的原子操作虽然比mutex锁好多了，但是仍然会带来性能损失，原因如下：

• 阻止CPU的乱性执行
• 两个CPU对同一个地址进行原子操作，会导致cache失效，从而重新从内存中读数据
• 系统通常会lock住比目标地址更大的一片区域，影响逻辑上不相关的地址访问

  这也是在多核时代，各大编译器厂商都选择SSO实现的原因。

COW 写时复制代码实现

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string.h>
#include <stdio.h>

using std::cout;
using std::endl;
using std::cin;

class String {
    friend std::ostream& operator<<(std::ostream& os, const String&rhs);

public:
    //设计模式之代理模式
    //区分(代理)下标运算符是赋值还是输出流
    //操作String的类
    class Char
    {
    public:
        Char(String & self, size_t idx)//不加const的原因，有写操作
            : m_self(self)
            , m_idx(idx) {
            cout << "Char()" << endl;
        }

        char& operator=(const char &ch);

        operator char() {
            return m_self.m_pStr[m_idx];
        }

    private:
        String& m_self;
        size_t  m_idx;
    };



    //留出4个字节放引用计数，1个字节放'\0'，+4即从已分配的堆区空间（5个字节）向后偏移4个字节
    String() :m_pStr(new char[5]() + 4) {
        cout << "String()" << endl;
        _InitRefCount();
    }

    //重载构造函数，存储的数据 + 5（用于引用计数）的空间，指针偏移到数据的位置
    String(const char* pStr) : m_pStr(new char[strlen(pStr) + 5]() + 4) {
        cout << "String(const char* pStr)" << endl;
        strcpy(m_pStr, pStr);
        _InitRefCount();
    }

    //拷贝构造函数
    String(const String& rhs) : m_pStr(rhs.m_pStr) {
        cout << "String(const String& rhs)" << endl;
        _IncreRefCount();
    }

    //"="运算符重载
    String& operator=(const String& rhs) {
        cout << "String& operator=(const String& rhs) " << endl;
        //防止自复制
        if (this != &rhs) {
            _ReleaseFunc();
            m_pStr = rhs.m_pStr;
            _IncreRefCount();
        }
        return *this;
    }


    //"[]"运算符重载
    //char 不能重载，区分赋值和输出流，返回定义的自定义类型
    Char operator[](size_t index) {
        return Char(*this, index);
    }

    ~String() {
        cout << "~String()" << endl;
        _ReleaseFunc();
    }


    //获取引用计数
    int GetRefCount() {
        return *(int *)(m_pStr - 4);
    }

    //转C风格字符串
    const char* c_str() {
        return m_pStr;
    }

    //字符串大小
    size_t Size() {
        return strlen(m_pStr);
    }


private:
    //初始化引用计数
    void _InitRefCount() {
        //引用计数初始化为1
        //(m_pStr - 4) 指针回到堆区起始位置（引用计数起始位置）
        //(int *)将char[5]从0到3的4个字节强转为int *指针类型。
        //*(int *)(m_pStr - 4) 为解引用

        *(int *)(m_pStr - 4) = 1;
    }

    //引用计数自增
    void _IncreRefCount() {
        ++ *(int *)(m_pStr - 4);
    }

    //引用计数自减
    void _DecreRefCount() {
        -- *(int *)(m_pStr - 4);
    }

    //堆区空间释放
    void _ReleaseFunc() {
        _DecreRefCount();
        if (GetRefCount() == 0) {
            delete[](m_pStr - 4);
            m_pStr = nullptr;
        }
    }
private:
    char* m_pStr;
};


std::ostream & operator<<(std::ostream& os, const String& rhs) {
    os << rhs.m_pStr;
    return os;
}

char& String::Char::operator=(const char& ch) {
    if (m_idx < m_self.Size()) {
        //如果引用计数不是最后一个，那么当使用者在访问str[index]时可能修改对应的值
        if (m_self.GetRefCount() > 1) {
            char *pTmp = new char[m_self.Size() + 5]() + 4;
            strcpy(pTmp, m_self.m_pStr);
            m_self._DecreRefCount();
            m_self.m_pStr = pTmp;
            m_self._InitRefCount();
        }
        m_self.m_pStr[m_idx] = ch; //赋值
        return m_self.m_pStr[m_idx];
    }
    else {
        static char nullChar = '\0';
        return nullChar;
    }
}


void Test() {
    String s1 = "Hello";
    String s2 = s1;
    
    cout << "s1 = " << s1 << endl;
    cout << "s2 = " << s2 << endl;
    cout << "s1 count is " << s1.GetRefCount() << endl;
    cout << "s2 count is " << s2.GetRefCount() << endl;
    printf("s1 address is %p\n", s1.c_str());
    printf("s2 address is %p\n", s2.c_str());

    cout << endl;
    String s3("world");
    s3 = s1;
    cout << "s1 = " << s1 << endl;
    cout << "s2 = " << s2 << endl;
    cout << "s3 = " << s3 << endl;
    cout << "s1 count is " << s1.GetRefCount() << endl;
    cout << "s2 count is " << s2.GetRefCount() << endl;
    cout << "s3 count is " << s3.GetRefCount() << endl;
    printf("s1 address is %p\n", s1.c_str());
    printf("s2 address is %p\n", s2.c_str());
    printf("s3 address is %p\n", s3.c_str());


    //写时复制
    cout << endl;
    cout << "s3[0]写操作: s3[0] = 'h'" << endl;
    s3[0] = 'h';
    cout << "s1 = " << s1 << endl;
    cout << "s2 = " << s2 << endl;
    cout << "s3 = " << s3 << endl;
    cout << "s1 count is " << s1.GetRefCount() << endl;
    cout << "s2 count is " << s2.GetRefCount() << endl;
    cout << "s3 count is " << s3.GetRefCount() << endl;
    printf("s1 address is %p\n", s1.c_str());
    printf("s2 address is %p\n", s2.c_str());
    printf("s3 address is %p\n", s3.c_str());


    //读操作（出错）
    cout << endl;
    cout << "s1[0]读操作" << endl;
    cout << "s1[0] = " << s1[0] << endl;
    cout << "s1 = " << s1 << endl;
    cout << "s2 = " << s2 << endl;
    cout << "s3 = " << s3 << endl;
    cout << "s1 count is " << s1.GetRefCount() << endl;
    cout << "s2 count is " << s2.GetRefCount() << endl;
    cout << "s3 count is " << s3.GetRefCount() << endl;
    printf("s1 address is %p\n", s1.c_str());
    printf("s2 address is %p\n", s2.c_str());
    printf("s3 address is %p\n", s3.c_str());

}

int main() {
    Test();
	return 0;
}
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217