【STL】深入理解 string 的底层思想

一、STL的定义

        STL是C++标准库的一部分它不仅是一个可复用的组件库还是一个包含数据结构和算法的软件框架。

二、STL的历史和版本

原始版本：

        Alexander Stepanov、Meng Lee在惠普实验室完成的原始版本，本着开源精神，他们声明允许任何人任意运用、拷贝、修改、传播、商业使用这些代码，无需付费。唯一的条件就是也需要向原始版本一样做开源使用。HP 版本--所有STL实现版本的始祖。

P.J.版本：

        由P.J.Plauger开发，继承自HP版本，被Windows Visual C++采用，不能公开或修改，缺陷：可读性比较低，符号命名比较怪异。

RW版本：

        由Rouge Wage公司开发，继承自HP版本，被C++Builder采用，不能公开或修改，可读性一般。

SGI版本：

        由Silicon Graphics Computer Systems,Inc公司开发,继承自HP版本。被GCC(Linux)采用,可移植性好，可公开、修改甚至贩卖，从命名风格和编程风格上看，阅读性非常高。

三、STL的六大组件

STL的六大组件：仿函数、空间配置器、算法、容器、迭代器、配接器。

四、STL的重要性

 1、笔试中不用自己写二叉树和栈、队列等等快速解答。

 2、帮助我们应对面试中HR的提问

 3、不懂STL不要说你会C++，STL在工作中可以帮助我们不要自己写数据结构和算法，让我们快速开发。

五、学习STL的方法

        《The C++ Standard Library》一书中把学习STL比喻成三个境界：熟用STL，了解STL的底层、扩展STL

六、string类

string类文档链接：string - C++ Reference 

        string是char类型的顺序表的类同时也STL的一种容器，使用string类的时候需要包含头文件和using namespace std;

        我们要想学习string类先了解它的构造函数和接口。

 1、string类的构造函数（string::string - C++ Reference）

注意：由于析构函数程序结束之后就自动调用所以我们不需要太关注析构函数。

       注意：我们只要掌握常见的几种构造就行：

  1.1、string()

代码示例：

#include<string>
#include<iostream>
using namespace std;

int main()
{
	string s1;//调用默认构造
	cout << s1 << endl;

	return 0;
}

注意：流插入和流提取已经在库里面重载了，我们直接用就行。 

运行结果：

 注意：从上面运行结果可以看出调用默认构造编译器啥也不干。

        1.2、string(const char* s)

代码示例1：

#include<string>
#include<iostream>
using namespace std;

int main()
{

	string s2("hello word");
	cout << s2 << endl;

	return 0;
}

运行结果：

 代码示例2：

#include<string>
#include<iostream>
using namespace std;

int main()
{

	//string s2("hello word");
	string s3 = "hello word";//隐式类型转换
	cout << s3 << endl;

	return 0;
}

运行结果：

         1.3、string(const string& str)

代码示例：

#include<string>
#include<iostream>
using namespace std;

int main()
{

	string s1("hello world");
	string s2(s1);//拷贝构造

	cout << s2 << endl;

	return 0;
}

运行结果：

        1.4、string(size_t n,char c) 

代码示例：

#include<string>
#include<iostream>
using namespace std;

int main()
{

	string s1("hello world");
	string s2(10,'I');//用10I来构造s2

	cout << s2 << endl;

	return 0;
}

运行结果：

 2、string的赋值重载（string::operator= - C++ Reference）

他们用法都差不多这里就不一一细讲。

代码示例：

#include<string>
#include<iostream>
using namespace std;

int main()
{

	string s3 = "HooL";

	cout << s3 << endl;

	return 0;
}

运行结果：

3、string的遍历和修改（https://legacy.cplusplus.com/reference/string/string/operator[]/）

3.1下标+[  ]遍历  

代码示例：

#include<string>
#include<iostream>
using namespace std;

int main()
{
	string s1("hello world");
	cout << s1 << endl;
	s1[0] = 'x';
	cout << s1 << endl;
	s1[1]++;
	cout << s1 << endl;

	return 0;
}

运行结果： 

#include<string>
#include<iostream>
using namespace std;

