【C++笔记】C++string类模拟实现

C++的string类也就是字符串，它是一个比较早的类，所以就没有被归到STL里。
这里实现的string只是为了粗浅的了解一下string的底层原理，所以可定不会有库里面的那么详细，而且这里也只会实现一些常用的接口，一些不常用的接口实现起来也没什么意思。

一、实现模型和基本接口

既然是管理字符串的，那我们就直接封装一个char*即可：

class String {
public :
private :
	char* _str; // 时刻被操作的字符串
	size_t _size; // 长度
	size_t _capacity; // 容量
};
1
2
3
4
5
6
7

然后我们实现的各个接口都是为了操作类中封装的这个_str即可。

1.1、各种构造和析构

构造函数：
其实构造函数有很多种实现方式，但我们日常用的最多的应该就是字符串构造，因为他本身就是存储字符串的嘛。
所以我们仅提供一个全缺省的构造函数即可：

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

需要注意的是，这里的容量表示的是该字符串最多能存多少个字符，但我们都知道字符串的结束标志’\0’是不能少的，每个字符串的结尾都必须存一个’\0’，所以我们这里开空间是中要比容量多1。
拷贝构造：
拷贝构造也很简单，直接开一段新空间然后复制参数中_str的内容即可。

String(const String& str) {
		// 只用来提示构造函数被调用
		cout << "String(const String& str)" << endl;
		_str = new char[str._capacity + 1];
		strcpy(_str, str._str);
		_size = str._size;
		_capacity = str._capacity;
	}
1
2
3
4
5
6
7
8

但是依然要注意，我们这里开空间一定要比容量多1。
析构函数：
因为我们至始至终都只管理着一个外部资源也就是_str，所以析构函数要做的工作也就很简单了，直接释放掉_str即可：

~String() {
		// 只用来提示析构函数被调用
		cout << "~String()" << endl; 
		delete[] _str;
		_str = nullptr;
		_size = 0;
		_capacity = 0;
	}
1
2
3
4
5
6
7
8

然后我们可以先提供一个简易的打印接口，来试验我们以上所写的接口：

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

从运行的结果来看，以上写的接口是没什么问题的。

1.2、迭代器

C++中的迭代器是一个很棒的设计，有了迭代器，我们就可以使很多类的遍历方法变得相同。
但这只是写的时候相同，迭代器其实是屏蔽了底层的原理，然后使用一套统一的方法来遍历，例如：

如上，字符串、vector和链表的底层肯定是不一样的，但它们展现出来的遍历方式却是一样的，这就是iterator迭代器的妙处。
这样一来即使有一些容器我们并不知道它的底层实现原理怎样，但是我们也还是可以照常遍历它们。

相信大家从上面对it的解引用也可以看得出，其实迭迭代器底层就是模拟的指针的行为。
但迭代器也并非都是用原生指针来实现的，对于像string和vector指针顺序结构，使用原生指针是完全可以的。但是对于list这种链式结构和各种树形结构使用原生指针的话就不行了，这需要对原生指针就行再次封装才行。

而现在的string使用原生指针是完全可以的：

class String {
public :
typedef char* iterator;
private :
	char* _str; // 时刻被操作的字符串
	size_t _size; // 长度
	size_t _capacity; // 容量
};
1
2
3
4
5
6
7
8

迭代器我们往往只需要提供两个位置即开始和结尾即可：

iterator begin() {
	return _str;
}
// 迭代器结束位置
iterator end() {
	return _str + _size;
}
1
2
3
4
5
6
7

这样我们就可以使用迭代器来遍历我们模拟实现的string类了：

有了迭代器，我们就可以使用一个更简便的遍历方式——范围for，因为范围for的底层就是使用迭代器实现的，编译器只是把范围for的语法傻傻的替换成迭代器而已：

二、各种插入和删除接口

2.1、插入接口

尾插一个字符
string中的_size指的是字符串的长度，但是因为字符串的下标其实是从0开始的，所以实际上_size所指向的位置其实是’\0’的位置：

所以当我们要尾插一个字符的时候，这个字符其实是要放在_size的位置。

void push_back(char ch) {
	// 检查扩容
	if (_size == _capacity) {
		reverse(_capacity == 0 ? 4 : 2 * _capacity);
	}
	_str[_size] = ch;
	_size++;
	_str[_size] = '\0';
}
1
2
3
4
5
6
7
8
9

如上，要插入数据就必定会遇到空间不足的情况，所以我们在正式插入之前必须先检查是否需要扩容。扩容的逻辑很简单，就是申请一块新容量的空间然后拷贝数据到新空间然后释放就空间在在让_str指向新空间即可：

