手写简易 STL string｜C++ 字符串底层实现

前言很多人会用std::string但不清楚它底层是一块动态字符数组。本篇博客我们从零实现简化版bit::string实现迭代器、扩容、尾插、追加、插入、下标访问等核心接口吃透顺序容器的设计思想关于 nposnpos 是 string 的静态常量类型是size_t定义写成-1实际是无符号最大值代表不存在的位置staticconstsize_t npos-1;接口实现// 自定义一个命名空间,防止和标准库里的string冲突namespacebit{classstring{public:// 这里放成员函数(各种接口)的声明// ----------------------------------------------// 一些需要频繁调用的函数直接在类内给出实现逻辑// 这里为了博客看起来不冗杂,我就直接单独拎出来写实现逻辑typedefchar*iterator;typedefconstchar*const_iterator;iteratorbegin();iteratorend();const_iteratorbegin()const;const_iteratorend()const;// 构造函数...// 拷贝构造...// 赋值重载...// 析构函数...constchar*c_str()const;voidclear();size_tsize()const;size_tcapacity()const;charoperator[](size_t pos);constcharoperator[](size_t pos)const;//-------------------------------------------------// 其他调用没那么频繁的函数,在类外(声明和定义分离)给出实现逻辑voidreserve(size_t n);voidpush_back(charch);voidappend(constchar*str);stringoperator(charch);stringoperator(constchar*str);voidinsert(size_t pos,charch);voidinsert(size_t pos,constchar*str);voiderase(size_t pos,size_t lennpos);size_tfind(charch,size_t pos0);size_tfind(constchar*str,size_t pos0);stringsubstr(size_t pos0,size_t lennpos);private:char*_strnullptr;size_t _size0;size_t _capacity0;// 加上 static让 npos 成为类的静态常量// 所有 string 对象共享同一份不需要每个对象都存一份节省内存staticconstsize_t npos;};// 现在的位置----bit命名空间中,string类外// static 成员类内只是声明必须在类外面单独定义初始化constsize_t string::npos-1;// 单独定义在命名空间里的全局函数booloperator(conststrings1,conststrings2);booloperator(conststrings1,conststrings2);booloperator(conststrings1,conststrings2);booloperator(conststrings1,conststrings2);booloperator(conststrings1,conststrings2);booloperator!(conststrings1,conststrings2);ostreamoperator(ostreamout,conststrings);istreamoperator(istreamin,strings);// 各种接口的具体实现逻辑...}迭代器 begin / endtypedefchar*iterator;typedefconstchar*const_iterator;iteratorbegin(){return_str;}iteratorend(){return_str_size;}// 函数后const 代表不修改对象const_iteratorbegin()const{return_str;}const_iteratorend()const{return_str_size;}string 的迭代器就是原生的 char* 指针构造 析构 拷贝构造 赋值重载// 构造函数---利用C风格字符串初始化string对象string(constchar*str)// 缺省值为空的C风格字符串,注意是双引号!!{// strlen不计算C风格字符串里的\0_sizestrlen(str);_capacity_size;// 多一个位置是留给\0,为了兼容C风格_strnewchar[_capacity1];// strcpy会拷贝C风格字符串里的\0strcpy(_str,str);}// 析构函数~string(){if(_str){delete[]_str;_strnullptr;}_size_capacity0;}// 深拷贝问题(拷贝构造)//// s2(s1)string(conststrings){_strnewchar[s._capacity1];strcpy(_str,s._str);_sizes._size;_capacitys._capacity;}// 赋值重载stringoperator(conststrings){if(this!s){delete[]_str;_strnewchar[s._capacity1];strcpy(_str,s._str);_sizes._size;_capacitys._capacity;}return*this;} 注意 :为什么构造函数的参数默认值是空字符串而不是nullptr是合法的空 C 风格字符串它在内存里只有一个\0strlen()得到 0后续代码strlen(str)、strcpy可以安全执行如果默认写nullptr不传参数时strnullptr执行strlen(nullptr)直接程序崩溃空指针访问new[容量1]多一个位置保存字符串结束符\0兼容 C 语言c_str()reserve 扩容核心接口// 声明和定义分离时要指定命名空间和类域// 由于这篇博客默认将实现逻辑写在对应命名空间内,所以可以只指定类域// 预先控制底层字符数组的容量voidstring::reserve(size_t n){if(n_capacity){// _capacity不包含\0的位置//// 所以要 new1char*tmpnewchar[n1];// strlen 不包含\0// strcpy 包含\0strcpy(tmp,_str);delete[]_str;_strtmp;_capacityn;}}只开空间、不改变有效数据_size, 只有 n 比当前容量大才扩容push_back 尾插字符、operator (char)voidstring::push_back(charch){// 插入之前先检查是否要扩容if(_size_capacity){// 扩容按照2倍来扩reserve(_capacity0?4:2*_capacity);}_str[_size]ch;_size;// 末尾主动补\0,保证底层始终是合法的C风格字符串_str[_size]\0;}stringstring::operator(charch){push_back(ch);return*this;}复用思想直接调用 push_back避免重复写扩容逻辑append 追加字符串、operator (const char*)// 末尾追加字符串voidstring::append(constchar*str){size_t lenstrlen(str);// 插入前先检查容量if(_sizelen_capacity){// 如果追加后的字符串很长,直接按需要扩容// 如果不长,就按照2倍扩容reserve(_sizelen2*_capacity?_sizelen:2*_capacity);}// 从字符数组最后一个有效元素的后一位开始黏贴strcpy(_str_size,str);_sizelen;}stringstring::operator(constchar*str){append(str);return*this;}insert 插入难点挪动数据// 在任意位置插入字符voidstring::insert(size_t pos,charch){assert(pos_size);// 插入前先检查是否需要扩容if(_size_capacity){reserve(_capacity0?4:2*_capacity);}// 要连同末尾的\0一起拷贝size_t end_size1;// 将pos位置空出来存放要插入的数据while(endpos){// 将pos位置及其以后的数据// 从尾巴开始一个一个往后移动一位_str[end]_str[end-1];end--;}_str[pos]ch;_size;// 末尾主动补\0,保证底层始终是合法的C风格字符串_str[_size]\0;}//------------------------------------------------voidstring::insert(size_t pos,constchar*str){assert(pos_size);size_t lenstrlen(str);// 插入前先检查是否扩容if(_sizelen_capacity){reserve(_sizelen2*_capacity?_sizelen:2*_capacity);}// 要连同末尾的\0一起拷贝size_t end_sizelen;// pos~poslen-1 这len个空间是留给要插入的新字符串的//// 将下标大于等于 poslen-1的元素整体往后移动len个单位长度//// 从数组末尾移动,防止数据覆盖while(endposlen-1){_str[end]_str[end-len];end--;}// 移动完成// 现在从pos位置开始填数据for(size_t i0;ilen;i){_str[posi]str[i];}_sizelen;// 末尾主动补\0,保证底层始终是合法的C风格字符串_str[_size]\0;}✅ 面试重点必须从后往前搬数据如果从前向后移动原有数据会被覆盖丢失✅ 时间复杂度 O (N)所以 string 中间插入效率很低operator[ ] 下标重载// 类内实现charoperator[](size_t pos){assert(pos_size);return_str[pos];}constcharoperator[](size_t pos)const{assert(pos_size);return_str[pos];}返回引用可读可改const 版本保证 const 对象只能读不能修改erase( )字符串左闭右开减出来的就是中间元素个数voidstring::erase(size_t pos,size_t lennpos){// _size位置是\0的位置,len左闭右开减出来的长度是0,允许出现这个位置// reserve开的空间也包含了\0的位置assert(pos_size);// 分两种情况: 删除的长度超过后续字符串 or 删除的长度不超过后续字符串// 左闭右开 减出来的是中间字符串长度if(len_size-pos||lennpos){// clear接口的逻辑_str[pos]\0;_sizepos;}// 删除的长度不超过后续字符串else{size_t iposlen;// 后面的字符往前覆盖for(;i_size;i){_str[i-len]_str[i];}_size-len;_str[_size]\0;}}clear( ), size( ), capacity( ), c_str( )// 这些需要频繁调用的接口直接在类内实现voidclear(){_str[0]\0;_size0;}size_tsize()const{return_size;}size_tcapacity()const{return_capacity;}// 把 string 转回 C 风格 char * 字符串很多老接口需要constchar*c_str()const{return_str;}find( )查找字符size_t string::find(charch,size_t pos0){// _size位置代表数组里\0的位置assert(pos_size);for(intipos;i_size;i){if(_str[i]ch){returni;}}returnnpos;}查找字符串补充的C语言函数接口strstr#includestring.hchar*strstr(constchar*haystack,constchar*needle);作用在主串 haystack里查找子串needle第一次出现的位置返回匹配起始地址找不到返回NULL返回值细节 :找到返回haystack中该子串首字符指针没找到NULL特殊规则needle是空字符串直接返回 haystack 本身C 标准规定size_t string::find(constchar*str,size_t pos0){assert(pos_size);// 在主字符串中查找字串constchar*ptrstrstr(_strpos,str);if(ptrnullptr){returnnpos;}else{// 指针相减得到对应下标returnptr-_str;}}substr ( pos , len )// 截取子串string string::substr(size_t pos0,size_t lennpos){assert(pos_size);// 确认有效长度if(len_size-pos||lennpos){len_size-pos;}string sub;sub.reserve(len);for(size_t i0;ilen;i){sub_str[posi];}returnsub;}关系运算符号的重载先重载和,然后其他关系运算符直接复用这两个// 放在命名空间内,类外实现的全局函数// strcmp是针对C风格字符串的比较,所以先转化类型booloperator(conststrings1,conststrings2){returnstrcmp(s1.c_str(),s2.c_str())0;}booloperator(conststrings1,conststrings2){returnstrcmp(s1.c_str(),s2.c_str())0;}booloperator(conststrings1,conststrings2){returns1s2||s1s2;}booloperator(conststrings1,conststrings2){return!(s1s2);}booloperator(conststrings1,conststrings2){return!(s1s2);}booloperator!(conststrings1,conststrings2){return!(s1s2);}流插入运算符与流提取运算符的重载// 流插入运算符的重载ostreamoperator(ostreamout,conststrings){// 用范围for遍历 stringfor(autoch:s){coutch;}// 返回流引用,支持链式调用returnout;}// 流提取运算符的重载istreamoperator(istreamin,strings){// 默认以空格,换行作为分隔符号// 一个一个字符读取// 先将读到的字符存入缓冲数组// 等到缓冲数组满了再进字符串里// 先清空字符串的内存s.clear();// 这么做不会把缓冲数组的大小写死,方便自定义constintN256;charbuff[N];inti0;charch;// 读取一个输入的字符,包含空格与换行符号chin.get();// 读到空格与换行符号就停止读取while(ch! ch!\n){buff[i]ch;if(iN-1){buff[i]\0;sbuff;i0;}chin.get();}if(i0){buff[i]\0;sbuff;}// 返回流引用,支持链式调用returnin;}