【C++】STL——string（两万字详解）

🎇C++学习历程：STL——string学习

---

• 博客主页：一起去看日落吗
• 持续分享博主的C++学习历程
• 博主的能力有限，出现错误希望大家不吝赐教
• 分享给大家一句我很喜欢的话： 也许你现在做的事情，暂时看不到成果，但不要忘记，树🌿成长之前也要扎根，也要在漫长的时光🌞中沉淀养分。静下来想一想，哪有这么多的天赋异禀，那些让你羡慕的优秀的人也都曾默默地翻山越岭🐾。

---

🍁 🍃 🍂 🌿

---

🌿1. 为什么要学习string类？

🍃1.1 C语言中的字符串

C语言中，字符串是以’\0’结尾的一些字符的集合，为了操作方便，C标准库中提供了一些str系列的库函数，但是这些库函数与字符串是分离开的，不太符合OOP的思想，而且底层空间需要用户自己管理，稍不留神可能还会越界访问。

---

🍃1.2 两个面试题（暂不做讲解）

字符串转整形数字

字符串相加

在OJ中，有关字符串的题目基本以string类的形式出现，而且在常规工作中，为了简单、方便、快捷，基本都使用string类，很少有人去使用C库中的字符串操作函数。

---

🌿2. 标准库中的string类

🍃2.1 string类(了解)

string类的文档介绍

