C++STL库中不可或缺的部分—string（模拟实现）

前文

大家好，本篇文章主要是讲解一下string一些常用接口的模拟实现。
众所周知，在日常生活中，字符串无处不在，如''just do it'',''中国'',''一坤年''等，想要在计算机上将这些字符展现出来就需要用到string类，而对我们C++程序员来说能否模拟实现string是对我们基本功的一个重要考验。
话不多说，下面就开始模拟实现。(文末有源代码，需要自取)

一，常用接口的实现

ps：为了和库里面的string区分开，所以我们新创了一个命名空间，名字为mjw，我们将在里面实现string。
本次模拟成员变量如下定义

1.1 构造函数

如图所示，上面是库中string构造函数的各个函数重载，其中比较常用的是的是(1)无参构造函数,(2)拷贝构造函数,(4)有参构造函数。

1.1.1 有参/无参构造函数

由于无参构造函数其实就是传字符' '，所以我们将(1)(4)合到一起实现，(1)将作为(4)的缺省参数实现。
在写代码时，我们需要注意两点：
1. strlen(str)计算的时'\0'前面的字符数量，所以在开空间时要加上'\0'的位置
2. 开空间要注意有可能开辟失败，所以我们先创建一个指针ptr开空间，成功后再将ptr赋值给_str
3.字符串的拷贝我们直接用strcpy实现，下面简单介绍一些strcpy的用法

如上图所示，strcpy的作用是将source中的内容拷贝到destination指向的空间

        //有参构造函数，无参利用缺省参数实现string(const char* str = ""):_size(strlen(str)){//由于strlen计算的是"/0"前面字符的数量，//所以实际空间要留出'/0'的位置，也就是要多开辟一个空间_capaicty = strlen(str)==0?3:strlen(str);char* ptr = new char[_capacity + 1];strcpy(ptr, str);_str = ptr;}

1.1.1 拷贝构造函数

拷贝构造函数的逻辑和构造函数类似，但是需要注意不要用默认拷贝构造函数，那样看起来是拷贝成功，实际上两个指针指向的是同一个空间。
这里就涉及到深浅拷贝的问题。
浅拷贝就会造成如下问题：(用的是之前类和对象的图，原谅我偷懒啦)

因此如果一个类中涉及到资源管理，那么其拷贝构造函数，赋值重载函数，析构函数都需要显示给出，都需要按照深拷贝的方式提供。

拷贝构造函数代码如下：

//拷贝构造函数string(const string& s):_size(s.size()){_capaicty = s._capacity;char* ptr = new char[_capacity + 1];strcpy(ptr, s._str);_str = ptr;}

1.2析构函数

将开辟的空间释放，然后将_str置空即可，一定要注意开辟和释放所用关键字要配对(new []/delete[])

代码如下：

        //析构函数~string(){delete[] _str;_str = nullptr;_size = _capacity = 0;}

1.3 []运算符重载

由于[]访问字符串比较方便，所以我们为了后续方便测试，我们将[]运算符重载放到第三个实现。

为了应对不同情况的权限问题，所以我们打算完成上面的两个函数重载，这里需要注意的点就是要保证pos值的合法性，也就是pos<=_size.

代码如下：

        //[]重载char& operator[](size_t size){assert(!(size > _size));return _str[size];}const char& operator[](size_t size) const//应对只用[]遍历，不修改的权限问题{assert(!(size > _size));return _str[size];}

1.4 返回_size/返回_str的地址/返回_capacity

三个个比较简短却又不能缺少的接口，没什么难度就不做赘述了。

代码如下：

        //返回sizesize_t size() const{return _size;}//返回_str地址const char* c_str(){return _str;}//返回capacitysize_t capacity() const{return _capacity;}

1.5赋值函数重载

如上图所示，如果是第三种情况两个长度相等，那么容量不用变；如果是第一种情况s1的长度小于s2，要将s1赋值给s2，直接拷贝即可，但是此时会有一个问题，那就是有大量空间浪费掉了；第二种情况，s1的长度大于s2，想要将s1赋值给s2，s2就要扩容，但是new不支持扩容，所以我们只能将s2原来空间释放，重新开辟一个和s1一样大的空间再将s1的内容拷贝过去。
综上所述，我们为了满足每一种的情况，采取第二种的应对方法，就是将原来空间释放掉，重新开辟一个空间进行拷贝。

