STL String是最重要，最常用的STL之一，能够大大降低我们处理字符串的工作量。今天我们来自己写一个MyString,在编码中理解它的工作原理。

基本结构

从一个容器的角度讲，string的结构并不复杂，本质上还是一个顺序表。如图可以生动展示一个string所占用的空间。其中**_size表示当前已经使用的空间,_capacity表示最大容量。特别需要注意的是，string的字符串结尾会固定存放一个’/0**’来表示字符串结尾。在实践中我发现在不主动调用reserve()方法与resize()方法的情况下，string.capacity()的值往往与string().size()相同。

         由此可以得到string的私有部分定义：

1
2
3
4
private:
	char* _ptr;						//实际存储字符串内容的空间 
	size_t _size;					//存储字符串当前的容量 
	size_t _capacity;				//存储字符串最大容量

构造方法

下面给出string的构造方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public:
	//构造函数 
	MyString():_ptr(new char[1]),_size(0),_capacity(){
		*_ptr='\0';
	}//没有参数的构造函数
	MyString(const char* ptr):_ptr(new char[strlen(ptr)+1]),_size(0),_capacity(0){//带参数的构造函数 
		strcpy(_ptr,ptr);			//将字符串赋值给string 
		_size=strlen(_ptr);			//将字符串的大小和容量更新为当前值 
		_capacity=strlen(_ptr);
	}
	MyString(const MyString& str):_ptr(nullptr),_size(0),_capacity(0){		//拷贝构造 
		strcpy(_ptr,str._ptr);
		_size=strlen(_ptr);
		_capacity=strlen(_ptr);
	}
	~MyString(){					//析构函数 
		if(_ptr){
			delete[] _ptr;
			_ptr=nullptr;
			_size=0;
			_capacity=0;
		}
	}

上述代码基本没有新难点。 

重载运算符

下面代码对一些运算符进行了重载

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
MyString& operator=(MyString str){			//对=符号进行重载 
		strcpy(_ptr,str._ptr);
		_size=strlen(_ptr);
		_capacity=strlen(_ptr);
		return *this;
	}
	const char& operator[](size_t n) const{		//对[]符号进行重载,用以实现字符串随机访问 
		assert(n<_size);
		return _ptr[n];
	}
	
	MyString& operator+=(const char& c){		//对+=重载，来实现+=字符的操作 
		this->push_back(c);
		return *this; 
	}
	MyString& operator+=(const char* str){
		this->append(str);
		return *this;
	}
	MyString& operator+=(const MyString& str){
		this->append(str._ptr);
		return *this;
	}

string的方法为了能够满足地址，指针和string三种情况的调用，往往要多次重写方法。建议先实现一些常用的方法再来完成运算符重载，这样可以直接调用已经写好的方法，避免出错，简化代码。例如上述代码中的**push_back()**与append()方法可以提前写好调试完成。

assert()方法在<assert.h>头文件中定义，用来对内部条件进行判定。一旦内部表达式为false,就向stderr打印一条错误信息，并终止程序。

方法实现