• 字符串是表示字符序列的类。
• 标准的字符串类提供了对此类对象的支持，其接口类似于标准字符容器的接口，但添加了专门用于操作单字节字符字符串的设计特性。
• string 类是使用 char(即作为它的字符类型，使用它的默认 char_traits 和分配器类型 (关于模板的更多信息，请参阅 basic_string)。
• string 类是 basic_string 模板类的一个实例，它使用 char 来实例化 basic_string 模板类，并用 char_traits 和 allocator 作为 basic_string 的默认参数(根于更多的模板信息请参考 basic_string)。
• 注意，这个类独立于所使用的编码来处理字节:如果用来处理多字节或变长字符(如 UTF-8) 的序列，这个类的所有成员(如长度或大小)以及它的迭代器，将仍然按照字节(而不是实际编码的字符)来操作。

总结：

• string 是表示字符串的字符串类。
• 该类的接口与常规容器的接口基本相同，再添加了一些专门用来操作 string 的常规操作。
• string 在底层实际是：basic_string 模板类的别名，typedef basic_string string;。
• 不能操作多字节或者变长字符的序列。

在使用 string 类时，必须包含 string 头文件以及 using namespace std;

#include
#include
using namespace std;
int main()
{
	cout << sizeof(char) << endl;
	cout << sizeof(wchar_t) << endl;

	char arr1[] = "hello bit";
	char arr2[] = "byih";
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13

---

🍃2.1 string类的常用接口说明（只讲解最常用的接口）

🍂2.1.1 string类对象的常见构造

#include
#include
using namespace std;   
//大概原理
template<class T>
class basic_string
{
	T* _arr;
	int _size;
	int _capacity;
};
//typedef basic_string string;
int main()
{
	string s1;
	string s2("hello");  
	string s3("byih");
	string s4(10, 'a');
	string s5(s2);
	//对于string它重载了流提取和流插入等，这里就可以直接用
	cout << s1 << endl;
	cout << s2 << endl;
	cout << s3 << endl;
	cout << s4 << endl;
	cout << s5 << endl;
	
	//赋值 ———— 深拷贝
	s1 = s5;
	cout << s1 << 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

s1虽然是无参的，但是他的第一个位置会有一个\0

---

🍂2.1.2 string类对象的容量操作造

#include
#include
using namespace std;
void test_string1()
{
	//1、size | length
	string s1("hello world");
	cout << s1.size() << endl;
	cout << s1.length() << endl;
	cout << "----------cut----------" << endl;
	//2、max_size
	string s2;
	cout << s1.max_size() << endl;
	cout << s2.max_size() << endl;	
	cout << "----------cut----------" << endl;
	//3、capacity
	cout << s1.capacity() << endl;
	cout << "----------cut----------" << endl;
	//4、resize
	string s3("hello world");
	cout << s3.size() << endl;
	cout << s3 << endl;
	//s3.resize(20);//n大于当前的字符串的长度且没有指定c，所以hello world\0\0\0\0...   
	//s3.resize(5);//n小于当前的字符串的长度， 它会删除掉从n开始的这些字符
	s3.resize(20, 'x');//n大于当前的字符串的长度且指定c，所以hello worldxxxx...
	cout << s3.size() << endl;
	cout << s3 << endl;
	cout << "----------cut----------" << endl;
	//5、reserve
	string s4("hello world");
	s4.reserve(20);
	cout << s4 << endl;
	cout << s4.size() << endl;
	cout << s4.capacity() << endl;
	s4.reserve(10);
	cout << s4 << endl;
	cout << s4.size() << endl;
	cout << s4.capacity() << endl;
	cout << "----------cut----------" << endl;
	//6、clear | empty
	string s5("hello world");
	cout << s5 << endl;
	cout << s5.empty() << endl;;
	s5.clear();
	cout << s5 << endl;
	cout << s5.empty() << endl;
	cout << "----------cut----------" << endl;
	//7、shrink_to_fit 暂且不演示
}   
void test_string2()
{
	string s;
	size_t sz = s.capacity();
	cout << "making s grow:\n" << sz << endl;
	for(int i = 0; i < 500; ++i)
	{
		s.push_back('c');
		if(sz != s.capacity())
		{
			sz = s.capacity();
			cout << "capacity changed:" << sz << '\n';
		}
	}
	cout << "----------cut----------" << endl;
}
int main()
{
	test_string1();
	test_string2();

	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

注意：

1. size()与length()方法底层实现原理完全相同，引入size()的原因是为了与其他容器的接口保持一致，一般情况下基本都是用size()。
2. clear()只是将string中有效字符清空，不改变底层空间大小。
3. resize(size_t n) 与 resize(size_t n, char c)都是将字符串中有效字符个数改变到n个，不同的是当字符个数增多时：resize(n)用0来填充多出的元素空间，resize(size_t n, char c)用字符c来填充多出的元素空间。注意：resize在改变元素个数时，如果是将元素个数增多，可能会改变底层容量的大小，如果是将元素个数减少，底层空间总大小不变。
4. reserve(size_t res_arg=0)：为string预留空间，不改变有效元素个数，当reserve的参数小于string的底层空间总大小时，reserver不会改变容量大小。

---

🍂2.1.3 string类对象的访问及遍历操作

#define _CRT_SECURE_NO_WARNINGS

#include 
using namespace std;

#include 


// 测试string容量相关的接口
// size/clear/resize
void Teststring1()
{
	// 注意：string类对象支持直接用cin和cout进行输入和输出
	string s("hello, bit!!!");
	cout << s.size() << endl;
	cout << s.length() << endl;
	cout << s.capacity() << endl;
	cout << s << endl;

	// 将s中的字符串清空，注意清空时只是将size清0，不改变底层空间的大小
	s.clear();
	cout << s.size() << endl;
	cout << s.capacity() << endl;

	// 将s中有效字符个数增加到10个，多出位置用'a'进行填充
	// “aaaaaaaaaa”
	s.resize(10, 'a');
	cout << s.size() << endl;
	cout << s.capacity() << endl;

	// 将s中有效字符个数增加到15个，多出位置用缺省值'\0'进行填充
	// "aaaaaaaaaa\0\0\0\0\0"
	// 注意此时s中有效字符个数已经增加到15个
	s.resize(15);
	cout << s.size() << endl;
	cout << s.capacity() << endl;
	cout << s << endl;

	// 将s中有效字符个数缩小到5个
	s.resize(5);
	cout << s.size() << endl;
	cout << s.capacity() << endl;
	cout << s << endl;
}

//====================================================================================
void Teststring2()
{
	string s;
	// 测试reserve是否会改变string中有效元素个数
	s.reserve(100);
	cout << s.size() << endl;
	cout << s.capacity() << endl;

	// 测试reserve参数小于string的底层空间大小时，是否会将空间缩小
	s.reserve(50);
	cout << s.size() << endl;
	cout << s.capacity() << endl;
}

// 利用reserve提高插入数据的效率，避免增容带来的开销
//====================================================================================
void TestPushBack()
{
	string s;
	size_t sz = s.capacity();
	cout << "making s grow:\n";
	for (int i = 0; i < 100; ++i)
	{
		s.push_back('c');
		if (sz != s.capacity())
		{
			sz = s.capacity();
			cout << "capacity changed: " << sz << '\n';
		}
	}
}

// 构建vector时，如果提前已经知道string中大概要放多少个元素，可以提前将string中空间设置好
void TestPushBackReserve()
{
	string s;
	s.reserve(100);
	size_t sz = s.capacity();

	cout << "making s grow:\n";
	for (int i = 0; i < 100; ++i)
	{
		s.push_back('c');
		if (sz != s.capacity())
		{
			sz = s.capacity();
			cout << "capacity changed: " << sz << '\n';
		}
	}
}



// string的遍历
// begin()+end()   for+[]  范围for
// 注意：string遍历时使用最多的还是for+下标 或者 范围for(C++11后才支持)
// begin()+end()大多数使用在需要使用STL提供的算法操作string时，比如：采用reverse逆置string
void Teststring3()
{
	string s1("hello Bit");
	const string s2("Hello Bit");
	cout << s1 << " " << s2 << endl;
	cout << s1[0] << " " << s2[0] << endl;

	s1[0] = 'H';
	cout << s1 << endl;

	// s2[0] = 'h';   代码编译失败，因为const类型对象不能修改
}

void Teststring4()
{
	string s("hello Bit");
	// 3种遍历方式：
	// 需要注意的以下三种方式除了遍历string对象，还可以遍历是修改string中的字符，
	// 另外以下三种方式对于string而言，第一种使用最多
	// 1. for+operator[]
	for (size_t i = 0; i < s.size(); ++i)
		cout << s[i] << endl;

	// 2.迭代器
	string::iterator it = s.begin();
	while (it != s.end())
	{
		cout << *it << endl;
		++it;
	}

	// string::reverse_iterator rit = s.rbegin();
	// C++11之后，直接使用auto定义迭代器，让编译器推到迭代器的类型
	auto rit = s.rbegin();
	while (rit != s.rend())
		cout << *rit << endl;

	// 3.范围for
	for (auto ch : s)
		cout << ch << endl;
}


//
// 测试string：
// 1. 插入(拼接)方式：push_back  append  operator+= 
// 2. 正向和反向查找：find() + rfind()
// 3. 截取子串：substr()
// 4. 删除：erase
void Teststring5()
{
	string str;
	str.push_back(' ');   // 在str后插入空格
	str.append("hello");  // 在str后追加一个字符"hello"
	str += 'b';           // 在str后追加一个字符'b'   
	str += "it";          // 在str后追加一个字符串"it"
	cout << str << endl;
	cout << str.c_str() << endl;   // 以C语言的方式打印字符串

	// 获取file的后缀
	string file("string.cpp");
	size_t pos = file.rfind('.');
	string suffix(file.substr(pos, file.size() - pos));
	cout << suffix << endl;

	// npos是string里面的一个静态成员变量
	// static const size_t npos = -1;

	// 取出url中的域名
	string url("http://www.cplusplus.com/reference/string/string/find/");
	cout << url << endl;
	size_t start = url.find("://");
	if (start == string::npos)
	{
		cout << "invalid url" << endl;
		return;
	}
	start += 3;
	size_t finish = url.find('/', start);
	string address = url.substr(start, finish - start);
	cout << address << endl;

	// 删除url的协议前缀
	pos = url.find("://");
	url.erase(0, pos + 3);
	cout << url << endl;
}

int main()
{
	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

---

🍂2.1.4 string类对象的修改操作

#define _CRT_SECURE_NO_WARNINGS

#include 
using namespace std;

#include 


// 测试string容量相关的接口
// size/clear/resize
void Teststring1()
{
	// 注意：string类对象支持直接用cin和cout进行输入和输出
	string s("hello, bit!!!");
	cout << s.size() << endl;
	cout << s.length() << endl;
	cout << s.capacity() << endl;
	cout << s << endl;

	// 将s中的字符串清空，注意清空时只是将size清0，不改变底层空间的大小
	s.clear();
	cout << s.size() << endl;
	cout << s.capacity() << endl;

	// 将s中有效字符个数增加到10个，多出位置用'a'进行填充
	// “aaaaaaaaaa”
	s.resize(10, 'a');
	cout << s.size() << endl;
	cout << s.capacity() << endl;

	// 将s中有效字符个数增加到15个，多出位置用缺省值'\0'进行填充
	// "aaaaaaaaaa\0\0\0\0\0"
	// 注意此时s中有效字符个数已经增加到15个
	s.resize(15);
	cout << s.size() << endl;
	cout << s.capacity() << endl;
	cout << s << endl;

	// 将s中有效字符个数缩小到5个
	s.resize(5);
	cout << s.size() << endl;
	cout << s.capacity() << endl;
	cout << s << endl;
}

//====================================================================================
void Teststring2()
{
	string s;
	// 测试reserve是否会改变string中有效元素个数
	s.reserve(100);
	cout << s.size() << endl;
	cout << s.capacity() << endl;

	// 测试reserve参数小于string的底层空间大小时，是否会将空间缩小
	s.reserve(50);
	cout << s.size() << endl;
	cout << s.capacity() << endl;
}

// 利用reserve提高插入数据的效率，避免增容带来的开销
//====================================================================================
void TestPushBack()
{
	string s;
	size_t sz = s.capacity();
	cout << "making s grow:\n";
	for (int i = 0; i < 100; ++i)
	{
		s.push_back('c');
		if (sz != s.capacity())
		{
			sz = s.capacity();
			cout << "capacity changed: " << sz << '\n';
		}
	}
}

// 构建vector时，如果提前已经知道string中大概要放多少个元素，可以提前将string中空间设置好
void TestPushBackReserve()
{
	string s;
	s.reserve(100);
	size_t sz = s.capacity();

	cout << "making s grow:\n";
	for (int i = 0; i < 100; ++i)
	{
		s.push_back('c');
		if (sz != s.capacity())
		{
			sz = s.capacity();
			cout << "capacity changed: " << sz << '\n';
		}
	}
}



// string的遍历
// begin()+end()   for+[]  范围for
// 注意：string遍历时使用最多的还是for+下标 或者 范围for(C++11后才支持)
// begin()+end()大多数使用在需要使用STL提供的算法操作string时，比如：采用reverse逆置string
void Teststring3()
{
	string s1("hello Bit");
	const string s2("Hello Bit");
	cout << s1 << " " << s2 << endl;
	cout << s1[0] << " " << s2[0] << endl;

	s1[0] = 'H';
	cout << s1 << endl;

	// s2[0] = 'h';   代码编译失败，因为const类型对象不能修改
}

void Teststring4()
{
	string s("hello Bit");
	// 3种遍历方式：
	// 需要注意的以下三种方式除了遍历string对象，还可以遍历是修改string中的字符，
	// 另外以下三种方式对于string而言，第一种使用最多
	// 1. for+operator[]
	for (size_t i = 0; i < s.size(); ++i)
		cout << s[i] << endl;

	// 2.迭代器
	string::iterator it = s.begin();
	while (it != s.end())
	{
		cout << *it << endl;
		++it;
	}

	// string::reverse_iterator rit = s.rbegin();
	// C++11之后，直接使用auto定义迭代器，让编译器推到迭代器的类型
	auto rit = s.rbegin();
	while (rit != s.rend())
		cout << *rit << endl;

	// 3.范围for
	for (auto ch : s)
		cout << ch << endl;
}


//
// 测试string：
// 1. 插入(拼接)方式：push_back  append  operator+= 
// 2. 正向和反向查找：find() + rfind()
// 3. 截取子串：substr()
// 4. 删除：erase
void Teststring5()
{
	string str;
	str.push_back(' ');   // 在str后插入空格
	str.append("hello");  // 在str后追加一个字符"hello"
	str += 'b';           // 在str后追加一个字符'b'   
	str += "it";          // 在str后追加一个字符串"it"
	cout << str << endl;
	cout << str.c_str() << endl;   // 以C语言的方式打印字符串

	// 获取file的后缀
	string file("string.cpp");
	size_t pos = file.rfind('.');
	string suffix(file.substr(pos, file.size() - pos));
	cout << suffix << endl;

	// npos是string里面的一个静态成员变量
	// static const size_t npos = -1;

	// 取出url中的域名
	string url("http://www.cplusplus.com/reference/string/string/find/");
	cout << url << endl;
	size_t start = url.find("://");
	if (start == string::npos)
	{
		cout << "invalid url" << endl;
		return;
	}
	start += 3;
	size_t finish = url.find('/', start);
	string address = url.substr(start, finish - start);
	cout << address << endl;

	// 删除url的协议前缀
	pos = url.find("://");
	url.erase(0, pos + 3);
	cout << url << endl;
}

int main()
{
	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

注意：

1. 在string尾部追加字符时，s.push_back© / s.append(1, c) / s += 'c’三种的实现方式差不多，一般情况下string类的+=操作用的比较多，+=操作不仅可以连接单个字符，还可以连接字符串。
2. 对string操作时，如果能够大概预估到放多少字符，可以先通过reserve把空间预留好。

---

🍂2.1.5 string类非成员函数

上面的几个接口大家了解一下，下面的OJ题目中会有一些体现他们的使用。string类中还有一些其他的操作，这里不一一列举，大家在需要用到时不明白了查文档即可。

---

🍂2.1.6 vs和g++下string结构的说明

注意：下述结构是在32位平台下进行验证，32位平台下指针占4个字节。

• vs下string的结构
  string总共占28个字节，内部结构稍微复杂一点，先是有一个联合体，联合体用来定义string中字符串的存储空间：
  — 当字符串长度小于16时，使用内部固定的字符数组来存放
  — 当字符串长度大于等于16时，从堆上开辟空间

union _Bxty
{ 	// storage for small buffer or pointer to larger one
	value_type _Buf[_BUF_SIZE];
	pointer _Ptr;
	char _Alias[_BUF_SIZE]; // to permit aliasing
} _Bx;
1
2
3
4
5
6

这种设计也是有一定道理的，大多数情况下字符串的长度都小于16，那string对象创建好之后，内部已经有了16个字符数组的固定空间，不需要通过堆创建，效率高。
其次：还有一个size_t字段保存字符串长度，一个size_t字段保存从堆上开辟空间总的容量
最后：还有一个指针做一些其他事情。
故总共占16+4+4+4=28个字节。

• g++下string的结构
  G++下，string是通过写时拷贝实现的，string对象总共占4个字节，内部只包含了一个指针，该指针将来指向一块堆空间，内部包含了如下字段：
  — 空间总大小
  — 字符串有效长度
  — 引用计数

struct _Rep_base
{
	size_type _M_length;
	size_type _M_capacity;
	_Atomic_word _M_refcount;
};
1
2
3
4
5
6

— 指向堆空间的指针，用来存储字符串。

---

🍁小试牛刀（做题训练）

🍂第一题

仅仅反转字母

给你一个字符串 s ，根据下述规则反转字符串：

• 所有非英文字母保留在原有位置。
• 所有英文字母（小写或大写）位置反转。

返回反转后的 s 。

示例 1：

输入：s = “ab-cd”
输出：“dc-ba”

示例 2：

输入：s = “a-bC-dEf-ghIj”
输出：“j-Ih-gfE-dCba”

示例 3：

输入：s = “Test1ng-Leet=code-Q!”
输出：“Qedo1ct-eeLg=ntse-T!”

提示:

• 1 <= s.length <= 100
• s 仅由 ASCII 值在范围 [33, 122] 的字符组成
• s 不含 ‘"’ 或 ‘\’

题解思路：

我们使用 begin 指针从左边开始扫描字符串 s，end 指针从右边开始扫描字符串 s。如果两个指针都扫描到字母，且begin < end，那么交换 s[begin]和 s[end]，然后继续进行扫描；否则表明反转过程结束，返回处理后的字符串。

代码实现：

class Solution 
{
public:
    bool isLetter(char ch)//判断是否为字母，如果是返回treu，否则返回false
    {
        if(ch >= 'a' && ch <= 'z')
            return true;
        if(ch >= 'A' && ch <= 'Z')
            return true;
        return false;
    }
    string reverseOnlyLetters(string s) 
    {
        auto begin = s.begin();
        auto end = s.end() - 1;
        while(begin < end)
        {
            while(begin < end && !isLetter(*begin))//非英文字母，且保证最后begin和end重合
            {
                ++begin;
            }
            while(begin < end && !isLetter(*end))//非英文字母，且保证最后begin和end重合
            {
                --end;
            }
            swap(*begin, *end);//交换
            //交换后还要调整
            ++begin;
            --end;
        }
        return s;
    }
};
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

---

🍂第二题

字符串中第一个唯一字符

题述：给定一个字符串 s ，找到它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。

示例1：

输入：s = “leetcode”
输出：0

示例2：

输入: s = “loveleetcode”
输出: 2

示例3：

输入: s = “aabb”
输出: -1

提示:

• 1 <= s.length <= 105
• s 只包含小写字母

解题思路：

首先遍历一遍字符串，然后把每个字母的出现次数计算出来。

之后再遍历一遍字符串。遍历过程中，如果遇到了一个值出现过一次的字母，就返回这个字母的下标。

代码实现：

class Solution 
{
public:
    int firstUniqChar(string s) 
    {
        int count[26] = {0};
        //统计每个字符出现的次数
        for(auto ch:s)
        {
           count[ch - 'a']++;
        }
        //找出字符串中第一个不重复的字符
        for(int i = 0; i < s.size(); ++i)
        {
            if(count[s[i] - 'a'] == 1)
            {
				return i;
            }
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

---

🍂第三题

字符串最后一个单词的长度

• 解题思路

注意这里读区字符串不能直接cin，因为cin遇到空格就会终止，要用getline

• 代码实现

#include
#include
using namespace std;
int main()
{
    string s;
    //cin >> s;
    getline(cin, s);
    size_t pos = s.rfind(' ');
    if(pos != string::npos)//多个单词
    {
        cout << s.size() - (pos + 1) << endl;
    }
    else//一个单词
    {
        cout << s.size() << endl;
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

---

🍂第四题

验证回文串

• 解题思路

使用双指针。初始时，左右指针分别指向 sgood\textit{sgood}sgood 的两侧，随后我们不断地将这两个指针相向移动，每次移动一步，并判断这两个指针指向的字符是否相同。当这两个指针相遇时，就说明 sgood\textit{sgood}sgood 时回文串。

• 代码演示

class Solution {
public:
    bool IsLetterOrNun(char ch)
    {
        if((ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z') || (ch >= '0' && ch <= '9'))
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    bool isPalindrome(string s) {
        int begin = 0, end = s.size() - 1;
        while(begin < end)
        {
            while(begin < end && !IsLetterOrNun(s[begin]))//跳过非字母数字
            {
                ++begin;
            }
            while(begin < end && !IsLetterOrNun(s[end]))//跳过非字母数字
            {
                --end;
            }
            if(s[begin] != s[end])
            {
                //有一个是数字，就不存在大小写比较问题
                if(s[begin] < 'A' || s[end] < 'A')
                {
                    return false;
                }
                else if(s[begin] < s[end] && s[begin] + 32 == s[end])
                {
                    ++begin;
                    --end;
                }
                else if(s[end] < s[begin] && s[end] + 32 == s[begin])
                {
                    ++begin;
                    --end;
                }
                else
                {
                    return false;
                }
            }
            else
            {
                ++begin;
                --end;
            }
        }
        return true;
    }
};

//改进代码


class Solution {
public:
    bool isPalindrome(string s) {
        string sgood;
        for (char ch: s) {
            if (isalnum(ch)) {
                sgood += tolower(ch);
            }
        }
        int n = sgood.size();
        int left = 0, right = n - 1;
        while (left < right) {
           if (sgood[left] != sgood[right]) {
                return false;
            }
            ++left;
            --right;
        }
        return true;
    }
};


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

---

🍂第五题

字符串相加

• 解题思路

本题我们只需要对两个大整数模拟「竖式加法」的过程。竖式加法就是我们平常学习生活中常用的对两个整数相加的方法，回想一下我们在纸上对两个整数相加的操作，是不是如下图将相同数位对齐，从低到高逐位相加，如果当前位和超过 101010，

• 代码演示

class Solution {
public:
    string addStrings(string num1, string num2) {
        string retStr;
        int end1 = num1.size() - 1;
        int end2 = num2.size() - 1;
        int carry = 0;
        while(end1 >= 0 || end2 >= 0)//只要还有一位那么就继续
        {
            int val1 = 0, val2 = 0;
            if(end1 >= 0)
            {
                val1 = num1[end1] - '0';
                --end1;
            }
            if(end2 >= 0)
            {
                val2 = num2[end2] - '0';
                --end2;
            }
            int ret = val1 + val2 + carry;
            if(ret > 9)//进位
            {
                ret -= 10;
                carry = 1;
            }
            else
            {
                carry = 0;
            }
            //头插
            retStr.insert(0, 1, '0' + ret);
            //retStr.insert(retStr.begin(), '0' + ret);//同上
        } 
        if(carry == 1)//还有一位的情况："1","9"
        {
           retStr.insert(retStr.begin(), '1');
        }
        return retStr;
    }
};

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

---

🌿3. string类的模拟实现

🍃3.1 经典的string类问题

上面已经对string类进行了简单的介绍，大家只要能够正常使用即可。在面试中，面试官总喜欢让学生自己来模拟实现string类，最主要是实现string类的构造、拷贝构造、赋值运算符重载以及析构函数。大家看下以下string类的实现是否有问题？

string.h

// 为了和标准库区分，此处使用String
class String
{
public:
	/*String()
	:_str(new char[1])
	{*_str = '\0';}
	*/
	//String(const char* str = "\0") 错误示范
	//String(const char* str = nullptr) 错误示范
	String(const char* str = "")
	{
	// 构造String类对象时，如果传递nullptr指针，可以认为程序非
		if (nullptr == str)
		{
			assert(false);
		return;
		}
		_str = new char[strlen(str) + 1];
		strcpy(_str, str);
	}
	~String()
	{
		if (_str)
		{
			delete[] _str;
			_str = nullptr;
		}
	}
private:
	char* _str;
};
// 测试
void TestString()
{
	String s1("hello bit!!!");
	String s2(s1);
}
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

string.cpp

#include"string.h"
int main()
{
	TestString();
	return 0;
}

1
2
3
4
5
6
7

说明：上述String类没有显式定义其拷贝构造函数与赋值运算符重载，此时编译器会合成默认的，当用s1构造s2时，编译器会调用默认的拷贝构造。最终导致的问题是，s1、s2共用同一块内存空间，在释放时同一块空间被释放多次而引起程序崩溃，这种拷贝方式，称为浅拷贝。

---

🍃3.2 浅拷贝

由如上代码我们了解了浅拷贝会带来两个问题：

• 析构两次空间
• 其中一个去修改，会影响另一个

浅拷贝：也称位拷贝，编译器只是将对象中的值拷贝过来。如果对象中管理资源，最后就会导致多个对象共享同一份资源，当一个对象销毁时就会将该资源释放掉，而此时另一些对象不知道该资源已经被释放，以为还有效，所以当继续对资源进项操作时，就会发生发生了访问违规。

就像一个家庭中有两个孩子，但父母只买了一份玩具，两个孩子愿意一块玩，则万事大吉，万一不想分享就你争我夺，玩具损坏。

可以采用深拷贝解决浅拷贝问题，即：每个对象都有一份独立的资源，不要和其他对象共享。父母给每个孩子都买一份玩具，各自玩各自的就不会有问题了。

---

🍃3.3 深拷贝

如果一个类中涉及到资源的管理，其拷贝构造函数、赋值运算符重载以及析构函数必须要显式给出。一般情况都是按照深拷贝方式提供。

深拷贝会新开辟一块与原对象一样大的空间，再把原对象空间上的值拷贝过来。

---

3.3.1 🍂深拷贝的传统版写法的string类

string.h

#pragma once
namespace bit
{
	class string
	{
	public:
		string(char* str)
			:_str(new char[strlen(str) + 1]
		{
			strcpy(_str, str);
		}
		//s2(s1)
		string(const string& s)
			:_str(new char[strlen(s.str) + 1])
		{
			strcpy(_str, s._str);
		}
		//s1 = s3
		string operator=(const string& s)
		{
			if(this != &s)//防止自己赋值
			{
				/*delete[] _str;//this->_str
				_str = new char[strlen(s._str) + 1];*/
				char* tmp = new char[strlen(s._str) + 1];
				delete[] _str;
				_str = tmp;
				strcpy(_str, s._str);
			}
			return *this;
		}
		~string()
		{
			delete[] _str;
			_str = nullptr;
		}
		char& operator[](size_t pos)
		{
			return _str[pos];
		}
	private:
		char* _str;
	};
	void f1(string s)
	{}
	void f2(const string& s)
	{}
	template<class T>
	void f3(T x)
	{}
	void f3(const T& x)
	{}
	void test_string1()
	{
		string s1("hello");
		s1[0] = 'x';

		string s2(s1);
		s2[0] = 'y';
		
		string s3("hello bit");
		s1 = s3;
	
		f1(s1);
		f2(s2);
	}
}

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

string.cpp

#include"string.h"
int main()
{
	try
	{
		bit::test_string1();	
	}
	catch(exception& e)
	{
		cout << e.what() << endl;	
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

---

3.3.2 🍂深拷贝的现代版写法的String类

class String
{
public:
	String(const char* str = "")
	{
		if (nullptr == str)
		{
			assert(false);
			return;
		}
		_str = new char[strlen(str) + 1];
		strcpy(_str, str);
	}
	String(const String& s)
		: _str(nullptr)
	{
		String strTmp(s._str);
		swap(_str, strTmp._str);
	}
	// 对比下和上面的赋值那个实现比较好？
	String& operator=(String s)
	{
		swap(_str, s._str);
		return *this;
	}
	/*
	String& operator=(const String& s)
	{
		if(this != &s)
		{
			String strTmp(s);
			swap(_str, strTmp._str);
		}
		return *this;
	}
	*/
	~String()
	{
		if (_str)
		{
			delete[] _str;
			_str = nullptr;
		}
	}
private:
	char* _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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

它们俩的效率是一样的，但两者都各有千秋

• 传统写法，可读性高，便于理解，但操作性较低
• 现代写法，代码更加简洁高效，但是逻辑更加复杂

---

🍃3.4 写时拷贝(了解)

写时拷贝就是一种拖延症，是在浅拷贝的基础之上增加了引用计数的方式来实现的。

引用计数：用来记录资源使用者的个数。在构造时，将资源的计数给成1，每增加一个对象使用该资源，就给计数增加1，当某个对象被销毁时，先给该计数减1，然后再检查是否需要释放资源，如果计数为1，说明该对象时资源的最后一个使用者，将该资源释放；否则就不能释放，因为还有其他对象在使用该资源。

早期 Linux 选择了写时拷贝的技术，而 VS 下选择了直接深拷贝的技术。它们本质都是深拷贝，只是说 Linux 下先做浅拷贝，如果不写就不做深拷贝，写了再去做深拷贝，并且是谁写谁做。

写时拷贝

写时拷贝在读取时的缺陷

---

🍃3.5 string类的模拟实现

#pragma once

namespace bit
{
	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])
			, _size(0)
			, _capacity(0)
		{
			_str[0] = '\0';
		}*/

		// 不能这么初始化空对象
		/*string()
			:_str(nullptr)
			, _size(0)
			, _capacity(0)
			{}*/

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

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

		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])
		//	, _size(s._size)
		//	, _capacity(s._capacity)
		//{
		//	strcpy(_str, s._str);
		//}

		 s1 = s3
		 s1 = s1
		//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;
		//}

		// 现代写法 -- 资本主义/老板思维
		// s2(s1)
		void swap(string& tmp)
		{
			::swap(_str, tmp._str);
			::swap(_size, tmp._size);
			::swap(_capacity, tmp._capacity);
		}

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

		// s1 = s3
		//string& operator=(const string& s)
		//{
		//	if (this != &s)
		//	{
		//		//string tmp(s._str);
		//		string tmp(s);
		//		swap(tmp); // this->swap(tmp);
		//	}

		//	return *this;
		//}

		// s1 = s3
		// s顶替tmp做打工人
		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;
		}

		const char& operator[](size_t pos) const
		{
			assert(pos < _size);

			return _str[pos];
		}

		char& operator[](size_t pos)
		{
			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 push_back(char ch)
		{
			// 满了就扩容
			/*if (_size == _capacity)
			{
				reserve(_capacity == 0 ? 4 : _capacity * 2);
			}

			_str[_size] = ch;
			++_size;
			_str[_size] = '\0';*/
			insert(_size, ch);
		}

		void append(const char* str)
		{
			//size_t len = strlen(str);

			 满了就扩容
			 _size + len  8  18  10  
			//if (_size + len > _capacity)
			//{
			//	reserve(_size+len);
			//}

			//strcpy(_str + _size, str);
			strcat(_str, str); 需要找\0，效率低
			//_size += len;
			insert(_size, str);
		}

		/*void append(const string& s)
		{
		append(s._str);
		}

		void append(size_t n, char ch)
		{
		reserve(_size + n);
		for (size_t i = 0; i < n; ++i)
		{
		push_back(ch);
		}
		}*/

		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)
			{
				reserve(_capacity == 0 ? 4 : _capacity * 2);
			}

			 挪动数据
			//int end = _size;
			//while (end >= (int)pos)
			//{
			//	_str[end + 1] = _str[end];
			//	--end;
			//}
			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)
			{
				_str[end] = _str[end - len];
				--end;
			}

			strncpy(_str + pos, str, len);
			_size += len;

			return *this;
		}

		void 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;
			}
		}

		size_t find(char ch, size_t pos = 0) const;
		size_t find(const char* sub, size_t pos = 0) const;
		bool operator>(const string& s) const;
		bool operator==(const string& s) const;
		bool operator>=(const string& s) const;
		bool operator<=(const string& s) const;
		bool operator<(const string& s) const;
		bool operator!=(const string& s) const;
	private:
		size_t _capacity;
		size_t _size;
		char* _str;

		// const static 语法特殊处理
		// 直接可以当成定义初始化
		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)
	{
		// 输入字符串很长，不断+=，频繁扩容，效率很低，大家可以想法优化一下 
		char ch;
		//in >> ch;
		ch = in.get();
		while (ch != ' ' && ch != '\n')
		{
			s += ch;
			ch = in.get();
		}

		return in;
	}

	//size_t string::npos = -1;

	void test_string1()
	{
	    /*std::string s1("hello world");
		std::string s2;*/
		string s1("hello world");
		string s2;

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

		for (size_t i = 0; i < s1.size(); ++i)
		{
			cout << s1[i] << " ";
		}
		cout << endl;

		for (size_t i = 0; i < s1.size(); ++i)
		{
			s1[i]++;
		}

		for (size_t i = 0; i < s1.size(); ++i)
		{
			cout << s1[i] << " ";
		}
		cout << endl;
	}

	void test_string2()
	{
		string s1("hello world");
		string::iterator it = s1.begin();
		while (it != s1.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;

		it = s1.begin();
		while (it != s1.end())
		{
			*it += 1;
			++it;
		}
		cout << endl;

		for (auto ch : s1)
		{
			cout << ch << " ";
		}
		cout << endl;
	}

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

		s2[0] = 'x';
		cout << s1.c_str() << endl;
		cout << s2.c_str() << endl;

		string s3("111111111111111111111111111111");
		s1 = s3;
		cout << s1.c_str() << endl;
		cout << s3.c_str() << endl;

		s1 = s1;

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

	void test_string4()
	{
		string s1("hello world");
		string s2("xxxxxxx");

		s1.swap(s2);
		swap(s1, s2);
	}

	void test_string5()
	{
		string s1("hello");
		cout << s1.c_str() << endl;
		s1.push_back('x');
		cout << s1.c_str() << endl;
		cout << s1.capacity() << endl;

		s1 += 'y';
		s1 += 'z';
		s1 += 'z';
		s1 += 'z';
		s1 += 'z';
		s1 += 'z';
		s1 += 'z';
		cout << s1.c_str() << endl;
		cout << s1.capacity() << endl;
	}

	void test_string6()
	{
		string s1("hello");
		cout << s1.c_str() << endl;
		s1 += ' ';
		s1.append("world");
		s1 += "bit hello";
		cout << s1.c_str() << endl;

		s1.insert(5, '#');
		cout << s1.c_str() << endl;

		s1.insert(0, '#');
		cout << s1.c_str() << endl;
	}

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

		s1.insert(2, "world");
		cout << s1.c_str() << endl;

		s1.insert(0, "world ");
		cout << s1.c_str() << endl;
	}

	void test_string8()
	{
		string s1("hello");
		s1.erase(1, 10);
		cout << s1.c_str() << endl;


		string s2("hello");
		s2.erase(1);
		cout << s2.c_str() << endl;

		string s3("hello");
		s3.erase(1, 2);
		cout << s3.c_str() << endl;
	}

	void test_string9()
	{
	/*	string s1;
		cin >> s1;
		cout << s1 << endl;*/

		string s1("hello");
		cout << s1 << endl;
		cout << s1.c_str() << endl;
		s1 += '\0';
		s1 += "world";
		cout << s1 << endl;
		cout << s1.c_str() << endl;

		string s3, s4;
		cin >> s3 >> s4;
		cout << s3<< s4 << 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
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528

---

🌿4. 拓展阅读

面试中string的一种正确写法

STL中的string类怎么了

---