【LeetCode-C-Container】string

`substr`

`substr()` 的底层原理与用法详解

substr() 是 C++ 中 std::string 类的成员函数，用于从原字符串中提取子字符串。以下是其底层原理和使用方法的详细说明：

函数签名

string substr(size_type pos = 0, size_type len = npos) const;

参数：
- pos：子字符串的起始位置（默认为 0，即字符串开头）。
- len：子字符串的长度（默认为 npos，即从 pos 到原字符串末尾的所有字符）。
返回值：新构造的 std::string 对象，包含提取的子字符串。

底层原理

内存分配与复制：
- 当调用 substr() 时，函数会根据 pos 和 len 确定需要复制的字符范围。
- 新字符串会分配独立的内存空间，并将原字符串中对应的字符数据深拷贝到新内存中。
- 例如，原字符串 s = "HelloWorld"，调用 s.substr(5, 3) 会创建一个新字符串 "Wor"，其内存与原字符串完全独立。
参数处理逻辑：
- 如果 pos > s.size()，抛出 std::out_of_range 异常。
- 如果 len 超过原字符串剩余长度（s.size() - pos），则自动截断到原字符串末尾。
- 示例：
```
std::string s = "ABCDEF";
s.substr(2, 3);   // 返回 "CDE"（pos=2，len=3）
s.substr(4, 10);  // 返回 "EF"（len 被截断为 2）
```
时间复杂度：
- 时间复杂度为 O(len)，因为需要逐个复制字符到新字符串。

用法示例

基本用法：

#include <string>
#include <iostream>

int main() {
    std::string s = "HelloWorld";
    std::string sub1 = s.substr(5);      // sub1 = "World"（从索引5到末尾）
    std::string sub2 = s.substr(0, 5);   // sub2 = "Hello"（前5个字符）
    std::cout << sub1 << " " << sub2;    // 输出 "World Hello"
}

处理边界条件：

std::string s = "12345";
// 安全调用：检查 pos 是否越界
if (pos <= s.size()) {
    std::string sub = s.substr(pos, len);
} else {
    // 处理错误
}

默认参数行为：

std::string s = "C++";
s.substr();     // 返回整个字符串 "C++"
s.substr(2);    // 返回 "++"

异常与错误处理

pos 越界：如果 pos >= s.size()，抛出 std::out_of_range 异常。
len 越界：若 len 超过剩余字符数，自动截断到末尾，不抛出异常。

示例：

try {
    std::string s = "abc";
    std::string sub = s.substr(5); // 抛出异常
} catch (const std::out_of_range& e) {
    std::cerr << "Error: " << e.what(); // 输出 "Error: basic_string::substr"
}

性能优化建议

避免频繁调用：
- 频繁调用 substr() 生成大量子字符串可能导致内存和性能开销（深拷贝）。
- 优化方案：使用 std::string_view（C++17 引入）避免复制：
```
#include <string_view>
std::string s = "HelloWorld";
std::string_view sv = s;
std::string_view sub = sv.substr(5, 5); // 零拷贝，sub引用原数据
```

预分配内存：

如果已知子字符串长度，可以预先分配目标字符串的内存：

std::string s = "Data";
std::string sub;
sub.reserve(3); // 预分配内存
sub = s.substr(1, 3); // 减少可能的重新分配

与其他方法的对比

方法	特点
`substr()`	返回独立字符串，安全但可能低效（深拷贝）
`std::string_view`	轻量级只读视图，零拷贝，但不管理内存，需确保原字符串生命周期足够长
指针/迭代器	直接操作内存，高效但需手动管理边界

总结

底层原理：substr() 通过深拷贝生成新字符串，时间复杂度为 O(len)。
核心用法：指定 pos 和 len 提取子串，注意处理边界条件和异常。
优化场景：高频调用时优先使用 std::string_view 或预分配内存。

`reserve`