下面代码实现了一些常用的方法。

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
size_t strlen(const char *str){			//strlen方法从当前指针位置开始向后累加,计算到\0为止的字符串长度 
    	size_t length=0;
    	if(str==nullptr) return 0;
    	while(*str++!='\0') length++;
    	return length;
	}
	
	char* strcpy(char *strDest, const char *strSrc){		//strcpy将strSrc的内容复制到strDest中,并且返回strDest的头指针 
     	assert((strDest!=NULL) && (strSrc !=NULL));			//如果两个字符串都是空的就直接中断 
     	char *address = strDest;							//用address指向strDest开始地址
     	while( (*strDest++ = * strSrc++) != '\0' );
     	return address ;									//返回strDest开始地址                       
	}
	
	void reserve(size_t newCapacity){			//reserve用来修改的是capacity 
		if (newCapacity>_capacity)
		{
			char* str = new char[newCapacity+1];//开新的空间
			for (size_t i=0;i<_size;i++){
				str[i] = _ptr[i];
			}
			delete[] _ptr;
			_ptr = str;
			_capacity = newCapacity;
		}
	}
	void resize(size_t newSize){							//resize用来修改的是size 
		if(newSize>_capacity){								//如果string容量不足，要先开辟容量 
			reserve(newSize);
		}
		if(newSize>_size){
			memset(_ptr+_size,'/0', newSize-_size);	//memset用来对一块空间进行初始化,这里将没有赋值但在string容器内的内存赋值为/0
		}
		_size=newSize;
		_ptr[_size]='\0'; 
	}
	
	void push_back(const char& c){				//在string后面插入新的字符 
		int newCapacity;
		if(_size==_capacity){					//string已满,需要扩容 
			if(_capacity==0){					//string的容量为0,此时扩容为 32
				newCapacity=32; 			
			}else{
				newCapacity=_capacity*2;
			}
			reserve(newCapacity);				//执行实际的扩容操作 
		}
		_ptr[_size]=c;
		_size++;
		_ptr[_size]='\0';
	} 
	
	size_t size(){
		return _size;
	}
	
	size_t capacity(){
		return _capacity;
	}
	
	void append(const char* str){
		int newLength=strlen(str);
		if(newLength+_size>_capacity){//容量不足，需要扩容 
			reserve(newLength+_size);
		}
		_ptr[newLength+_size]='\0';
		for(int i=_size;i<=_size+newLength;i++){//将str内容复制过来 
			_ptr[i]=str[i-_size];
		}
		_size+=newLength;
	}
	
	void insert(size_t position,const char& c){//插入一个字符 
		assert(position<=_size);
		if (_size == _capacity){
			size_t newCapacity;
			if(_capacity==0){
				newCapacity=32;
			}else{
				newCapacity=_capacity*2;
			}
			reserve(newCapacity);
		}
		size_t endPosition=_size;
		while (endPosition-position)
		{
			_ptr[endPosition] =_ptr[endPosition-1];		//将插入点后面的元素右移一位 
			--endPosition;
		}
		_ptr[position]=c; 					//插入新字符 
		_ptr[++_size] = '\0';
	}
	void insert(size_t position, const char* str){
		if(_size+strlen(str)>_capacity){//如果容量不足，就进行扩容 
			reserve(_size+strlen(str));
		} 
		for(int i=0;i<strlen(str);i++){
			insert(position++,str[i]);	//偷个懒，直接调用上面一个insert 
		}
		_ptr[_size]='\0';
	}
	
	void erase(size_t position,size_t length){	//用来删除指定位置的指定长度字符串 
		assert(position<_size&&position>=0);
		if (position+length>=_size){			//删除点后面没有需要保留的字符。直接将后续全部删除 
			_ptr[position]='\0';
			_size=position;
			return;
		}
		size_t start =position+length;			//start为后半部分保留的字符指针，将后半部分逐个前移到删除点 
		while(start<_size){
			_ptr[position++] =_ptr[start++];
		}
		_size-=length;
		_ptr[_size]='\0';						//'/0'不能忘 
	}
	
	size_t find(const char& c, size_t position=0){//查找position位置后面的第一个c的位置 
		assert(position<_size);
		while(position<_size){
			if (_ptr[position]==c){
				return position;
			}
			position++;
		}
		return -1;								//查不到就返回-1 
	}
	
	char* strstr(char *src,char *substr){ 		//用于查询src中是否存在substr 
  		assert(src != NULL && substr != NULL); 
  		unsigned int size = strlen(src); 
  		for(int i = 0; i < size; ++i,++src){ 
    		char *p = src; 
    		for(char *q = substr;;p++,q++){ 
      		if(*q == '\0'){//在src中找到连续的substr子串停止并返回 
        		return src; 
      			} 
      		if(*q != *p){ 
        		break; 
      			}
    		}
  		}
  	}
	size_t find(char* str, size_t position=0){
		assert(position< _size);
		char* s=strstr(_ptr+position, str);
		if (s){
			return s - _ptr;
		}
		return -1;
	}