代码如下：

//赋值string& operator=(const string& s){if (this != &s)//s1=s1的情况{//new开辟失败的时候，赋值没有实现，但s1却已经被破坏/*delete[] _str;_str = new char[s._capaicty + 1];_size = s._size;_capaicty = s._capaicty;strcpy(_str, s._str);*/char* ptr = new char[s._capaicty + 1];strcpy(ptr, s._str);delete[] _str;_str = ptr;_size = s._size;_capaicty = s._capaicty;}return *this;}

1.6 迭代器

迭代器(Iterator)是一个对象，它的工作是遍历并选择序列中的对象，它提供了一种访问一个容器(container)对象中的各个元素，而又不必暴露该对象内部细节的方法。
string的迭代器实现方式比较简单，用typedef就可以实现。

代码如下：

//迭代器typedef char* iterator;typedef const char* const_iterator;iterator begin(){return _str;}iterator end(){return _str + _size;}//const修饰的迭代器const_iterator begin() const{return _str;}const_iterator end() const{return _str + _size;}

但是由于string中的[]更加方便，所以迭代器用的地方比较少，但是后面的list迭代器用处很大。

1.7 reserve(扩容)

扩容函数接口是我们后面模拟插入，尾插等必不可少的接口，虽然很重要但是实现还是比较简单的。

reserve接口的实现和赋值函数重载的实现一致，都是把原来的空间销毁，然后新开空间。

代码如下：

        //扩容，和赋值的思路类似void reserve(const size_t n){if (_capacity < n){//开n+1的空间，是要给'/0'留一个空间char* ptr = new char[n + 1];//防止开空间失败所以先用ptr接收，成功后在赋值给_strstrcpy(ptr, _str);delete[] _str;_str = ptr;_capacity = n;}}

1.8 insert(重点)

insert接口实现是string模拟中比较重要的一个点，后面的尾插可以复用这个，而且这一部分的细节比较多，需要多注意。

对于intsert部分，我们打算实现两个函数重载：
1.在pos位置插入字符串 2.在pos位置插入字符

1.8.1 insert(插入字符串)

insert:在指定的位置插入字符或者字符串
插入字符串的大体逻辑如下：
首先检查是否需要扩容，然后在将pos位置往后的字符往后挪len(要插入的字符串的长度)个位置，给要插入的字符串留出足够的位置，然后拷贝字符串。
注意:最后的拷贝字符串可以手动拷贝，我们这里选择的是用库里的函数strncpy进行拷贝，相比与strcpy，strncpy的控制更加精准

strncpy简单介绍

函数的作用大致为从source中拷贝num个字符到destination中

代码如下：

//在pos的位置插入字符串sstring& insert(size_t pos, const string& s){assert(pos <= _size);//检查pos是否合法int len = s.size();//检查扩容if (_size + len > _capacity){reserve(_size + len);}size_t end = _size;//pos的数据及后面的数据向后挪len个位置while (end >= pos){_str[end + len] = _str[end];end--;}//插入字符串//strcpy(_str + pos, s._str);strncpy(_str + pos, s._str,len);_size += len;return *this;}

插入的基本功能差不多完成了，但是其中还有一个小bug不知道铁子们发现没有，那就是当pos为0时，循环会进入死循环。

注意此时end为0，按照我们的逻辑来看，下一步为-1，就该跳出循环了。

实际上并不是我们想的那样，end变成-1，而变成了最大值，这是因为什么呢，
因为end和pos的类型都是size_t，而size_t实际上是unsignen int,因此当end为0进行--时就直接变成了最大值.

那么有没有避免这种情况的方法？
答案肯定是有的如：
1. 将end和pos的类型都变成int，但是这样就和库中的参数不同，有违我们模拟的初衷
ps:如果只改变end的类型，在比大小的时候仍会被强制转成size_t，当然也可以在比的时候把pos强制转出int，但是这样可能会导致数据失真。
2. 改变循环逻辑

