【C++】string类的模拟实现

一、string类的构造、拷贝构造、赋值重载以及析构

1.构造函数

分为无参和带参这两种构造函数。无参构造函数默认构造空字符串""，所以我们只需要给一个缺省值即可。

string(const char* str = "")
{
    _size = strlen(str);
    _capacity = _size;
    _str = new char[_capacity + 1];
	strcpy(_str, str);
}
1
2
3
4
5
6
7

对于这里的capacity问题，这里是字符的个数，不包括\0,所以要给\0预留位置。

2.拷贝构造

对于拷贝构造和赋值是默认成员函数，不写编译器会自动生成，对于内置类型完成浅拷贝，对于自定义类型调用拷贝构造

对于string类型来说，如果不写拷贝构造会导致浅拷贝问题（只完成值拷贝）

所以我们需要进行深拷贝：

• 传统写法

string(const string& s)
		{
			_str = new char[s._capacity + 1];
			_capacity = s._capacity;
			_size = s._size;

			strcpy(_str, s._str);
		}
1
2
3
4
5
6
7
8

• 现代写法

传统写法比较循规蹈矩，现代写法更加灵活，拷贝构造的现代写法可以通过构造出tmp，然后把tmp和s2进行交换（swap）

注意：我们需要把s2的_str置为nullptr,如果不置为空，tmp会变成随机值，tmp是局部变量出作用域时会调用析构函数