int main()
{
	string s1("hello world");
	for (int i = 0; i < 11; i++)
	{
		cout << s1[i];
	}

	return 0;
}

 运行结果：

小贴士：修改和遍历本质是运算符的重载。

注意：string的size是不包含\0，如：

#include<string>
#include<iostream>
using namespace std;

int main()
{
	string s1("hello world");
	cout << s1.size();

	return 0;
}

运行结果：

注意：string会对[ ]进行检查看它是否越界，如果越界会断言报错。如：

代码示例：

#include<string>
#include<iostream>
using namespace std;

int main()
{
	string s1("hello world");
	s1[12];
	return 0;
}

运行结果：

3.2、迭代器遍历和修改

        迭代器跟指针差不多，那么我们来看看怎么用迭代器来遍历string。

代码示例：

int main()
{
	string s1("hello world");
	string::iterator it = s1.begin();//begin指向第一个字符

	while (it != s1.end())//end指向\0字符
	{
		cout << *it ;
		it++;
	}


	return 0;
}

 运行结果：

int main()
{
	string s1("hello world");
	string::iterator it = s1.begin();//begin指向第一个字符

	while (it != s1.end())//end指向\0字符
	{
		*it = 'h';
		cout << *it ;
		it++;
	}


	return 0;
}

运行结果：

注意：下标+[  ] 和迭代器访问和修改的区别，下标+[  ] 是特定容器支持，二迭代器访问是容器的通用访问和修改方式。

3.3、范围for遍历

代码示例1：

int main()
{
	int i = 10;
	auto k = i;//根据i的类型推出k的类型，相当于：int k=i;
	auto j = &i;//相当于：int* j=&i;
	auto* a = &i;//相当于int* a=&i
	auto* b = i;//相当于：int* b=i;//编译报错

	auto c = i;//相当于：int& c=i;

	return 0;
}

代码示例2： 

auto Add(auto x, auto y)
{
	return x + y;
}

int main()
{
	int x = 1, y = 2;
	cout << Add(x, y);
	return 0;
}

运行结果：

注意：只有C++20以上的版本才支持这样写，atuo尽量少用。

代码示例3

int main()
{
	string s1("hello world");
	for (auto e : s1)//自动取容器的数据依次给对象，自动判断结束
	{
		cout << e;
	}
	return 0;
}

运行结果：

代码示例4：

int main()
{
	string s1("hello world");
	for (auto e : s1)//把s1的元素一一给e,e就是s1的拷贝，e的修改和不影响s1
	{
		e--;
		cout << e;
	}
	cout << endl;
	cout << s1;

	
	return 0;
}

 运行结果：

代码示例5：

int main()
{
	string s1("hello world");
	for (auto& e : s1)//如果想修改s1的值可以用引用
	{
		e--;
		cout << e;
	}
	cout << endl;
	cout << s1;

	
	return 0;
}

 运行结果：

 3.4、string迭代器介绍

这里只介绍 begin 和 end 因为后面的迭代器跟这两个差不多。

begin()和end()是个迭代器，迭代器我们理解为是一个指针。

 用法示例：

int main()
{
	string s("hello world");
	string::iterator it = s.begin();
	while (it != s.end())
	{
		cout << *it;//可以像指针那样访问
		it++;
	}

	return 0;
}

注意：begin()指向起始位置，end()指向\0

那么 rbegin() 和 rend() 的用法是：

int main()
{
	string s("hello world");
	string::reverse_iterator rit = s.rbegin();//rend（）指向第一个数据的前一个，rbegin()指向最后一个数据不包含\0
	while (rit != s.rend())
	{
		cout << *rit;//可以像指针那样访问
		rit++;//和正向迭代器不一样，反向迭代器++往左走
	}

	return 0;
}

int main()
{
	string s("hello world");//反向迭代器和正向迭代器的类型不一样
	string::reverse_iterator rit = s.rend();//rend（）指向第一个数据的前一个，rbegin()指向最后一个数据不包含\0
	rit--;
	while (rit != s.rbegin())//不能用小于大于或者小等大等
	{
		cout << *rit;//可以像指针那样访问
		rit--;//和正向迭代器不一样，反向迭代器++往左走
	}
	cout << *rit;
	return 0;
}

