C++ STL—— String库

        在C++编程中，字符串操作是几乎每个项目都会涉及的基础功能。C++标准模板库（STL）中的string类为我们提供了强大而灵活的工具，使得字符串的处理变得简单高效。无论是字符串的创建、修改、查找，还是复杂的文本处理，string库都能轻松应对。

一、常用的String函数：

函数	功能
length( )	返回字符串的长度
size( )	返回字符串的长度
push_back( )	在字符串尾部添加一个字符
append( )	在字符串尾部添加一个字符串
find(str,pos)	查找str在pos（含）之后第一次出现的位置，若不写pos，默认为pos=0。如果找不到，返回-1，注意需要强制转换为int型才能输出-1（后面的模拟实现会讲到）
substr(pos,len)	返回从pos位置开始截取最多len个字符组成的字符串，如果从pos开始的子串长度不足len，则截取这个子串
insert(index,count,str)	在index出连续插入count次字符串str
insert(index,str)	在index处插入字符串str
erase(index,count)	将字符串从index位置开始（含）的count个字符删除，若不传参给count，则表示删除index位置及以后的所有字符
replace(pos,count,str)	把从pos位置开始count个字符的子串替换为str
replace(first,last,str)	把以first开始（含）、last结束（不含）的子串（左闭右开区间）替换为str，其中first和last均为迭代器
empty( )	判断字符串是否为空，如果为空返回1，不为空则返回0

二、底层实现

        以下是 C++ STL 中 std::string 类相关运算符和成员函数的底层实现原理的详细说明。由于标准库的具体实现因编译器而异（如 GCC 的 libstdc++ 或 LLVM 的 libc++），此处描述的是通用的设计思路和典型实现方式。

---

1、运算符重载的底层实现

1. operator+（字符串连接）

• 功能：将两个字符串连接成一个新字符串。

• 底层实现：

  std::string operator+(const std::string& lhs, const std::string& rhs) {std::string result;result.reserve(lhs.size() + rhs.size()); // 预分配内存result = lhs;                            // 复制左操作数result.append(rhs);                      // 追加右操作数return result;
  }

  • 创建新字符串对象，分配足够内存（lhs.size() + rhs.size()）。

  • 依次复制左、右操作数的字符内容。

  • 返回新对象（可能触发移动语义优化，避免深拷贝）。

2. operator==（相等比较）

• 功能：判断两个字符串内容是否相同。

• 底层实现：

  bool operator==(const std::string& lhs, const std::string& rhs) {if (lhs.size() != rhs.size()) return false;       // 长度不同直接返回 falsereturn memcmp(lhs.data(), rhs.data(), lhs.size()) == 0; // 逐字节比较
  }

  • 先比较长度，长度不同直接返回 false。

  • 使用 memcmp 快速比较内存块。

3. operator< 和 operator>（字典序比较）

• 功能：按字典序比较字符串。

• 底层实现（以 < 为例）：

  bool operator<(const std::string& lhs, const std::string& rhs) {size_t min_len = std::min(lhs.size(), rhs.size());int cmp = memcmp(lhs.data(), rhs.data(), min_len); // 比较前 min_len 个字符if (cmp != 0) return cmp < 0;                     // 发现不同字符return lhs.size() < rhs.size();                   // 前面字符全相同，比较长度
  }

  • 逐字符比较，直到找到第一个不同的字符。

  • 若所有字符相同，则长度较短的字符串更小。

---

2、成员函数的底层实现

1. length() 和 size()

• 功能：返回字符串长度。

• 底层实现：

  size_t size() const noexcept {return _size; // 直接返回内部维护的 size 成员变量
  }
  size_t length() const noexcept {return _size; // 通常与 size() 完全等价
  }

  • 直接返回内部存储的 size 值，时间复杂度 O(1)。

2. push_back(char c)

• 功能：在字符串末尾追加一个字符。