这部分代码量最然比较大，但大部分内容还是常规的顺序表操作。

值得一提的是，其中reserve()方法用来修改的是_capacity的值，也就是最大容量。而resize()方法用来修改的是_size,也就是已占用的空间。这让我对_size和_capacity的意义出现了混淆。所以我使用原版的string进行了验证，令我意外的是原版的string中_size与_capacity似乎是始终相等的。于是我通过下面的代码进行测试：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
#include<cstring>
using namespace std;
int main(){
	string s="abcabcabcabcabc";                        //一个随意的字符串
	cout<<s<<endl;
	cout<<"s.size() is "<<s.size()<<endl;              //输出当前的字符串长度和容量
	cout<<"s.capacity() is "<<s.capacity()<<endl;
	
	s.reserve(600);                                    //将字符串扩容
	s.resize(500);                                     //修改字符串长度
	cout<<s<<endl;
	cout<<"s.size() is "<<s.size()<<endl;              //再次输出字符串长度和容量
	cout<<"s.capacity() is "<<s.capacity()<<endl;
	cout<<"|"<<(int)s[490]<<"|"<<endl;                 //尝试获取新增加的有效空间的字符的ASCII码
}

得到了以下结果：

 当我使用reserve()方法与resize()方法修改string的长度时，情况果然发生了改变。为了让结果更加明显，设置了500和600两个比较夸张的数字，得到的字符串后面出现了大量的空白。猜测是resize()导致的原字符串后面的填充，于是让程序输出后面随意一个空格的ASCII码，果然其值为0.也就是说，在string中，如果用户强行将其_size提高，那么新增的有效空间会用ASCII码为0的空字符填充。

由此可见，假如用户实际使用的空间<_size<_capacity，那么此时string中的存储情况是这样的：

另外，起初我使用的resize()的值大于reserve()的值，导致结果中size和capacity仍然是同样大的。这种现象是因为，当resize()的参数值大于reserve()时，会自动调用reserve()将string进行扩容，并扩容到resize()的大小。这一点在上面的resize()方法中已经体现。

迭代器

下面代码实现了string的迭代器。由于是顺序存储，所以迭代器并不复杂。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef char* iterator;
	typedef const char* const_iterator;
	iterator begin(){//首元素位置 
		return _ptr;
	}
	iterator end(){//末元素位置 
		return _ptr+_size;
	}
	const_iterator begin()const{
		return _ptr;
	}
	const_iterator end()const{
		return _ptr + _size;
	}

其它

为了让string能够符合用户习惯地输入和输出，需要对输入和输出进行一些处理。本质上其实属于’<<’和’>>’运算符的重载。

在MyString对象类中，加入以下代码：

1
2
friend ostream& operator<<(ostream& out, const MyString& str);
	friend istream& operator>>(istream& in, MyString& str);

其中friend是声明友元函数。友元函数可以调用本类中的私有部分。

在MyString对象之外加入以下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
ostream& operator<<(ostream& out, MyString& str){//重载输出运算符,注意添加头文件iostream 
		for (size_t i=0;i<str.size();i++){				
			out<<str[i];
		}
		cout<<endl;
		return out;
}
istream& operator>>(istream& in, MyString& str){//重载输入运算符 
		char ch;
		str.resize(0);
		str._size = str._capacity = 0;
		while ((ch=getchar())!=EOF){
			if (ch=='\n'){							//输入以回车作为结束 
				return in;
			}
			str+=ch;
	}
	return in;
}

在对‘<<’的重载中，主要实现的是用户可以通过cout<<StringName;的方式直接打印整个字符串。在对’>>’的重载中，主要实现的是以用户输入的回车键作为输入的结尾。当然，如果你喜欢也可以做一些个性化的输入输出设置。

整体代码

