[C++知识库]【C++】STL — string的使用 + 模拟实现

📖前言

🎬STL简介：

（1）什么是STL：

STL是（standard template libaray-标准模板库）的首字母缩写，是C++标准库的重要组成部分，不仅是一个可复用的组件库，而且是一个包罗数据结构与算法的软件框架。

（2）STL的版本：

• 原始版本：
• P.J. 版本：
  由P. J. Plauger开发，继承自HP版本，被Windows Visual C++采用，不能公开或修改，缺陷：可读性比较低，符号命名比较怪异。
• RW版本：
• SGR版本：
  由Silicon Graphics Computer Systems，Inc公司开发，继承自HP版 本。被GCC(Linux)采用，可移植性好，可公开、修改甚至贩卖，从命名风格和编程 风格上看，阅读性非常高。

我们后面学习STL要阅读部分源代码，主要参考的就是这个版本。

虽然每个版本整体大致相同，但是有些细节处理还是不尽相同的，所以会出现同一段代码在不同平台上跑出来的结果是不同的，有可能在Linux平台上能跑过，在Windows平台上会崩溃的情况。

（3）STL的六大组件：

• 空间配置器
• 迭代器
• 配接器
• 容器
• 仿函数
• 算法
  

后期我们会慢慢介绍这六个组件。

我们主要的任务是：学会使用 + 了解框架 + 模拟实现。

1. string的使用

string是类模板，string是被typedef出来的，比STL产生的早，遵循STL的那一套。

• 使用string的时候，要包含头文件 #include< string >
• 由于string这个类中有上百个成员函数的接口，我们要会用其中比较常见的接口，其余不熟悉的我们要学会自己查文档，自主学习的能力很重要，一般看了成员函数参数和下面的介绍就差不多了
• string的学习文档：👉传送门

1.1 初始化子字符串：

string是管理动态增长字符数组，这个字符串以\0结尾。

void test_string1()
{
	//string是属于std这个标准库的命名空间
	//std::string s;
	char str[10];

	string s1;//只有一个\0
	string s2("hello world");
	s2 += "!!!";
	//cout << s2 << endl;

	//已存在的对象去初始化未存在的对象，都是拷贝构造
	string s3(s2);
	string s4 = s2;
	string s5("");//空字符串和string s1;一样的

	//用前四个初始化
	string s6("https://cplusplus.com/reference/string/string/string/", 4);

	//重载了流插入
	cout << s1 << endl;
	cout << s2 << endl;
	cout << s3 << endl;
	cout << s4 << endl;
	cout << s5 << endl;
	cout << s6 << endl;

	//用10个x初始化
	string s7(10, 'x');
	cout << s7 << endl;

	string s8(s2, 6, 3);
	cout << s8 << endl;

	string s9(s2, 6, 100);
	cout << s9 << endl;

	string s10(s2, 6);
	//npos的作用，如果不给最后一个参数，就相当于给npos，
	//那就从pos位置向后取42亿9千万个字符，正常字符串没有这么长
	//默认是有多少取多少
	cout << s10 << endl;
}

• string是属于std这个标准库的命名空间
• std::string s