void swap(string& s)
{
    std::swap(_str, s._str);
	std::swap(_size, s._size);
	std::swap(_capacity, s._capacity);
}
string(const string& s)
        :_str(nullptr)
        ,_size(0)
        ,_capacity(0)
        {
			string tmp(s._str);
			swap(tmp);//this->swap(tmp)
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3.swap问题

对于上面现代写法swap的问题：标准库有一个swap，string也有一个swap，有什么区别？

s1.swap(s2);
swap(s1,s2);
1
2

第二个swap交换代价比较大，需要三次深拷贝(拷贝+赋值+赋值)，造成空间损耗，所以我们可以提供一个成员函数swap交换string，直接交换，swap中的swap要指定作用域std::，否则需要从局部找，再去全局找，发现参数不匹配

4.赋值重载

默认生成的赋值重载也会导致浅拷贝，所以我们需要实现深拷贝。同时，对于赋值重载，我们不要直接去进行销毁，有可能自己给自己赋值，导致自身进行销毁。同时，为了安全起见，我们最好利用tmp来进行赋值

• 传统写法

string& operator =(const string& s)
{
    if (this != &s)
    {
        char* tmp = new char[s._capacity + 1];
        strcpy(tmp, s._str);
        delete[] _str;
        _str = tmp;
		_size = s._size;
		_capacity = s._capacity;
    }
    return *this;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

• 现代写法

string& operator = (const string& s)
{
    if (this != &s)
    {
        //string tmp(s._str);
		string tmp(s);
		swap(tmp);
    }
    return *this;
}
1
2
3
4
5
6
7
8
9
10

但是此方法仍然可以简化,不需要临时tmp,直接进行传值传参，更加简洁

	//直接传值传参
string& operator = (string s)
{
    swap(s);
    return *this;
}
1
2
3
4
5
6

5.析构函数

析构函数比较简单，直接delete[]释放空间即可

~string()
{
    delete[] _str;
	_str = nullptr;
	_size = _capacity = 0;
}
1
2
3
4
5
6

---

二、常用接口

下面几个常用的接口实现比较简单，我们先一起来看一看：

1.c_str

const char* c_str() const
{
    return _str;
}
1
2
3
4

2.[]

//普通对象：可读可写
char& operator[](size_t pos)
{
    assert(pos < _size);
	return _str[pos];
}
//const对象：可读不可写
const char& operator[](size_t pos) const
{
    assert(pos < _size);
    return _str[pos];
}
1
2
3
4
5
6
7
8
9
10
11
12

3.迭代器和范围for

• 迭代器

迭代器有普通迭代器以及const修饰的迭代器，所以我们可以实现两种不同的迭代器，其中，const迭代器可读不可写

typedef char* iterator;
typedef const char* const_iterator;
iterator begin()
{
    return _str;
}

iterator end()
{
	return _str + _size;
}

const_iterator begin() const
{
	return _str;
}
const_iterator end() const
{
	return _str + _size;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

• 范围for

实现完迭代器之后，对于范围for我们自然可以直接使用：

4.size和capacity

直接返回值即可，比较简单

size_t size() const
{
    return _size;
}

size_t capacity() const
{
	return _capacity;
}
1
2
3
4
5
6
7
8
9

---

三、插入

1.reserve和resize

• reserve

在已知开多少空间是调用，避免频繁扩容，具体实现要开辟新的空间，在进行拷贝，对旧空间进行释放

void reserve(size_t n)
{
    if (n > _capacity)
    {
        char* tmp = new char[n + 1];
		strcpy(tmp,_str);
		delete[] _str;
        _str = tmp;
		_capacity = n;
    }
}
1
2
3
4
5
6
7
8
9
10
11

• resize

resize需要分情况：

1.元素个数大于容量，需要扩容，多出来的用’\0’（默认情况下）来进行填充

2.元素个数小于原有的，需要删除

void resize(size_t n, char ch = '\0')
{
    if (n > _size)
    {
        reserve(n);
        for (size_t i = _size; i < n; i++)
        {
            _str[i] = ch;
        }
        _size = n;
        _str[_size] = '\0';
    }
    else
    {
        _str[n] = '\0';
        _size = n;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.push_back

尾插一个字符，我们需要考虑扩容问题，我们需要判断capacity是否为0的情况，同时，尾插之后’\0’要重新处理

void push_back(char ch)
{
    //开辟2倍空间
    if (_size == _capacity)
    {
        size_t newCapacity = _capacity == 0 ? 4 : _capacity * 2;
		reserve(newCapacity);
    }
    _str[_size] = ch;
    ++_size;
    _str[_size] = '\0';
}
1
2
3
4
5
6
7
8
9
10
11
12

3.append

这里开多少空间取决于插入字符串的长度，我们需要计算，然后决定开多少空间（直接开2倍可能不够用）

//2倍不一定够用
void append(const char* str)
{
    size_t len = strlen(str);
    if (_size + len > _capacity)
    {
        reserve(_size + len);
	}
    strcpy(_str + _size, str);
	_size += len;
}
1
2
3
4
5
6
7
8
9
10
11

4.+=

实现了push_back和append之后，对于+=来说，简直就是手到擒来，直接调用即可

//字符
string& operator+=(char ch)
{
    push_back(ch);
	return *this;
}
//字符串
string& operator+=(const char* str)
{
	append(str);
	return *this;
}
1
2
3
4
5
6
7
8
9
10
11
12

5.insert

insert的问题比较多

• 插入字符

这里存在着一个很大的问题：

pos=0的时候，–end会变成-1（但是不要忽略了，end的类型是size_t,怎么可能是-1，此时有人会说了，可以把end改成int类型，但是实际上这样子会发生隐式类型提升，范围小往大的提升，也就是int会提升为size_t,还是没解决问题）这里太坑了，悄悄提升

所以解决的方式有两种：

1.强转

2.把=号给去掉

string& insert(size_t pos, char ch)
{
    assert(pos <= _size);
    if (_size == _capacity)
    {
        size_t newCapacity = _capacity == 0 ? 4 : _capacity * 2;
		reserve(newCapacity);

	}
    //移动数据
	size_t end = _size + 1;
    while (end > pos)
    {
        _str[end] = _str[end-1];
        --end;
	}
    _str[pos] = ch;
    ++_size;
    return *this;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

• 插入字符串

插入字符串，要把插入的字符串拷贝过来，但是不要把’\0’顺便拷贝过来，所以不要用strcpy而是要用strncpy

同时，要防止越界问题

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;
    while (end > pos + len-1)
    {
        _str[end] = _str[end - len];
        --end;
	}
    strncpy(_str + pos, str, len);
    _size += len;
	return *this;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

---

四、删除

1.erase

说到erase，自然要跟npos联系起来，npos是string类的静态成员变量，静态成员变量要在类外定义的：

size_t string::npos = -1
1

普通成员对象可以给缺省值，在构造函数初始化列表完成初始化，但是静态成员变量不会在初始化列表阶段进行初始化，静态成员变量不属于某个具体的对象，属于整个类，所以需要在类外初始化。

但是有一个**特例**，const静态成员变量可以在声明时定义(只针对整型)：

private:
		char* _str;
		size_t _size;
		size_t _capacity;

		const static size_t npos = -1;
1
2
3
4
5
6

erase实现：

建议这个地方自己画个图辅助理解

1.如果len太长，直接把pos之后的删除即可

2.只需要删除部分，挪动数据

string& erase(size_t pos,size_t len = npos)
{
    assert(pos < _size);
    if (len == npos||pos+len>=_size)
    {
        _str[pos] = '\0';
        _size = pos;
    }
    //挪动数据
    else
    {
        strcpy(_str + pos, _str + pos + len);
		_size -= len;
    }
    return *this;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2.clear

void clear()
{
    _str[0] = '\0';
    _size = 0;
}
1
2
3
4
5

五、查找

1.find

从pos处开始查找字符或者字符串，找到返回下标值，没找到则返回npos

对于字符串的查找可以调用strstr

size_t find(const char ch, size_t pos = 0)
{
    assert(pos < _size);
	while (pos < _size)
    {
        if (_str[pos] == ch)
        {
            return pos;
		}
        ++pos;
	}
    return npos;
}
size_t find(const char* str, size_t pos = 0)
{
    const char* ptr = strstr(_str + pos, str);
    if (ptr == nullptr)
    {
        return npos;
    }
    else
    {
        return ptr - _str;
    }
}
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

六、运算符重载

流插入<<和流提取>>

对于流插入和流提取我们之前就在日期类接触了。不能重载成成员，会让this指针抢占第一个位置问题。所以需要定义成全局的

• <<

ostream& operator<<(ostream& out, const string& s)
	{
		for (size_t i = 0; i < s.size(); ++i)
		{
			out << s[i];
		}
		return out;
	}
1
2
3
4
5
6
7
8

对于<<和c_str()的区别：<<按照size进行打印，跟\0没有关系，而c_str()遇到\0结束

所以用流插入读取比较好一点。

• >>

scanf和cin一样，都拿不到’ ‘和’\0’

所以要读取一个 一个的字符，我们可以用get函数

istream& operator>>(istream& in, string& s)
	{
		s.clear();
		char ch = in.get();
		while (ch != ' ' && ch != '\n')
		{
			s += ch;
			ch = in.get();
		}
		return in;
	}
1
2
3
4
5
6
7
8
9
10
11

这个代码存在缺点：输入很长内容时，+=会大量扩容，效率降低

istream& operator>>(istream& in, string& s)
{
    s.clear();
    char buff[128] = { '\0' };
    size_t i = 0;
    char ch = in.get();
    while (ch != ' ' && ch != '\n')
    {
        if (i == 127)
        {
            s += buff;
            i = 0;
        }
        buff[i++] = ch;
        ch = in.get();
    }
    if (i >= 0)
    {
        buff[i] = '\0';
        s += buff;
    }
    return in;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

七、总体代码

#pragma once
#include 
namespace hwc
{
	class string
	{
	public:
		typedef char* iterator;
		typedef const char* const_iterator;
		iterator begin()
		{
			return _str;
		}

		iterator end()
		{
			return _str + _size;
		}

		const_iterator begin() const
		{
			return _str;
		}
		const_iterator end() const
		{
			return _str + _size;
		}

		/*string()
		{
			_str = new char[1];
			_str[0] = '\0';
			_capacity = _size = 0;
		}*/
		string(const char* str = "")
		{
			_size = strlen(str);
			_capacity = _size;
			_str = new char[_capacity + 1];
			strcpy(_str, str);
		}

		//s2(s1)
		//传统写法
		/*string(const string& s)
		{
			_str = new char[s._capacity + 1];
			_capacity = s._capacity;
			_size = s._size;

			strcpy(_str, s._str);
		}*/
		
		//现代写法

		void swap(string& s)
		{
			std::swap(_str, s._str);
			std::swap(_size, s._size);
			std::swap(_capacity, s._capacity);
		}
		string(const string& s)
			:_str(nullptr)
			,_size(0)
			,_capacity(0)
		{
			string tmp(s._str);
			swap(tmp);//this->swap(tmp)
		}

	/*	string& operator =(const string& s)
		{
			if (this != &s)
			{
				char* tmp = new char[s._capacity + 1];
				strcpy(tmp, s._str);
				delete[] _str;
				_str = tmp;
				_size = s._size;
				_capacity = s._capacity;
			}
			return *this;
		}*/

		//现代写法
		//string& operator = (const string& s)
		//{
		//	if (this != &s)
		//	{
		//		//string tmp(s._str);
		//		string tmp(s);
		//		swap(tmp);
		//	}
		//	return *this;
		//}
		//直接传值传参
		string& operator = (string s)
		{
			swap(s);
			return *this;
		}
		~string()
		{
			delete[] _str;
			_str = nullptr;
			_size = _capacity = 0;
		}
		const char* c_str() const
		{
			return _str;
		}

		size_t size() const
		{
			return _size;
		}
		size_t capacity() const
		{
			return _capacity;
		}
		//可读可写
		char& operator[](size_t pos)
		{
			assert(pos < _size);
			return _str[pos];
		}
		//const对象，可读不可写
		const char& operator[](size_t pos) const
		{
			assert(pos < _size);
			return _str[pos];
		}
		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;
				}
				_size = n;
				_str[_size] = '\0';
			}
			else
			{
				_str[n] = '\0';
				_size = n;
			}

		}
		//开辟2倍
		void push_back(char ch)
		{
			if (_size == _capacity)
			{
				size_t newCapacity = _capacity == 0 ? 4 : _capacity * 2;
				reserve(newCapacity);
			}
			_str[_size] = ch;
			++_size;
			_str[_size] = '\0';
		}
		//2倍不一定够用
		void append(const char* str)
		{
			size_t len = strlen(str);
			if (_size + len > _capacity)
			{
				reserve(_size + len);
			}
			strcpy(_str + _size, str);
			_size += len;
		}
		string& operator+=(char ch)
		{
			push_back(ch);
			return *this;
		}
		string& operator+=(const char* str)
		{
			append(str);
			return *this;
		}

		string& insert(size_t pos, char ch)
		{
			assert(pos <= _size);
			if (_size == _capacity)
			{
				size_t newCapacity = _capacity == 0 ? 4 : _capacity * 2;
				reserve(newCapacity);

			}
			//移动数据
			size_t end = _size+1;
			while (end >pos)
			{
				_str[end] = _str[end-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;
			while (end > pos + len-1)
			{
				_str[end] = _str[end - len];
				--end;
			}
			strncpy(_str + pos, str, len);
			_size += len;
			return *this;
		}

		string& erase(size_t pos,size_t len = npos)
		{
			assert(pos < _size);
			if (len == npos||pos+len>=_size)
			{
				_str[pos] = '\0';
				_size = pos;
			}
			//挪动数据
			else
			{
				strcpy(_str + pos, _str + pos + len);
				_size -= len;
			}
			return *this;
		}

		void clear()
		{
			_str[0] = '\0';
			_size = 0;
		}

		size_t find(const char ch, size_t pos = 0)
		{
			assert(pos < _size);
			while (pos < _size)
			{
				if (_str[pos] == ch)
				{
					return pos;
				}
				++pos;
			}
			return npos;
		}
		size_t find(const char* str, size_t pos = 0)
		{
			const char* ptr = strstr(_str + pos, str);
			if (ptr == nullptr)
			{
				return npos;
			}
			else
			{
				return ptr - _str;
			}
		}
	private:
		char* _str;
		size_t _size;
		size_t _capacity;

		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();
		char ch = in.get();
		while (ch != ' ' && ch != '\n')
		{
			s += ch;
			ch = in.get();
		}
		return in;
	}*/
	istream& operator>>(istream& in, string& s)
	{
		s.clear();
		char buff[128] = { '\0' };
		size_t i = 0;
		char ch = in.get();
		while (ch != ' ' && ch != '\n')
		{
			if (i == 127)
			{
				s += buff;
				i = 0;
			}
			buff[i++] = ch;
			ch = in.get();
		}
		if (i >= 0)
		{
			buff[i] = '\0';
			s += buff;
		}
		return in;
	}



	void test_string1()
	{
		string s1("hello world");
		string::iterator it1 = s1.begin();
		while (it1 != s1.end())
		{
			cout << *it1 << " ";
			++it1;
		}
		cout << endl;
		for (auto ch : s1)
		{
			cout << ch << " ";
		}
		cout << endl;
	}

	void test_string2()
	{
		string s1("hello");
		s1 += ' ';
		s1 += "world hello world";

		string s2;
		s2 += 'X';
	}

	void test_string3()
	{
		string s1("hello world");
		s1.insert(0, 'X');
		cout << s1.c_str() << endl;
		s1.insert(12, 'Y');
		cout << s1.c_str() << endl;
		s1.insert(13,"CWH");
		cout << s1.c_str() << endl;
		s1.insert(0, "hwc");
		cout << s1.c_str() << endl;

	}
	void test_string4()
	{
		string s1("hello world");
		s1.erase(3, 4);
		cout << s1.c_str() << endl;
	}

	void test_string5()
	{
		string s1("hello world");
		cout << s1.c_str() << endl;
		s1.resize(16, 'X');
		cout << s1.c_str() << endl;

		string s2("hello world");
		s2.resize(5);
		cout << s2.size() << endl;
		cout << s2.capacity() << endl;
		cout << s2.c_str() << endl;
	}

	void test_string6()
	{
		string s1("hello world");
		cout << s1 << endl;
		cout << s1.c_str() << endl;

		s1.insert(5, 'X');
		cout << s1.size() << endl;
		cout << s1.capacity()<< endl;

		cout << s1 << endl;
		cout << s1.c_str() << endl;

		string s2;
		cin >> s2;
		cout << s2 << endl;
	}

	void test_string7()
	{
		string s1("hello world");
		string s2(s1);

		cout << s1 << endl;
		cout << s2 << endl;

		string s3("HWC");
		s1 = s3;
		cout << s1 << endl;
		cout << s3 << endl;

		s1.swap(s2);
		swap(s1, s2);
		cout << s1 << endl;
		cout << s2 << endl;

	}
}
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
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439