整体的代码如下：

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
#ifndef MYSTRING_H
#define MYSTRING_H
#include<assert.h>	//size_t类型在assert.h头文件中 
#include<memory.h>	
#include<iostream>				
using namespace std;
class MyString{
private:
	char* _ptr;						//实际存储字符串内容的空间 
	size_t _size;					//存储字符串当前的容量 
	size_t _capacity;				//存储字符串最大容量 			
public:
	//构造函数 
	MyString():_ptr(new char[1]),_size(0),_capacity(){
		*_ptr='\0';
	}//没有参数的构造函数
	MyString(const char* ptr):_ptr(new char[strlen(ptr)+1]),_size(0),_capacity(0){//带参数的构造函数 
		strcpy(_ptr,ptr);			//将字符串赋值给string 
		_size=strlen(_ptr);			//将字符串的大小和容量更新为当前值 
		_capacity=strlen(_ptr);
	}
	MyString(const MyString& str):_ptr(nullptr),_size(0),_capacity(0){		//拷贝构造 
		strcpy(_ptr,str._ptr);
		_size=strlen(_ptr);
		_capacity=strlen(_ptr);
	}
	~MyString(){					//析构函数 
		if(_ptr){
			delete[] _ptr;
			_ptr=nullptr;
			_size=0;
			_capacity=0;
		}
	}
	
	//运算符重载 
	MyString& operator=(MyString str){			//对=符号进行重载 
		strcpy(_ptr,str._ptr);
		_size=strlen(_ptr);
		_capacity=strlen(_ptr);
		return *this;
	}
	const char& operator[](size_t n) const{		//对[]符号进行重载,用以实现字符串随机访问 
		assert(n<_size);
		return _ptr[n];
	}
	
	MyString& operator+=(const char& c){		//对+=重载，来实现+=字符的操作 
		this->push_back(c);
		return *this; 
	}
	MyString& operator+=(const char* str){
		this->append(str);
		return *this;
	}
	MyString& operator+=(const MyString& str){
		this->append(str._ptr);
		return *this;
	}
	
	//方法实现 
	size_t strlen(const char *str){			//strlen方法从当前指针位置开始向后累加,计算到\0为止的字符串长度 
    	size_t length=0;
    	if(str==nullptr) return 0;
    	while(*str++!='\0') length++;
    	return length;
	}
	
	char* strcpy(char *strDest, const char *strSrc){		//strcpy将strSrc的内容复制到strDest中,并且返回strDest的头指针 
     	assert((strDest!=NULL) && (strSrc !=NULL));			//如果两个字符串都是空的就直接中断 
     	char *address = strDest;							//用address指向strDest开始地址
     	while( (*strDest++ = * strSrc++) != '\0' );
     	return address ;									//返回strDest开始地址                       
	}
	
	void reserve(size_t newCapacity){			//reserve用来修改的是capacity 
		if (newCapacity>_capacity)
		{
			char* str = new char[newCapacity+1];//开新的空间
			for (size_t i=0;i<_size;i++){
				str[i] = _ptr[i];
			}
			delete[] _ptr;
			_ptr = str;
			_capacity = newCapacity;
		}
	}
	void resize(size_t newSize){							//resize用来修改的是size 
		if(newSize>_capacity){								//如果string容量不足，要先开辟容量 
			reserve(newSize);
		}
		if(newSize>_size){
			memset(_ptr+_size,'/0', newSize-_size);	//memset用来对一块空间进行初始化,这里将没有赋值但在string容器内的内存赋值为/0
		}
		_size=newSize;
		_ptr[_size]='\0'; 
	}
	
	void push_back(const char& c){				//在string后面插入新的字符 
		int newCapacity;
		if(_size==_capacity){					//string已满,需要扩容 
			if(_capacity==0){					//string的容量为0,此时扩容为 32
				newCapacity=32; 			
			}else{
				newCapacity=_capacity*2;
			}
			reserve(newCapacity);				//执行实际的扩容操作 
		}
		_ptr[_size]=c;
		_size++;
		_ptr[_size]='\0';
	} 
	
	size_t size(){
		return _size;
	}
	