如上所示，这样以来end的最小值不会再低于0，这样就不会因为是无符号整形，导致永远是正数，从而导致死循环。

改良后的代码：

//在pos的位置插入字符串sstring& insert(size_t pos, const string& s){assert(pos <= _size);//检查pos是否合法int len = s.size();//检查扩容if (_size + len > _capacity){reserve(_size + len);}size_t end = _size+len;//pos的数据及后面的数据向后挪len个位置/*while (end >= pos){_str[end + len] = _str[end];end--;}*/while (end > pos + len - 1){_str[end] = _str[end - len];end--;}//插入字符串//strcpy(_str + pos, s._str);strncpy(_str + pos, s._str,len);_size += len;return *this;}

1.8.2 insert(插入字符)

插入字符和插入字符串一样，其实就是把插入字符串中的len变成1就是插入字符。

//在pos的位置插入字符chstring& insert(size_t pos, const char ch){assert(pos <= _size);//检查pos是否合法//检查扩容if (_size + 1 > _capacity){reserve(_capacity * 2);//二倍扩容}size_t end = _size+1;while (end > pos){_str[end] = _str[end-1];end--;}_str[pos] = ch;_size++;return *this;}

1.9 erase

erase:在pos位置往后(包括pos)删除len个字符，当len>=_size时，默认pos后面的数据删完即可。
erase情况分三种：len==npos,len>=_size,len<size.因为len类型为size_t，而npos值恒定为-1，所以前两种情况可以归为一种，就是len>=_size.

代码如下:

//erase,在pos位置往后(包括pos)删除n/npos个字符string& erase(size_t pos = 0, size_t len = npos){assert(pos <= _size);//检查pos是否合法if (len == npos || len >= _size){_str[pos] = '\0';_size = pos;}else{//将pos后面的数据都向前挪len个位置//1.手动挪//size_t cur = pos;//while (cur <= _size - len)//{//    _str[cur] = _str[cur + len];//    cur++;//}//2.strcpystrcpy(_str + pos, _str + pos + len);_size -= len;}

1.10 push_back(尾插字符)和append(尾插字符串)

1.10.1 push_back

实现方法：
1.检查扩容，然后直接插入
2.复用insert(插入字符)

//尾插字符void push_back(char ch){//1.检查扩容，然后直接插入//检查扩容//if (_size + 1 > _capacity)//{//    reserve(_capacity*2);//二倍扩容//}当前_size指向的是原字符串'\0'的位置，此时赋值'\0'会被覆盖所以需要在后面补上'\0'//_str[_size] = ch;//_size++;//_str[_size] = '\0';//2.复用insertinsert(_size, ch);}

1.10.2 append

我们要实现的是上面的第一个函数重载
实现方法:
1.检查扩容，然后用strcpy拷贝
2. 复用insert(插入字符串)

//尾插字符串void append(const string& s){//1.检查扩容，然后用strcpy拷贝//int len = s._size;检查扩容//if (_size + len > _capacity)//{//    reserve(_size + len);//按需扩容//}//strcpy(_str + _size, s._str);//_size += len;//2. 复用insert(插入字符串)insert(_size, s);}

1.11 +=操作符重载

我们要实现上图的第一个和第三个函数重载
实现方式:复用push_back(尾插字符)和append(尾插字符串)即可

//+=重载 复用尾插和尾插字符串//+=字符//1.字符string& operator+=(const char ch){push_back(ch);return *this;}//2.字符串string& operator+=(const string& s){append(s);return *this;}

1.12 resize

resize:重新规划_size的大小，注意不是_capacity的大小，而是元素的个数。
resize的实现分为以下情况：

代码实现：