注意：一个对象被const修饰那么这个对象迭代器的类型就要改变

代码示例：

	const string s("abcd");
	string::const_iterator it = s.end();

那么反向迭代器也是一样，只要对象被const修饰。

3.5、string 的 capacity 介绍

 根据二八原则我们只要学习一下常用的就行。

1）size 和 length是一样的，但是由于 size 在其他容器也有所以这里推荐使用size。

用法：计算字符串的数据个数（不包含\0）

代码示例：

	const string s("abcd");
	cout << s.size();//打印结果是4

2）max_size介绍

        这个准确来说没什么意义，他是计算默认的最大的长度，不管这个字符串是长的还是短的。

代码示例：

	const string s("abcd");
	string s2("hello world");
	cout << s.max_size() << endl;
	cout << s2.max_size();

打印结果：

3）capacity介绍

        capacity是计算能存储的数据大小，即：容量；但是实际上容量会多一个来存储\0。

代码示例：

	const string s("abcd");
	string s2("hello world");
	cout << s.capacity() << endl;
	cout << s2.capacity();

 打印结果：

capacity是个默认值：15

4） clear 介绍

        clear就是把size置为0，容量不变。

代码示例：

	string s("abcd");
	cout << s.capacity() << endl;
	cout << s.size() << endl;

	s.clear();//把size变成0.容量不变

	cout << s.capacity() << endl;
	cout << s.size();

打印结果：

注意：字符串也没有了。

5）reserve 介绍

        在学习 reserve 之前我们先了解一下string的扩容机制。

代码示例：

	string s;
	int cap = s.capacity();
	cout << cap << endl;
	for (int i = 0; i < 200; i++)
	{
		s.push_back('x');//尾插数据
		if (cap != s.capacity())//判断扩容机制
		{
			cout << s.capacity() << endl;
			cap = s.capacity();
		}
	}

打印结果：

结论：VS除了第一次是2倍扩容，后面都是1.5倍扩容。不同普通平台的扩容倍数是不一样的；Linux是2倍扩容。

string的扩容机制是异地扩容，比如：size 为4，容量为15，它先在别的地方申请容量为31的空间，再把那4个数据复制过去然后再把原来的空间释放掉。

reserve 如果扩容的大小比capacity小，会不会缩容是不确定的（不建议用reserve进行缩容），看平台，对size不影响。

代码示例：

	string s;
	cout << s.capacity() << endl;

	s.reserve(100);
	cout << s.capacity() << endl;

	s.reserve(200);
	cout << s.capacity() << endl;

	s.reserve(100);
	cout << s.capacity() << endl;

打印结果：

 注意： 在VS下 reserve 扩容会比指定的值大，缩容有可能缩也可能不缩。

 6）resize 介绍

        resize有三种情况：size<n<capacity（插入数据）、n>capacity（扩容+插入数据）、n<size（删除数据）。

图片解疑：

注意：插入数据默认为\0

代码示例：

int main()
{
	string s("hello world");
	s.resize(20);//扩容后面默认是\0
	cout << s << endl;

	s.resize(5);//删除数据
	cout << s << endl;

	s.resize(20, 'Y');//扩容指定插入数据Y
	cout << s << endl;

	return 0;
}

 运行结果：

 3.5、string的修改和访问介绍

 1）[ ] 和 at 介绍

        [ ] 使得string像数组那样进行修改和访问。

代码示例：

	string s("hello world");
	for (int i = 0; i < s.size(); i++)
	{
		cout << s[i] << ' ';
	}
	cout << endl;

	for (int j = 0; j < s.size(); j++)
	{
		s[j]++;
	}
	cout << s << endl;

运行结果：

         at也可以对string进行访问和修改。

代码示例：

	string s("hello world");
	for (int i = 0; i < s.size(); i++)
	{
		cout << s.at(i) << ' ';
	}
	cout << endl;

	for (int j = 0; j < s.size(); j++)
	{
		s.at(j)++;
	}
	cout << s << endl;

