---

一、经典的string类问题

针对string的一些补充:

    string s1("hello world");
    cin >> s1;
    cout << s1;
    // 这里cin后会将新输入的字符串追加在hello world后面，而非把它替换掉
1
2
3
4

我们来实现string类，最主要是实现string类的构造、拷贝构造、赋值运算符重载以及析构函数：

---

1.1 浅拷贝

namespace zmm
{
	// 标准库也有一个string，为了防止冲突，放在zmm命名空间
	class string
	{
	private:
		char* _str;

	public:
		// 拷贝构造不是调用的构造函数！！！
		string(const char* str) // 构造函数
			//:_str(str) // 不能这样子初始化，不然无法扩容等操作
			:_str(new char[strlen(str) + 1])
		{
			strcpy(_str, str);
		}
		~string() // 析构函数
		{
			delete[] _str;
		}
	};
	void test_string1()
	{
		string s1("hello world"); // 一般使用常量字符串初始化
		// 要让他扩容等操作——堆上
		string s2(s1); // 对于自定义类型默认浅拷贝 s1，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

此时没有默认的拷贝构造，对于自定义类型，系统自动生成的拷贝构造是浅拷贝，此时s1与s2指向同一个空间
s1上new的空间有一个字符串hello world

因此只想让他们内容一样，但是指向的空间不一样，这里就涉及到了深浅拷贝
因此要实现深拷贝——更深层次的拷贝，只拷贝指向的空间

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

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

浅拷贝的问题：
1、析构两次
2、其中一个对象进行修改会影响另外一个（因为指向了同一块空间）
解决浅拷贝的问题：
1、深拷贝——会付出代价进行拷贝
2、引用计数的写时拷贝（写的时候在进行深拷贝但是析构不会析构两次，用一个计数器，如果有两个指向该空间，就不进行析构，如果只有一个，在析构），这样子如果对象不修改就只是增加引用计数，不进行深拷贝，提高了效率，但是他也有一定的缺陷（1、存在线程安全的问题，需要加锁，在多线程环境下，要付出代价；2、在动态库和静态库中的某些场景也会存在一些问题）
1
2
3
4
5
6

---

1.2 深拷贝

1.2.1 深拷贝传统写法

深拷贝：每个对象独立分配资源，保证多个对象之间不会因为共享资源而造成多次释放造成程序崩溃的问题

namespace zmm
{
	// 标准库也有一个string，为了防止冲突，放在zmm命名空间
	class string
	{
	private:
		char* _str;

	public:
		string(const char* str) // 构造函数
			//:_str(str) // 不能这样子初始化，不然无法扩容等操作
			:_str(new char[strlen(str) + 1])
		{
			strcpy(_str, str);
		}
		string(const string& str) // 拷贝构造
			:_str(new char[strlen(str._str) + 1]) // 开一个一样大的空间
		{
			strcpy(_str, str._str);
		}
		~string()
		{
			delete[] _str;
		}
	};
	void test_string1()
	{
		string s1("hello world"); // 一般使用常量字符串初始化
		// 要让他扩容等操作——堆上
		string s2(s1); // 对于自定义类型默认浅拷贝 s1，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

此时两者空间就不一样了，就实现了深拷贝

1.2.2 赋值运算符重载传统写法

s1 = s3
s1与s3都有空间，还需不需要像之前一样开空间？——需要
这里涉及两个问题，如果是小拷大，可能空间会浪费很多，用不完；如果是大拷小，可能空间不够
因此我们就把原本的空间(s1)释放掉，然后开一个与他相等的空间(s3)，在将数据拷贝过去

string& operator=(const string& s)
{
	// delete[] this->_str; 与下面写法一样
	delete[] _str;
	_str = new char[strlen(s._str) + 1];
	strcpy(_str, s._str);
	return *this;
}
1
2
3
4
5
6
7
8

但是这段代码还是存在些小的问题，比如如果是s3 = s3，自己给自己赋值就会出现问题，这时候他们两个都是同一个空间，先释放掉，然后strlen就出现了问题，因此还要进行一些优化

// s1 = s3
string& operator=(const string& s)
{
	if (this != &s)
	{
		// delete[] this->_str; 与下面写法一样
		delete[] _str;
		_str = new char[strlen(s._str) + 1];
		strcpy(_str, s._str);
		return *this;
	}

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

但是此时还是有一些小问题：
如果new失败了怎么办？——此时没有讲抛异常所以先不管
new失败了，在new之前还把s1空间释放掉了，防止这种情况所以要先开空间

string& operator=(const string& s)
{
	if (this != &s)
	{
		/*
		// delete[] this->_str; 与下面写法一样
		delete[] _str;
		_str = new char[strlen(s._str) + 1]; // new失败抛异常
		// 如果开失败了，之前也delete了，有些不好，所以进行优化
		strcpy(_str, s._str);
		return *this;
		*/
		char* tmp = new char[strlen(s._str) + 1];
		// 如果开失败了，直接跳转到异常，就不会进行释放了
		strcpy(tmp, s._str);
		delete[] _str;
		_str = tmp;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

1.2.3 深拷贝现代写法

在这里我们实现简单的string类，不考虑增删查改，不考虑size，capacity

// 深拷贝现代写法
// s2(s1)  _str是s2，
string(const string& s)
:_str(nullptr) // 不加会崩溃
{
	string tmp(s._str); // 构造函数构造一个tmp
	swap(_str, tmp._str);
}
1
2
3
4
5
6
7
8

如果没有 :_str(nullptr)，则 此时交换后，tmp指向了随机值，tmp是临时变量，出了作用域要调用析构函数，就会崩溃，所以就让他指向空，而非是随机值
delete 空不会报错
也可以修改析构函数，保证为空不释放

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

1.2.4 赋值运算符重载现代写法

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

再进行优化

// s1 = s3
string& operator=(string s) // s就是s3的拷贝，实际上就相当于是tmp（调用了拷贝构造）
{
	swap(_str, s._str);
	return *this;
}
1
2
3
4
5
6

为什么这里不去判断自己给自己赋值这种情况了？因为这种情况没办法判断
在这里不判断也不会有特别大的问题

---

二、增删查改

2.1 增加成员变量与修改成员函数

为了实现此功能，增加两个私有成员

private:
	char* _str;
	size_t _size;
	size_t _capacity; // 有效字符的空间数，不算\0
1
2
3
4

于是就将刚刚写过的函数全部更改：

class string
{
public:
	string(const char* str)
		//:_str(str) // 不能这样子
		:_size(strlen(str))
		, _capacity(_size)
		// 如果capacity算\0，扩容条件是_size == _capacity
		// 如果不算，扩容条件是_size + 1 == _capacity
	{
		_str = new char[_capacity + 1];
		strcpy(_str, str);
	}
	// s2(s1)
	string(const string& s)
		// :_str(new char[strlen(s._str) + 1])
		:_size(s._size)
		, _capacity(s._capacity)
	{
		_str = new char[_capacity + 1];
		strcpy(_str, s._str);
	}
	~string()
	{
		delete[] _str;
		_str = nullptr;
		_capacity = _size = 0;
	}
	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;
	}

private:
	char* _str;
	size_t _size;
	size_t _capacity; // 有效字符的空间数，不算\0，也可以算\0看自己怎么实现
};
void test_string1()
{
	string s1("hello world");
	string s2(s1); // 默认生成的是浅拷贝
	string s3("sort");
	s1 = s3; // 默认生成的也是浅拷贝
}

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

这时候如果使用string s4; 不带参数，要提供一个全缺省的构造函数，所以我们继续补充一个不带参数的构造函数（如下），这样子写是否正确？

string() // 如果不传参数
	:_str(nullptr)
{

}
1
2
3
4
5

不能这样子写，不能给他赋空

// 若有此函数，遇到\0才截止，但是默认构造函数是空，所以会崩溃
const char* c_str() const
{
	return _str;
}
cout << s4.c_str() << endl;
1
2
3
4
5
6

改造为：

string() // 如果不传参数
			// :_str(nullptr) 不能这样子，如果返回c_str要遇到\0才截止
	:_str(new char[1])
	, _size(0)
	, _capacity(0) // 虽然有一个空间，但是他不是有效字符
{
	_str[0] = '\0';
}
1
2
3
4
5
6
7
8

在进行优化——将有参构造函数改造为全缺省，所以就去掉上述代码，改为下文所示：

// 缺省值给多少？——不能给空，不然会崩。strlen（空指针）会崩溃掉
string(const char* str = "") // 如果写“\0”就是第一个和第二个字符都是\0
	//:_str(str) // 不能这样子
	:_size(strlen(str))
	,_capacity(_size)
	// 如果capacity算\0，扩容条件是_size == _capacity
	// 如果不算，扩容条件是_size + 1 == _capacity
	{
		_str = new char[_capacity + 1];
		strcpy(_str, str);
	}
1
2
3
4
5
6
7
8
9
10
11

为了方便遍历，增加函数：

size_t size() const
{
	return _size;
}
1
2
3
4

2.2 operator[]

char& operator[](size_t pos)
{
	// at是抛异常，他是直接断言
	assert(pos < _size);
	return _str[pos];
}
// 若是const对象调用，则需要在提供一个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

2.3 迭代器的实现

typedef char* iterator;
typedef const char* const_iterator;
const_iterator begin() const
{
	return _str;
}
const_iterator end() const
{
	return _str + _size;
}
iterator begin()
{
	return _str;
}
iterator end()
{
	return _str + _size;
}
void test_string2()
{
	string s1 = "hello world";
	string::iterator it = s1.begin();
	while (it != s1.end())
	{
		*it += 1;
		it++;
	}
	it = s1.begin();
	while (it != s1.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
	// 范围for被编译后就被替换为了迭代器
	for (auto e : s1) // 去找begin，end那些
	{
		cout << e << " ";
	}
	cout << 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

2.4 swap（）的两种调用方式对比

std::string s1("hello world");
std::string s2("11111");
// 调用swap的两种方式
s1.swap(s2); // string中提供的swap
swap(s1, s2); // 全局库提供的swap——代价大，不推荐使用
1
2
3
4
5

库里面自带的swap函数说明：

template <class T> 
void swap ( T& a, T& b )
{
  T c(a); a=b; b=c;
}
1
2
3
4
5

第一种的swap效率高——因为仅仅是针对成员变量进行交换
第二种的代价很大，经历了三次string的深拷贝（s1，s2进行传参给a和b，之后要创建临时对象c，用s1去拷贝构造一个临时对象c，再把b赋值给a，再把c给b）

2.5 reserve()实现

当我们去实现append和push_back接口的时候，若空间不够，需要对原先空间进行扩容，则扩容的操作为：

// 改变容量
void reserve(size_t n) // n是容量，有效字符，不包含\0
{
	if (n > _capacity)
	{
		char* tmp = new char[n + 1]; // tmp是内置类型，不会去调用析构函数，所以不会造成一个空间会被两次释放
		strcpy(tmp, _str);
		delete[] _str;
		_str = tmp;
		_capacity = n;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

2.6 push_back()实现

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

在实现insert接口函数后，可以修改push_back

void push_back(char ch)
{
	insert(_size, ch);
}
1
2
3
4

2.7 append()实现

void append(const char* str)
{
	size_t len = strlen(str);
	if (_size + len > _capacity)
	{
		reserve(_size + len);
	}
	strcpy(_str + _size, str); // 从原先\0的位置开始拷贝
}
1
2
3
4
5
6
7
8
9

在实现insert接口函数后，可以修改append()

void push_back(char ch)
{
	insert(_size, str);
}
1
2
3
4

2.8 operator+=(char ch)实现

string& operator+=(char ch)
{
	push_back(ch);
	return *this;
}
1
2
3
4
5

2.9 operator+=(const char* str)实现

string& operator+=(const char* str)
{
	append(str);
	return *this;
}
1
2
3
4
5

2.10 resize()实现

resize的三种情况

resize给的n比原先字符串长度小，只会减小size，不会减小capacity

void resize(size_t n, char ch = '\0')
{
	if (n <= _size) // 若n小于size
	{
		_size = n;
		_str[_size] = '\0';
	}
	else
	{
		if (_capacity < n)
		{
			reserve(n);
		}
		// 从_str+_size位置开始填写数据，填写ch，有n-_size个
		memset(_str + _size, ch, n - _size);
		_size = n;
		_str[_size] = '\0';
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2.11 find()实现

查找字符

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

查找子串

size_t find(const char* s, size_t pos = 0)
{
	const char* ptr = strstr(_str + pos, s); // 从pos位置开始查找
	if (ptr == nullptr) // 若没有找到
	{
		return npos;
	}
	// 找到了是返回该位置的指针->通过该指针计算出下标
	else
	{
		return ptr - _str;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2.12 insert()实现

插入字符

		string& insert(size_t pos, char ch)
		{
			assert(pos <= _size);
			if (_size == _capacity)
			{
				reserve(_capacity == 0 ? 4 : _capacity * 2);
			}
			// 从最后一个位置开始依次往右边移动
			size_t end = _size; // 从size位置开始挪动，size本身就是\0，所以最后不需要添加\0
			while (end > pos) 
			{
				_str[end + 1] = _str[end];
				--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

上述代码还是存在一些问题，比如pos为0，就相当于是头插，当–end到0了以后，0>=0，继续–end为-1，但是end是size_t 类型就是无穷大了
如果把end改为int类型依然会发生越界，因为pos还是size_t类型，与int比较，int会转换为size_t类型（往大的转），虽然这里可以把pos转化为int类型，但是这种做法并不是很好
因此在这里我们把end改为size+1的位置，这时候end就只有＞pos了

string& insert(size_t pos, char ch)
{
	assert(pos <= _size);
	if (_size == _capacity)
	{
		reserve(_capacity == 0 ? 4 : _capacity * 2);
	}
	// 从最后一个位置开始依次往右边移动
	size_t end = _size + 1; // 从size位置开始挪动，size本身就是\0，所以最后不需要添加\0
	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

插入字符串

string& insert(size_t pos, const char* s)
{
	assert(pos <= _size);
	size_t len = strlen(s);
	if (_size + len > _capacity)
	{
		reserve(_size + len);
	}

	size_t end = _size + len;
	while (end >= pos + len) 
	{
		_str[end] = _str[end - len];
		--end;
	}
	_size += len;
	// 这里不能使用strcpy拷贝（会拷贝\0过去）
	strncpy(_str + pos, s, len);
	return *this;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2.13 erase()实现

要删除，必须是要pos < _size 位置开始删除

// 从pos位置开始删除len个长度
string& erase(size_t pos = 0, size_t len = npos)
{
	assert(pos < _size);
	if (len == npos || pos + len >= _size)
	{
		// 要删完的情况
		_str[pos] = '\0';
		_size = pos; // 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
17

三、运算符重载

3.1 各种关系符的实现

// 放在类里面可以使用strcmp改为全局就没办法去使用了——没办法访问私有
bool operator<(const string& s) const
{
	return strcmp(_str, s._str) < 0;
}
1
2
3
4
5

// 重载为全局的
bool operator<(const string& s1, const string& s2)
{
	size_t i1 = 0, i2 = 0;
	while (i1 < s1.size() && i2 < s2.size())
	{
		if (s1[i1] < s2[i2])
		{
			return true;
		}
		else if (s1[i1] > s2[i2])
		{
			return false;
		}
		else
		{
			++i1;
			++i2;
		}
	}
	return i2 < s2.size() ? true : false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

	bool operator<(const string& s1, const string& s2) // 这里使用的是const，因此下面使用的c_str也必须后面加const
	{
		return strcmp(s1.c_str(), s2.c_str()) < 0;
	}
	bool operator==(const string& s1, const string& s2)
	{
		return strcmp(s1.c_str(), s2.c_str()) == 0;
	}
	bool operator<=(const string& s1, const string& s2)
	{
		return s1 < s2 || s2 == s2;
	}
	bool operator>(const string& s1, const string& s2)
	{
		return !(s1 <= s2);
	}
	bool operator>=(const string& s1, const string& s2)
	{
		return !(s1 < s2);
	}
	bool operator!=(const string& s1, const string& s2)
	{
		return !(s1 == 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

3.2 流插入与流提取

ostream& operator<<(ostream& out, const string& s) // out支持输出内置类型
{
	// 方式1
	for (auto ch : s)
	{
		out << ch;
	}
	// 不能使用这种方式，因为不符合规范
	// out << s.c_str(); // 这种输出形式不是因为size为多少，就输出多少字符，而是遇到\0就停止
	// 方式2
	/*for (size_t i = 0; i < s.size(); ++i) // 因为这里使用了size（）接口函数，所以可以不用更改为友元，所以重载流插入和流提取不一定非要去使用友元，要用友元是要看有没有去直接访问私有——尽量少用友元
	{
		out << s[i];
	}*/
	return out;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

为什么不能使用out << s.c_str();因为遇到\0就停止了，而for循环是把size内的字符全部输出
如下这种情况，两者就会有很大的区别：

string s1("hello");
s1 += '\0';
s1 += 'world';
1
2
3

'\0’在打印出来可能是其他各种字符——可能与编译器显示问题有关

istream& operator>>(istream& in, string& s) // 这里不能去使用const了,字符串s自带\0
{
	// 获取每个字符的方式：get()获取一个字符
	char ch = in.get();
	while (ch != ' ' && ch != '\n') // 遇到换行才结束，遇到空格不结束，相当于是getline
	{
		s += ch;
		ch = in.get();
	}
	return in;
}
1
2
3
4
5
6
7
8
9
10
11