void resize(size_t n, char ch = '\0'){if (n <= _size){_size = n;_str[_size] = '\0';}else{//判断扩容if (n > _capacity){reserve(n);}for(int i = _size; i < n; i++){_str[i] = ch;}_size = n;_str[_size] = '\0';}}

1.13 swap

写交换函数的时候尽量不要直接复用库里的swap函数，下面代码会解释。

//交换函数//swap(s1,s2);//和上面库中的交换函数比，类中的交换函数效率更高//因为库中函数需要调用三次构造函数构造s1,s2//而类中的交换函数，可以直接引用传参，不需要调用构造函数void swap(string& s){//用库中的swap函数，前面要加std//不然会优先调用当前类中的swap函数，参数不对会出错std::swap(_str, s._str);std::swap(_size, s._size);std::swap(_capacity, s._capacity);}

1.14 <<(流插入)和>>(流提取)重载

流插入流提取都不能作为成员函数实现，因为成员函数中*this永远是第一个参数，所以在成员函数中实现只能实现这样的效果:s1<<cout，所以我们一般是作为全局函数或者友元函数实现。

1.14.1 <<(流插入)

流插入我们采取一个范围for来实现

//流插入ostream& operator<<(ostream& out,string& s){for (auto ch : s){out << ch;}return out;}

1.14.2 >>(流提取)重载

在写流提取重载前，我们可以看看库中是如何运行的

观察上面程序我们发现，每次进行流提取，会将字符串的原数据删除，然后输入流提取的内容。
ps：在写入字符时，要用istream中的get()函数，如果直接用>>，库中函数默认空格和'\n'会清除缓存，导致ch无法读取，从而无法停止循环，如下所示

因此需要用in.get()函数提取字符

代码如下：

//流提取istream& operator>>(istream& in,string& s){char ch = in.get();//直接流提取输入默认' '是单词的间隔s.erase();while (ch!=' '&&ch != '\n'){s += ch;ch = in.get();}return in;}

二，源码

#pragma once
#include <iostream>
#include <assert.h>
using namespace std;
namespace mjw
{class string{public://迭代器typedef char* iterator;typedef const char* const_iterator;iterator begin(){return _str;}iterator end(){return _str + _size;}//const修饰的迭代器const_iterator begin() const{return _str;}const_iterator end() const{return _str + _size;}//有参构造函数，无参利用缺省参数实现string(const char* str = ""):_size(strlen(str)){//由于strlen计算的是"/0"前面字符的数量，//所以实际空间要留出'/0'的位置，也就是要多开辟一个空间_capacity = strlen(str)==0?3:strlen(str);char* ptr = new char[_capacity + 1];strcpy(ptr, str);_str = ptr;}//拷贝构造函数string(const string& s):_size(s.size()){_capacity = s.capacity();char* ptr = new char[_capacity + 1];strcpy(ptr, s._str);_str = ptr;}//[]重载char& operator[](size_t size){assert(!(size > _size));return _str[size];}const char& operator[](size_t size) const//应对只用[]遍历，不修改的权限问题{assert(!(size > _size));return _str[size];}//返回sizesize_t size() const{return _size;}//返回_str地址const char* c_str(){return _str;}//返回capacitysize_t capacity() const{return _capacity;}//赋值string& operator=(const string& s){if (this != &s)//s1=s1的情况{//new开辟失败的时候，赋值没有实现，但s1却已经被破坏/*delete[] _str;_str = new char[s._capaicty + 1];_size = s._size;_capaicty = s._capaicty;strcpy(_str, s._str);*/char* ptr = new char[s.capacity() + 1];strcpy(ptr, s._str);delete[] _str;_str = ptr;_size = s._size;_capacity = s.capacity();}return *this;}//比较大小// 对于不修改成员变量的函数尽量用const修饰一下//<bool operator<(const string& s) const{return strcmp(_str, s._str) < 0;}//==bool operator==(const string& s) const{return strcmp(_str, s._str) == 0;}//>bool operator>(const string& s) const{return !(*this < s) && !(*this == s);}// <=bool operator<=(const string& s) const{return (*this < s) || (*this == s);}// >=bool operator>=(const string& s) const{return !(*this < s) || (*this == s);}// !=bool operator!=(const string& s) const{return !(*this == s);}//扩容，和赋值的思路类似void reserve(const size_t n){if (_capacity < n){//开n+1的空间，是要给'/0'留一个空间char* ptr = new char[n + 1];//防止开空间失败所以先用ptr接收，成功后在赋值给_strstrcpy(ptr, _str);delete[] _str;_str = ptr;_capacity = n;}}//尾插字符void push_back(const char ch){//1.检查扩容，然后直接插入//检查扩容//if (_size + 1 > _capacity)//{//    reserve(_capacity*2);//二倍扩容//}当前_size指向的是原字符串'\0'的位置，此时赋值'\0'会被覆盖所以需要在后面补上'\0'//_str[_size] = ch;//_size++;//_str[_size] = '\0';//2.复用insertinsert(_size, ch);}//尾插字符串void append(const string& s){//1.检查扩容，然后用strcpy拷贝//int len = s._size;检查扩容//if (_size + len > _capacity)//{//    reserve(_size + len);//按需扩容//}//strcpy(_str + _size, s._str);//_size += len;//2. 复用insert(插入字符串)insert(_size, s);}//+=重载 复用尾插和尾插字符串//+=字符//1.字符string& operator+=(const char ch){push_back(ch);return *this;}//2.字符串string& operator+=(const string& s){append(s);return *this;}//void resize(size_t n, char ch = '\0'){if (n <= _size){_size = n;_str[_size] = '\0';}else{//判断扩容if (n > _capacity){reserve(n);}for(int i = _size; i < n; i++){_str[i] = ch;}_size = n;_str[_size] = '\0';}}//insert//在pos的位置插入字符chstring& insert(size_t pos, const char ch){assert(pos <= _size);//检查pos是否合法//检查扩容if (_size + 1 > _capacity){reserve(_capacity * 2);//二倍扩容}size_t end = _size+1;while (end > pos){_str[end] = _str[end-1];end--;}_str[pos] = ch;_size++;return *this;}//在pos的位置插入字符串sstring& insert(size_t pos, const string& s){assert(pos <= _size);//检查pos是否合法int len = s.size();//检查扩容if (_size + len > _capacity){reserve(_size + len);}size_t end = _size+len;//pos的数据及后面的数据向后挪len个位置/*while (end >= pos){_str[end + len] = _str[end];end--;}*/while (end > pos + len - 1){_str[end] = _str[end - len];end--;}//插入字符串//strcpy(_str + pos, s._str);strncpy(_str + pos, s._str,len);_size += len;return *this;}//erase,在pos位置往后(包括pos)删除n/npos个字符string& erase(size_t pos = 0, size_t len = npos){assert(pos <= _size);//检查pos是否合法if (len == npos || len >= _size){_str[pos] = '\0';_size = pos;}else{//将pos后面的数据都向前挪len个位置//1.手动挪//size_t cur = pos;//while (cur <= _size - len)//{//    _str[cur] = _str[cur + len];//    cur++;//}//2.strcpystrcpy(_str + pos, _str + pos + len);_size -= len;}return *this;}//交换函数//swap(s1,s2);//和上面库中的交换函数比，类中的交换函数效率更高//因为库中函数需要调用三次构造函数构造s1,s2//而类中的交换函数，可以直接引用传参，不需要调用构造函数void swap(string& s){//用库中的swap函数，前面要加std//不然会优先调用当前类中的swap函数，参数不对会出错std::swap(_str, s._str);std::swap(_size, s._size);std::swap(_capacity, s._capacity);}//析构函数~string(){delete[] _str;_str = nullptr;_size = _capacity = 0;}private:char* _str;size_t _size;size_t _capacity;static size_t npos;//static const size_t npos;两个是一样的};size_t string::npos = -1;//流插入ostream& operator<<(ostream& out,string& s){for (auto ch : s){out << ch;}return out;}//流提取istream& operator>>(istream& in,string& s){char ch = in.get();//直接流提取输入默认' '是单词的间隔s.erase();while (ch!=' '&&ch != '\n'){s += ch;ch = in.get();}return in;}}

总结

以上就是我们模拟实现的接口，我们模拟实现string的目的不是造一个更好的轮子，而是更加深入的了解string的各个常用接口，希望能够对铁子们有所帮助。