运行结果和上面的一样。

        他们两个的区别在于越界检查，[ ] 对于越界处理是断言报错，at是抛异常。

代码示例：

	string s("hello world");
	s[15];

运行结果：

	string s("hello world");
	s.at(13);

 运行结果：

	string s("hello world");
	s.push_back('abc');
	cout << s;

注意：断言报错直接把程序终止了，很恶心，但是抛异常我们只要把异常捕获了久不会终止程序。

2）push_back介绍

        pushi_back就是尾插数据。

代码示例：

	string s("hello world");
	s.push_back('a');//只能尾插单个字符
	cout << s;

运行结果：

3）append介绍

        尾插字符串火车字符串对象。

代码示例：

	string s("hello world");
	s.append("abcd");
	cout << s << endl;

	string s2("cde");
	s.append(s2);
	cout << s << endl;

运行结果：

4）+=介绍

        它可以尾插字符串或者单个字符或者string对象。

代码示例：

	string s("hello world");
	s += "abcd";
	cout << s << endl;

	string s1("acd");
	s += s1;
	cout << s << endl;

	s += 'g';
	cout << s;

 运行结果：

注意：关于头插和头删string是不支持的，效率极低。但是有尾删 pop_back。

5）erase 介绍

        删除 string 指定位置的字符。

代码示例：

	string s("hello world");
	s.erase(0, 1);//删除下标为0的那一个字符
	cout << s;

 运行结果：

注意：这样的效率是极低的，因为删除了前面的数据，后面的数据要往前面移动。

6）replace介绍

         把字符串中的某一段替换成另一段字符串或者单个字符，如果把字符串中的单个字符替换成多个字符数据就要往后移动，效率极低。

代码示例：

	string s("hello world");
	s.replace(2, 1, "hhh");//从下标为2的字符串那里开始计算到长度为1的区间代替为“hhh”
	cout << s;

 运算结果：

 7）c_str 介绍

        返回一个字符串的指针，这个字符串包含\0。

代码示例：

	string s("string6_19.cpp");//当前文件名
	FILE* fout = fopen(s.c_str(), "r");//打开当前文件，s.c_str()相当于string6_19.cpp，它返回的是这个字符串的指针
	char ch = fgetc(fout);//获得当前的文件的一个字符
	while (ch != EOF)
	{
		cout << ch;
		ch = fgetc(fout);
	}

运行结果：

3.6、find 和 substr 介绍

        find是寻找某个字符并且返回这个字符的下标；substr是取出从某个下标开始长度为len的字符串。

 代码示例：

	string s("hello world");
	string ret;
	size_t pos = s.find('w');//默认从下标为0开始找,没有找到返回npos，就是无符号整形的最大值42亿9千万
	if (pos != string::npos)//就是找到了
	{
		ret = s.substr(pos);//取出w后面(包含w)的字符串
	}
	cout << ret;

运行结果：

注意：如果有多个w，想取出最后一个w就要倒着找，使用rfind来找。

代码示例：

	string s("hellow world");
	string ret;
	size_t pos = s.rfind('w');//默认从下标为0开始找,没有找到返回npos，就是无符号整形的最大值42亿9千万
	if (pos != string::npos)//就是找到了
	{
		ret = s.substr(pos);//取出w后面(包含w)的字符串
	}
	cout << ret;

运行结果和上面一样。

3.7、find_first_of 介绍

        find_first_of 是根据条件找到指定的字符。

代码示例：

	string s("hhh eee ooo ccc");
	size_t pos = s.find_first_of("hec");//根据条件（hec）从字符串找到包含这些条件的字符，返回它的下标
	while (pos != string::npos)
	{
		cout << s[pos] << endl;
		s[pos] = '*';//修改
		pos = s.find_first_of("hec",pos + 1);//从下个开始找
	}
	cout << s;

运行结果：

七、string类的底层模拟实现

代码示例 ：

//stringVR.h
#pragma once
#include<iostream>
#include<stdlib.h>
#include<string>
#include<assert.h>
using namespace std;
namespace LA
{
	//const size_t string::npos = -1;
	class string
	{
	public:
		//string()
		//	:_str(new char[1]{'\0'})
		//	, _size(0)
		//	,_capacity(0)
		//{