• 增长字符串：
• string中增长字符串，直接用+号即可，运算符重载，具体的实现被封装在了string类成员函数当中。
• 字符串的初始化：
• 用前四个初始化： string s6(“https://cplusplus.com/reference/string/string/string/”, 4);
• 用指定的字符串指定位置指定个数初始化： string s8(s2, 6, 3); 从s2字符串第六个字符开始，取三个字符初始化s8字符串。
• 特殊情况（npos介绍）：
  （1）当string s9(s2, 6, 100);中第三个参数超出s2的字符长度的时候，默认是取到这个字符串的末尾结束为止。
  （2）当第三个参数没有的时候，默认第三个参数为npo，默认值是-1， 但是类型是size_t的，二进制全为1，所以为非常大的一个数，那就从pos位置向后取42亿9千万个字符，正常字符串没有这么长，默认是有多少取多少。

• 赋值重载：

直接见代码：

void test_string2()
{
	string s1("hello");
	string s2("xxx");

	s1 = s2;
	s1 = "yyy";
	s1 = 'y';
}

1.2 遍历字符串string的每一个字符：

遍历字符串有三种方法：

• 第一种方式，下标 + [] – []是C++重载的运算符。
• 第二种方式，迭代器 – 迭代器是用来访问数据结构的。
• 第三种方式，范围for – 前提是：C++11才支持的语法。

void test_string3()
{
	//遍历string的每一个字符
	string s1("hello");
	cout << s1[0] << endl;
	s1[0] = 'x';
	cout << s1.size() << endl;

	//遍历一共有三种方式

//·第一种方式，下标 + []  -- []是C++重载的运算符：

	//size就是返回它有多少个字符，是不包含\0的
	for (size_t i = 0; i < s1.size(); i++)
	{
		//s1.operator[](i);相当于调用这个函数
		cout << s1[i] << " ";//[]相当于函数调用
	}
	cout << endl;

	//编译器是看类型的，下面的运用和上面的类中调用成员函数完全不同
	//const char* s2 = "world";
	//s2[i];//*(s2 + i)

//·第二种方式，迭代器   --   迭代器是用来访问数据结构的：

	//sting::iterator是个类型，用这个类型可以定义一个对象

	string::iterator it = s1.begin();//或者叫iter
	//begin是指向第一个位置
	//end不是结束位置，而是最后一个位置的下一个位置
	//如果end是最后一个位置的下一个的话就会访问不到最后一个位置
	//[    ) -- 左闭右开的结构 -- 方便遍历

	//写成小于 < 也是可以的，但是不建议，标准的地方就是写的不等于 != 
	//统一用不等于 != 
	while (it != s1.end()) 
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;

	//现阶段理解的迭代器：像指针一样的东西或者就是指针

//·第三种方式，范围for  --  前提是：C++11才支持的语法
    //范围for的原理：替换成迭代器
	//自动取元素，赋值给ch，自动判断结束，自动++
	for (auto ch : s1)
	{
		cout << ch << " ";
	}
	cout << endl;
}

• 用下标是类中封装了运算符重载这个成员函数，直接调用即可
• sting::iterator是个类型，用这个类型可以定义一个对象

现阶段理解的迭代器：像指针一样的东西或者就是指针。

• begin是指向第一个位置
• end不是结束位置，而是最后一个数据的下一个位置
• 如果end不是最后一个数据的下一个位置的话，循环条件中就会访问不到最后一个位置
• [ ) – 左闭右开的结构 – 方便遍历

范围for：

• 范围for又叫语法糖，因为它用起来很舒服很好用，省略了大量的代码
• 其实在底层编译器替代成了迭代器，只是上层个看起来厉害
• 大家可以通过看汇编代码来看底层实现的逻辑
• 范围for和迭代器底层并没有太大差异

1.3 迭代器：

四种迭代器分类：

• 第一种，普通的正向迭代器：
• 第二种，反向迭代器：
• 第三种，正向迭代器，能读不能写
• 第四种，反向迭代器，能读不能写

//不改变就加const保护
//普通迭代器是可读可写的
void Func(const string& rs)
{
//第三种，正向迭代器，能读不能写
	string::const_iterator it = rs.begin();
	while (it != rs.end())
	{
		//(*it) += 1;
		cout << *it << " ";
		it++;
	}
	cout << endl;

//第四种，反向迭代器，能读不能写
	//string::const_reverse_iterator rit = rs.rbegin();
	//auto自动推导：
	auto rit = rs.rbegin();
	while (rit != rs.rend())
	{
		//(*rit) -= 1;
		cout << *rit << " ";
		rit++;
	}
	cout << endl;
}

//四种迭代器：
void test_string5()
{
//第一种，普通的正向迭代器：
	string s("hello world");
	string::iterator it = s.begin();
	while (it != s.end())
	{
		(*it) += 1;
		cout << *it << " ";
		it++;
	}
	cout << endl;
	cout << s << endl;

//第二种，反向迭代器：
	string::reverse_iterator rit = s.rbegin();
	while (rit != s.rend())
	{
		(*rit) -= 1;
		cout << *rit << " ";
		rit++;
	}
	cout << endl;
	cout << s << endl;

	Func(s);

}
//iterator是终极方式，[] + 下标，是附带方式

以我们目前的理解方式，迭代器是个指针。

正向迭代器：

反向迭代器（rbegin）：

• 普通的迭代器是可读可写的
• 要是不想string的内容不被修改
• 可以用const_iterator 或者 const_reverse_iterator类型的反向迭代

如果迭代器类型太长的话，可以用之前学过的auto直接根据对象类型直接推导出来。

• string::const_reverse_iterator rit = rs.rbegin();
• auto自动推导：auto rit = rs.rbegin();

1.4 string的内存管理：

string的容量大小：
string的长度，既可以用length()，也可以用size();

void test_string6()
{
	string s("hello world");
	//length产生的比size早
	cout << s.length() << endl;
	cout << s.size() << endl;
	cout << s.max_size() << endl;
	//容量要扩容
	cout << s.capacity() << endl;
}

因为length产生的比size早，string产生的比STL早，所以兼容STL中的size()。

扩容的规律：

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

由此可见VS平台下是1.5倍扩容。

补充：Linux下是2倍的扩容。

reserve/resize/clear的使用：

void test_string7()
{
	
	// 注意：string类对象支持直接用cin和cout进行输入和输出
	string s("hello world!!!");
	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;

}

• resever只是开空间，而resize是开空间 + 初始化
• s.resize(10, ‘a’);将s中有效字符个数增加到10个，多出位置用’a’进行填充
• s.resize(15);将s中有效字符个数增加到15个，多出位置用缺省值’\0’进行填充
• 将s中的字符串清空，注意清空时只是将size清0，不改变底层空间的大小

reserve和resize都不会缩容量capacity，但是resize会让size降下来，只留size个。

push_back 和 erase和之前数据结构一样，使用起来直接调用该成员函数即可：


insert的其他用法：

直接见代码：

void test_string9()
{
	//运算符重载
	string s("hello");
	
	//string底层的迭代器就是指针
	s.insert(3, 1, 'x');
	s.insert(s.begin() + 3, 'y');
	//插入就要挪动数据
	cout << s << endl;

	s.insert(0, "sort");
	cout << s << endl;
	//底层是要挪动数据的，空间不够要扩容
}

在指定位置前面插入字符或字符串。

string获取子字符串，解析网址为例，直接见下述代码：

//解析网址:
void test_string4()
{
	// 取出url中的域名，url是网址
	string url1("http://www.cplusplus.com/reference/string/string/find/");
	string url2("https://blog.csdn.net/m0_63059866?spm=1000.2115.3001.5343");

	//解析别的网址的时候避免下面全都要换：
	string& url = url2;

	//协议 域名 uri

//找协议：
	string protocol;
	size_t pos1 = url.find("://");

	//没有匹配到返回npos
	if (pos1 != string::npos)
	{
		//子串的起始位置是前面数据的个数
		protocol = url.substr(0, pos1);//这里的pos1是协议的长度
		cout << "protocol:" << protocol << endl;
	}
	else
	{
		cout << "非法的url" << endl;
	}

//找域名:
	string domain;
	size_t pos2 = url1.find('/', pos1 + 3);

	//指定位置找，从pos1后第三个找，直到找到'/'
	if (pos2 != string::npos)
	{
		domain = url.substr(pos1 + 3, pos2 - (pos1 + 3));
		cout << "domain:" << domain << endl;
	}
	else
	{
		cout << "非法url" << endl;
	}

	string uri = url.substr(pos2 + 1);
	cout << "uri:" << uri << endl;
}

2. string模拟实现

2.1 深拷贝：

浅拷贝的问题：

如果是栈的类，普通的浅拷贝（按字节拷贝），会出现问题，两个栈的str指针指向同一个地方，两个栈相互影响，我们并不希望这样，所以我们要学习一下深拷贝。

浅拷贝的效果：

深拷贝的效果：

2.2 具体代码实现（string.h）：

#pragma once

#include<iostream>
#include<assert.h>
#include<string>

using namespace std;

//class mystring
//class String

//自己实现的封装在命名空间中防止冲突
namespace YY
{
	//实现一个简单的string，只考虑资源管理深浅拷贝的问题
	//暂且不考虑增删查改

	//string需要考虑完善的增删查改和使用的string
	class string
	{
	public:
		//const对象遍历访问是不可以被修改的，应该实现两种
		//两种迭代器的参数不同，函数重载
		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;
		}

		//无参的构造函数
		/*string()
			:_size(0)
			,_capacity(0)
		{
			_str = new char[1];
			_str[0] = '\0';
		}*/

		//全缺省
		//1、"\0"这是有两个\0  
		//2、""这是有一个\0  
		//3、'\0'这里是把\0的assic码值0给了指针，实际是空指针
		string(const char* str = "")     //""是C语言默认常量字符串，后面有\0
			:_size(strlen(str))          //strlen()是不会判空指针的
			, _capacity(_size)

		{
			_str = new char[_capacity + 1];//给'\0'多开一个
			strcpy(_str, str);
		}

//·构造函数：
//·传统的写法：本分，老实，老老实实干活，该开空间开空间，该拷贝数据就自己拷贝数据
		//s2(s1); - 深拷贝
		//在类里面只要用string对象访问成员都是不受限制的
		//私有是限制在类外面使用对象去访问成员
		/*string(const string& s)
			:_size(strlen(s._str))
			, _capacity(_size)
		{
			_str = new char[_capacity + 1];
			strcpy(_str, s._str);
		}*/

//·现代写法：剥削，要完成深拷贝，自己不想干活，安排别人干活，然后窃取劳动成果
		//要初始化一下，不然有可能释放野指针
		string(const string& s)
			:_str(nullptr)
			,_size(0)
			,_capacity(0)
		{
			string tmp(s._str);
			swap(tmp);
		}


//赋值重载：
//传统写法：
		//s1 = s3，如果不传引用返回，用传值返的话会深拷贝，代价太大了
		//new失败了之后会抛异常，用try捕获
		//string& operator = (const string& s)
		//{
		//	if (this != &s)
		//	{
		//		//1、先释放：如果s1开空间失败了，之前的空间也被释放了
		//			/*delete[] _str;
		//			_str = new char[strlen(s._str) + 1];
		//			strcpy(_str, s._str);*/

		//		//2、先开空间：下面写法可以避免上述问题
		//		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);
				swap(tmp);
			}
			return *this;
		}*/

