本篇目标掌握string类的部分接口的实现一. string类的底层实现1.构造函数首先我们为了与tsd库里面的string 隔离一下我们需要定义一个自己的命名空间我的就是kong了C 中的字符串本质上是由字符数组构成的而 C 风格字符串底层就是char*所以这个模拟string 类的大致框架为:在string类中:#pragma once #define _CRT_SECURE_NO_WARNINGS #include iostream #include assert.h using namespace std; namespace kong { class string { public: string() :_str(nullptr), _size(0), _capacity(0) ~string() {} private: char*_str; size_t _size; size_t _capacity; }; }其中_str指向动态开辟的字符空间字符串内容存储在_str指向的数组中_capacity表示当前开辟的容量。当前有效字符数量。然后我们再实现一个c_str的接口方便后面看这个字符串是否是符合我们预期结果的这个还是比较简单的如代码所示const char* c_str()const { return _str; }那么在string.cpp中#include string.h namespace kong { void test_string1() { string s1; couts1.c_str()endl; } }注意这个test_string1也就是测试代码我们还需要在string.h里面的kong命名空间里面有个声明后面就不再提醒了。我们接下来就可以直接在test.cpp中进行测试了如代码#include string.h int main() { test_string1(); return 0; }注意:后面我们仅需在这里面添加一个测试代码即可后面就不在演示了直接测试即可。运行结果可是我们发现这个居然失败了这是为啥啊原因其实我们在给s1初始化时是使用nullptr初始化_str的。但是c_str()返回的是const char*它需要返回一个有效的 C 风格字符串。如果_str是nullptr那么返回的就是空指针后续访问时相当于解引用nullptr会导致错误。因此_str不应该初始化为nullptr而应该开辟一块空间存放\0保证空字符串也符合 C 风格字符串的要求。所以正确的默认构造是这样子的string():_str(new char[1]{\0}),_size(0),_capacity(0) { }有了这个以后其他的构造函数也是比较简单的如代码所示//构造函数 string(const char* str) { size_t len strlen(str); _size _capacity len; _str new char[_capacity 1]; strcpy(_str, str); } //拷贝构造函数 string(const string str) { _size str._size; _capacity str._capacity; _str new char[_capacity 1]; strcpy(_str, str._str); }2.赋值重载与析构函数对于赋值重载函数来说我们需要考虑被赋值对象原有空间大小的问题。如果赋值对象的空间比当前对象大或者小都可以直接释放原来的空间然后根据新的字符串长度重新开辟一块合适大小的空间再进行数据拷贝。但是这里还有一个需要注意的问题如果出现自己给自己赋值的情况例如s1 s1如果不提前判断而是先释放原来的空间再使用strcpy拷贝数据那么此时源数据已经被释放后续访问会导致未定义行为。因此在赋值重载函数中需要先判断是否为自身赋值如果是则直接返回避免不必要的资源释放。代码块string operator(const string str) { if (this ! str) { delete[] _str; _size str._size; _capacity str._capacity; _str new char[_capacity 1]; strcpy(_str, str._str); } return *this; }析构函数~string() { _size _capacity 0; delete[] _str; _str nullptr; }3.小接口实现char operator[] (size_t pos) { assert(pos _size); return _str[pos]; } const char operator[] (size_t pos)const { assert(pos _size); return _str[pos]; } char back() { return _str[_size - 1]; } char front() { return _str[0]; } size_t size()const { return _size; } size_t capacity() { return _capacity; } void clear() { _size 0; } bool empty() {return _capacity 0 ? true : false;}其实对于[]的重载我们需要注意判断一下pos的位置是否在_size的范围里面。4.插入接口4.1.push_back和append函数首先我们需要注意的是在向字符串尾部中插入字符/字符串时如果当前空间已经满了那么就需要进行扩容。但是对于 C 中的动态数组来说我们无法像 C 语言中的realloc一样直接对原空间进行扩容。因为realloc可能会直接在原空间后面扩展也可能会重新申请一块新的空间并拷贝数据而C 中使用new[]开辟的空间不能直接扩展。因此按照之前的思路我们仍然需要开辟一块新的空间将原来的字符串内容拷贝过去释放旧空间让_str指向新的空间。但是这里又有一个问题新的空间应该开辟多大呢对于push_back插入一个字符来说如果每插入一个字符就只增加一个空间例如插入a - 扩容一次 插入b - 扩容一次 插入c - 扩容一次 ...那么每次插入字符都需要重新申请空间而申请空间本身是一个比较耗时的操作会严重降低效率。所以实际工程中不会每次只增加一个字符的空间而是采用扩容机制。通常情况下new_capacity old_capacity * 2;也就是将容量扩大为原来的两倍。这样可以减少频繁申请空间的次数。但是对于append函数来说情况又有所不同。push_back每次只插入一个字符s.push_back(a);所以采用倍增扩容比较合适。但是append是一次插入一整个字符串s.append(hello);如果仍然按照原来的capacity * 2扩容可能会出现空间不足的问题。例如当前_size 10 _capacity 16现在追加abcdefghijklmnopqrstuvwxyz长度len 26那么新的需求_size len 36但是_capacity * 2 32仍然无法满足需求。所以对于append我们应该根据实际需要的空间进行扩容new_capacity _size len;也就是当前字符串长度 新插入字符串长度。这样能够保证一次扩容后一定能存放新的字符串。不过实际实现时还需要注意如果_size len _capacity才需要扩容。如果_size len _capacity说明当前空间已经足够直接进行拷贝即可不需要重新申请空间。有了上面的认识我们的代码就比较好写了reverse首先我们需要在string.h声明一下需要实现的函数将声明与定义分离后面我就直接在string.cpp中写接口的代码void reserve(size_t n 0); void push_back(char ch); void append(const char* str);void string::reserve(size_t n) { if (n _capacity) { _capacity n; char* str new char[_capacity 1]; strcpy(str, _str); delete[] _str; _str str; } }push_backvoid string::push_back(char ch) { if (_size _capacity) { reserve(_capacity 0 ? 4 : 2 * _capacity); } _str[_size] ch; _str[_size] \0; }appendvoid string::append(const char* str) { size_t len strlen(str); if (_size len _capacity) { reserve(_size len); } strcpy(_str _size, str); _size len; }4.2.insert接口insert函数主要用于在字符串指定位置插入数据。在实际使用中插入操作比较常见的有两种情况插入单个字符插入一个字符串。因此我们主要实现这两个接口。首先来看插入字符的情况。例如str hello 在 pos 2 位置插入 X原字符串h e l l o 0 1 2 3 4插入后h e X l l o 0 1 2 3 4 5可以发现插入位置pos后面的所有字符都需要向后移动一个位置。也就是pos及后面的字符 ↓ 整体向后移动1位移动完成后_str[pos] ch;即可将新的字符放入指定位置。过程图代码块void string::insert(size_t pos, char ch) { assert(pos _size); // 扩容 if (_size _capacity) { reserve(_capacity 0 ? 4 : _capacity * 2); } // 挪动数据 size_t end _size; while (end pos) { _str[end 1] _str[end]; --end; } _str[pos] ch; _size; }测试代码void test_string2() { string s1; s1.insert(0,1); couts1.c_str()endl; }但是当我们运行代码时会发现程序并没有正常结束而是出现了死循环。那么问题出在哪里呢原因我们来看数据移动部分size_t end _size; while(end pos) { _str[end 1] _str[end]; --end; }假设s1 此时_size 0 pos 0进入循环第一次end 0满足end pos执行_str[1] _str[0];然后--end;此时end -1;看起来应该退出循环。但是问题来了我们的end类型是size_t而size_t是一种无符号类型。所以-1不能被存储。当执行--end时end会发生无符号整数下溢。结果不是-1而是1844674407370955161564位环境下于是end pos仍然成立。循环继续执行_str[end 1] _str[end];最终导致程序一直运行也就是我们看到的“卡住”。既然我已经知道问题出现在size_t类型的下溢上那么我直接将end的类型修改为int不就可以了吗例如int end _size;但是我们实际修改后运行代码仍然可能发现程序依旧出现死循环。原因错误真正出现在while的判断条件上while(end pos)虽然我们将end修改成了int但是pos的类型仍然是size_t而size_t是无符号整型。在 C 中当有符号整数和无符号整数进行比较时会发生整型提升为了保证比较结果一致int类型的end会被转换成size_t类型。因此也会触发与上面一样的问题所以完整的修改是如下void string::insert(size_t pos, char ch) { assert(pos _size); // 扩容 if (_size _capacity) { reserve(_capacity 0 ? 4 : _capacity * 2); } // 挪动数据 // version1: int end _size; while (end (int)pos) { _str[end 1] _str[end]; --end; } // version2: /*size_t end _size 1; while (end pos) { _str[end] _str[end - 1]; --end; }*/ _str[pos] ch; _size; }其中版本2的代码也是可以通过的。有了单个字符的插入那么多字符插入的流程如图4.3.重载函数既然我们已经知道了有关插入的操作那么关于重载的实现就比较简单了如代码所示string string::operator (const string str) { const_iterator it str.cbegin(); while (it ! str.cend()) { *this *it; it; } return *this; } string string::operator (const char* s) { append(s); return *this; } string string::operator (char ch) { push_back(ch); return *this; }5.删除接口关于删除字符的操作我们需要关注的一个点就是当pos _size时如果从pos开始剩余字符的个数是_size - pos那么当len _size - pos或者len string::npos时就相当于删到末尾。这时把_str[pos]改成\0再把_size改成pos字符串就被截断了。只写\0还不够长度也要同步更新。如果len _size - pos说明被删除部分后面还有字符需要保留。比如原字符串a b c d e f \0 下标 0 1 2 3 4 5 6执行erase(2, 2)要删掉下标2、3的c、d。下标4的e是删除范围后面第一个要保留的字符所以先把它放到下标2填上第一个空位。然后把f从下标5放到下标3。最后还得把\0从下标6放到下标44 → 2搬 e 5 → 3搬 f 6 → 4搬 \0 结果a b e f \0因此挪动时有两个位置同时往后走读取位置从pos len开始写入位置从pos开始。一直搬到原来_size所在的位置把\0也搬过去。搬完再执行_size - len。因为是往左挪按从左到右的顺序搬就可以每次写入的位置都在当前读取位置的前面不会盖掉后面尚未读取的字符。但是我们需要现在类里面定义一下这个npos仅需static const size_t npos-1;即可。流程图代码块void string::erase(size_t pos, size_t len) { assert(pos _size); // pos以后的都要删除 if (len string::npos || len _size - pos) { _str[pos] \0; _size pos; } else { for (size_t i pos len; i _size; i) { _str[pos] _str[i]; } _size - len; } }6.查找接口关于查找的接口我们主要实现查找一个字符和查找一个字符串。查找一个字符的比较好实现遍历字符一遍看看有没有匹配的字符有就返回下标没有就返回npos如代码所示size_t string::find(char ch, size_t pos)const { assert(pos _size); for (int i pos; i _size; i) { if (_str[i] ch) { return i; } } return npos; }可是对于一个字符串的查找目前我们可以暴力匹配一个一个字符的比对但是我们可以用一个函数解决即strstr函数。使用如下strstr可以直接理解为拿一个小字符串去一个大字符串里找调用时第一个参数放大字符串第二个参数放要找的小字符串。比如在ababcabc里找abc就是让它从左往右检查找到第一次出现的abc。它返回的不是下标2而是指向那个a的指针。这个a是大字符串中下标2的字符所以返回的指针指向大字符串内部从这个位置往后看内容就是abcabc。如果你想知道“从第几个字符开始匹配”才用返回的指针减去大字符串的起始指针得到2。没找到时它返回空指针。还有一点strstr找的是以\0结尾的字符字符串所以放到你正在写的string类里理解就是拿_str这样的字符数组去查而不是让它直接处理整个string对象。所以代码如下size_t string::find(const char* s, size_t pos )const { assert(pos _size); char*str strstr(_str, s); if (str nullptr) { return npos; } else { return str - _str; } }7.比较字符串至于这个比较函数我们需要重载!即可我们可以先重载和即可其他的函数复用即可代码如下bool operator(const string s1, const string s2) { return strcmp(s1.c_str(), s2.c_str())0; } bool operator(const string s1, const string s2) { return s1 s2 || s1 s2; } bool operator(const string s1, const string s2) { return strcmp(s1.c_str(), s2.c_str()) 0; } bool operator(const string s1, const string s2) { return !(s1 s2); } bool operator(const string s1, const string s2) { return !(s1 s2); } bool operator!(const string s1, const string s2) { return !(s1 s2); }8.重载和函数这个的重载非常的简单我们仅需输出字符即可如代码ostream operator(ostream out, const string str) { for (size_t i 0; i str.size(); i) { out str[i]; } return out; }至于流提取首先调用str.clear()清空字符串原有的内容让这次输入从空字符串开始。随后用in.get()读取一个字符。只要读到的字符不是空格 也不是换行符\n就通过str ch将它追加到字符串末尾再读取下一个字符。例如输入内容是hello world\n第一次读取时h、e、l、l、o会依次加入str读到空格后停止得到hello。再次读取时会从w开始读到换行后停止得到world。这里的空格或换行已经被get()取走只是没有加入字符串。函数最后返回in的引用是为了支持连续输入例如cin str1 str2前一次调用返回的输入流可以继续交给下一次调用使用。不过这份代码有一个必须指出的问题它没有处理文件结束EOF。in.get()的返回值本来可以表示“已经没有字符可读”代码却立刻把它存进char ch随后只检查空格和换行。如果输入在没有这两种字符的情况下结束循环就可能一直读下去。因此这段代码可以用来说明逐字符读取和追加的基本思路但博客里不能把它称为完整正确的实现。还有一点它不会跳过开头的空格开头就是空格时本次读取会得到空字符串。代码块istream operator(istream in, string str) { str.clear(); char ch in.get(); while (ch ! \n ch ! ) { str ch; ch in.get(); } return in; }但是还有个问题我们这个str是要扩容的啊扩容是要消耗时间的啊如果我输入一大串字符到str中那不就要不断的扩容吗这时有人会想那我用reserve来提前开好空间不就行了吗那么要开多大呢开100的话如果我就输入一个字符那剩下的99个空间不就浪费了吗那么就没有更好的办法了吗有的如代码所示istream operator(istream in, string str) { str.clear(); char buffer[128]; int i 0; int ch in.get(); while (ch ! std::char_traitschar::eof() ch ! \n ch ! ) { buffer[i] static_castchar(ch); // 攒够 127 个字符留出最后一个位置放 \0 if (i 127) { buffer[i] \0; str buffer; i 0; } ch in.get(); } // 输入结束时可能还有不足 127 个字符没追加 if (i 0) { buffer[i] \0; str buffer; } return in; }我们通过buffer这个字符数组来存储输入的字符当输入的数据满足一定的条件时就加入到str中就可以避免多次扩容的问题了。9.重载函数这个也比较简单直接看代码即可string operator (const string lhs, const string rhs) { string tmp(lhs); tmp rhs; return tmp; } string operator (const string lhs, const char* rhs) { string tmp(lhs); tmp rhs; return tmp; } string operator (const char* lhs, const string rhs) { string tmp(lhs); tmp rhs; return tmp; }10.交换与反转函数交换函数我们可以直接用库里面的如代码所示void string::swap(string str) { std::swap(_str, str._str); std::swap(_size, str._size); std::swap(_capacity, str._capacity); }反转函数我们实现迭代器版的即可void string::reverse(iterator begin, iterator end) { iterator left begin, right end - 1; while (left right) { std::swap(*left, *right); left; right--; } }11.优化部分其实有了这个交换函数后我们的拷贝构造等函数就可以优化了如下string(const string str) { string tmp(str); swap(tmp); } string operator(const string str) { if (this ! str) { string tmp(str); swap(tmp); } return *this; }不过拷贝构造函数里还有一个前提要检查当前对象的成员在swap(tmp)前是否已经初始化。拷贝构造是怎么工作的假设要根据str构造一个新对象string tmp(str._str)先调用const char*构造函数申请内存复制str的字符内容。tmp此时有自己独立的一份数据。swap(tmp)把tmp的_str、_size、_capacity交换给当前正在构造的对象。tmp离开作用域并析构释放它在交换后拿到的资源。问题出在第 2 步**当前对象刚进入拷贝构造函数时成员不会因为你要调用swap就自动变成空字符串。**如果_str、_size、_capacity没有类内默认值也没有写在初始化列表里swap就会读取未初始化的成员之后tmp还可能尝试释放一个无效指针。因此假设你的类没有给成员设置默认值至少要先把当前对象初始化为空状态如果你已经在类里写了_str nullptr、_size 0、_capacity 0这样的成员默认值就不必重复写这份初始化列表所以我们需要这么写赋值运算符是怎么工作的赋值时当前对象本来就已经构造好了因此可以直接创建tmp再交换。交换后当前对象得到新内容tmp拿走当前对象的旧内容函数结束时tmp的析构函数负责释放旧内容。if (this ! str)则避免给自己赋值时白做一次复制。12.写时拷贝写时拷贝可以理解成复制字符串时先不复制字符等某个对象真的要修改字符时再给它单独复制一份。拿你的string类举例。假设a的内容是abc然后执行b a。普通的深拷贝会立刻为b申请新空间把a的abc复制过去。此时两个对象各有一份数据。而写时拷贝会先让a和b共用同一份abc并记录“现在有 2 个对象在用这份数据”。接下来分两种情况只读取例如查看a、b的内容。谁也没改数据它们就可以继续共用不需要复制字符。准备修改例如把b[0]改成x。如果直接在共用的数据上改a也会跟着变成xbc这显然不对。所以修改前先为b复制一份abc让b脱离共享然后只修改b的那份。最终a是abcb是xbc。这里的“写时”指的是修改数据之前。如果已经把共用的字符改了再去复制就晚了。实现时通常要有一个引用计数表示同一份字符数据正在被多少个string对象使用。复制对象时计数加一对象析构或脱离共享时计数减一减到零才释放这份字符数据。执行append、erase、修改某个字符等操作之前都要判断如果数据只有自己在用就直接改如果有多个对象共用就先复制再改。它和你上一段代码的区别在于string tmp(str._str)当场就复制了字符属于深拷贝写时拷贝在这一步只共享数据真正的字符复制推迟到修改时。好处是“复制很多次、但很少修改”时能省下复制开销代价是每次修改前都要检查是否共享而且像operator[]返回可修改的char这种接口会让实现变复杂——引用交出去之后类就不一定能拦住使用者直接改字符。总结本文通过模拟实现string类梳理了字符串的构造、扩容、插入、删除、查找和输入输出等操作。重点在于维护好字符数组、_size和_capacity的关系并理解拷贝交换与写时拷贝各自如何管理字符串数据。