精通C++ STL（二）：string类的模拟实现
目录
string类各函数接口总览
默认成员函数
构造函数
拷贝构造函数
赋值运算符重载函数
析构函数
迭代器相关函数
begin和end
容量和大小相关函数
size和capacity
reserve和resize
empty
修改字符串相关函数
push_back
append
operator+=
insert
erase
clear
swap
c_str
访问字符串相关函数
operator[ ]
find和rfind
find函数
rfind函数
关系运算符重载函数
>>和运算符的重载
=(const string& s)const; bool operator(istream& in, string& s); ostream& operator _capacity) //当n大于对象当前容量时才需执行操作 { char* tmp = new char[n + 1]; //多开一个空间用于存放'\0' strncpy(tmp, _str, _size + 1); //将对象原本的C字符串拷贝过来（包括'\0'） delete[] _str; //释放对象原本的空间 _str = tmp; //将新开辟的空间交给_str _capacity = n; //容量跟着改变 } }
注意：代码中使用strncpy进行拷贝对象C字符串而不是strcpy，是为了防止对象的C字符串中含有有效字符’\0’而无法拷贝（strcpy拷贝到第一个’\0’就结束拷贝了）。
resize函数目的与规则：
- 扩容并填充：当请求的大小n大于当前的_size时，函数会将字符串的大小调整到n，新增的部分用指定字符ch填充（默认为\0）。
- 缩减：若请求的大小n小于当前的_size，函数会直接将字符串的大小缩减到n，超出部分的字符被移除（但实际实现中，通常并不物理移除，而是通过更新size来隐式实现“截断”）。
//改变大小
void resize(size_t n, char ch = '\0')
{
if (n _capacity) //判断是否需要扩容
{
reserve(n); //扩容
}
for (size_t i = _size; i
empty
empty是string的判空函数，我们可以调用strcmp函数来实现，strcmp函数是用于比较两个字符串大小的函数，当两个字符串相等时返回0。
//判空
bool empty()
{
return strcmp(_str, "") == 0;
}
修改字符串相关函数
push_back
push_back函数的作用就是在当前字符串的后面尾插上一个字符，尾插之前首先需要判断是否需要增容，若需要，则调用reserve函数进行增容，然后再尾插字符，注意尾插完字符后需要在该字符的后方设置上’\0’，否则打印字符串的时候会出现非法访问，因为尾插的字符后方不一定就是’\0’。
//尾插字符
void push_back(char ch)
{
if (_size == _capacity) //判断是否需要增容
{
reserve(_capacity == 0 ? 4 : _capacity * 2); //将容量扩大为原来的两倍
}
_str[_size] = ch; //将字符尾插到字符串
_str[_size + 1] = '\0'; //字符串后面放上'\0'
_size++; //字符串的大小加一
}
注：增容时以二倍的形式进行增容，避免多次调用push_back函数时每次都需要调用reserve函数。
实现push_back还可以直接复用下面即将实现的insert函数。
//尾插字符
void push_back(char ch)
{
insert(_size, ch); //在字符串末尾插入字符ch
}
append
append函数的作用是在当前字符串的后面尾插一个字符串，尾插前需要判断当前字符串的空间能否容纳下尾插后的字符串，若不能，则需要先进行增容，然后再将待尾插的字符串尾插到对象的后方，因为待尾插的字符串后方自身带有’\0’，所以我们无需再在后方设置’\0’。
//尾插字符串
void append(const char* str)
{
size_t len = _size + strlen(str); //尾插str后字符串的大小（不包括'\0'）
if (len > _capacity) //判断是否需要增容
{
reserve(len); //增容
}
strcpy(_str + _size, str); //将str尾插到字符串后面
_size = len; //字符串大小改变
}
实现append函数也可以直接复用下面即将实现的insert函数。
//尾插字符串
void append(const char* str)
{
insert(_size, str); //在字符串末尾插入字符串str
}
operator+=
+=运算符的重载是为了实现字符串与字符、字符串与字符串之间能够直接使用+=运算符进行尾插。
+=运算符实现字符串与字符之间的尾插直接调用push_back函数或append函数即可。
//+=运算符重载
string& operator+=(char ch)
{
push_back(ch); //尾插字符串
return *this; //返回左值（支持连续+=）
}
//+=运算符重载
string& operator+=(const char* str)
{
append(str); //尾插字符串
return *this; //返回左值（支持连续+=）
}
insert
insert函数的作用是在字符串的任意位置插入字符或是字符串。
insert函数在字符串类中插入单个字符的基本逻辑。具体步骤如下：
-
合法性检查：首先确保给定的插入位置pos是合法的，意味着它应该在字符串当前有效长度的范围内。这一步通常通过断言或者条件语句来完成，以确保不会发生越界访问。
-
容量检查：在实际插入字符之前，需要检查当前字符串对象是否有足够的容量来容纳新增的字符。如果现有的容量不足以存放插入字符后的字符串，程序将调用reserve方法来增加字符串的容量。这个过程可能会使字符串的容量加倍，以减少频繁扩容带来的效率损失。
-
字符移动：为了在指定位置pos插入字符，需要将pos位置及之后的所有字符向后移动一个位置，为新字符腾出空间。这个过程通常涉及一个循环，逐个将字符向后复制。
-
字符插入：在腾出的空间中插入新的字符。这一步通常直接通过指针或迭代器操作完成，将字符写入到已经为空的指定位置。
-
更新状态：完成字符插入后，需要更新字符串的实际大小（即有效字符数量），并确保字符串末尾有终止符\0，以保持C风格字符串的完整性。
//在pos位置插入字符
string& insert(size_t pos, char ch)
{
assert(pos = _str + pos)
{
*(end + 1) = *(end);
end--;
}
_str[pos] = ch; //pos位置放上指定字符
_size++; //size更新
return *this;
}
insert函数用于插入字符串的基本逻辑。具体步骤如下：
-
合法性检查：在尝试插入字符串之前，首先验证提供的插入位置pos是否合法。这意味着pos必须在字符串现有长度范围内，以确保不会发生数组越界错误。通常，这通过一个断言或条件语句来实现。
-
容量评估：接下来，程序会检查当前字符串是否有足够的容量来容纳插入新字符串后的结果。如果当前的容量不足以满足需求，程序会调用reserve方法来预先分配足够的内存。这个过程可能涉及将现有容量至少增加到足以容纳新字符串后的总长度，通常采取倍增策略以优化性能。
-
字符移动：为了在指定位置pos插入字符串，需要将pos位置及其之后的所有字符向右移动len个位置，这里len是待插入字符串的长度。这一操作通常通过一个循环实现，逐个将字符复制到它们的新位置。
-
字符串插入：在腾出的空间中，使用类似strncpy的函数将待插入的字符串复制进去。注意，直接使用strcpy是不合适的，因为它会连同源字符串的终止符\0一起复制，导致字符串提前结束。正确做法是明确指定复制的字符数。
-
更新状态：插入完成后，需要更新字符串的大小（有效字符数量）以及确保字符串末尾有正确的终止符\0。此外，如果_size和_capacity是类的成员变量，它们也需要相应地更新以反映最新的字符串状态。
//在pos位置插入字符串
string& insert(size_t pos, const char* str)
{
assert(pos _capacity) //判断是否需要增容
{
reserve(len + _size); //增容
}
char* end = _str + _size;
//将pos位置及其之后的字符向后挪动len位
while (end >= _str + pos)
{
*(end + len) = *(end);
end--;
}
strncpy(_str + pos, str, len); //pos位置开始放上指定字符串
_size += len; //size更新
return *this;
}
注意：插入字符串的时候使用strncpy，不能使用strcpy，否则会将待插入的字符串后面的’\0’也插入到字符串中。
erase
erase函数的作用是删除字符串任意位置开始的n个字符。
判断pos的合法性
在执行删除操作前，首先需要确保给定的索引pos是有效的，即它应该在字符串的大小范围内（0 到 size()-1 之间）。这一步骤通常通过断言或条件语句来实现，以确保不会引发数组越界错误。
删除操作的两种情况
1. 删除从pos位置到字符串末尾的所有字符
- 操作方式：如果需要删除从pos位置直到字符串末尾的所有字符，实际上只需要调整字符串的_size成员变量（表示字符串的有效长度），使其等于pos。这是因为字符串对象通常在其分配的内存末尾已经有一个终止符\0，因此不需要额外添加。通过这种方式，从pos位置开始的所有字符虽然还在内存中，但已经被视作无效，不会影响字符串的正常行为。
2. 删除pos位置开始的特定数量的字符
- 操作方式：当只需要删除从pos开始的特定数量的字符时，操作稍微复杂一些。首先，同样需要确认pos加上要删除的字符数len不会超过当前字符串的有效长度。之后，可以使用如strcpy这样的函数，将从pos+len位置开始的有效字符覆盖到pos位置上，以此来实现删除效果。由于字符串末尾原本就有\0，所以覆盖操作后字符串仍然是有效格式化的，无需额外添加\0。
更新字符串状态
无论是哪种情况，在删除操作后，都需要更新字符串的_size成员变量，以反映删除操作后的实际有效字符数量。同时，如果删除操作导致大量空间不再使用，某些实现可能会考虑调用类似于shrink_to_fit的方法来释放未使用的内存，但这通常不是删除操作的直接部分，而是作为一个可选的优化步骤。
//删除pos位置开始的len个字符 string& erase(size_t pos, size_t len = npos) { assert(pos = n) //说明pos位置及其后面的字符都被删除 { _size = pos; //size更新 _str[_size] = '\0'; //字符串后面放上'\0' } else //说明pos位置及其后方的有效字符需要保留一部分 { strcpy(_str + pos, _str + pos + len); //用需要保留的有效字符覆盖需要删除的有效字符 _size -= len; //size更新 } return *this; }clear
clear函数用于将对象中存储的字符串置空，实现时直接将对象的_size置空，然后在字符串后面放上’\0’即可。
//清空字符串 void clear() { _size = 0; //size置空 _str[_size] = '\0'; //字符串后面放上'\0' }swap
swap函数用于交换两个对象的数据，直接调用库里的swap模板函数将对象的各个成员变量进行交换即可。
//交换两个对象的数据 void swap(string& s) { //调用库里的swap ::swap(_str, s._str); //交换两个对象的C字符串 ::swap(_size, s._size); //交换两个对象的大小 ::swap(_capacity, s._capacity); //交换两个对象的容量 }注意：若想让编译器优先在全局范围寻找某函数，则需要在该函数前面加上“ :: ”（作用域限定符）。
c_str
c_str函数用于获取对象C类型的字符串，实现时直接返回对象的成员变量_str即可。
//返回C类型的字符串 const char* c_str()const { return _str; }访问字符串相关函数
operator[ ]
[ ]运算符的重载是为了让string对象能像C字符串一样，通过[ ] +下标的方式获取字符串对应位置的字符。
读写访问的重载
char& operator[](size_t i) { assert(i这段代码重载了[]运算符，它接收一个size_t类型的下标i作为参数，并返回该下标处字符的引用。这样，用户就可以通过s[i]的形式读取或修改字符串中的字符，如s[0] = 'A';。但是，这样的实现没有对const对象提供保护，也就是说，即使对象是常量，也能通过此重载修改其内容，这通常是不期望的行为。
只读访问的重载
为了支持对const对象的安全访问，即允许读取但禁止修改，需要提供一个额外的重载版本：
//[]运算符重载（只读） const char& operator[](size_t i)const { assert(i这个版本通过添加const关键字在函数声明的最后，表明该函数适用于const对象，并且返回值是一个指向const char的引用，这意味着即使尝试通过s[i]对字符串内容进行修改，也会因赋值给常量引用而导致编译错误，从而保护了数据的不可变性。
find和rfind
find函数和rfind函数都是用于在字符串中查找一个字符或是字符串，find函数和rfind函数分别用于正向查找和反向查找，即从字符串开头开始向后查找和从字符串末尾开始向前查找。
find函数
查找单个字符
size_t find(char ch, size_t pos = 0) { assert(pos这段代码通过线性搜索的方式从指定位置pos开始在字符串中查找字符ch。如果找到，返回其在字符串中的索引；否则，返回npos。
查找子字符串
size_t find(const char* str, size_t pos = 0) { assert(pos此版本的find函数利用了C标准库中的strstr函数来查找子字符串。strstr函数直接返回子字符串在原字符串中的起始地址，如果未找到则返回NULL。找到子字符串后，通过计算地址差得到子字符串在原字符串中的起始索引并返回。如果没有找到，同样返回npos。
rfind函数
实现rfind函数时，我们可以考虑复用已经写好了的两个find函数，但rfind函数是从后先前找，所以我们需要将对象的C字符串逆置一下。若是查找字符串，还需将待查找的字符串逆置一下，然后调用find函数进行查找，但注意传入find函数的pos以及从find函数接收到的pos都需要镜像对称一下。
反向查找单个字符 这个过程包括几个关键步骤：
- 创建临时对象：为了避免原字符串被修改，首先通过拷贝构造函数创建了一个临时字符串tmp。
- 逆置字符串：利用reverse函数将tmp的字符顺序颠倒，以便从后向前查找。
- 调整查找起始位置：如果给定的pos超出字符串有效长度，将其调整为字符串末尾。接着，计算出相对于逆置后字符串的起始查找位置。
- 调用正向查找：在逆置后的字符串tmp上使用find函数查找字符。
- 返回结果：如果找到匹配字符，计算其在原始字符串中的位置并返回；如果未找到，返回npos。
//反向查找第一个匹配的字符 size_t rfind(char ch, size_t pos = npos) { string tmp(*this); //拷贝构造对象tmp reverse(tmp.begin(), tmp.end()); //调用reverse逆置对象tmp的C字符串 if (pos >= _size) //所给pos大于字符串有效长度 { pos = _size - 1; //重新设置pos为字符串最后一个字符的下标 } pos = _size - 1 - pos; //将pos改为镜像对称后的位置 size_t ret = tmp.find(ch, pos); //复用find函数 if (ret != npos) return _size - 1 - ret; //找到了，返回ret镜像对称后的位置 else return npos; //没找到，返回npos }反向查找子字符串 除了上述步骤外，还额外包括：
- 逆置待查找字符串：因为是在逆置后的字符串中查找，所以待查找的子字符串也需要被逆置。
- 内存管理：为逆置的子字符串分配新的内存，并确保在查找结束后正确释放这块内存。
- 结果调整：找到子字符串的最后一个字符位置后，需要进一步调整计算，找到其在原字符串中的起始位置，即返回_size - ret - len。
//反向查找第一个匹配的字符串 size_t rfind(const char* str, size_t pos = npos) { string tmp(*this); //拷贝构造对象tmp reverse(tmp.begin(), tmp.end()); //调用reverse逆置对象tmp的C字符串 size_t len = strlen(str); //待查找的字符串的长度 char* arr = new char[len + 1]; //开辟arr字符串（用于拷贝str字符串） strcpy(arr, str); //拷贝str给arr size_t left = 0, right = len - 1; //设置左右指针 //逆置字符串arr while (left = _size) //所给pos大于字符串有效长度 { pos = _size - 1; //重新设置pos为字符串最后一个字符的下标 } pos = _size - 1 - pos; //将pos改为镜像对称后的位置 size_t ret = tmp.find(arr, pos); //复用find函数 delete[] arr; //销毁arr指向的空间，避免内存泄漏 if (ret != npos) return _size - ret - len; //找到了，返回ret镜像对称后再调整的位置 else return npos; //没找到，返回npos }关系运算符重载函数
关系运算符有 >、>=、运算符重载 bool operator>(const string& s)const { return strcmp(_str, s._str) > 0; } //==运算符重载 bool operator==(const string& s)const { return strcmp(_str, s._str) == 0; }
剩下的四个关系运算符的重载，就可以通过复用这两个已经重载好了的关系运算符来实现了。
//>=运算符重载 bool operator>=(const string& s)const { return (*this > s) || (*this == s); } //和运算符的重载重载>>运算符是为了让string对象能够像内置类型一样使用>>运算符直接输入。输入前我们需要先将对象的C字符串置空，然后从标准输入流读取字符，直到读取到’ ‘或是’\n’便停止读取。
//>>运算符的重载 istream& operator>>(istream& in, string& s) { s.clear(); //清空字符串 char ch = in.get(); //读取一个字符 while (ch != ' '&&ch != '\n') //当读取到的字符不是空格或'\n'的时候继续读取 { s += ch; //将读取到的字符尾插到字符串后面 ch = in.get(); //继续读取字符 } return in; //支持连续输入 }
- 操作方式：当只需要删除从pos开始的特定数量的字符时，操作稍微复杂一些。首先，同样需要确认pos加上要删除的字符数len不会超过当前字符串的有效长度。之后，可以使用如strcpy这样的函数，将从pos+len位置开始的有效字符覆盖到pos位置上，以此来实现删除效果。由于字符串末尾原本就有\0，所以覆盖操作后字符串仍然是有效格式化的，无需额外添加\0。
