【C++笔记】string类深度解剖及其模拟实现
?个人主页：大白的编程日记
?专栏：C++笔记
文章目录
【C++笔记】string类深度解剖及其模拟实现前言一.string类说明1.1为什么实现string类1.2string类了解 二.string类的常用接口说明2.1string类对象的常见构造2.2string类对象的容量操作2.3string类对象的访问及遍历操作2.4string类对象的修改操作2.5string类非成员函数2.6字符串补充接口 二.vs和g++下string结构的说明二. string的实现2.1string的定义2.2 构造和拷贝构造2.3 operator[]2.4 迭代器2.5 string比较2.6 reserve2.7 push_back2.8 append2.9 operator+=2.10 insert2.11 find2.12 clear2.13erase2.43 IO流2.15 operator= 后言
前言
哈喽，各位小伙伴大家好！上期我们讲了模版，就用我们来讲一下string类及其实现。话不多说，我们进入正题！向大厂冲锋！
一.string类说明
1.1为什么实现string类
C语言中，字符串是以’\0’结尾的一些字符的集合，为了操作方便，C标准库中提供了一些str系列的库函数，但是这些库函数与字符串是分离开的，不太符合面向对象的思想，而且底层空间需要用户自己管理，稍不留神可能还会越界访问。并且日常生活中字符串使用场景还是很多的，比如：身份证，电话号码等。所以单独搞一个数据结构出来给字符窜还是很有必要的
1.2string类了解
string其实是typedef basic_string char来的。那意思除了char还有其他的字符类型吗？是的。由于编码原因还有其他的字符类型。string是一个类。string的本质是个字符顺序表。
想学习了解string类可以看这个文档：string的文档介绍
在使用string类时，必须包含#include头文件以及using namespace std
二.string类的常用接口说明
2.1string类对象的常见构造
string的构造有这些。
但重点是这几个。
构造空串。
用一个常量字符串构造
用一个string构造 
用另一个stirng的pos位置开始后面的len个字符构造
如果给的长度过大会怎么样呢？会越界吗？
2.2string类对象的容量操作
| 函数名称 | 功能说明 |
|---|---|
| size（重点） | 返回字符串有效字符长度 |
| length | 返回字符串长度 |
| empty（重点） | 检测字符串释放为空串，是返回true，否则返回false |
| capacity | 返回空间总大小 |
| clear(重点) | 清空有效字符 |
| reserve(重点) | 为字符串预留空间 |
| resize(重点) | 将有效字符的个数该成n个，多出的空间用字符c填充 |
string容量相关代码演示
length
length获取字符串的长度。但是这个接口不具有通用性。比如二叉树就没有length.
size
获取字符串的长度。size具有通用性。
empty
判断字符串是否为空。
- clear清理有效字符内容。
- capacity 返回空间总大小。string容量只包含有效字符，也就是说这里是16个字符的空间。
C++string的capacity如何扩容是没有规定的。具体看平台实现。
vs下是先用一个16字符大小buff字符数组存储，当字符数组不够用时再开辟一块空间。第一次2倍扩，后面1.5倍扩容。
g++是2倍扩容。
reserve
reserve保留空间。可以避免频繁扩容。
resize
将有效字符的个数该成n个，多出的空间用给定字符填充字符填充，如果没有就填充0。
总结
size()与length()方法底层实现原理完全相同，引入size()的原因是为了与其他容器的接口保持一致，一般情况下基本都是用size()。clear()只是将string中有效字符清空，不改变底层空间大小。resize(size_t n) 与 resize(size_t n, char c)都是将字符串中有效字符个数改变到n个，不同的是当字符个数增多时：resize(n)用0来填充多出的元素空间，resize(size_t n, char c)用字符c来填充多出的元素空间。注意：resize在改变元素个数时，如果是将元素个数增多，可能会改变底层容量的大小，如果是将元素个数减少，底层空间总大小不变。reserve(size_t res_arg=0)：为string预留空间，不改变有效元素个数，当reserve的参数小于string的底层空间总大小时，reserver不会改变容量大小。2.3string类对象的访问及遍历操作
| 函数名称 | 功能说明 |
|---|---|
| operator[](重点) | 返回pos位置的字符，const string类对象调用 |
| begin +end | begin获取一个字符的迭代器 + end获取最后一个字符下一个位置的迭代器 |
| rbegin+rend | begin获取一个字符的迭代器 + end获取最后一个字符下一个位置的迭代器 |
| 范围for | C++11支持更简洁的范围for的新遍历方式 |
string中元素访问及遍历演示
string的遍历方式有三种：
下标+[]char& string::operator[](size_t pos){assert(pos < _size);return _s[pos];}这里因为string的底层是字符数组所以我们可以用下标+[]直接访问到pos位置的字符
从而遍历字符串。同时我们返回的是pos位置字符的引用这样还可以修改pos位置的字符。
迭代器支持所有容器的访问。
string s("hello,world!");string::iterator it = s.begin();while (it!=s.end()){cout << *it << " ";it++;}
auto关键字:
在这里补充2个C++11的小语法，方便我们后面的学习。
在早期C/C++中auto的含义是：使用auto修饰的变量，是具有自动存储器的局部变量，后来这个不重要了。C++11中，标准委员会变废为宝赋予了auto全新的含义即：auto不再是一个存储类型指示符，而是作为一个新的类型指示符来指示编译器，auto声明的变量必须由编译器在编译时期推导而得。
用auto声明指针类型时，用auto和auto*没有任何区别，但用auto声明引用类型时则必须加&当在同一行声明多个变量时，这些变量必须是相同的类型，否则编译器将会报错，因为编译器实际只对第一个类型进行推导，然后用推导出来的类型定义其他变量。
auto不能作为函数的参数，可以做返回值，但是建议谨慎使用
auto不能直接用来声明数组
auto的价值就是自动推导类型，如果类型过长就很方便。
但是一定程度牺牲了可读性。
范围for遍历的用法如下：
//自动迭代 自动判断结束string s("hello,world!");for (auto x : s){cout << x << " ";}
所有的容器都支持范围for,因为i所有的容器都支持迭代器。
范围for写起来更方便。
加上引用即可。
总结
反向迭代器
反向迭代器就是倒着遍历容器。
string s("hello,world!");string::reverse_iterator rit = s.rbegin();while (rit!=s.rend()){cout << *rit << " ";rit++;}
如果是const容器就需要用const迭代器访问呢。因为普通迭代器可读可写。但是容器的数据不允许修改。
2.4string类对象的修改操作
| 函数名称 | 功能说明 |
|---|---|
| push_back | 在字符串后尾插字符c |
| append | 在字符串后追加一个字符串 |
| operator+=(重点) | 在字符串后追加字符串str |
| c_str(重点) | 返回C格式字符串 |
| find+npos(重点) | 从字符串pos位置开始往后找字符c，返回该字符在字符串中的位置 |
| rfind | 从字符串pos位置开始往前找字符c，返回该字符在字符串中的位置 |
| substr | 在str中从pos位置开始，截取n个字符，然后将其返回 |
string中插入和查找等代码演示
push_back
可以尾插一个字符。
append
在字符串后追加一个字符串。
operator+=
在字符串后追加字符串str.
insert
在某个位置插入字符或字符串。
但注意要谨慎使用insert因为在头部或中间位置插入必然要挪动数据。大量使用会降低程序效率。
find
在字符串的某个位置开始查找第一个位置的字符或字符串。找到就返回目标起始位置。
需要注意的是如果不存在查找目标，那就返回npos
erase
在某个位置删除一个或多个字符。
需要注意的是，如果用数字作为位置的话，len大于剩余字符串的长度或是npos。
只会删除到最后一个位置的字符。
注意erase也需要谨慎使用，因为删除也要挪动数据。
replace
将字符串的一部分替换为一个字符或字符串。
repalce也会挪动数据所以也不要大量使用。
c_str
返回C格式字符串.兼容c语言返回c语言字符串的首地址。
如果len大于pos后的字符长度或len==npos。
就从pos构造到最后一个位置。
find_first_of
在一个string中查找出现在另一个字符串的字符第一次出现的位置
另外再字符串中表示转义字符如\n，只需要多加一个\即可。因为对\转义字符转义后就表示不是转义字符了。
find_last_of
在一个string从后往前查找出现在另一个字符串的字符第一次出现的位置。
这时我们就可以利用这个接口完成windows或linux下的路径分割。
substr
用另一个string从pos位置后的len个字符构造string。
2.5string类非成员函数
上面的几个接口大家了解一下，下面的OJ题目中会有一些体现他们的使用。string类中还有一些其他的操作，这里不一一列举，大家在需要用到时不明白了查文档即可。
这里perator+重载成全局的是为了支持这样的写法。
如果重载成成员函数，那this指针就会锁定左边第一个位置。
也就不支持，字符串+string的写法了。relational operators
支持string与string或字符串比较。
getlibe自定义IO输入终止符。
以这道题为例。
题目：最后一个单词的长度
2.6字符串补充接口
刷题时可能需要用到一些快速判断的接口。
二.vs和g++下string结构的说明
注意：下述结构是在32位平台下进行验证，32位平台下指针占4个字节。
vs下string的结构string总共占28个字节，内部结构稍微复杂一点，先是有一个联合体，联合体用来定义string中字符串的存储空间：
当字符串长度小于16时，使用内部固定的字符数组来存放
当字符串长度大于等于16时，从堆上开辟空间
union _Bxty{ // storage for small buffer or pointer to larger onevalue_type _Buf[_BUF_SIZE];pointer _Ptr;char _Alias[_BUF_SIZE]; // to permit aliasing} _Bx;这种设计也是有一定道理的，大多数情况下字符串的长度都小于16，那string对象创建好之后，内部已经有了16个字符数组的固定空间，不需要通过堆创建，效率高。
其次：还有一个size_t字段保存字符串长度，一个size_t字段保存从堆上开辟空间总的容量.
最后：还有一个指针做一些其他事情。
故总共占16+4+4+4=28个字节。
G++下，string是通过写时拷贝实现的，string对象总共占4个字节，内部只包含了一个指针，该指针将来指向一块堆空间，内部包含了如下字段：
二. string的实现
2.1string的定义
这里我们用一个char*指针指向字符串空间。
一个size表示有效字符个数。一个capacity表示空间大小。
在定义一个npos。
class string{private:char* _s;size_t _size;size_t _capacity;static const size_t npos;};前面我们说静态成员不能再声明的位置给缺省值，因为他不走初始化列表。但是注意这里的static const相当于就是一个定义，可以给缺省值。可以认为是编译器特殊处理了。并且只有static const 整形可以。
private:char* _s;size_t _size;size_t _capacity;static const size_t npos=-1;static const int N = 10;int buff[N];};某种程度可以理解为这样的设计，方便定义一个整形常量。去定义一个数组。
2.2 构造和拷贝构造
这里我们给一个缺省值就可以构造函数和拷贝构造都一起实现。注意缺省值要给空字符串而不能给空指针，表示有一个字符串但字符串为空。同时申请空间时要多开一个给\0。
string::string(const char* str=""){_capacity = _size = strlen(str);_s = new char[_size + 1];strcpy(_s, str);}2.3 operator[]
直接返回字符的引用即可。
operator[]还可以实现const版本只读不写。
char& string::operator[](size_t pos){assert(pos < _size);return _s[pos];}const char& string::operator[](size_t pos) const{assert(pos < _size);return _s[pos];}2.4 迭代器
迭代器就是模拟指针的行为。
我们直接返回第一个字符和最后一个字符端点指针即可。
typedef char* iterator;typedef const char* const_iterator;string::const_iterator string::begin() const{return _s;}string::const_iterator string::end() const{return _s + _size;}string::iterator string::begin(){return _s;}string::iterator string::end(){return _s+_size;}还有注意范围for必须按照库里的命名风格走，他只是傻瓜式的替换。
例如我们把begin换成大写的。范围for我们自己写的迭代器能跑，范围for不行。
2.5 string比较
这里我们实现operator<和operator==再复用即可。
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);}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);}2.6 reserve
这里我们直接new手动开空间，注意要多开一个给\0.
然后拷贝原数据。释放旧空间。
void string::reserve(size_t n){if (n > _capacity){char*tmp = new char[n+1];strcpy(tmp, _s);delete[] _s;_s = tmp;_capacity = n;}}2.7 push_back
这里插入我们先检查一下是否需要扩容。然后再进行插入，同时size++，末尾补上\0
void string::push_back(char ch){if (_size == _capacity){reserve(_capacity == 0 ? 4 : 2 * _capacity);}_s[_size++] = ch;_s[_size] = '\0';}2.8 append
这里我们先计算插入字符串的长度。然后检查一下二倍扩容是否够。不够就申请size+len的空间。再拷贝数据，更新size即可。
void string::append(const char* str){size_t len = strlen(str);if (_size+len > _capacity){reserve(_size + len>2*_capacity? _size + len:2*_capacity);}strcpy(_s + _size, str);_size += len;}2.9 operator+=
这里我们直接复用append和push_back即可。
string& string::operator+=(const char* str){append(str);return *this;}string& string::operator+=(char ch){push_back(ch);return *this;}2.10 insert
这里我需要检查扩容。然后再挪动数据。插入数据，再更新size即可。
void string::insert(size_t pos, char ch){assert(pos <= _size);if (_size == _capacity){reserve(_capacity == 0 ? 4 : 2 * _capacity);}for (int i = _size+1; i >pos; i--){_s[i] = _s[i-1];}_s[pos] = ch;_size++;}void string::insert(size_t pos, const char* str){int len = strlen(str);assert(pos <= _size);if (_size+len > _capacity){reserve(_size + len >2*_capacity ? _size + len : 2 * _capacity);}for (int i = _size+len; i >=pos+len; i--){_s[i] = _s[i-len];}int j = 0;for (int i = pos; i <pos+len; i++){_s[i] = str[j++];}_size+=len;}2.11 find
find查找
size_t string::find(char ch, size_t pos){assert(pos < _size);for (int i = pos; i < _size; i++){if (_s[i] == ch){return i;}}return npos;}size_t string::find(const char* str, size_t pos){assert(pos < _size);const char* ch = strstr(_s+pos, str);if (ch == nullptr){return npos;}return ch - _s;}2.12 clear
直接把size改为0，同时在补上\0即可。
void string::clear(){_s[0] = '\0';_size = 0;}2.13erase
如果pos开始的len个字符长度超过剩余的最大长度。那就直接把pos位置不上/0,更改size即可。
如果长度不超过剩余的最大长度，那就直接挪动数据。
再更改size即可。
void string::erase(size_t pos, size_t len){assert(pos >= 0 && pos < _size);if (pos + len >= _size ){_s[pos] = '\0';_size = pos;}else{for (int i = pos+len; i <= size(); i++){_s[i-len] = _s[i];}_size -= len;}}2.43 IO流
operator<< 输出直接遍历字符输出即可。
operator>>输入为了避免频繁插入扩容和空间浪费
我们先用一个大小适中的字符数据存储读取数据。
当字符数据满了就把字符数据尾插入到str。
依次这样读取数据即可。
当读取结束再将字符数据的数据尾插str即可。
ostream& operator<<(ostream& out, const string& str){for (auto& x : str){out << x;}return out;}istream& operator>>(istream& in, string& str){str.clear();//清空数据char ch;const int N = 256;char buff[N];//定义字符数组int i = 0;ch = in.get();//字符while (ch != ' ' && ch != '\n')//遇到空格和换行结束{buff[i++] = ch;if (i == N - 1)//空间满{buff[i] = '\0';str += buff;//将数据插入stri = 0;}ch = in.get();//继续读取。}if (i > 0)//读取结束且还有数据未插入{buff[i] = '\0';str += buff;//将数据插入str}return in;}2.15 operator=
这里我们可以手动new空间在拷贝内容。更新size和capacity。
也可用算法库里的swap交换。相当于让编译器帮我们干活。
void string::swap(string& str){std::swap(_s, str._s);std::swap(_size, str._size);std::swap(_capacity, str._capacity);}string& string::operator=(const string& tmp)//传统写法{if (this != &tmp){delete[] _s;_s = new char[tmp._capacity + 1];strcpy(_s, tmp._s);_size = tmp._size;_capacity = tmp._capacity;}return *this;}string& string::operator=(string str){swap(str);return *this;}后言
这就是string类深度解剖及其模拟实现。大家不熟悉string的可以去官方查文档。今天就分享到这，感谢大家的耐心垂阅！咱们下期见！拜拜~
