C++算法
C++ string 模拟实现与底层细节深度解析
深入剖析 C++ string 类的模拟实现过程。涵盖内存管理（构造/析构）、深拷贝机制（拷贝构造/赋值重载）、基础操作接口（reserve/push_back/append 等）、查找与子串操作、访问类接口及运算符重载。重点讲解动态扩容策略、无符号整数溢出处理、流插入/提取运算符的全局函数实现，以及避免浅拷贝和死循环的关键细节。旨在帮助开发者理解 string 底层逻辑与 C++ 类设计核心思路。
深入剖析 C++ string 类的模拟实现过程。涵盖内存管理（构造/析构）、深拷贝机制（拷贝构造/赋值重载）、基础操作接口（reserve/push_back/append 等）、查找与子串操作、访问类接口及运算符重载。重点讲解动态扩容策略、无符号整数溢出处理、流插入/提取运算符的全局函数实现，以及避免浅拷贝和死循环的关键细节。旨在帮助开发者理解 string 底层逻辑与 C++ 类设计核心思路。
string是 C++ 中最常用的字符串工具，但多数人只懂用、不懂其底层逻辑。本文带你手搓一个简易 string：从内存管理的构造/析构，到深拷贝的拷贝构造/赋值重载，再到基础接口封装，帮你吃透 string 的核心机制，同时掌握 C++ 类设计的关键思路。
在实现 string 前，为了避免和库中冲突，我们需要定义一个命名空间：
namespace ljh { class string { }; }
我们要实现的简易 string 的底层实际是动态顺序表，所以，需要定义一个字符指针去指向字符串，同时还得搭配记录当前字符串长度和存储空间容量的变量，这样后续才能通过动态调整字符指针指向的堆内存空间，实现字符串的增删改等操作。
namespace ljh { class string { private: size_t _size; size_t _capacity; char* _str; };
同时我们在上一篇的学习中发现，标准库的 string 类里还定义了一个 npos 静态共有成员变量，它主要用于作为某些接口的缺省参数，以及在查找类操作中表示'未找到'的结果标识。
namespace ljh { class string { private: size_t _size; size_t _capacity; char* _str; public: static size_t npos; };
size_t string::npos = -1; // 库中的定义就是无符号整数的 -1 也就是无符号整数的最大值
以上就是我们在实现各类接口之前，搭建好的整体框架了。
// 全缺省构造函数：支持无参调用（默认空字符串），或传入 C 风格字符串
string(const char* str) {
_size = strlen(str); // 计算字符串长度（不包含末尾的\0）
_capacity = _size; // 容量初始化为当前字符串长度
_str = new char[_capacity + 1]; // 分配空间：额外多 1 个字节存\0
// 【注意】strcpy 的特性：会自动拷贝到源字符串的\0为止（包括\0本身）
// 但如果源字符串中间包含\0，strcpy 会提前终止，导致拷贝不完整
// 当然对于标准 C 风格常量字符串（仅末尾含 \0）的场景，strcpy 能正常完成拷贝
// 但是出于代码的统一性，所以我整个 string 拷贝相关的代码都用的是 memcpy
// strcpy(_str, str);
// 改用 memcpy：按指定字节数（有效字符数 + 1 个\0）拷贝，避免上述问题
memcpy(_str, str, _size + 1);
}
// 析构函数
~string() {
delete[] _str;
_str = nullptr;
_size = _capacity = 0;
}
【传统写法】
string(const string& s) {
_str = new char[s._capacity + 1];
memcpy(_str, s._str, s._size + 1);
_size = s._size;
_capacity = s._capacity;
}
由于 string 类包含动态申请的资源（比如 _str 指向的堆内存），因此不能使用浅拷贝（浅拷贝仅复制指针地址，会导致多个对象共用同一块内存，引发析构时重复释放等问题），必须实现深拷贝：先为新构造的对象单独开辟一块与原对象容量匹配的内存空间，再将原对象的字符串数据完整拷贝到新空间中。
需要注意：这里不能使用 strcpy 函数 —— 因为 strcpy 是按'遇到 \0'就停止'的规则拷贝，若原字符串中存在\0（比如类似"hello\0!!!!!!!!!!"这种包含内嵌\0的情况），strcpy 会只拷贝到第一个\0为止，无法完整复制所有数据。因此代码中用memcpy（按指定字节数拷贝），确保连\0在内的所有数据都被完整复制。
【现代写法】
void swap(string& s) {
std::swap(_str, s._str);
std::swap(_size, s._size);
std::swap(_capacity, s._capacity);
}
// 拷贝构造（现代写法）
string(const string& s) :_str(nullptr), _size(0), _capacity(0) {
string tmp(s._str);
swap(tmp);
}
由于要用到 swap 接口，所以我先在前面提前写好这个成员函数（其实用算法库的 std::swap 也可以，但咱们 string 类里已经实现了这个接口，就直接用成员函数版本）。
假设我们要用对象 s 拷贝构造一个新对象 s1（方便后面描述），现代写法的思路是：先构造一个和 s 内容完全一致的临时对象 tmp，接着让 s1 和 tmp 交换资源。但要注意：不能直接交换两个 string 对象—— 如果直接交换对象，会触发一次拷贝构造和两次赋值运算符重载（这俩操作都是深拷贝，开销很大）；而只交换对象的成员变量（_str、_size、_capacity），本质是 3 次内置类型（指针、整数）的交换，几乎没有额外开销。
整体逻辑就是'让 tmp 干脏活'：深拷贝的工作全交给 tmp 做，要是这过程中出了问题（比如内存分配失败），也只会影响 tmp，不会波及目标对象 s1；等 tmp 把深拷贝的资源准备好，s1 直接通过交换'坐享其成'拿到资源；最后函数结束，tmp 出了作用域会自动销毁，顺带把交换过来的'空资源'（s1 初始化时的默认值）清理掉，不会有任何残留。
切记：在交换之前，一定要先对目标对象（比如这里的 s1）的成员变量做初始化（比如把 _str 设为 nullptr、_size 和_capacity 设为 0）。否则如果直接拿未初始化的成员去交换，会导致野指针、随机值等未定义行为，后续 tmp 销毁时还可能误释放非法资源。
但是，现代写法在含\0的字符串场景有缺陷：依赖 C 风格字符串构造的临时对象会以\0截断内容，无法完整拷贝\0后的字符，而传统写法按_size遍历复制可避免此问题。
【传统写法】
string& operator=(string& s) {
// 如果两个不相等
if (*this != s) {
char* tmp = new char[s._capacity + 1];
memcpy(tmp, s._str, _size + 1);
delete[] _str;
_str = tmp;
_size = s._size;
_capacity = s._capacity;
}
return *this;
}
传统写法的逻辑是：先为新数据开辟独立内存，把 s 的内容完整拷贝过去；接着释放当前对象原来的内存，让当前对象的指针指向新内存；最后同步更新长度和容量 —— 这样既完成了深拷贝，也避免了浅拷贝的资源共享问题。
【现代写法】
先讲错误写法：构造出 tmp 对象后直接交换两个 string 对象，这种写法完全错误 —— 因为赋值运算符里调用 std::swap 时，std::swap 内部会调用赋值运算符，由此陷入'赋值→swap→赋值'的死循环。
而之前拷贝构造的现代写法，虽然可以直接交换对象（只是效率低），但它的前提是临时对象已经通过拷贝构造完成了深拷贝，和这里的错误写法场景不同。
string& operator=(string tmp) {
if(*this != tmp) {
swap(tmp);
return *this;
}
}
最终的现代写法（让 tmp 先通过拷贝构造完成深拷贝，再调用成员函数 swap 交换）是正确的 —— 成员 swap 仅交换内置类型的成员变量，不会触发赋值/拷贝，既避免了死循环，也保证了异常安全。
// 用于预分配内存、扩容容器容量、缩容是非约束行为、不会对创建好的空间进行初始化
void reserve(size_t n) {
// 仅当请求容量超过当前容量时执行扩容操作
if (n > _capacity) {
// 分配新的字符数组，额外+1 用于存储字符串终止符'\0'
// 注意：_capacity 仅记录可存储的有效字符数，不包含终止符
char* tmp = new char[n + 1];
// 将原字符串内容（包括可能存在的中间'\0'）复制到新空间
// _size+1 会将\0 也拷贝过去
memcpy(tmp, _str, _size + 1);
// 释放原空间，防止内存泄漏
delete[] _str;
// 更新字符串指针指向新空间
_str = tmp;
// 更新容量为新分配的大小（不包含终止符的空间）
_capacity = n;
}
}
这里不用 strcpy 拷贝的原因是：strcpy 遇到 '\0' 就会停止拷贝，但如果字符串中间本身就包含 '\0'，用 strcpy 会导致拷贝不完整。而 memcpy 是直接按指定的字符个数来拷贝，能避免这个问题，所以我在所有需要拷贝的地方，都用 memcpy 这个函数。
void push_back(char ch) {
if (_size == _capacity) {
// 2 倍扩容
reserve(_capacity == 0 ? 4 : _capacity * 2);
}
_str[_size] = ch;
++_size;
// 补'\0'
_str[_size] = '\0';
}
void append(const char* str) {
assert(str);
size_t len = strlen(str);
// 如果 len+_size = _capacity 就代表刚好够
// 大于代表空间不够了
if (len + _size > _capacity) {
// 至少扩容到 len+_size
reserve(len + _size);
}
// 由于拷贝 len+1 个字符，所以\0 也被拷贝过去了
memcpy(_str + _size, str, len + 1);
_size += len;
}
该接口我仅实现两种函数重载：一种是在指定位置 pos 插入 n 个字符，另一种是在 pos 位置插入字符串。
在指定位置 pos 插入 n 个字符：
// 在指定位置插入 n 个字符
void insert(size_t pos, size_t n, char ch) {
// pos 等于_size 等于尾插
assert(pos <= _size);
// 扩容逻辑
if (_size + n > _capacity) {
// 这块不能随便二倍扩容，因为你也不知道_size + n 是大于 2 倍_size 还是小于
reserve(_size + n);
}
// 挪动数据方法三：
size_t end = _size + 1;
while (end > pos) {
_str[end + n - 1] = _str[end - 1];
end--;
}
// 填充字符
for (size_t i = 0; i < n; i++) {
_str[pos + i] = ch;
}
_size += n;
// 不用给_size 位置加\0，因为挪动数据时\0 也被挪到_size 位置了
}
这个接口最核心的问题出在挪动数据的实现部分，我先给你写一种错误的挪动方式做示例：
size_t end = _size;
while (end >= pos) {
_str[end + n] = _str[end];
end--;
}
这段挪动代码看着没问题，但在 pos=0 的场景下会出严重问题：
当最后一次挪动完成后，
end会减到 - 1—— 但end是无符号整数类型，-1 在无符号数里会直接溢出成该类型的最大值（比如 64 位系统下是18446744073709551615）。这时候循环条件end >= pos（即'最大值>= 0'）会一直成立，代码会陷入死循环，还会访问非法内存导致崩溃。
现在来分析我给出的 3 种相对正确的实现方式：
挪动数据方法一：
int end = _size;
while (end >= (int)pos) {
_str[end + n] = _str[end];
end--;
}
这种写法看似解决了 pos=0 时的问题，但也引入了新隐患：当 _size 超过有符号整数的最大值时，把 _size 转换成 int 类型会发生数值截断，导致后续逻辑出错。
举个例子：假设 _size 为有符号整数最大值 +1：
我用 32 位二进制演示 size_t _size=2147483648 转 int 的截断过程：
步骤 1：size_t 类型的 2147483648 的二进制（32 位无符号数）
2147483648 对应的 32 位二进制是：1000 0000 0000 0000 0000 0000 0000 0000
步骤 2：强制转成 int（32 位有符号数）
32 位有符号数用补码表示：
也就是说 end 直接变成负数了，根本就不会进入循环更别提挪动数据了。
挪动数据方法二：
size_t end = _size;
// end != npos：拦截 end 减到 -1（无符号溢出值）的情况，避免死循环
// end >= pos：只挪动 pos 及之后的字符（含末尾'\0'）
while (end != npos && end >= pos) {
_str[end + n] = _str[end];
end--;
}
这种写法仅通过增加 end != npos 的判断，直接规避了 end 为 - 1（无符号数溢出后的值）时再次进入循环的问题，功能上能精准终止循环，逻辑简单直接；仅需注意注释说明该判断是为了拦截 end 溢出为 - 1 的情况，避免后续维护时误删即可。
挪动数据方法三：
// 挪动数据方法三：
size_t end = _size + 1;
while (end > pos) {
_str[end + n - 1] = _str[end - 1];
end--;
}
这种写法通过将 end 初始化为 _size + 1（包含字符串终止符\0的下一位），结合 end > pos 的显式边界判断，直接规避了无符号数溢出的问题：无需依赖溢出特性，仅通过索引范围控制循环终止，逻辑直观且无隐性规则依赖，是更稳健的挪动实现方式。
在 pos 位置插入字符串：
// 在指定位置插入字符串
void insert(size_t pos, const char* str) {
// pos 必须是有效数据
// pos=_size 是尾插
assert(pos <= _size);
size_t len = strlen(str);
// 扩容
if (len + _size > _capacity) {
reserve(len + _size);
}
// 挪动数据
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] = str[i];
}
_size += len;
}
这个接口的挪动数据逻辑，和前面的实现是一样的，你选自己习惯的方式写就行。
void erase(size_t pos, size_t len = npos) {
// 起始删除位置必须在有效字符范围内，防止越界访问
// 同时避免了_size 为 0 的问题，当_size=0 时，pos 始终小于_size
assert(pos < _size);
// 场景 1：删除从 pos 到字符串末尾的所有字符（len 为默认值 或 待删除长度覆盖剩余全部字符）
if (len == npos || pos + len >= _size) {
// 直接在 pos 位置写入字符串结束符，截断后续字符
_str[pos] = '\0';
// 更新有效字符长度，完成逻辑删除（无需释放内存，仅修改长度标记）
_size = pos;
}
// 场景 2：删除指定长度的字符（len 合法且未覆盖到字符串末尾）
else {
// 计算待删除区间的结束下一个位置（即需要保留的第一个字符位置）
size_t end = pos + len;
// 内存覆盖：将 end 开始的字符依次向前拷贝到 pos 位置，直至覆盖到原结束符
// 循环终止条件包含_size，保证字符串结束符'\0'也被正确迁移
while (end <= _size) {
_str[pos++] = _str[end++];
}
// 更新有效字符长度：减去实际删除的字符数
_size -= len;
}
}
// 开空间、填值、删值（容量不会变化）
void resize(size_t n, char ch = '\0') {
// 删值
if (n < _size) {
_size = n;
_str[_size] = '\0';
}
// 填值
else {
// 如果 n 大于_capacity 才会扩容
reserve(n);
// 从已有的有效数据后开始填
for (size_t i = _size; i < n; i++) {
_str[i] = ch;
}
_size = n;
_str[_size] = '\0';
}
}
void clear() {
_str[0] = '\0';
_size = 0;
}
size_t size() const { return _size; }
size_t capacity() const { return _capacity; }
bool empty() const { return _size == 0; }
void swap(string& s) {
std::swap(_str, s._str);
std::swap(_size, s._size);
std::swap(_capacity, s._capacity);
}
string& operator+=(char ch) {
push_back(ch);
return *this;
}
string& operator+=(const char* ch) {
append(ch);
return *this;
}
该接口复用 push_back 和 append 的逻辑。
// 从字符串 pos 位置开始往后找字符 c
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;
}
// 从字符串 pos 位置开始往后找字符串 str
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;
}
}
第一个接口直接暴力查找，找到就返回对应字符的下标，没找到返回 npos。
第二个接口调用了 C 语言 strstr 函数，如果找到了返回对应位置的指针，没找到返回空指针，找到后想要获取字符串第一个位置的下标可通过指针相减得到。
// 获取子串 从 pos 开始取 len 个字符，如果 len = npos，或者 pos+len 大于字符串长度，取 pos 后面的所有字符
string substr(size_t pos = 0, size_t len = npos) {
assert(pos < _size);
size_t n = len;
// 如果 len = npos 或者 pos+len 大于字符串长度，更新应获取的字符串长度
if (len == npos || pos + len > _size) {
n = _size - pos;
}
string tmp;
// 开空间
tmp.reserve(n);
// 拷贝数据 - 结束条件必须是 n+pos，因为 i 不一定是从 0 开始的
for (size_t i = pos; i < n + pos; i++) {
// 不用考虑'\0'，因为+=已经将'\0'补了
tmp += _str[i];
}
return tmp;
}
class string {
public:
typedef char* iterator;
typedef const char* const_iterator;
iterator begin() { return _str; }
iterator end() { return _str + _size; }
const_iterator begin() const { return _str; }
const_iterator end() const { return _str + _size; }
};
string 的迭代器其实就是'换了个马甲的指针'，谁让 string 底层是字符数组呢，直接拿指针当迭代器遍历，简单粗暴又好用。
重点：迭代器类型必须设成 public！不然藏得严严实实的，外面想用都摸不着门。
反向迭代器暂不展开，需特殊包装才好用。
char& operator[](size_t pos) {
assert(pos < _size);
return _str[pos];
}
const char& operator[](size_t pos) const {
assert(pos < _size);
return _str[pos];
}
这两个 operator[] 分别是读写自由人和锁死编辑权：没加 const 的版本既能看字符也能直接改；加了 const 的版本只能瞅一眼，想改不行。
const char* c_str() const { return _str; }
【写法一】
// 写法 1：
bool operator<(const string& s) const {
size_t i1 = 0;
size_t i2 = 0;
while (i1 < _size && i2 < s._size) {
if (_str[i1] < s._str[i2]) {
return true;
} else if (_str[i1] > s._str[i2]) {
return false;
} else {
++i1;
++i2;
}
}
// 走到这还有这 3 种情况要处理
// "hello" "hello" false
// "helloxx" "hello" false
// "hello" "helloxx" true
// 处理写法 1：
/*if (i1 == _size && i2 != s._size) {
return true;
} else {
return false;
}*/
// 写法 2：
// return i1 == _size && i2 != s._size;
// 写法 3：
// return _size < s._size;
}
【写法二】
bool operator<(const string& s) const {
int ret = memcmp(_str, s._str, _size < s._size ? _size : s._size);
// "hello" "hello" false
// "helloxx" "hello" false
// "hello" "helloxx" true
// 如果 ret==0 考虑上面 3 种情况，否则直接返回结果
return ret == 0 ? _size < s._size : ret < 0;
}
注意：以上两种比较方式，均优先对较短长度的部分进行逐字符比对；若短部分的字符完全一致，则通过'本串长度是否更短'来决定最终结果。
bool operator==(const string& s) const {
return _size == s._size && memcmp(_str, s._str, _size) == 0;
}
两个字符串要相等，需同时满足两个条件：
false；memcmp 逐字符比较所有内容，确保每一位都相同。bool operator<=(const string& s) const {
return *this < s || *this == s;
}
bool operator>(const string& s) const {
return !(*this <= s);
}
bool operator>=(const string& s) const {
return !(*this < s);
}
bool operator!=(const string& s) const {
return !(*this == s);
}
实际只需要实现前两个核心逻辑即可，后面的功能可以直接复用已实现的部分，不用重复编写代码。
ostream& operator<<(ostream& out, const string& s) {
/*for (size_t i = 0; i < s.size(); i++) {
out << s[i];
}*/
for (auto e : s) {
out << e;
}
return out;
}
流插入运算符（<<）不适合重载为类的成员函数 —— 因为成员函数的左操作数会被 *this 占用，会导致使用顺序（比如 cout << s）与预期颠倒。
因此，直接将其重载为全局函数更合理；又因为这里不需要访问类的私有成员，所以也不用声明为友元函数。
istream& operator>>(istream& in, string& s) {
s.clear();
char ch = in.get();
// 处理前缓冲区前面的空格或者换行
while (ch == ' ' || ch == '\n') {
ch = in.get();
}
char buff[128];
int i = 0;
while (ch != ' ' && ch != '\n') {
buff[i++] = ch;
if (i == 127) {
buff[i] = '\0';
s += buff;
i = 0;
}
ch = in.get();
}
if (i != 0) {
buff[i] = '\0';
s += buff;
}
return in;
}
注意：cout和cin这类对象默认是禁止拷贝的，所以在使用时只能传递它们的引用。
这是流提取的错误实现 —— 当输入到空格或换行时，程序会陷入阻塞状态。
因为 cin 的 >> 运算符默认不会读取空格和换行符，这些字符会被当作输入的'结束标识'留在输入缓冲区中；后续的 in >> ch 会一直等待有效字符，从而导致进程阻塞。
这次修改的核心是用 get() 来读取输入 —— get() 是标准输入对象的成员函数，它会读取输入中的所有字符（包括换行符\n和空格），避免了之前 >> 运算符跳过空白字符的问题。
这个版本存在两个主要缺陷：
未清空旧数据，连续读取会拼接混乱：若连续执行多次
cin >> s，新读取的内容会直接拼接到字符串s的旧数据后面（比如第一次读"abc"，第二次读"def"，结果会是"abcdef"），不符合流提取'覆盖旧值'的预期行为。 逐字符拼接导致频繁扩容：每次用s += ch拼接单个字符，当输入字符串较长时，字符串会频繁触发内存扩容（重新分配更大空间、拷贝旧数据），造成不必要的性能损耗。
添加 s.clear() 是为了解决「连续提取两次字符串时，第一次的旧数据没有被覆盖」的问题 —— 比如连续执行 cin >> s1 >> s2，若不先清空 s，第二次读取的内容会拼接在第一次的结果后面，导致数据错误。
当前实现的缺陷：每次通过 s += ch 拼接字符时，若输入的字符串过长，字符串会频繁触发'扩容（重新分配内存、拷贝旧数据）'操作，导致性能损耗较大。
最终版本解决的两个核心问题：
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online