• 底层实现：

  void push_back(char c) {if (_size + 1 > _capacity) {      // 容量不足时扩容reserve(_capacity * 2 + 1);   // 通常按指数扩容（如 2 倍）}_data[_size] = c;                 // 写入新字符_size++;                          // 更新长度_data[_size] = '\0';              // 添加终止符（某些实现可能省略）
  }

  • 若容量不足，触发扩容（reserve）。

  • 在末尾写入字符并更新长度，时间复杂度 平摊 O(1)。

3. append(const std::string& str)

• 功能：追加另一个字符串。

• 底层实现：

  std::string& append(const std::string& str) {if (_size + str.size() > _capacity) {reserve(_size + str.size());  // 确保容量足够}memcpy(_data + _size, str.data(), str.size()); // 复制内容_size += str.size();              // 更新长度return *this;
  }

  • 类似 operator+，但直接在原字符串上操作，时间复杂度 O(n)。

4. find(const std::string& str, size_t pos)

• 功能：从 pos 位置开始查找子串 str。

• 底层实现（简化版）：

  size_t find(const std::string& str, size_t pos = 0) const {if (pos > _size || str.size() > _size - pos) return npos;for (size_t i = pos; i <= _size - str.size(); ++i) {if (memcmp(_data + i, str.data(), str.size()) == 0) {return i; // 找到匹配}}return npos;       // 未找到
  }

  • 暴力匹配算法，时间复杂度 O(n*m)（实际可能优化为 KMP 或 Boyer-Moore）。

        在C++中，string::find函数的返回值类型为size_t（无符号整数类型）。当未找到目标时，它返回string::npos，其值实际上是size_t类型的最大值（例如，64位系统中为18446744073709551615）。以下是关键原因：

为什么强制转换为int会输出-1？

1. 无符号到有符号的转换：
   size_t是无符号的，而int是有符号的。当string::npos（即size_t最大值）被强制转换为int时，会发生二进制位的直接截断。
   例如，size_t的18446744073709551615（二进制全1）转换为int时，会解释为补码形式的-1。

2. 实现依赖行为：
   这种转换的结果依赖于平台和编译器。若int为32位，则高位被丢弃，剩余的32位全1即对应-1；若int为64位，则结果可能不同。因此，强制转换并非完全可靠。

示例验证

#include <iostream>
#include <string>
using namespace std;int main() {string s = "abc";size_t pos = s.find("d"); // 未找到，pos = string::nposcout << "直接输出 size_t: " << pos << endl;      // 输出 18446744073709551615cout << "强制转为 int: " << (int)pos << endl;   // 输出 -1return 0;
}

正确做法

1. 直接比较是否等于string::npos：

   if (s.find("xxx") == string::npos) {cout << "未找到" << endl;
   }

2. 避免依赖强制转换：
   强制转换可能导致不可移植性，尤其在跨平台代码中。若必须输出-1，可以显式判断：

   size_t pos = s.find("xxx");
   cout << (pos == string::npos ? -1 : (int)pos) << endl;

总结

• find未找到时返回string::npos（无符号最大值），直接输出会显示大整数。

• 强制转换为int后输出-1，是因为二进制截断触发了补码的符号位机制，但这是实现相关的。

• 推荐使用pos == string::npos进行逻辑判断，而非依赖强制转换后的值。

5. substr(size_t pos, size_t len)

• 功能：返回从 pos 开始的长度为 len 的子串。

• 底层实现：

  std::string substr(size_t pos = 0, size_t len = npos) const {len = std::min(len, _size - pos); // 修正 len 为有效值return std::string(_data + pos, len); // 直接构造新 string
  }

  • 构造新字符串并复制指定区间的字符，时间复杂度 O(len)。

6. insert(size_t index, size_t count, char c) 和 insert(size_t index, const std::string& str)

• 功能：在指定位置插入字符或字符串。

• 底层实现（插入字符串）：

  std::string& insert(size_t index, const std::string& str) {if (index > _size) throw std::out_of_range(...);if (_size + str.size() > _capacity) reserve(_size + str.size());memmove(_data + index + str.size(), _data + index, _size - index); // 后移原有字符memcpy(_data + index, str.data(), str.size());     // 插入新内容_size += str.size();                              // 更新长度return *this;
  }

  • 使用 memmove 处理内存重叠，时间复杂度 O(n)。

7. erase(size_t index, size_t count)

• 功能：删除从 index 开始的 count 个字符。

• 底层实现：

  std::string& erase(size_t index, size_t count = npos) {count = std::min(count, _size - index);          // 修正实际删除长度memmove(_data + index, _data + index + count, _size - index - count);_size -= count;                                  // 更新长度_data[_size] = '\0';                             // 终止符return *this;
  }

  • 用 memmove 将后续字符前移覆盖被删除部分，时间复杂度 O(n)。

8. replace(size_t pos, size_t count, const std::string& str)

• 功能：替换从 pos 开始的 count 个字符为 str。

• 底层实现：

  std::string& replace(size_t pos, size_t count, const std::string& str) {erase(pos, count);                   // 删除旧内容insert(pos, str);                   // 插入新内容return *this;
  }

  • 组合 erase 和 insert，时间复杂度 O(n + m)。

9. empty()

• 功能：判断字符串是否为空。

• 底层实现：

  bool empty() const noexcept {return _size == 0; // 直接检查长度是否为 0
  }

  • 时间复杂度 O(1)。

---

3、关键实现细节

1. 内存管理：

   • 使用动态数组（char* _data）存储字符。

   • 维护 size（当前长度）和 capacity（当前容量）。

   • 扩容时通常按指数增长（如 reserve(2 * _capacity)）以平摊时间复杂度。

2. 短字符串优化（SSO）：

   • 短字符串（如长度 ≤15）直接存储在对象内部，避免堆内存分配。

3. 异常安全：

   • 内存分配失败时可能抛出 std::bad_alloc。

4. 移动语义（C++11）：

   • 移动构造函数直接“窃取”源对象的 _data，避免深拷贝。

三、 String库函数的直接应用

# include <bits/stdc++.h>
using namespace std;
int main()
{//定义、初始化、赋值string s1;  // 定义一个空字符串s1string s2 = "bcd";  // 定义并初始化字符串s2为"bcd"s2 = "efg";  // 将s2重新赋值为"efg"cout << s2 << endl;  // 输出s2的值。输出:efgstring s("abc");  // 定义并初始化字符串s为"abc"string s3(s);  // 定义字符串s3并用s初始化，s3为"abc"//长度cout << s.length() << endl;  // 输出字符串s的长度。输出:3//遍历for (int i = 0; i < s.size(); i++) cout << s[i]; cout << endl;  // 遍历并输出字符串s的每个字符。输出:abc//添加，合并字符串s.push_back('d'); cout << s << endl;  // 在s的末尾添加字符'd'。输出:abcds.append('efg'); cout << s << endl;  // 在s的末尾添加字符串"efg"。输出:abcdefgs = s + 'h'; s += 'i'; cout << s << endl;  // 在s的末尾添加字符'h'和'i'。输出:abcdefghi//用重载的 + 在尾部添加字符。输出：abcdefgh1s = s + "jk"; s += "lmnabc"; s = "xyz" + s; cout << s << endl;  // 在s的末尾添加字符串"jk"和"lmnabc"，并在s的开头添加"xyz"。输出:xyzabcdefghijklmnabc//输出：xyzabcdefghijklmnabcstring s4 = "uvw";  // 定义并初始化字符串s4为"uvw"cout << s + s4 << endl; //合并字符串。输出：xyzabcdefghijklmnabcuvw//查找字符串字符串cout << "pos of b = "<<s.find('b') << endl;  // 查找字符'b'第一次出现的位置。输出:pos of b = 4cout << "pos of ef = "<<s.find('ef') << endl;  // 查找字符串"ef"第一次出现的位置。输出:pos of ef = 8cout << "pos of ab = "<<s.find('ab',5) << endl;  // 从s[5]开始查找字符串"ab"第一次出现的位置。输出:pos of ab = 18cout << "pos of hello = "<<(int)s.find('hello') << endl;  // 查找字符串"hello"第一次出现的位置，未找到返回-1。输出:pos of hello = -1//截取字符串cout << s.substr(3, 5) << endl;  // 从s[3]开始截取5个字符构成的字符串。输出:abcdecout << s.insert(4,"opq") << endl;  // 在s[4]位置插入字符串"opq"。输出:xyzoppqabcdefghijklmnabc//删除、替换cout << s.erase(10,2)<< endl;//从s[10]开始删除两个字符。输出:xyzaopqbcdghijklmnabccout << s.erase(10)<< endl;//从s[10]开始删除后面的所有字符。输出:xyzaopqbcdcout << s.replace(2,3,"1234")<< endl;//把从s[2]开始的3个字符替换为"1234"。输出:xy1234pqbcdcout << s.replace(s.begin() + 7,s.begin() + 9,"5678")<< endl;//把s[7]->s[8]替换为"1234"。输出:xy1234p5678cd//清理、判断cout << s.empty()<< endl;    //判断是否为空，不空返回0，空返回1。输出:0s.clear();    //清空cout << s.empty()<< endl;    //输出:1//比较string s5 = "abc"; string s6 = "abc"; string s7 = "bc";if(s5 == s6) cout << "== "<< endl;if(s5 < s7) cout << "<" << endl;if(s5 > s7) cout << ">" << endl;if(s5 != s7) cout << "!=" << endl;return 0;
}