void reverse(size_t newCapacity) {
	if (newCapacity > _capacity) {
		char* temp = new char[newCapacity + 1];
		strcpy(temp, _str);
		delete[] _str;
		_str = temp;
		_capacity = newCapacity;
	}
}
1
2
3
4
5
6
7
8
9

尾插一个字符串(追加)
尾插一个字符串的逻辑其实和尾插一个字符的逻辑大差不差，只不过是字符变多了而已。

void append(const char* str) {
	assert(str);
	// 检查扩容
	size_t len = strlen(str);
	if (_size + len > _capacity) {
		reverse(_size + len);
	}
	strncpy(_str + _size, str, len);
	_size += len;
	// 因为strcpy并不会连带'\0'一起拷贝，所以我们得自己补上
	_str[_size] = '\0'; 
}
1
2
3
4
5
6
7
8
9
10
11
12

随机插入一个字符
在pos位置插入一个字符ch。
因为string也属于顺序结构，对于顺序结构来说随机插入最烦人的就是挪动数据，例如这里我们要把从pos位置其后面的所有数据都向后移动一个位置：

未完成这个操作我们可以定义一个end指向_size的位置 (使end从_size开始是为了连‘‘0’一起移动，到最后就不需要再手动加上’\0’了)，也就是’\0’的位置：

然后循环操作_str[end + 1] = _str[end]，并让end–直到end与pos重合为止。

