【STL源码剖析】string类模拟实现 了解底层-走进底层-掌握底层【超详细的注释和解释】

博主对大家的话

从今天开始，STL源码剖析的专栏就正式上线了！其实在很多人学习C++过程中，都是只学习一些STL的使用方式，并不了解底层的实现。博主本人认为，这样的学习这样的技术是不深的。如果我们想要熟悉的掌握一门语言，我认为，底层的实现必不能少！
但是，想从0开始模拟实现STL的容器，需要我们熟悉C++的语法，特别是类和对象部分的知识！
博主学习C++到现在，我认为C++类和对象基本语法的学习比任何部分都要重要，而我花在这上面的时间也是最多的！只要搞清楚C++面向对象编程的基本规则，我们才能在STL的世界里游刃有余！
所以我希望大家在学习STL之前，先将数据结构与算法，C++的类和对象部分内容掌握熟悉！

前言

那么这里博主先安利一下一些干货满满的专栏啦！

数据结构专栏：数据结构 这里包含了博主很多的数据结构学习上的总结，每一篇都是超级用心编写的，有兴趣的伙伴们都支持一下吧！
STL源码剖析专栏：STL容器的模拟实现 以STL源码为基础，模拟实现STL的各种容器。从底层开始，一步一步解密STL。掌握底层，才是真正学会STL
算法专栏：算法
力扣刷题专栏：Leetcode
C的深度解剖专栏：C语言的深度解剖
**

实现过程一些要注意的点

因为STL库里面的string其实是很多年发展出来的类，里面一共有106个成员函数。
在这里面其实并不是每一个我们都要去实现的，我们要去实现的其实是一些重要的，必备的，有代表性的功能。其实关于string类发展到现在这么久，其实很多人对它有很多不同的评价，这里博主分享一篇文章。

• STL 的string类怎么啦？https://blog.csdn.net/haoel/article/details/1491219

因此，在博主的模拟实现中，只提供了STL中的部分接口，但是这些，对于在初学阶段来说，足够了！
对于实现过程的一些细节问题，博主会在源代码的注释中指出！

STL中string类模拟实现

#pragma once
#include
#include
#include
using namespace std;


//为了区分和库里面的，我们用命名空间包起来
namespace MyString {
	class string {
	public:
		//迭代器和const迭代器
		typedef char* iterator;
		typedef const char* const_iterator;
		iterator begin() {
			return _str;
		}
		iterator end() {
			return _str + _size;
		}
		//const迭代器 -- 只读不写
		const_iterator begin() const {
			return _str;
		}
		const_iterator end() const {
			return _str + _size;
		}
		//构造
#if false
		string()//初始化的时候一定不能给nullptr，因为如果创建一个空对象的时候，去打印
			//就会造成空指针的解引用
			//或者给全却称
			:_str(new char[1]),
			_size(0),
			_capacity(0)
		{
			_str[0] = '\0';//给一个空间放'\0'
		}
#endif
		string(const char* str = "\0")//写""是等价的，因为""会自带'\0'
			//:_str(new char[strlen(str) + 1]),
			//_size(strlen(str)),
			//_capacity(strlen(str)) -- 这样搞用三次strlen() -- 别用初始化列表了
		{
			//动态开辟空间
			size_t len = strlen(str);
			_str = new char[len + 1];
			_size = len;
			_capacity = len;
			strcpy(_str, str);
		}
		//析构
		~string() {
			delete[] _str;
			_str = nullptr;
			_size = _capacity = 0;
		}
		//拷贝构造(实现一个深拷贝)		
		//写法1：传统写法
#if 0
		string(const string& s) 
			:_str(new char[s._capacity+1]),
			_size(s._size),
			_capacity(s._capacity)
		{
			strcpy(_str, s._str);
		}

