C++效率掌握之STL库：string底层剖析

文章目录

1.学习string底层的必要性
2.string类对象基本函数实现
3.string类对象的遍历
4.string类对象的扩容追加
5.string类对象的插入、删除
6.string类对象的查找、提取、大小调整
7.string类对象的流输出、流提取
希望读者们多多三连支持
小编会继续更新
你们的鼓励就是我前进的动力！

了解完 string 函数的主要用法，很有必要对 string 进行深层次的剖析，进一步了解其运作原理，深化理解的同时帮助我们在找 Bug 时提升效率

在学习本专题前，请详细学习有关 string 的使用

传送门：C++效率掌握之STL库：string函数全解

1.学习string底层的必要性

在 C++ 中，知道 string 是如何以字符数组的形式存储，以及字符串连接、查找等操作的时间复杂度，就可以避免在循环中频繁进行字符串连接操作，因为这可能会导致多次内存重新分配和数据复制，从而影响性能，而是选择更高效的方式，如预先分配足够的空间。同时，理解 string 底层对内存的管理方式，有助于优化内存使用，避免空指针和越界的情况出现

2.string类对象基本函数实现

实现一个类首先先从其基本函数开始，包括构造函数、析构函数、内存管理等

namespace bit
{class string{public:string()//空构造:_size(0), _capacity(0), _str(new char[1]){_str[0] = '\0';}string(const char* str)//字符串构造:_size(strlen(str)),_capacity(_size),_str(new char[_capacity + 1]){strcpy(_str, str);}string(const string& s)//拷贝构造{_str = new char[s._capacity + 1];strcpy(_str, s._str);_size = s._size;_capacity = s._capacity;}// 赋值运算符重载string& operator=(const string& s) {if (this != &s) {  // 避免自我赋值delete[] _str;  // 释放原有内存_size = s._size;_capacity = s._capacity;_str = new char[_capacity + 1];  // 分配新内存strcpy(_str, s._str);  // 复制内容}return *this;}~string(){delete[] _str;_str = nullptr;_size = _capacity = 0;}const char* c_str() const{return _str;}private:size_t _size;size_t _capacity;char* _str;};
}

简单实现一个空构造和字符串构造，因为还没写 string 流输出的运算符重载，先将 string 类转成 C 语言风格来输出

🔥值得注意的是： 注意变量声明的顺序要和初始化列表一致，也要注意变量初始化顺序对另一个变量的影响；=运算符重载：自我赋值是指对象在赋值时被赋值给自己，例如 s1 = s1，在这种情况下，如果我们没有进行检查，就会先删除对象的内存，然后再试图复制同一个对象的内容，这样会导致程序崩溃。因此，重载赋值运算符时，自我赋值检查是非常必要的

3.string类对象的遍历

size_t size() const//加const保证const和普通string都能调用
{                  //增加普遍性，涉及权限的缩小return _size;
}char& operator[](size_t pos)//可读写
{assert(pos < _size);return _str[pos];
}char& operator[](size_t pos) const//只读
{assert(pos < _size);return _str[pos];
}typedef char* iterator;
iterator begin()
{return _str;
}iterator end()
{return _str + _size;
}typedef const char* const_iterator;
iterator begin() const
{return _str;
}iterator end() const
{return _str + _size;
}

想要遍历一个字符串，首先就要知道大小，然后需要用方括号来获取索引，或者用迭代器遍历，迭代器的本质其实就是一个字符数组

🔥值得注意的是：

注意 size 函数和 c_str 函数要具有普遍性，所以要包括 const 变量的情况，，即使是普通类型调用也是权限的缩小，两种情况共用一个函数
operator[] 分为加 const 和不加 const ，分别代表只读和可读写
同样迭代器也分为 iterator 和 const_iterator
begin() 指向第一个有效字符，end() 指向最后一个有效字符的后一位

4.string类对象的扩容追加

void reserve(size_t n)
{// 检查请求的内存大小 n 是否大于当前的容量 _capacityif (n > _capacity){// 若 n 大于 _capacity，则分配 n + 1 个字符的内存空间// 多分配一个字符是为了存储字符串的结束符 '\0'char* tmp = new char[n + 1];// 将原字符串 _str 复制到新分配的内存区域 tmp 中strcpy(tmp, _str);// 释放原字符串 _str 所占用的内存空间delete[] _str;// 将 _str 指针指向新分配的内存区域 tmp_str = tmp;// 更新当前字符串的容量为 n_capacity = n;}
}void push_back(char ch)
{// 检查当前字符串的实际字符数量 _size 是否等于其容量 _capacityif (_size == _capacity){// 如果容量为 0，将容量扩展为 4；否则将容量扩大为原来的 2 倍reserve(_capacity == 0 ? 4 : _capacity * 2);}// 在字符串的末尾（即 _size 位置）添加新字符 ch_str[_size] = ch;// 实际字符数量加 1++_size;// 在新的字符串末尾添加字符串结束符 '\0'_str[_size] = '\0';
}void append(const char* str)
{// 计算要追加的字符串的长度size_t len = strlen(str);// 检查当前字符串的实际长度 _size 加上要追加的字符串长度 len 是否超过当前容量 _capacityif (_size + len > _capacity){// 如果超过容量，调用 reserve 函数进行扩容，扩容后的容量至少为 _size + lenreserve(_size + len);}// 将追加的字符串 str 复制到当前字符串 _str 的末尾位置（_str + _size）strcpy(_str + _size, str);// 更新当前字符串的实际长度，加上要追加的字符串的长度_size += len;
}string& operator+=(const char* str)
{append(str);return *this;
}

或许扩容添加的函数看起来操作简单，但其实其底层有许多细节

🔥值得注意的是：

reserve 传入的参数 n 指的是有效字符，new 一个新空间时 +1 是为了给 '\0' 留位置，capacity 也表示的是有效字符的容量，同时要记得释放原来指向的不使用的空间
push_back 函数 reserve 时要判断下是因为扩容是 *2 ，避免空间为 0 时扩容 *2 导致出错
push_back 通常只是添加一个字符，不会涉及修改，所以不用传 const 参数；append 的参数可能会被错误修改，所以要传 const 参数，普通的参数可以通过权限缩小正常使用函数

5.string类对象的插入、删除

void insert(size_t pos, size_t n, char ch)
{assert(pos <= _size);if (_size + n > _capacity){reserve(_size + n);}size_t end = _size;while (end >= pos && end != npos){_str[end + n] = _str[end];--end;}for (size_t i = 0; i < n; i++){_str[pos + i] = ch;}_size += n;
}void insert(size_t pos, const char* str)
{assert(pos <= _size);size_t len = strlen(str);if (_size + len > _capacity){reserve(_size + len);}size_t end = _size;while (end >= pos && end != npos){_str[end + len] = _str[end];--end;}for (size_t i = 0; i < len; i++){_str[pos + i] = len;}_size += len;
}void erase(size_t pos, size_t len = npos)
{assert(pos <= _size);if (len == npos || pos + len >= _size){_str[pos] = '\0';_size = pos;_str[_size] = '\0';}else{size_t end = pos + len;while (end <= _size){_str[pos++] = _str[end++];}_size -= len;}
}

string 类的插入删除都利用的是移动覆盖的思想，这里就不画图了，在数据结构阶段就已经学习了大致的思路

🔥值得注意的是：

这里使用 size_t 类型的 end 作为索引来遍历字符串，size_t 是无符号整数类型。当 end 递减到 0 后再进行 --end 操作时，会发生无符号整数溢出，end 的值会变成 size_t 类型所能表示的最大值，这个值恰好和 npos（被初始化为 -1 转换后的 size_t 最大值）相等
如果没有 end != npos 这个条件，当 end 溢出后，end >= pos 仍然可能为真（因为溢出后的值很大），这就会导致循环继续执行，从而造成数组越界访问，引发未定义行为。加上 end != npos 这个条件，当 end 溢出变成 npos 时，循环就会终止，避免了越界访问的问题
注意 capacity 在 reserve 里已经修改过了，所以外面只需要再修改 size 就行了

6.string类对象的查找、提取、大小调整

size_t find(char ch, size_t pos = 0)
{assert(pos < _size);for (size_t i = pos; i < _size; i++){if (_str[i] == ch){return i;}}return npos;
}size_t find(const char* str, size_t pos = 0)
{assert(pos < _size);const char* ptr = strstr(_str + pos, str);if (ptr){return ptr - _str;}else{return npos;}}string substr(size_t pos = 0, size_t len = npos)
{assert(pos < _size);size_t n = len;if (len == npos || len + pos > _size){n = _size - pos;}string tmp;tmp.reserve(n);for (size_t i = pos; i < n; ++i){tmp.push_back(_str[i]);}return tmp;
}void resize(size_t n, char ch = '\0')
{if (n < _size){_size = n;_str[_size] = '\0';}else{reserve(n);for (size_t i = _size; i < n; ++i){_str[i] = ch;}_size = n;_str[_size] = '\0';}
}

string 的查找操作比较简单，提取要注意提取的长度与原字符串长度的关系，调整大小也要注意 '\0' 的位置

🔥值得注意的是：

return ptr - _str：通过指针相减计算子字符串在原字符串中的起始位置索引。因为 ptr 指向子字符串的起始位置，_str 指向原字符串的起始位置，两者相减得到的差值就是子字符串的起始位置索引

7.string类对象的流输出、流提取

void clear()
{_str[0] = '\0';_size = 0;
}ostream& operator<<(ostream& out, const string& s)
{for (size_t i = 0; i < s.size(); i++){out << s[i];}return out;
}istream& operator>>(istream& in, string& s)
{// 清空字符串 s 原有的内容s.clear();// 从输入流 in 中读取一个字符并赋值给 chchar ch = in.get();//处理前缓冲区前面的空格和换行while (ch == ' ' || ch == '\n'){ch = in.get();}// 定义一个大小为 128 的字符数组 buff 用于临时存储字符，初始化为全 '\0'char buff[128] = { '\0' };// 定义一个索引变量 i 用于记录 buff 数组当前存储字符的位置，初始化为 0int i = 0;// 循环处理连续的空格和换行符while (ch == ' ' || ch == '\n'){// 将当前读取到的空格或换行符存入 buff 数组，并将索引 i 加 1buff[i++] = ch;// 检查 buff 数组是否快满（只剩下一个位置用于存储字符串结束符 '\0'）if (i == 127){// 在 buff 数组末尾添加字符串结束符 '\0'buff[i] = '\0';// 将 buff 数组中的内容添加到字符串 s 中s += buff;// 重置索引 i 为 0，以便重新使用 buff 数组i = 0;}// 从输入流 in 中读取下一个字符并赋值给 chch = in.get();}// 如果 buff 数组中还有剩余字符（即 i 不为 0）if (i != 0){// 在 buff 数组末尾添加字符串结束符 '\0'buff[i] = '\0';// 将 buff 数组中的剩余内容添加到字符串 s 中s += buff;}// 返回输入流 in，以便支持链式输入操作return in;
}