使用 .reserve() 预分配内存的主要意义在于优化字符串或容器的性能，具体体现在以下几个方面：

减少内存重分配次数

当频繁向字符串或容器（如 std::string、std::vector）添加元素时，其底层内存可能因容量不足而反复扩容。每次扩容都会触发以下操作：

申请更大的内存块
将旧数据拷贝到新内存
释放旧内存
这一过程的时间复杂度为 O(n)，频繁操作会导致性能显著下降。
通过预先调用 .reserve(n)，可以一次性分配足够的内存空间，避免后续多次扩容。例如，若已知需要存储 1000 个字符，直接预留相应容量可将时间复杂度优化为 O(1)。

避免迭代器失效

内存重分配会导致指向原内存的指针、引用或迭代器失效（例如 std::vector 的插入操作可能使迭代器失效）。预分配内存后，只要操作不超过预留容量，迭代器将保持有效，从而提高代码的稳定性和安全性。

优化内存使用效率

防止过度分配：某些容器（如 std::string 和 std::vector）的默认扩容策略可能按指数级增长（例如每次扩容为当前容量的 2 倍）。这可能导致内存浪费，尤其是当最终数据量远小于预留容量时。手动指定合理容量可减少内存碎片和冗余。
避免共享内存的影响：当多个字符串共享同一块内存时（通过写时复制技术），调用 .reserve() 会强制分配独立内存，确保后续修改不会影响其他共享对象。

性能对比示例

std::string str;
str.reserve(1000);  // 预分配
for (int i = 0; i < 1000; ++i) {
    str += 'a';    // 无内存重分配
}

未使用 .reserve() 时，上述循环可能触发多次扩容（例如从初始容量 15 逐步扩容到 30、60、120…），而预分配后仅需一次内存分配。

与 `resize()` 的区别

需注意 .reserve() 仅影响容量（capacity），不改变实际元素数量（size）。若需同时调整容量和元素数量（例如初始化默认值或截断数据），应使用 .resize()。

适用场景建议

已知数据量上限：例如读取文件前预分配缓冲区。
高频数据追加：如日志记录、流式处理。
性能敏感代码：实时系统或大规模数据处理。

总结来说，.reserve() 通过预分配内存，将不可预测的多次内存操作转化为一次可控的分配，是优化 C++ 程序性能的关键手段之一。

`resize`

`std::string` 的 `resize` 函数可能改变容量（capacity），但具体是否改变取决于操作类型：

1. 当 `resize` 扩大字符串时：

会改变容量：如果新的 size 超过了当前容量（capacity），resize 会触发内存扩容。此时，容器的容量会根据实现策略自动增大（例如，可能按指数级增长或倍增策略）以容纳新的大小。
新增元素初始化：新增的部分会根据第二个参数（若有）填充指定字符，否则默认填充空字符 '\0'。
示例（来自网页1和4）：
```
std::string s("hello");
s.resize(20);  // 原capacity为15，扩容后可能变为30
```
此时 size 变为20，capacity 可能从15扩容到30。

2. 当 `resize` 缩小字符串时：

不改变容量：仅截断多余元素，size 减小，但 capacity 保持不变。例如，原 size 为11的字符串缩小到5后，capacity 仍为15。
示例（来自网页1和5）：
```
std::string s("hello world");
s.resize(5);  // size变为5，capacity仍为15
```

3. 与 `reserve` 的区别

resize 直接影响 size 和可能的 capacity，而 reserve 仅调整 capacity（当参数大于当前容量时扩容，否则无操作）。
reserve 不会初始化或修改 size，仅预留内存空间以提高后续操作的效率。

总结

resize 的主要作用是调整 size，但在需要扩容时会同步改变 capacity。
容量缩小的唯一方式是通过 shrink_to_fit（非强制），而 resize 本身不会主动缩小容量。

如需进一步优化性能，可结合 reserve 预分配容量，避免频繁扩容。

substr

substr() 的底层原理与用法详解