		//赋值重载
		string& operator=(const string& s) {
			if (this == &s)return *this;//自己给自己赋值 -- 直接避开
			//无论什么情况，都选择把原来的空间释放掉+开新的空间+拷贝
			char*tmp = new char[s._capacity + 1];//一定要记得+1
			//new失败怎么办 -- 这样就会造成拷贝失败，而且原来的string被释放了，所以最好先new再delete原来的
			strcpy(tmp, s._str);
			delete[] _str;

			_str = tmp;
			_size = s._size;
			_capacity = s._capacity;
			return *this;
			//这样写的话，自己给自己赋值就会出问题 -- 因为自己给自己释放了 -- 拷贝自己 -- 拷贝到的就是随机值！
		}
#endif
		//现代写法
		//构造来当打工人
		void swap(string& tmp) {
			std::swap(_str, tmp._str);
			std::swap(_size, tmp._size);
			std::swap(_capacity, tmp._capacity);
		}
		string(const string& s)
			: _str(nullptr),
			_size(0),
			_capacity(0)
		{
			//因为s里面的东西可能是随机值
			//如果换给tmp之后，tmp出了作用域是会析构的 -- 析构随机的东西就会出问题
			//析构0或者null是不会出问题的，所以初始化一下
			//因为swap要频繁调用，我们这里自己再写一个最好
			string tmp(s._str);
			swap(tmp);//this->swap(tmp)
		}
		//写法2：
#if 0
		string& operator=(const string& s) {
			if (this == &s)return *this;//自己给自己赋值 -- 直接避开
			string tmp(s);
			swap(tmp);//this和swap换
			return *this;
			//把原来的s换给tmp之后 -- tmp还需要帮忙打扫s的空间，因为tmp是一个局部对象！
		}
#endif
		//写法3
		string& operator=(string s) {//s就是顶替tmp，s就完成拷贝了，而且是局部对象！
			swap(s);
			return *this;
		}
		//在以后复杂数据结构的学习中 -- 现代写法的优势会更大
		
		
		//size
		size_t size()const {
			return _size;
		} 
		size_t capacity()const {
			return _capacity;
		}
		//[]重载
		char& operator[](size_t pos) {
			assert(pos < _size);
			return _str[pos];
		}
		char& operator[](size_t pos) const { //这个是不能写的
			assert(pos < _size);
			return _str[pos];
		}
		//兼容C字符串接口
		const char* c_str() {
			return _str;
		}
		void reserve(size_t n) {
			if (n > _capacity) {
				//扩容不缩容
				char* tmp = new char[n + 1];
				strcpy(tmp, _str);
				delete[] _str;

				_str = tmp;
				_capacity = n;
			}
		}
		void resize(size_t n, char ch = '\0') {
			//开空间+初始化
			if (n > _size) {
				//插入数据
				reserve(n);
				for (size_t i = _size; i < n; i++) {
					_str[i] = ch;
				}
				_str[n] = '\0';
				_size = n;
			}
			else {
				//删除数据
				_str[n] = '\0';
				_size = n;
			}
		}
		void push_back(char ch) {
			//不用去写CheckCapacity函数，我们先写reserve这个函数，复用！
#if 0
			if (_size==_capacity)
			{
				//注意：如果一开始是用了构造的缺省值，也就是0，就不能扩二倍！
				reserve(_capacity == 0 ? 4 : _capacity * 2);
			}
			_str[_size] = ch;
			++_size;
			_str[_size] = '\0';//一定要记得'\0'
#endif
			insert(_size, ch);
		}
		void append(const char* str) {
#if 0
			size_t len = strlen(str);
			if (_size + len > _capacity)//注意，此时不能扩容二倍了！因为可能不够
			{
				reserve(_size + len);
			}
			strcpy(_str + _size, str);//哪个好？
			//strcat(_str, str);//这个效率是比较低的 -- 因为要去strcat要去找'\0',持续追加的时候效率非常低！
			_size += len;
#endif
			insert(_size, str);
		}
		string& operator+=(char ch) {
			push_back(ch);
			return *this;
		}
		string& operator+=(const char* str) {
			append(str);
			return *this;
		}
		//insert
		string& insert(size_t pos, char ch) {
			assert(pos <= _size);
			if (_size == _capacity) {
				reserve(_capacity == 0 ? 4 : _capacity * 2);
			}
			//pos==0情况第一种处理方法
#if 0
			int end = _size;
			while (end >= (int)pos) {
				//注意：pos==0的时候会出问题，end--之后会变成-1->整型最大值，所以给pos强转一下,_size改成int就行
				_str[end + 1] = _str[end];
				--end;
			}
#endif
			//第二种处理方法(比较推荐)
			size_t end = _size + 1;//这些都别改，继续用uint
			while (end > pos)//这里写成大于！
			{
				_str[end] = _str[end - 1];//这里改成-1
				--end;
			}
			_str[pos] = ch;
			++_size;
			return * this;
		}
		//实现这些接口一定要很细心很细心！
		string& insert(size_t pos, const char* str) {
			assert(pos <= _size);
			size_t len = strlen(str);
			if (_size + len > _capacity) {
				reserve(_size + len);
			}
			//挪动数据
			size_t end = _size + len;//这些都别改，继续用uint
			while (end >= pos + len)//这里写成大于！
			{
				_str[end] = _str[end - len];//这里改成-1
				--end;
			}
			//放数据
			strncpy(_str + pos, str, len);//这里用ncpy，不要把'\0'拷贝进去
			_size += len;
			return *this;
		}
		//erase
		string& erase(size_t pos, size_t len = npos) {
			assert(pos < _size);
			if (len == npos || pos + len >= _size) {
				//相当于pos后面的全部删掉了
				_str[pos] = '\0';
				_size = pos;
			}
			else {
				//删除部分
				//需要挪动数据
				strcpy(_str + pos, _str + pos + len);
				_size -= len;
			}
			return *this;
		}
		void clear() {
			_str[0] = '\0';
			_size = 0;
		}
		//find系列
#if true
		size_t find(char ch, size_t pos = 0) {
			assert(pos < _size);
			for (size_t i = pos; i < _size; i++) {
				if (ch == _str[i]) {
					return i;
				}
				return npos;
			}
		}
		size_t find(const char* sub, size_t pos = 0) {
			//strstr -- 暴力
			//字符串匹配算法 kmp/bm
			assert(pos < _size);
			assert(sub);
			const char* ptr = strstr(_str + pos, sub);
			if (ptr == nullptr) {
				return npos;
			}
			return ptr - _str;
		}
		//substr --  从pos位置开始，取len个字符
		string substr(size_t pos = 0, size_t len = npos)const {
			//不用改变自己，const也行
			assert(pos < _size);
			size_t realLen = len;
			if (len == npos || pos + len > _size) {
				//超范围了
				//有多少取多少
				realLen = _size - pos;
			}
			string sub;
			for (size_t i = 0; i < realLen; ++i) {
				sub += _str[pos + i];
			}
			return sub;
		}
#endif
		//运算符重载比较系列
#if true
		bool operator>(const string& s)const {
			return strcmp(_str, s._str) > 0;
		}
		bool operator==(const string& s)const {
			return strcmp(_str, s._str) == 0;
		}
		bool operator>=(const string& s)const {
			return *this > s || *this == s;
		}
		bool operator<=(const string& s)const {
			return !(*this > s);
		}
		bool operator<(const string& s)const {
			return !(*this >= s);
		}
		bool operator!=(const string& s)const {
			return !(*this == s);
		}
#endif
	private:
		char* _str;
		size_t _size;
		size_t _capacity;
	public:
		//这个npos按道理在外面也可以取到才对
		const static size_t npos = -1;
	};
	//流提取和流插入
	//不是必须是友元的，因为不一定要访问私有，这里就不用
	ostream& operator<<(ostream& out, const string& s) {
		for (size_t i = 0; i < s.size(); i++) {
			out << s[i];
		}
		return out;
	}
	istream& operator>>(istream& in, string& s) {

		s.clear();

		//输入字符串很长，不断+=，频繁扩容，效率很低，大家可以想办法优化一下
		//1.reserve() -- 缺陷：浪费空间
		//2.别动string先，先放到一个临时数组里面，因为这个临时数组是在栈上的 -- 出了>>就销毁了
		char ch;
		ch = in.get();

		const size_t N = 32;
		char buff[N];
		size_t i = 0;

		//s.reserve(128);
		while (ch != ' ' && ch != '\n') {
			buff[i++] = ch;
			if (i == N - 1) {//表示满了
				buff[i] = '\0';
				s += buff;//一批一批加到string里面
				i = 0;
			}
			ch = in.get();
		}
		//把最后一批加上去
		//buff相当于缓冲了
		buff[i] = '\0';
		s += buff;
		return in;
		//但是现在会有bug
		//如果字符串里面原来有东西的话，会留下
		//我们先要清空一下string
	}
	//size_t string::npos = -1;//在类外面定义
	//但是const static变量可以在类里面给缺省，外面就不用写了，这是C++的特例
}
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
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381

尾声

看到这里，相信大家对string类的模拟实现已经有一定的了解了！string的模拟实现，知识我们掌握STL的开始，后面，博主将会给大家带来vector，list等等STL容器的模拟实现，持续关注，订阅专栏，点赞收藏都是我创作的最大动力！

( 转载时请注明作者和出处。未经许可，请勿用于商业用途 )
更多文章请访问我的https://blog.csdn.net/Yu_Cblog?type=blog