void insert(size_t pos, char ch) {
	assert(pos <= _size);
	// 检查扩容
	if (_size == _capacity) {
		reverse(_capacity == 0 ? 4 : 2 * _capacity);
	}
	// 挪动数据
	int end = _size;
	while (end >= (int)pos) {
		_str[end + 1] = _str[end];
		end--;
	}
	_str[pos] = ch;
	_size++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

随机插入一个字符串
随机插入一个字符串的逻辑也和随机插入一个字符的逻辑大差不差，我们几乎可以复用之前的逻辑，然后只需要改动挪动数据的间隔即可。

void insert(size_t pos, const char* str) {
		assert(pos <= _size);
		// 检查扩容
		size_t len = strlen(str);
		if (_size + len > _capacity) {
			reverse(_size + len);
		}
		// 挪动数据
		int end = _size;
		while (end >= (int)pos) {
			// 这里只需要将1改成len即可
			_str[end + len] = _str[end];
			end--;
		}
		// 拷贝数据
		strncpy(_str + pos, str, len);
		_size += len;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

写完我们可以顺势来检验一下：

2.2、删除接口

从pos位置开始，删除len个字符。
这个接口的逻辑就比insert要简单了，我们只需要将后面的数都向前挪动len个位置，覆盖掉前面的数据即可。
例如pos = 5，len = 6的情况：

为了完成这个操作，定义一个变量begin，让它从pos + len位置开始，然后循环执行_str[begin - len] = _str[begin]，并让begin++，直到begin和_size重合(连带’\0’一起挪动)：

有了以上分析，那我们写起代码来也就水到渠成了：

void erase(size_t pos, size_t len) {
	assert(pos < _size);
	size_t begin = pos + len;
	// 挪动数据
	while (begin <= _size) {
		_str[begin - len] = _str[begin];
		begin++;
	}
	_size -= len;
}
1
2
3
4
5
6
7
8
9
10

2.3、resize接口

有时候我们可能需要重置长度，特别是想要删除后面的数据只保留前面若干个数据的时候，我们或许会觉得使用erease可能太麻烦了。
所以我们要用到resize，这个接口可以一键保留前几个字符，或者扩大容量，后面的空间以某个字符进行填充。

实现这个接口其实要分两种情况：
当newSize < _size时候，我们要做的其实很简单，就是直接让_size = newSize，然后再让_str[_size] = '\0’即可。
而当newSize > _size时候我们才要进行填充，特别是当newSize > _capacity时，我们就需要先扩容再进行填充。

void resize(size_t newSize, char ch = '\0') {
	if (newSize > _size) {
		if (newSize > _capacity) {
			reverse(newSize);
		}
		// 填充字符
		memset(_str + _size, ch, newSize - _size);
	}
	_size = newSize;
	_str[_size] = '\0';
}
1
2
3
4
5
6
7
8
9
10
11

三、各种运算符重载

有了各种运算符重载我们就可以像内置类型一样使用我们的自定义类型了。

3.1、方括号运算符重载

有了方括号运算符重载，我们就可以像数组一样使用方括号[]来对我们定义的字符串进行遍历了。
它的实现原理很简单，就是返回_str[i]位置的引用即可：

char& operator[](size_t index) {
	assert(index < _size);
	return _str[index];
}
const char& operator[](size_t index) const {
	assert(index < _size);
	return _str[index];
}
1
2
3
4
5
6
7
8

但方括号运算符重载也要分const和非const版本的，因为有些时候我们只是想读取数据而不想修改数据，有些时候我们即想读也想改。

紧接着我们就可以来测试一下了：

3.2、各种比较运算符重载

小于运算符重载
既然我们都是在对_str进行操作，那当然就可以直接使用strcmp进行比较了：

bool operator<(const String& str) {
	return strcmp(_str, str._str) < 0;
}
1
2
3

等于运算符重载

bool operator==(const String& str) {
	return strcmp(_str, str._str) == 0;
}
1
2
3

小于等于运算符重载
其实实现了上面这两个之后，其他的都变得很简单了，我们直接复用即可，这不仅对于string这个类如此。几乎所有类都可以这样，因为这都是一些逻辑判断而已。

bool operator<=(const String& str) {
	return (*this < str) || (*this == str);
}
1
2
3

大于运算符重载

bool operator>(const String& str) {
	return !(*this <= str);
}
1
2
3

大于等于运算符重载

bool operator>=(const String& str) {
	return (*this > str) || (*this == str);
}
1
2
3

不等于运算符重载

bool operator!=(const String& str) {
	return !(*this == str);
}
1
2
3

四、查找接口

4.1、查找字符

从pos位置开始查找，返回字符ch在String中第一次出现的位置，找不到则返回起始位置。
这个逻辑其实很简单，从pos位置开始匹配即可。

size_t find(char ch, size_t pos = 0) const {
	assert(pos < _size);
	for (size_t i = pos; i < _size; i++) {
		if (ch == _str[i]) {
			return i;
		}
	}
	return pos;
}
1
2
3
4
5
6
7
8
9

我们可以测试一下：

4.2、查找子串

从pos位置开始查找，返回子串str在String中第一次出现的位置。
这个接口我们可以直接使用C++的前身C语言中的库函数strstr：

但是通过查看上面文档中的描述我们就会发现，strstr返回的并不是整数而是一个指针——指向子串在字符串中第一次出现的位置。
但这并不是什么大问题，不要忘了指针是可以相减的，并且相减得的结果也是一个整数，所以我们可以拿strstr的返回值减去_str，也就得到了我们想要的结果。

size_t find(const char* str, size_t pos = 0) const {
	assert(pos < _size);
	return strstr(_str + pos, str) - _str;
}
1
2
3
4

我们同样可以来测试一下：

五、流插入流提取运算符重载

5.1、流插入运算符重载

虽然我们已经有了三种遍历字符串的方式(方括号、迭代器、范围for)，但好像觉得都不是很方便。因为我们内置的字符数组其实是可以直接使用cout打印的：

如果用这个和其他的遍历方式进行比较，毫无疑问这个就是最方便的遍历方式了。
那我们实现的string能不能也只用这样的方法呢？
当然可以，我们只需要对String重载流插入运算符即可。

我们之前已经了解过了，因为参数的顺序问题，流插入和流提取运算符重载最好是重载成全局函数。
而又因为在类外边不能访问私有成员，所以我们要将这两个函数声明称String类的友元函数：

class Stirng {
	// 流插入流提取友元声明
	friend ostream& operator<<(ostream& _cout, const String& str);
	friend istream& operator>>(istream& _cin, String& str);
public :
private :
	char* str;
	size_t _size;
	size_t _capacity;
};
1
2
3
4
5
6
7
8
9
10

然后我们就可以开始动手写代码了：

ostream& operator<<(ostream& _cout, const String& str) {
	for (auto it : str) {
		_cout << it;
	}
	return _cout;
}
1
2
3
4
5
6

这里还要补充的一点就是关于const迭代器的事项，如果我们没有定义实现const迭代器，那我们直接使用范围for是会报错的：

原因就在于我们这里传的是一个const对象，而我们这里只实现了非const的迭代器，const对象是不能调用非const函数的。
想要解决这个问题我们就要把const迭代器实现了：

然后在实现const迭代器版本的begin和end：

这样我们的代码才能正确运行：

5.2、流提取运算符重载

流提取就相当于C语言中的scanf函数和C++中的cin运算符：

想要重载这个操作符我们在正式接收数据的时候需要先将原字符串内的数据清空：

// 清理数据
void clear() {
	_size = 0;
}
1
2
3
4

然后在接收数据插入字符串。

然后我们就可以动手写代码了：

// 流提取运算符重载
istream& operator>>(istream& _cin, String& str) {
	// 先清理数据
	str.clear();
	char ch = _cin.get();
	while (ch != ' ' && ch != '\n') {
		str += ch;
		ch = _cin.get();
	}
	return _cin;
}
1
2
3
4
5
6
7
8
9
10
11

这里还需要注意的一点就是，像scanf和cin都是默认以空格和换行符为多个字符的分隔的，也就是说他们不会接收空格和换行符。所以要想接收到空格和换行符不能直接用cin，而是要使用cin.get()。