C++《string的模拟实现》
在之前的篇章C++《string》中我们已经了解了string中关于构造、容量、访问、修改操作等函数的功能，以及初步学习了这些函数的使用该如何使用。通过学习string内的各个函数后我们可以发现在解决一些要使用到字符串的环境下有了string内的这些函数操作能大大简化，在此当中最主要的是在进行插入、删除等操作时我们不用再显示的去对字符串的内存空间进行调整。那么在之前我们只是了解了string的该如何使用，接下来在本篇当中我们将试着模拟实现string，我们在学习了string的使用之后要模拟实现是为了能从更底层来了解string的各个功能时如何实现的，这会让加深对string的了解。接下来就开始本篇的学习吧！！！
注：在本篇string模拟实现当中是将需重点掌握的函数进行实现，而在日常较少使用的未进行实现
1.实现各个函数之前的工作
在模拟实现string各个函数之前我们先要来解决在实现过程中文件应如何创建、模拟实现的string如何避免和std内的string冲突等问题
在此我们先来创建三个文件分别是string.h、string.cpp、test.cpp这三个文件将分别完成类的定义以及函数的声明、函数的定义、实现完函数之后的测试
接下来在来分析如何解决我们模拟实现的string和std这个命名空间内的string不冲突的问题
在此要解决这个问题就需要创建一个不与std名字相同的命名空间，这样只需要在调用string时指定为我们创建的命名空间就不会出现冲突的问题。因此在之后我们模拟实现string的各个函数都要放在我们创建的命名空间内。接下来模拟实现函数时还是采用声明和定义分离的方式，将声明放在string.h文件内，将定义放在string.cpp内，但如果实现的函数时较为短小的函数就直接将定义也放在string.h内让其变为内联函数
注：在创建命名空间时在string.cpp和头文件当中都定义一个相同名字的命名空间，这时因为在多个文件当中同名的命名空间会被认为是同一个namespace，不会出现冲突
解决了以上的问题接下来我们就先创建一个名字为zhz的命名空间，接下来在该命名空间内完成类string的定义
在string.h内定义string，在此我们先来定义string的成员变量，接下来再一一实现各成员函数
#include<iostream> #include<string> #include<assert.h> using namespace std; namespace zhz { class string { public: //成员函数 private: //成员变量 char* _str = nullptr; size_t _size = 0; size_t _capacity = 0; };由于string的底层是顺序表，因此在此string类的成员变量和我们之前实现顺序表一样定义三个变量，_str为指向内存空间的字符指针、_size为有效数据个数、_capacity为空间大小。并且在定义之后还给这几个变量加上缺省值
2.构造函数与析构函数
2.1构造函数
通过之前对string构造函数的学习我们知道string的构造函数提供了许多的接口，但在此模拟实现时我们只实现无参和参数为常量字符串的指针两个接口
接下来就来实现构造函数，在实现string无参的构造函数时你可能会直接想到和之前实现顺序表一样直接将指针置为nullptr，再将_size和_capacity赋值为0。但仔细思考就会发现这种做法是错误，这是由于在字符串和顺序表不同字符串的结尾都有\0,因此即使当字符串当中一个元素也没有时也要在末尾加上\0
先在srring.h完成函数的声明
string();接下来在string.cpp内完成函数的定义
string::string()
:_str(new char[1]{'\0'})
,_size(0)
,_capacity(0)
{
}在此你可能又会出现一个疑问是这里只申请一个char类型的空间那为什么在使用new时不直接使用new char('\0')，而是使用申请多个内存空间的方式new char[ ]{ }。要解决这个问题我们就不能只将视角放在无参的构造函数当中，我们要想到在之后实现的含参的构造等构造函数当中都是使用new来申请多个char类型的内存空间，那么这就使得在析构函数当中要使用到delete [ ]来释放，因此为了匹配析构函数当中的delete [ ]在构造函数当中也要使用new char[N]
完成了无参的构造函数接下来继续来实现参数为指向字符串指针的构造函数
先在srring.h完成函数的声明
string(const char* s );接下来在string.cpp内完成函数的定义
我们之前在C语言学习了要求一个字符串的长度，使用strlen即可得到。那么你可能就会直接想到使用以下方式来实现
string::string(const char* s)
:_size(strlen(s))
,_capacity(_size)
,_str(new char[_size+1])
{
strcpy(_str,s);
}以上看起来没什么问题但其实存在非常大的错误，在之前我们声明类string的成员变量顺序如下所示
提供之前构造函数初始化列表的学习我们知道初始化列表中变量的初始化顺序是按照各个变量的定义顺序先后初始化的，因此在以上按照这种方式实现的构造函数在初始化列表当中会先将变量_str初始化，但这时表示有效元素的变量_size还未完成初始化，这时_size的值就是随机值。
因此通过以上的分析就可以看出以上这种构造函数的写法是错误的，这时确实可以通过改变初始化列表内的初始化顺序来避免以上的问题，但是更优的解法是将_str和_capacity的初始化放在构造函数的函数体内实现
string::string(const char* s) :_size(strlen(s)) { _str = new char[_size + 1]; _capacity = _size; strcpy(_str, s); }
以上就完成了string的构造函数，以上我们是将无参和带参的两个函数分开定义这样会显得较为繁琐，那么是否能将以上两个函数合并为一个函数呢？
答案是当然可以，这就只需要在带参的函数在声明是加上缺少参数，这样就可以同时实现带参和不带参的string对象的初始化
先在srring.h完成函数的声明
string(const char* s = "");注：在此使用""来作为参数的缺省值，就可以使得在用户未传参数时，参数值就为字符串"",这时字符串内就没有元素字符串长度就为0，当在末尾还是一个\0
接下来在string.cpp内完成函数的定义
string::string(const char* s)
:_size(strlen(s))
{
_str = new char[_size + 1];
_capacity = _size;
strcpy(_str, s);
}2.2析构函数
析构函数是要完成资源的清理，也就是要将我们之前申请的内存空间进行释放
先在srring.h完成函数的声明
~string();接下来在string.cpp内完成函数的定义
string::~string()
{
delete[]_str;
_str = nullptr;
_size = _capacity = 0;
}
2.3拷贝构造函数
在此拷贝构造在string非常重要，因为在之后函数中的传值sting类型返回或者是传string类型参数都会调用拷贝构造，在此string当中有指向资源的指针因此当我们没有显示写拷贝构造时，编译器自主生成的拷贝构造完成的时浅拷贝，这就不符合我们的要求，因此只有显示的写拷贝构造才能实现深拷贝
先在srring.h完成函数的声明
string(const string& s);接下来在string.cpp内完成函数的定义
string::string(const string& s)
{
_str = new char[s._capacity + 1];
_size = s._size;
_capacity = s._capacity;
strcpy(_str, s._str);
}
3.赋值运算符重载
在string的赋值运算符重载和拷贝构造一样需要我们显示写以实现深拷贝
先在srring.h完成函数的声明
string& operator=(const string& str);接下来在string.cpp内完成函数的定义
string& string::operator=(const string& str)
{
if (this != &str)
{
delete[] _str;
_str = new char[str._capacity+1];
strcpy(_str, str._str);
_size = str._size;
_capacity = str._capacity;
}
return *this;
}4. c_str
通过之前string的学习我们知道c_str是输出string对象当中的成员变量中的数组指针，在我们模拟实现当中也就是输出_str指针
在此由于该函数为短小函数就直接将该函数放在string.h内而不再使用声明和定义分离的方式
const char* c_str()const
{
return _str;
}
5.size与capacity
在此由于这两个函数都为短小函数就直接将该函数放在string.h内而不再使用声明和定义分离的方式
size_t size()const
{
return _size;
}
size_t capacity()const
{
return _capacity;
}
6.下标+[ ]访问
在此对于string当中使用下标加[ ]来实现对string对象内的元素访问我们要实现非const版本和const版本，在对于非const对象访问时能读也能写，const对象访问时只能读。
要实现以上的要求接下来我们就要实现函数重载
先在srring.h完成函数的声明
char& operator[](size_t n);
const char& operator[](size_t n)const;接下来在string.cpp内完成函数的定义
char& string::operator[](size_t n)
{
assert(n < _size);
return _str[n];
}
const char& string::operator[](size_t n)const
{
assert(n < _size);
return _str[n];
}注：在此使用assert来检测下标位置n是否符合要求
7.迭代器
在此迭代器我们实现的是正向迭代器和const迭代器，而反向迭代器目前学习的知识还无法实现
在迭代器的模拟实现中我们使用的是将char*重命名为iterator，将const char*重命名为const_iterator
typedef char* iterator;
typedef const char* const_iterator;接下来就来实现begin和end
在此由于该迭代器地的函数都为短小函数就直接将该函数放在string.h内而不再使用声明和定义分离的方式
iterator begin()
{
return _str;
}
const_iterator begin()const
{
return _str;
}
iterator end()
{
return _str + _size;
}
const_iterator end()const
{
return _str + _size;
}
8.reserve
通过之前string的学习我们知道reserve的作用是将string对象的内存空间大小改为指定大小，并且我们知道当使用reserve时若当前的值小于原开间的大小时对原空间大小不做处理，只有当指定的值大于原空间大小的值时才做处理。
先在srring.h完成函数的声明
void reserve(size_t n);接下来在string.cpp内完成函数的定义
void string::reserve(size_t n)
{
if (n > _capacity)
{
char* tmp = new char[n + 1];
strcpy(tmp, _str);
delete[]_str;
_str = tmp;
_capacity = n;
}
}
在以上实现reserve函数时先使用new是申请n+1大小的内存空间，之后再将原_str指向的内存空间的数据拷贝到新创建的内存空间内，之后再将原_str指针指向新的内存空间，最后将_capacity值置为n即可
9.push_back和append
通过之前string的学习我们知道push_back可以将一个字符尾插到字符串当中，而append能将一个字符串尾插到另一个字符串当中
先在srring.h完成函数的声明
void push_back(char ch);
void append(const char* str);注：原append函数是实现了多个接口的， 在此我只是为了模拟实现，因此就只实现以上一个接口
接下来在string.cpp内完成函数的定义
在实现尾插时实现的过程代码是很简单的和之前我们完成顺序表的尾插类似，但在插入之前我们先要将字符串的空间问题解决，也就是在当字符串在插入之前先判断是否要进行空间的扩容
在此由于push_back只插入一个字符那么对于是否要对空间进行调整的判断就较为简单，代码如下所示：
void string::push_back(char ch)
{
if (_size == _capacity)//判断空间是否满了
{
reserve(_capacity == 0 ? 4 : 2 * _capacity);
}
_str[_size++] = ch;//尾插
_str[_size] = '\0';
}注：在此在将字符尾插到原字符串之后要在字符串下标_size位置值赋值为\0，这样才能让尾插之后也为字符串
完成了push_back的函数的实现接下来来实现append函数
在append函数当中由于插入的是字符串因此对于是否要对空间进行调整的判断就较为复杂，首先是要使用strlen得到要插入的字符串的长度，之后再判断将string对象中的字符串长度再加上要插入的字符串长度是否比原空间大小大；当比原空间大小小时就不需要扩容，比原空间大小大时就继续判断是否比原空间大小的两倍大，若比原空间大小的两倍大就将空间大小改变为原空间size+要插入的字符串的长度
void string::append(const char* str)
{
size_t len = strlen(str);
if (len + _size > _capacity)
{
size_t newcapacity = 2 * _capacity;
if (len + _size > newcapacity)
{
newcapacity = _size + len;
}
reserve(newcapacity);
}
strcpy(_str + _size, str);
_size += len;
}
10.+=运算符重载
在+=运算符的重载当中支持两个接口，分别是+=一个字符，+=一个字符串
先在srring.h完成函数的声明
string& operator+=(char ch);
string& operator+=(const char* str);接下来在string.cpp内完成函数的定义
在此在+=的实现当中直接调用之前实现的push_back和append即可
string& string::operator+=(char ch)
{
push_back(ch);
return *this;
}
string& string::operator+=(const char* str)
{
append(str);
return *this;
}11.Insrt
通过之前string的学习我们了解了Insert是实现字符串任意位置的插入，在此该函数都支持了多个接口
在模拟实现当中我们只实现Insert的以下接口，在此先在string.h进行函数的声明
void Insert(size_t pos, char ch);
void Insert(size_t pos, const char* str);
接下来在string.cpp内完成函数的定义
接下来先来分析Insert当中插入一个字符的接口该如何实现
在此来通过以上的示例来分析，在以上字符串当中如要在数组下标为8处插入字符X，也就是要在Wo和rld之间插入，那么就需要将从字符r开始的字符都向后移动一位，之后再将字符插入到数组下标为8处。
要实现以上的操作在此就定义一个变量end一开始为字符串末尾\0的数组下标，再定义一个变量pos为要插入字符的下标
之后从end位置开始将end位置的元素移动到end+1位置，再end--，之后一直重复该操作直到end与pos相等即停止。最后将要插入的字符插入到pos位置即完成字符串当中在pos位置插入字符
通过以上示例的分析就可以得出以下的代码
void string::Insert(size_t pos, char ch)
{
assert(pos < _size);
if (_size == _capacity)
{
reserve(_capacity == 0 ? 4 : 2 * _capacity);
}
size_t end = _size;
while (end >= pos)
{
_str[end+1] = _str[end];
end--;
}
_str[pos] = ch;
_size++;
}以上代码看起来似乎满足我们的要求，但实际上有一个非常大的问题没有考虑到，你发现了吗？
在此要注意的是由于数组下标没有负数因此一开始将pos类型定义为无符号整型size_t。之后将end的类型也定义为size_t这就使得当我们在下标为0位置插入字符时就会出现问题，问题是当最后将下标为0的数据赋值到下标为1处之后end--，在此end本应该为-1，之后就停止循环，但由于end为无符号整型再将0再减一之后就会变成整型的最大值，因此while循环会形成死循环。
通过以上的分析就可以看出以上代码是存在问题的，那么该如何修改呢？
这就要将变量类型修改成int，并且再while循环的判断部分要修改为end>=(int)pos，这是因为若不对pos进行强制类型转换，在该表达式会存在整型提升，会将有符号整型end提升为无符号整型，之后又会出现以上的问题
void string::Insert(size_t pos, char ch)
{
assert(pos < _size);
if (_size == _capacity)
{
reserve(_capacity == 0 ? 4 : 2 * _capacity);
}
int end = _size;
while (end >= (int)pos)
{
_str[end+1] = _str[end];
end--;
}
_str[pos] = ch;
_size++;
}
在以上我们使用的这种方法实现的过程中需要将end定义为int类型并且还要在循环时将pos强转为int，这个过程似乎有太多需要特别编写的地方，接下来就来实现一种更好的方法
在此也是先通过示例来讲解这种方法
还是在以上字符串当中如要在数组下标为8处插入字符X
在此还是先定义一个变量pos为要插入字符的下标，不同的是再再定义一个变量end一开始为字符串末尾\0的数组下标的下一位
之后从end位置开始将end-1位置的元素移动到end位置，再end--，之后一直重复该操作直到end-1与pos相等即停止。最后将要插入的字符插入到pos位置即完成字符串当中在pos位置插入字符
再以上使用这种方法就不存在最终end减一后为负数的情况了
以上方法实现的代码如下所示：
void string::Insert(size_t pos, char ch)
{
assert(pos < _size);
if (_size == _capacity)
{
reserve(_capacity == 0 ? 4 : 2 * _capacity);
}
size_t end = _size + 1;
while (end > pos)
{
_str[end] = _str[end - 1];
end--;
}
_str[pos] = ch;
_size++;
}接下来我们继续实现Insert的另一个接口
在此来通过以上的示例来分析，在以上字符串当中如要在数组下标为8处插入字符串XXX，也就是要在Wo和rld之间插入，那么就需要将从字符r开始的字符都向后移动三位，之后再将字符串插入到数组下标为8处。
在此插入字符串和插入字符一样也有两种方式，以下是第一种实现方法
要实现以上的操作在此就定义一个变量end一开始为字符串末尾\0的数组下标，再定义一个变量pos为要插入字符的下标
之后从end位置开始将end位置的元素移动到end+3位置，再end--，之后一直重复该操作直到end与pos相等即停止。最后将要插入的字符插入到pos位置即完成字符串当中在pos位置插入字符
该方法实现的代码如下所示：
void string::Insert(size_t pos, const char* str)
{
assert(pos < _size);
size_t len = strlen(str);
if (_size + len > _capacity)
{
size_t newcapacity = 2 * _capacity;
if (_size + len > newcapacity)
{
newcapacity = _size + len;
}
reserve(newcapacity);
}
int end = _size ;
while (end >= (int)pos)
{
_str[end + len] = _str[end];
end--;
}
for (size_t i = 0; i < len; i++)
{
_str[pos + i] = str[i];
}
_size += len;
}第二种实现方法
要实现以上的操作在此就定义一个变量end一开始为字符串末尾\0后一位的数组下标，再定义一个变量pos为要插入字符的下标
之后从end位置开始将end-3位置的元素移动到end位置，再end--，之后一直重复该操作直到end与pos+3相等即停止。最后将要插入的字符插入到pos位置即完成字符串当中在pos位置插入字符
该方法实现的代码如下所示：
void string::Insert(size_t pos, const char* str)
{
assert(pos < _size);
size_t len = strlen(str);
if (_size + len > _capacity)
{
size_t newcapacity = 2 * _capacity;
if (_size + len > newcapacity)
{
newcapacity = _size + len;
}
reserve(newcapacity);
}
size_t end = _size + len;
while (end > pos + len - 1)
{
_str[end] = _str[end - len];
end--;
}
for (size_t i = 0; i < len; i++)
{
_str[pos + i] = str[i];
}
_size += len;
}12.Erase
通过之前string的学习我们了解了Erase是实现字符串任意位置的删除，在此该函数都支持了多个接口
在模拟实现当中我们只实现Insert的以下接口，在此先在string.h进行函数的声明
void Erase(size_t pos = 0, size_t len = npos);
接下来在string.cpp内完成函数的定义
void string::Erase(size_t pos, size_t len)
{
if (_size - pos <= len)
{
_str[pos] = '\0';
_size = pos;
}
else
{
size_t end = pos + len;
while (end <= _size)
{
_str[end - len] = _str[end];
end++;
}
_size -= len;
}
}13.find
通过之前sting的学习我们知道find是用于在一个字符串当中查找一个字符或者或者字符串，当字符或者字符串在原被查找的string对象当中存在时就返回首个字符的下标，了解了这些之后接下来就来模拟实现find函数
在此先在string.h进行函数的声明
size_t find(char ch, size_t pos = 0);
size_t find(const char* str, size_t pos = 0);接下来在string.cpp内完成函数的定义
size_t string::find(char ch, size_t pos)
{
assert(pos < _size);
for (int i = pos; i < _size; i++)
{
if (_str[i] == ch)
{
return i;
}
}
return npos;
}
size_t string::find(const char* str, size_t pos)
{
assert(pos < _size);
char* p = strstr(_str + pos, str);
if (p == nullptr)
{
return npos;
}
return p - _str;
}
14.clear
在此在string中clear的功能是将srting对象的有效元素清除，那么模拟实现就很简单就只需要将string对象当中的_size变为0，并且再在_str数组下标为0处元素变为\0
由于该函数为短小函数，在此就将声明和定义都放在string.h内
void clear()
{
_str[0] = '\0';
_size = 0;
}
15.substr
通过之前的学习我们知道在substr是来实现在str中从pos位置开始，截取n个字符，然后将其返回
在此先在string.h进行函数的声明
string substr(size_t pos = 0, size_t len = npos)const;接下来在string.cpp内完成函数的定义
string string::substr(size_t pos, size_t len) const
{
if (len > _size - pos)
{
len = _size - pos;
}
string tmp;
tmp.reserve(len);//提前扩容，避免多次扩容
for (int i = 0; i < len; i++)
{
tmp += _str[pos + i];
}
return tmp;
}16.关系运算符
在string当中通过了以下多个关系的判断的接口，在此在模拟实现当中我们只实现参数都为string的接口，当参数传的是字符指针时会进行隐式类型转换。并且要实现原string当中类似的函数就需要将这些关系运算符函数放在我们定义的类外
接下来在string.cpp内完成函数的定义
bool operator== (const string& lhs, const string& rhs);
bool operator!= (const string& lhs, const string& rhs);
bool operator<= (const string& lhs, const string& rhs);
bool operator>= (const string& lhs, const string& rhs);
bool operator< (const string& lhs, const string& rhs);
bool operator> (const string& lhs, const string& rhs);
接下来在string.cpp内完成函数的定义
bool operator== (const string& lhs, const string& rhs)
{
return strcmp(lhs.c_str(), rhs.c_str()) == 0;
}
bool operator!= (const string& lhs, const string& rhs)
{
return !(lhs == rhs);
}
bool operator<= (const string& lhs, const string& rhs)
{
return lhs == rhs || lhs < rhs;
}
bool operator>= (const string& lhs, const string& rhs)
{
return !(lhs < rhs);
}
bool operator< (const string& lhs, const string& rhs)
{
return strcmp(lhs.c_str(), rhs.c_str()) < 0;
}
bool operator> (const string& lhs, const string& rhs)
{
return !(lhs <= rhs);
}