		//}
		//传统写法
		//string(string& s)
		//{
		//	_str = new char[s._capacity + 1];
		//	_size = s._size;
		//	_capacity = s._capacity;
		//	memcpy(_str, s._str,s._size+1);
		//}
		//现代写法
		string(const string& s)//浅拷贝问题：析构多次( 解决办法：引用计数（一个空间被多个对象指向记录指向个数） )，一个修改影响另一个（解决办法：写时拷贝就是深拷贝）
		{
			//引用计数的写时拷贝优势：赌博心态，赌它不会被修改，就不用开空间。最新版本：进行深拷贝
			//string tmp(s._str);//只要字符串中间没有\0，不然就会出错
			string tmp(s.begin(), s.end());
			swap(tmp);
		}
		//进一步写法
		template<class InputIterator>

		string(InputIterator first, InputIterator last)
		{
			while (first != last)
			{
				pushback(*first);
				first++;
			}
		}


		typedef char* iterator;//迭代器的模拟实现
		typedef const char* const_iterator;

		iterator begin()//指向第一个字符
		{
			return _str;
		}

		iterator end()
		{
			return _str + _size;//指向\0
		}

		const_iterator begin()const//指向第一个字符
		{
			return _str;
		}

		const_iterator end()const
		{
			return _str + _size;//指向\0
		}

		void reserve(size_t n);
		void pushback(char ch);
		void append(const char* str);
		string& operator+=(char ch);
		string& operator+=(const char* str);

		void insert(size_t pos, char ch);
		void insert(size_t pos,const char* str);
		void erase(size_t pos, size_t len = npos);

		size_t find(char ch, size_t pos = 0);
		size_t find(const char* str, size_t pos = 0);

		string substr(size_t pos = 0, size_t len = npos);

		string& operator=(const string& s);

		string(const char* str="")
			: _size(strlen(str))
		{
			_str = new char[_size + 1]; // +1是给\0也留了个位置
			_capacity=_size;
			memcpy(_str, str,_size+1);
		}

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

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

		size_t size()const;
		char& operator[](size_t i);
		const char& operator[](size_t i)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;

		void clear();
		void swap(string& s);


	private: 
		char* _str;
		size_t _size;//不包含\0
		size_t _capacity;//不包含\0
	public:
		static const size_t npos = -1;//特殊处理，只有static const int 才行
	};

	std::ostream& operator<<(std::ostream& os, const string& s);
	std::istream& operator>>(std::istream& is, string& s);

}

//stringVR.cpp
#define _CRT_SECURE_NO_WARNINGS 1
#include"stringVR.h"
namespace LA
{
	size_t string::size() const
	{
		return _size;
	}

	char& string::operator[](size_t i)
	{
		assert(i < _size);
		return _str[i];
	}

	const char& string::operator[](size_t i)const
	{
		assert(i < _size);
		return _str[i];
	}

	void string::reserve(size_t n)
	{
		if (n > _capacity)
		{
			char* tmp = new char[n + 1];
			if (_str)
			{
				memcpy(tmp, _str, _size + 1);
				delete[] _str;
			}
			_str = tmp;
			_capacity = n;
		}
	}


	void string::pushback(char ch)
	{
		if (_size == _capacity)
		{
			reserve(_capacity == 0 ? 4 : 2 * _capacity);
		}
		_str[_size++] = ch;
		_str[_size] = '\0';
	}

	void string::append(const char* str)
	{
		size_t len = strlen(str);
		if (_size + len > _capacity)
		{
			size_t newcapacity = _size + len > 2 * _capacity ? _size + len : 2 * _capacity;
			reserve(newcapacity);
		}
		memcpy(_str + _size, str, len + 1);
		_size += len;
	}

	string& string::operator+=(char ch)
	{
		pushback(ch);
		return *this;
	}

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