//现代方法二：-- 更简单，一行代码搞定，适用于所有深拷贝
		//s 就是 s1的深拷贝，先传参，传参就是拷贝构造
		string& operator=(string s)
		{
			swap(s);
			return *this;
		}

构造函数的现代写法：

• 先实例一个string类型的tmp对象：直接根据传来的指针实例化一个所需一样的对象
• 再将tmp对象的内容和所要拷贝构造的对象的成员变量进行交换
• 在将这个拷贝函数结束之后，tmp对象的生命周期结束，自动调用其析构函数，释放掉空间

负值重载的现代写法：

• 赋值函数中，形参是string类型的对象，调用函数是值传参
• s对象已经是拷贝的对象了，直接将s对象和所需要拷贝的对象交换就好

注意：

• 要被拷贝构造的对象中的成员变量为随机值，所以里面的str成员指针是随机值
• 这个随机值换给tmp这个对象之后
• tmp对象生命周期结束后，自动调用析构函数，对野指针进行释放，就会出错，程序崩溃
• 所以拷贝构造一开始要在初始化类表中对要被拷贝的对象成员变量进行初始化

		~string()
		{
			if (_str != nullptr)
			{
				delete[] _str;
				_str = nullptr;
				_size = _capacity = 0;
			}
		}

		const char* c_str() const
		{
			return _str;
		}

		//普通对象调用这个
		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];
		}