	size_t capacity(){
		return _capacity;
	}
	
	void append(const char* str){
		int newLength=strlen(str);
		if(newLength+_size>_capacity){//容量不足，需要扩容 
			reserve(newLength+_size);
		}
		_ptr[newLength+_size]='\0';
		for(int i=_size;i<=_size+newLength;i++){//将str内容复制过来 
			_ptr[i]=str[i-_size];
		}
		_size+=newLength;
	}
	
	void insert(size_t position,const char& c){//插入一个字符 
		assert(position<=_size);
		if (_size == _capacity){
			size_t newCapacity;
			if(_capacity==0){
				newCapacity=32;
			}else{
				newCapacity=_capacity*2;
			}
			reserve(newCapacity);
		}
		size_t endPosition=_size;
		while (endPosition-position)
		{
			_ptr[endPosition] =_ptr[endPosition-1];		//将插入点后面的元素右移一位 
			--endPosition;
		}
		_ptr[position]=c; 					//插入新字符 
		_ptr[++_size] = '\0';
	}
	void insert(size_t position, const char* str){
		if(_size+strlen(str)>_capacity){//如果容量不足，就进行扩容 
			reserve(_size+strlen(str));
		} 
		for(int i=0;i<strlen(str);i++){
			insert(position++,str[i]);	//偷个懒，直接调用上面一个insert 
		}
		_ptr[_size]='\0';
	}
	
	void erase(size_t position,size_t length){	//用来删除指定位置的指定长度字符串 
		assert(position<_size&&position>=0);
		if (position+length>=_size){			//删除点后面没有需要保留的字符。直接将后续全部删除 
			_ptr[position]='\0';
			_size=position;
			return;
		}
		size_t start =position+length;			//start为后半部分保留的字符指针，将后半部分逐个前移到删除点 
		while(start<_size){
			_ptr[position++] =_ptr[start++];
		}
		_size-=length;
		_ptr[_size]='\0';						//'/0'不能忘 
	}
	
	size_t find(const char& c, size_t position=0){//查找position位置后面的第一个c的位置 
		assert(position<_size);
		while(position<_size){
			if (_ptr[position]==c){
				return position;
			}
			position++;
		}
		return -1;								//查不到就返回-1 
	}
	
	char* strstr(char *src,char *substr){ 		//用于查询src中是否存在substr 
  		assert(src != NULL && substr != NULL); 
  		unsigned int size = strlen(src); 
  		for(int i = 0; i < size; ++i,++src){ 
    		char *p = src; 
    		for(char *q = substr;;p++,q++){ 
      		if(*q == '\0'){//在src中找到连续的substr子串停止并返回 
        		return src; 
      			} 
      		if(*q != *p){ 
        		break; 
      			}
    		}
  		}
  	}
	size_t find(char* str, size_t position=0){
		assert(position< _size);
		char* s=strstr(_ptr+position, str);
		if (s){
			return s - _ptr;
		}
		return -1;
	}
	//迭代器 
	typedef char* iterator;
	typedef const char* const_iterator;
	iterator begin(){//首元素位置 
		return _ptr;
	}
	iterator end(){//末元素位置 
		return _ptr+_size;
	}
	const_iterator begin()const{
		return _ptr;
	}
	const_iterator end()const{
		return _ptr + _size;
	}
	
	friend ostream& operator<<(ostream& out, const MyString& str);
	friend istream& operator>>(istream& in, MyString& str);
}; 

ostream& operator<<(ostream& out, MyString& str){//重载输出运算符,注意添加头文件iostream 
		for (size_t i=0;i<str.size();i++){				
			out<<str[i];
		}
		cout<<endl;
		return out;
}
istream& operator>>(istream& in, MyString& str){//重载输入运算符 
		char ch;
		str.resize(0);
		str._size = str._capacity = 0;
		while ((ch=getchar())!=EOF){
			if (ch=='\n'){							//输入以回车作为结束 
				return in;
			}
			str+=ch;
	}
	return in;
}
#endif