	void string::insert(size_t pos, char ch)
	{
		assert(pos <= _size);
		if (_size == _capacity)
		{
			reserve(_capacity == 0 ? 4 : 2 * _capacity);
		}
		size_t end = _size;
		while (end >= (int)pos)
		{
			_str[end + 1] = _str[end];
			end--;
		}
		_str[pos] = ch;
		_size++;
	}
	void string::insert(size_t pos, const char* str)
	{
		assert(pos<=_size);
		size_t len = strlen(str);
		if (_size + len > _capacity)
		{
			size_t newcapacity = _size + len > 2 * _capacity ? _size + len : 2 * _capacity;
			reserve(newcapacity);
		}
		size_t end = _size + len;
		while (end > pos + len + 1)
		{
			_str[end] = _str[end - len];
			end--;
		}
		for (size_t i = 0; i < len; i++)
		{
			_str[pos + i] = str[i];
		}
		_size += len;
	}

	void string::erase(size_t pos, size_t len)
	{
		assert(pos < _size);
		if (len == npos || len >= _size - pos)
		{
			//删完
			_str[pos] = '\0';
			_size = pos;
		}
		else
		{
			memmove(_str + pos, _str + pos + len, _size + 1 - (pos + len));
			_size -= len;
		}
	}

	size_t string::find(char ch, size_t pos)
	{
		for (size_t i = pos; i < _size; i++)
		{
			if (ch == _str[i])
			{
				return i;
			}
		}
		return npos;
	}
	size_t string::find(const char* str, size_t pos)
	{
		const char* p = strstr(_str, str);
		if (p == nullptr)
		{
			return npos;
		}
		else
		{
			return p - _str;
		}
	}
	string string::substr(size_t pos, size_t len)
	{
		assert(pos < _size);

		if (len > _size - pos)
		{
			len = _size - pos;
		}
		string ret;
		for (size_t i = 0; i < len; i++)
		{
			ret += _str[pos + i];
		}
		return ret;
	}

	string& string::operator=(const string& s)
	{
		if (this != &s)
		{
			string tmp(s);
			swap(tmp);
		}
		return *this;
	}

	bool string::operator<(const string& s) const
	{
		size_t len1 = _size;
		size_t len2 = s._size;
		size_t i1 = 0, i2 = 0;
		while (i1 < len1 && i2 < len2)
		{
			if (_str[i1] < s._str[i2])
			{
				return true;
			}
			else if (_str[i1] > s._str[i2])
			{
				return false;
			}
			else
			{
				i1++;
				i2++;
			}
		}
		return i1 == len1 && i2 < len2;
	}
	bool string::operator<=(const string& s) const
	{
		return *this < s || *this == s;
	}
	bool string::operator>=(const string& s) const
	{
		return !(*this < s);
	}
	bool string::operator==(const string& s) const
	{
		size_t len1 = _size;
		size_t len2 = s._size;
		size_t i1 = 0, i2 = 0;
		while (i1 < len1 && i2 < len2)
		{
			if (_str[i1] != s._str[i2])
			{
				return false;
			}
			else
			{
				i1++;
				i2++;
			}
		}
		return  i1 == len1 && i2 == len2;
	}
	bool string::operator!=(const string& s) const
	{
		return !(*this == s);
	}
	bool string::operator>(const string& s) const
	{
		return !(*this <= s);
	}

	std::ostream& operator<<(std::ostream& os, const string& s)
	{
		for (size_t i = 0; i < s.size(); i++)
		{
			os << s[i];
		}

		return os;
	}
	void string::clear()
	{
		_str[0] = '\0';
		_size = 0;
	}

	void string::swap(string& s)
	{
		std::swap(_str, s._str);
		std::swap(_size, s._size);
		std::swap(_capacity, s._capacity);
	}

	std::istream& operator>>(std::istream& is, string& s)
	{
		s.clear();
		char buff[256];
		size_t i = 0;
		char ch=is.get();
		//is >> ch;
		while (ch != ' '&&ch != '\n')
		{
			buff[i++] = ch;
			ch=is.get();
			if (i == 255)
			{
				buff[i] = '\0';
				s += buff;
				i = 0;
			}
		}
		if (i > 0)
		{
			buff[i] = '\0';
			s += buff;
		}

		return is;
	}



}

完！！

注意：本文只介绍一些string常见接口，具体接口请到官网进行查看！