这里用引用返回的原因：

• 如果是传值返回的话，返回的是临时对象，具有常性，要是相对其进行修改的话没救不行
• 传的是引用的话就没有这种问题

		//s.size(&s)
		//size_t size(cosnt string* const this)
		size_t size() const
		{
			return _size;
		}

		//加上const普通对象可以调用，const对象也可以调用
		//不加的话const对象调用会有权限放大的风险

		size_t capacity() const
		{
			return _capacity;
		}

		//扩容
		void reserve(size_t n)
		{
			if (n > _capacity)
			{
				char* tmp = new char[n + 1];
				strcpy(tmp, _str);
				delete[] _str;
				_str = tmp;

				_capacity = n;
			}
		}

这是注意的是，要先开所需要的空间再去拷贝之后再释放

• 因为如果先释放，当新空间空开失败了的时候
• 就会出现原来的空间也被释放了，原来的数据也找不到了

		//1、大于capacity
		//2、小于capacity，大于size
		//3、小于size
		//resize的作用
		//扩空间 + 初始化
		//删除部分数据，保留前n个
		void resize(size_t n, char ch = '\0')
		{
			if (n < _size)
			{
				_size = n;
				_str[_size] = '\0';
			}
			else
			{
				if (n > _capacity)
				{
					reserve(n);
				}

				for (size_t i = _size; i < n; i++)
				{
					_str[i] = ch;
				}
				_size = n;
				_str[_size] = '\0';
			}
		}

		//复用push_back
		string& operator+=(char ch)
		{
			push_back(ch);
			return *this;
		}

		//添加一个字符
		void push_back(char ch)
		{
			//if (_size == _capacity)
			//{
			//	reserve(_capacity == 0 ? 4 : _capacity * 2);
			//}

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

		//复用append
		string& operator+=(const char* str)
		{
			append(str);
			return *this;
		}

		//添加一个字符串
		void append(const char* str)
		{
			/*size_t len = _size + strlen(str);
			if (len > _capacity)
			{   
				reserve(len);
			}

			strcpy(_str + _size, str);
			_size = len;*/

			insert(_size, str);
		}

		string& insert(size_t pos, char ch)
		{
			assert(pos <= _size);

			if (_size == _capacity)
			{
				reserve(_capacity == 0 ? 4 : _capacity * 2);
			}  

			/*size_t end = _size;
			while (end >= 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 += 1;

			return *this;
		}

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

			//往后挪动len个位置
			size_t end = _size + len;
			//while(end >= pos + len) //-- 最好别这样写，怕别人给极端场景，pos，end都是0
			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
			{
				size_t begin = pos + len;
				while (begin <= _size)
				{
					_str[begin - len] = _str[begin];
					begin++;
				}

				_size -= len;
			}
			return *this;
		}

		size_t find(char ch, size_t pos = 0)
		{
			for (; pos < _size; pos++)
			{
				if (_str[pos] == ch)
				{
					return pos;
				}
			}
			return npos;
		}

		size_t find(const char* str, size_t pos = 0)
		{
			const char* p = strstr(_str + pos, str);
			//KMP，BM只做了解

			if (p == nullptr)
			{
				return npos;
			}
			else
			{
				return p - _str;
			}
		}

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

上述代码就是之前学过的数据结构 — 顺序表了

• 上述逻辑和之前C语言实现的逻辑并无二异
• 只使用C++这门语言写的，用了C++的语法

		//交换 -- 用库里的交换还要调用拷贝构造
		void swap(string& s)
		{
			//调用库里的 -- 库中的（类模板）是全局的，也可以写std
			::swap(_str, s._str);
			::swap(_size, s._size);
			::swap(_capacity, s._capacity);
		}

上述交换函数在现代写法的构造函数和赋值重载中用的到。

	private:
		char* _str;
		size_t _size;		//有效字符个数 -- 不包含'\0'
		size_t _capacity;	//存储有效字符的空间

		//const在static之前和之后都可以
		//const static size_t npos = -1;//确实可以这样，虽然这里是声明
		//静态不能给缺省值，强制要求在类外面定义

		const static size_t npos;
	};

	//定义
	const size_t string::npos = -1;

	//流插入
	ostream& operator<<(ostream& out, const string& s)
	{
		//中间有'\0'就不能将整个字符串打印完
		//out << s.c_str() << endl;
		
		//趋向于这样写 -- 这样能保证每个字符都能打印出来
		for (auto ch : s)
		{
			out << ch;
		}

		return out;
	}

	//流提取
	istream& operator>>(istream& in, string& s)
	{
		//方法一：
		//char ch;
		in >> ch;
		//ch = in.get();
		//while (ch != ' ' && ch != '\n')
		//{
		//	s += ch;
		//	//in >> ch;
		//	ch = in.get();
		//}

		//清理空间
		s.clear();
		char ch;
		ch = in.get();
		char buff[128] = { '\0' };
		size_t i = 0;
		while (ch != ' ' && ch != '\n')
		{
			buff[i++] = ch;
			if (i == 127)
			{
				s += buff;
				memset(buff, 0, sizeof(char) * 128);
				i = 0;
			}
			ch = in.get();
		}

		s += buff;
		return in;
	}

下述为运算符重载，多是复用：

	//运算符重载不一定是成员函数
	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 strcmp(s1.c_str(), s2.c_str()) == 0;
	}

	bool operator<=(const string& s1, const string& s2)
	{
		return s1 < s2 || s1 == 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);
	}
}

总结：

成员函数中层层调用、相互复用，封装在一个类当中，极大地考察了我们之前学的类和对象和C++各种语法，需要大家细心 + 谨慎。

但行好事莫问前程，欲戴皇冠必承其重，我们在路上，努力且不放弃……