模拟实现C++ string类：增删查改与内存管理实战

想自己写一个 C 的 string 类这事儿我琢磨了很久。原因很简单日常天天在用标准库的 std::string增删查改闭着眼都会调但真要问你底层是怎么实现的vector 的动态扩容、内存管理、深浅拷贝这些细节反而说不上来。这就像一个天天开车的老司机突然让你自己动手修发动机才发现平时踩的油门和刹车后面全是复杂的机械结构。这篇博文我想聊聊自己动手模拟实现一个 string 类主要实现增删查改功能的过程。我会从结构设计讲到核心函数实现每个关键点都附上实际踩坑记录。适合的人群是 C 基础已经过关、看过标准库源码但想自己动手验证一遍的人也想给正在准备 C 面试、需要深入理解容器底层原理的同学提供一份实战参考。理解了 string 的增删查改怎么实现你基本就摸清了 STL 容器的通用套路内存管理、迭代器、异常安全、性能取舍这些在一百个容器类里都是同样的逻辑。1. 项目整体设计从分析 std::string 的核心行为开始1.1 先定一个自己的“需求文档”动手之前我先梳理了 string 最常见的操作场景把增删查改四个维度拆开看增push_back 尾部追加、append 追加字符串、insert 任意位置插入删pop_back 尾部删除、erase 指定区间删除、clear 清空所有字符查find 查找子串、rfind 反向查找、operator[] 取指定位置字符改operator 赋值、replace 替换指定区间、assign 重新赋值、reserve/capacity 调整容量我的目标不是复制一个完整的 std::string那工作量太大了光小字符串优化 SSO 和各类分配器策略就够写几万行而是实现一个行为正确、逻辑完整的简化版重点吃透内存管理方式和边界处理。1.2 为什么用“连续存储 动态扩容”这套方案string 的底层本质上就是一个动态字符数组和 vector 非常像。我选择了char*指针 size/capacity三个成员变量这是最直观也最接近教科书思路的方式class MyString { private: char* _str; // 指向堆内存的指针 size_t _size; // 有效字符个数不包含\0 size_t _capacity; // 当前容量包含\0的总空间 };我在设计时看了很多 STL 源码分析的资料标准库的 string 通常包含_str、_size、_capacity再加上 SSO 用的联合体。这里我刻意省略了 SSO原因是首次实现把核心逻辑搞清楚比优化更重要。先做能跑的版本再做高效的版本这个顺序是实操出来的经验。1.3 模拟实现要避开的“坑”不要幻想一步到位我最初也想把标准库的所有接口都实现一遍后来发现这根本不是一个人短期内能完成的事情。std::string光与迭代器相关的重载版本就有七八个再加上c_str()、data()、比较运算、输入输出流重载全做完至少要两千行。我给自己划了一条清晰的边界线实现基础增删查改接口行为与std::string对齐对于find只实现str查找和char查找不做五参数带 pos 的版本虽然实际要做也很简单后面会讲不支持 SSO 优化、不支持迭代器接口实际上用数组索引访问就够了边界清晰了后面实现起来就快很多。2. 核心结构内存管理与构造析构2.1 构造函数的完整实现构造函数是第一个容易出错的点。默认构造、带参构造、拷贝构造、赋值四类构造各有各的坑。先看代码class MyString { public: // 默认构造空字符串也要有\0不能给空指针 MyString() : _str(new char[1]{\0}), _size(0), _capacity(0) {} // 带参构造用 C 风格字符串初始化 MyString(const char* str) : _size(strlen(str)), _capacity(strlen(str)) { _str new char[_capacity 1]; strcpy(_str, str); } // 拷贝构造深拷贝避免浅拷贝导致 double free MyString(const MyString s) : _size(s._size), _capacity(s._capacity) { _str new char[_capacity 1]; strcpy(_str, s._str); } // 析构函数 ~MyString() { delete[] _str; _str nullptr; _size _capacity 0; } private: char* _str; size_t _size; size_t _capacity; };默认构造这里我踩过第一个坑最开始我把默认构造函数写成_str(nullptr), _size(0)结果c_str()返回空指针外面用 printf 打印直接崩溃。真实的 string 必须保证内部始终维护一个有效的\0终止符哪怕是空字符串。这也是std::string的标准做法总是多开一个字符的空间存\0。2.2 拷贝构造必须深拷贝这是一个“经典事故”浅拷贝就是把_str指针直接复制给新对象两个对象指向同一块内存析构时先析构的对象delete[]另一个对象再析构就变成悬垂指针去释放同一块堆内存直接double free崩溃。这个我心有余悸调试时无论如何都排不到根因最终用gdb查了调用栈才确认是析构连续执行了两次。深拷贝方案虽然开销更大但语义正确。如果追求效率后续还能用写时拷贝COW改造不过 COW 在多线程下有严重的数据竞争问题这也是为什么 C11 之后标准库都逐步去掉了 COW。我的建议是理解深拷贝是正道COW 听听就好千万别在生产代码里用。2.3 赋值运算符先释放再拷贝还是先拷贝再释放赋值运算符是另一个高频考点因为它要考虑自赋值的情况MyString operator(const MyString s) { if (this ! s) { // 1. 自赋值检查 char* tmp new char[s._capacity 1]; // 2. 先开新空间 strcpy(tmp, s._str); // 3. 拷贝新内容 delete[] _str; // 4. 释放旧空间 _str tmp; // 5. 接管新空间 _size s._size; _capacity s._capacity; } return *this; }这里的关键是“先开新空间、再释放旧空间”。如果顺序反过来先delete[] _str再new char[]一旦new抛出bad_alloc异常当前对象就处于内存丢失状态。正常先 new 再 delete就算 new 失败旧内容还在对象状态依然有效最多是赋值没成功程序不会继续带着损坏状态跑。虽然是模拟实现但异常安全的条件保证strong exception guarantee从一开始就应该养成习惯。3. 增操作实现push_back、append 与 insert3.1 扩容机制为什么每次按 2 倍增容增操作的核心在于扩容策略。push_back在尾部追加一个字符时如果_size _capacity必须要扩容。常见的扩容倍率有三种1.5 倍、2 倍、固定增量。我用了 2 倍这条经典路线void reserve(size_t newCapacity) { if (newCapacity _capacity) { char* tmp new char[newCapacity 1]; // 多出来的1存 \0 if (_str ! nullptr) { strcpy(tmp, _str); // 拷贝原内容 } delete[] _str; _str tmp; _capacity newCapacity; } } void push_back(char c) { if (_size _capacity) { size_t newCapacity _capacity 0 ? 4 : _capacity * 2; reserve(newCapacity); } _str[_size] c; _str[_size] \0; // 时刻保证字符串结尾带 \0 }为什么固定按 2 倍而不是每次只扩容 1 个字节因为重新分配内存需要申请新空间、拷贝 N 个字符、释放旧空间这三个操作的总成本是 O(N)。如果每次 push 都做一次 O(N) 操作连续 push N 次的总成本就是 123...N O(N²)这效率没人接受。而按倍率扩容扩容次数是 log N 次总成本是 124...N ≈ 2N均摊下来每次 push 就是 O(1)这就是均摊复杂度的概念。3.2 append 追加字符串复用扩容再逐字符拷贝append本质上可以看作多次 push_back但我们不真的一个字符一个字符地去 push因为那样会频繁检查容量。更高效的做法是一次容量检查一次内存拷贝MyString append(const char* str) { size_t len strlen(str); if (_size len _capacity) { reserve(max(_size len, _capacity * 2)); // 至少保证能装下 } strcpy(_str _size, str); // 从尾部开始拷贝 _size len; return *this; }第二次拼接到尾部时strcpy(_str _size, str)会在目标字符串结束后自动加\0这里依然不需要手动再补一个\0。同样地operator 函数可以直接返回append这是最省事的复用方式。3.3 insert 在中间插从后往前挪数据的经典技巧insert是增操作里最容易写错的函数核心思路是“从后往前搬移”。问题在于在位置pos插入len个字符后原来pos到_size之间的字符必须整体向后挪len个位置。必须从尾部开始搬如果从 pos 开始向前向后搬后面的字符就会被前面的覆盖数据损坏。MyString insert(size_t pos, const char* str) { assert(pos _size); // pos 不能超过有效长度 size_t len strlen(str); if (_size len _capacity) { reserve(max(_size len, _capacity * 2)); } // 从后往前搬移把原 pos 之后的内容整体后移 len for (size_t i _size len; i pos len; i--) { _str[i] _str[i - len]; } // 在空出的区间填入新字符串 for (size_t i 0; i len; i) { _str[pos i] str[i]; } _size len; _str[_size] \0; return *this; }for (size_t i _size len; i pos len; i--)这行很容易出死循环当poslen为 0 时size_t减到 0 再减就变成最大值18446744073709551615循环不会终止。我在写的时候加了一个断言pos _size来兜底但size_t无符号的特性还是要牢记。如果意识不到这个细节调试时出现诡异的超时问题就很难定位。3.4 增操作中的“容量预补齐”技巧我提一嘴reserve与resize的区别这在增操作里很容易混淆reserve(n)只改变容量不改变_size不改变字符内容resize(n)会改变_size如果 n 大于当前_size会用\0填充新增字符小于则截断模拟实现时我只做了reserve但是如果你要接标准库的用法测试需要知道这两个接口的差异。这也是面试常问的一个点。4. 删操作实现erase、pop_back 与 clear4.1 erase 删除指定区间只做“向前搬移”删除操作比插入简单因为不需要扩容只需要把后面的字符往前挪。麻烦的是要支持两种形式删一个位置、删一个区间[pos, poslen)。MyString erase(size_t pos 0, size_t len npos) { assert(pos _size); if (len npos || pos len _size) { // 删到末尾直接截断 _str[pos] \0; _size pos; } else { // 把 [poslen, _size) 区间的内容搬移到 pos 位置 size_t remain _size - (pos len); for (size_t i 0; i remain; i) { _str[pos i] _str[pos len i]; } _size - len; _str[_size] \0; } return *this; }这个实现有两个细节一是npos的默认值标准库定义是static const size_t npos -1;也就是size_t的最大值表示“一直删到结尾”二是当pos len _size时直接截断避免越界访问。erase(pos)不传第二个参数的场景非常常用基本就等于“删掉从 pos 开始的所有字符”。4.2 pop_back 与 clear最容易被忽略的 \0 维护这两个函数非常简单但一定要写全void pop_back() { assert(_size 0); // 空串不能 pop _size--; _str[_size] \0; // 把尾部字符清理成 \0 } void clear() { _size 0; _str[0] \0; }很多人会忽略在pop_back后补\0。如果只让_size--不处理\0后续调用c_str()虽然因为_size的约束不会读越界但如果你把_str直接传给 C 函数它按\0判断字符串结尾就会读过头。C 的 string 要和 C 接口无缝互通必须始终维护终止符。这是一个严谨性体现的细节。4.3 移动后是否需要清空原对象这个虽然在模拟实现里没写到但面试经常会问 vector 的 erase 与 string 的 erase 在移动元素时有什么区别。对 string 来说删除一个区间后后面的字符往前挪逻辑上旧位置的数据变成了“没用”的垃圾值。严格来说不清理这些垃圾值不会错因为_size已经缩了访问不到。但如果你开了 AddressSanitizer有时候会把这种未定义行为标记出来。标准库实现通常也会把尾部残留字符置为无效值这有利于调试时发现问题。5. 查操作实现find、rfind 与 operator[]5.1 朴素匹配从朴素算法开始理解字符查找很简单直接遍历。子串查找有两种实现路线朴素匹配BF和 KMP 算法。我的模拟实现用了朴素算法因为在字符集小、字符串短的应用场景下性能完全够用而且代码简单容易验证。KMP 的 next 数组写错一个 corner case排查成本远高于收益。size_t find(const char* str, size_t pos 0) const { assert(str ! nullptr); size_t len strlen(str); if (len 0) return pos; // 空串直接返回 pos if (pos _size) return npos; // pos 越界返回 npos // 外层循环控制起始位置内层逐字符比较 for (size_t i pos; i len _size; i) { size_t j 0; while (j len _str[i j] str[j]) { j; } if (j len) return i; // 完全匹配返回起始下标 } return npos; // 没找到返回 npos }这里有一个性能优化的点外层循环只需要遍历到i len _size为止如果剩余字符数量都不足子串长度肯定匹配不上就不用再比了。这是朴素匹配最容易漏的边界。5.2 为什么需要 npos找不到时不能返回 -1很多初学者会问find 没找到返回什么直接返回 -1 能行吗C 标准库给的答案是npos定义为static const size_t npos -1;即size_t的最大值。这是因为索引类型是无符号的返回 0 表示找到了第一个字符返回负数不可能所以用无符号最大值当“找不到”的哨兵值。需要注意npos是const static size_t在 C17 之前如果要在类内初始化需要类外定义一下否则可能引发链接错误。虽然现在标准已经改进但老编译器上还是可能踩雷。bool starts_with(const char* str) const { size_t len strlen(str); if (len _size) return false; return strncmp(_str, str, len) 0; }顺带一提starts_with是 C20 才引入的接口但在模拟实现里自己写一个判断非常简单。这种“查”的语义值得自己动手补全能加深对查找边界条件的理解。5.3 operator[] 的两个版本const 与非 constoperator[]看似简单但有 const 重载的需求char operator[](size_t pos) { assert(pos _size); return _str[pos]; } const char operator[](size_t pos) const { assert(pos _size); return _str[pos]; }非 const 版本返回char因为外部可能要修改内容const 版本返回const char保证只读不写。这也是 STL 容器的通用约定凡是需要返回元素引用的接口通常都有两个重载版本。容器本身是 const 的时候调用的方法也要是 const 的否则语法层面上就过不去。6. 改操作实现replace、assign 与扩容整理6.1 replace 替换区间字符串替换的本质是“先删再插”。我实现 replace 时直接复用了 erase 和 insertMyString replace(size_t pos, size_t len, const char* str) { assert(pos _size); // 处理“替换长度超过剩余字符”的情况截断到剩余长度 if (pos len _size) { len _size - pos; } // 核心操作: 先删除 [pos, poslen)再插入新内容 erase(pos, len); insert(pos, str); return *this; }这是最干净的实现方式正确性先保证性能不是这个阶段最优先的。如果要优化可以直接拼接新字符串到最终结果一次性完成内存调整但逻辑复杂度会显著上升。初学者用“先删后插”更容易验证正确性。6.2 assign定位置新填充assign 与 operator 的区别是assign 可以用assign(str, pos, len)只取源字符串的一部分来赋值。我的实现简化到只做常见形式MyString assign(const char* str) { size_t len strlen(str); // 如果当前容量够用直接覆盖否则扩容后覆盖 if (len _capacity) { delete[] _str; _str new char[len 1]; _capacity len; } strcpy(_str, str); _size len; return *this; }一个细节assign 后字符串内容是新的但容量不缩小这就是标准库设计上的一个策略。频繁 assign 不同长度的内容场景下如果每次都重新分配内存会白白增加大量 malloc/free 开销。保留容量是高效的前提是你能接受内存占用。这也是 string 与普通 C 风格字符串管理的一个重要差异。6.3 容量策略缩容要不要做与 vector 类似string 默认不做缩容。原因是缩容需要重新申请内存、重新拷贝、释放旧空间成本很高而缩容后如果再增容很快又需要扩容。长期稳定的大内存占用与频繁分配之间的权衡STL 选择了默认不缩容。你如果想要类似shrink_to_fit的语义标准库也确实提供了这个接口但需要明确调用且实现不保证一定能缩容。我的模拟实现中写了一个简化版void shrink_to_fit() { if (_size _capacity) { char* tmp new char[_size 1]; strcpy(tmp, _str); delete[] _str; _str tmp; _capacity _size; } }这个功能我只用来做内存整理测试不常调用。理解“为什么不缩容”比知道怎么缩容更重要。7. 增删查改之外的“隐性接口”交换与比较7.1 swap看似简单实际降低开销很大std::string有专门的 swap 成员函数本质是交换三个成员变量的值而不是拷贝整个字符串。我实现时直接用了内置的 swapvoid swap(MyString s) { std::swap(_str, s._str); std::swap(_size, s._size); std::swap(_capacity, s._capacity); }三条指针交换代替整个字符数组拷贝这个优化在大型字符串下非常明显。很多新手把 swap 写成先拷贝 a 到临时变量、再拷贝 b 到 a、再拷贝临时变量到 b那是 O(N) 的复杂度。正确做法永远是指针交换O(1)。7.2 比较运算符复用 strcmp 与长度检查比较运算符我建议用strcmp来实现因为strcmp本身就是按照字典序比较的bool operator(const MyString s) const { return _size s._size strcmp(_str, s._str) 0; } bool operator(const MyString s) const { return strcmp(_str, s._str) 0; }operator先比较长度是个好习惯。如果长度都不同就没必要再逐字符比较了字符串内容肯定不相等。这个提前检查能减少不必要的内存读取开销。运算符直接靠strcmp的返回值就能完成字典序判断逻辑完全一致。8. 常见内存错误与调试技巧实录8.1 深浅拷贝导致的 double free这个问题我在 2.2 节提过场景。真实调试过程是程序运行结束析构时报错“munmap_chunk(): invalid pointer”开始完全摸不着头脑。后来用gdb查看发现 Report 出现在析构函数里两个对象的_str指向同一地址。这个经验就让“拷贝构造和赋值必须深拷贝”这个结论永不忘记。8.2 越界写入 \0 导致字符串内容神秘丢失我在写insert时曾经漏写了_str[_size] \0导致在 insert 后检查c_str()时发现输出不完整。查了很久才发现是尾部的\0被 insert 的数据覆盖了而_size又没同步更新最后的终止符丢失。这个问题其实就是“在_size变化时必须重新维护\0位置”这一原则的体现。所有增删操作都要在你修改完有效内容后主动把_str[_size]置为\0。8.3 检查工具Valgrind 与 AddressSanitizer一个快速验证内存错误的方法是编译时开启 AddressSanitizerg -fsanitizeaddress -g my_string.cpp -o my_string ./my_string开启后程序一旦越界读写、释放错误内存会直接报告具体代码行号。我第一次跑 AddressSanitizer 时报了一个 heap-use-after-free正是深浅拷贝问题。平时写代码有个好习惯每次写完一个类的核心功能跑一遍 ASan 再继续往下开发这样问题都是小问题积累到后面就麻烦了。8.4 常见问题速查表问题现象可能原因排查方向析构崩溃浅拷贝导致重复释放检查拷贝构造与赋值输出乱码\0未维护检查所有增删操作结尾find 返回异常pos len溢出或越界检查外层循环边界内存泄漏new没有对应delete[]ASan Valgrindinsert 死循环size_t无符号越界到最大值检查循环反向遍历条件赋值后旧数据丢失先 delete 再 new 顺序反了检查异常安全顺序9. 测试用例用真实场景验证增删查改9.1 基础功能测试写模拟实现的收尾工作永远是测试。我写了一段驱动代码覆盖了几乎每种操作的基本路径和边界路径int main() { MyString s; s.push_back(H); s.push_back(e); s.push_back(l); s.push_back(l); s.push_back(o); assert(s.c_str() string(Hello)); s.append( World); assert(s.c_str() string(Hello World)); s.insert(5, , C); // “Hello, C World” assert(s.c_str() string(Hello, C World)); s.erase(5, 4); // 删除“, C” - “Hello World” assert(s.c_str() string(Hello World)); size_t pos s.find(World); assert(pos 6); s.replace(6, 5, C); assert(s.c_str() string(Hello C)); s.pop_back(); assert(s.c_str() string(Hello C)); MyString copy s; // 拷贝构造 MyString assignStr; assignStr copy; // 赋值 assert(assignStr.c_str() s.c_str()); cout All tests passed! endl; return 0; }如果你在跑用例时发现最后一个assert失败了第一反应别去猜直接在关键操作后打印_str和_size马上就能看到是哪一步数据不对。我在做测试时养成了一个习惯写一个debugPrint()函数打印_str、_size、_capacity三个值所有操作测完以后这个函数帮我定位了至少一半的问题。10. 性能与下一步扩展10.1 当前实现的性能瓶颈我做完第一版后简单 benchmark 了一下发现与std::string的差距主要在以下几点缺少 SSO 优化短字符串也走堆内存分配每次创建字符串都有一次 malloc 调用扩容倍率固定是 2标准库通常用 1.5 倍到 2 倍之间的策略配合内存池优化无内存对齐标准库的分配器会考虑对齐尽量减少内存碎片find 用的是朴素匹配KMP 或 BM 在长字符串、多匹配场景下更快10.2 可以挑战的进阶方向如果你想把模拟实现推得更深可以按顺序做这几件事实现 KMP 查找把find的时间复杂度从 O(NM) 降到 O(NM)给类加入迭代器接口让它可以配合std::find、std::sort等算法使用实现 SSO 小字符串优化短字符串直接存栈上避免堆分配写一个简单的内存池分配器模拟标准库的低开销扩容10.3 一个关于“模拟实现”的最终建议模拟实现最大的收益是“把自己放在实现者的位置上思考”。当你觉得insert在中间位置插字符只需要搬一搬家的时候你就不会写出每次都全量拷贝的愚蠢版本。当你亲自跑了 ASan亲手解决过一次 double free 之后你对深浅拷贝的理解就不是背出来的而是刻进骨子里的。我个人实际体会是花一个周末实现这个 string 类比刷二十道链表题更能打通 C 的内存模型和容器设计思路。别想着一次到位先跑通所有测试用例再考虑优化这是最稳妥的路径。接下来我大概会继续写 vector 的模拟实现思路和这次差不多但会在内存分配上多花些心思做对比实验到时候有新的结论再来分享。