目录
一、string类的基本框架
二、基本函数的实现
(一)构造函数
1、无参构造
2、带参构造
3、无参与带参的合并
(二)遍历函数
1、有效字符个数与operator[]
2、迭代器
三、高级函数的实现
(一)插入函数
1、扩容操作reserve
2、push_back
3、append
4、operator+=
(1)插入字符
(2)插入字符串
5、insert
(1)插入字符
(2)插入字符串
四、删除函数的实现
五、查找函数的实现
六、截取函数的实现
七、运算符重载
八、整体代码
一、string类的基本框架
string模拟实现的底层结构设计为字符顺序表,又与顺序表不同,它有'\0',又有自己专用的接口,命名为string类会与库中自带的string类有命名冲突,可以把自己写的类放进自定义名字的命名空间中。string类的基本框架模拟实现如下:
#pragma once
#include<iostream>
#include<assert.h>
using namespace std;namespace zyb
{class string{public:private:size_t _size;size_t _capacity;char* _str;};
}
二、基本函数的实现
(一)构造函数
1、无参构造
不能把 _str、_size和_capacity粗暴地初始化为nullptr、0和0,因为库中的string类创造空对象后使用c_str可以打印空字符,程序不会崩溃,而初始化为nullptr后,使用c_str函数后进行打印,程序会崩溃:
string s1;
cout << s1.c_str() << endl;
因为这样是打印s1中的字符串_str,而打印字符串是遇到'\0'才终止,就要对函数返回的指针进行解引用找到内容中的'\0',但s1是个空指针,就会造成空指针解引用报错。
所以就要给初始化的值为:new charp[1]{'\0'},但为什么不写成new char('\0')?
① 用于后续扩容的操作。
② 为了与带参构造开辟方式进行统一,便于析构。在有参构造中需要new多个char,使用的是 new[],在析构函数中使用delete[]与new[]匹配,对无参构造与有参构造的动态申请的资源的清除。
无参构造函数的模拟实现如下:
string::string():_str(new char[1] {'\0'}), _size(0), _capacity(0)
{}
2、带参构造
因为传入的是一个字符串,此时_str的写法为:
_str(new char[strlen(str)+1])
因为strlen是不计算'\0'的长度,需要加一来补上'\0'的长度。
空间开辟后就要进行数据的拷贝,需要在函数体中解决,构造如下:
string(const char* str):_str(new char[strlen(str)+1]),_size(strlen(str)),_capacity(strlen(str))
{strcpy(_str, str);
}
因为strlen是一个io函数,与sizeof在编译时运算不同,strlen是在运行时计算的,在运行时计算会容易出风险,比如:缓冲区溢出、效率问题、字符串内容被意外修改等风险。尽量减少使用strlen进行初始化。
改进:
string(const char* str):_size(strlen(str)),_capacity(_size),_str(new char[_size+1])
{strcpy(_str, str);
}
但这也具有一定风险:初始化顺序是根据成员变量定义的顺序来进行的,这就会导致随机值的出现。
解决:修改成员变量定义的顺序。但后续代码被修改后风险依旧存在。
再改进:只留_size在初始化列表,剩下的成员变量在结构体中进行初始化,这样就不用担心成员变量在定义时被打乱位置而造成的构造错误与多次调用strlen的问题,代码如下:
string(const char* str):_size(strlen(str))
{_capacity = _size;_str = new char[_size + 1];strcpy(_str, str);
}
虽然在构造的时候_capacity与_str还是会走初始化列表,并且编译器会给一些默认值,但它们接下来会进入函数体中,把这些值进行修正,并不会影响最后的结果。
注意:在分离声明和定义的时候,声明的地方是有命名空间的,在定义的时候也可以使用同名的命名空间,编译器在编译的时候会把他们合为一体。定义函数时还是需要在命名空间中指定类域。
3、无参与带参的合并
构造函数最好提供一个全缺省的参数的,这样就可以把无参构造与带参构造合并起来,只需如下定义:
string(const char* str = "");
直接使用 "" 作为缺省值即可,因为常量字符串后面是自带一个'\0'的。
注意一点:若声明与定义分离,则只能在声明处给缺省值。
string.h文件
#pragma once #include<iostream> #include<assert.h> using namespace std;namespace zyb {class string{public://一、构造函数string(const char* str = "");private:size_t _size;size_t _capacity;char* _str;}; }
string.cpp文件
namespace zyb {//一、构造函数string::string(const char* str):_size(strlen(str)){_capacity = _size;_str = new char[_size + 1];strcpy(_str, str);} }
(二)遍历函数
1、有效字符个数与operator[]
//二、遍历操作
//(一)提供下标的最大值_size
size_t size() const
{return _size;
}//(二)普通版本的operator
char& operator[](size_t i)
{assert(i < _size);//判断是否在合理的范围之内return _str[i];
}
//(三)const版本的operator
const char& operator[](size_t i) const
{assert(i < _size);return _str[i];
}
const版本的返回值不能被修改,所以要用const修饰返回值。
2、迭代器
因为string的底层是一个数组,因此可以使用一个字符指针来对迭代器进行模拟实现:
using iterator = char*;
// typedef char* iterator;
范围for对迭代器是有要求的,对应的只能是begin函数,大小写字母不能改变,必须按照命名规则去写。
常量迭代器:
为什么是const_iterator,而不是const修饰iterator?
因为const_iterator表示的是迭代器所指向的内容不能修改,const修饰iterator表示的是迭代器不能修改。
string.h文件
using iterator = char*; using const_iterator = const char*; // 1、begin iterator begin() {return _str;// begin返回首元素的迭代器 } // 2、begin iterator end() {return _str + _size;// end返回末尾元素的下一个位置的迭代器 } // 3、const迭代器的begin const_iterator begin() const {return _str; } // 4、const迭代器的begin const_iterator end() const {return _str + _size; }
三、高级函数的实现
(一)插入函数
1、扩容操作reserve
//扩容
void string::reserve(size_t n)
{if (n > _capacity){char* temp = new char[n + 1];//+1是给'\0'留位置strcpy(temp, _str);delete[] _str;_str = temp;_capacity = n;}
}
2、push_back
//push_back
void string::push_back(char ch)
{if (_size == _capacity)//有效字符数与总容量相等就要进行扩容{reserve(_capacity == 0 ? 4 : _capacity * 2);//扩容,使用三目操作符,需要判断总空间是否为0的情况}_str[_size] = ch;_size++;
}
3、append
//append
void string::append(const char* str)
{size_t len = strlen(str);if (_size + len > _capacity){size_t NewCapacity = _capacity * 2;if (_size + len > NewCapacity)//括两倍不够,则需要多少就括多少NewCapacity = _size + len;reserve(NewCapacity);}strcpy(_str + _size, str);_size += len;
}
4、operator+=
对push_back与append进行复用即可
(1)插入字符
string& string::operator+=(char ch)
{push_back(ch);return *this;
}
(2)插入字符串
string& string::operator+=(char ch)
{push_back(ch);return *this;
}
5、insert
(1)插入字符
void string::insert(size_t pos, char ch)
{//扩容逻辑与push_back相同if (_size == _capacity)reserve(_capacity == 0 ? 4 : _capacity*2);//insert需要向后挪动数据rsize_t end = _size;while (end >= pos){_str[end + 1] = _str[end];end--;}//插入数据_str[pos] = ch;_size++;
}
这样写的话在pos等于0时会造成越界问题与死循环的出现,因为pos与end都等于0时,end会--,变成-1,而size_t类型的-1又是一个很大的数,就会造成越界访问。
断点调试小技巧,想要定条件判断断点,直接写一段无意义的代码,把判断条件写成想要的那个条件就行,例如:
if(end == 0)int i = 0;//在此处打断点然后继续向下走
pos等于0时解决越界方法:
解决方案一:把end设为为int类型,int类型的end与pos进行比较的时候,end会进行类型提高,成无符号类型,变成-1后依旧可以进行后移;所以比较时还要把pos的类型强转为无符号整形。
解决方案二:不把当前数据向后移,而是把前一位数据移向当前位置,做法:把end定位在_size 的后一位,也就是“\0”的后一位,然后赋值移动,当pos == end的时候,就终止了,不会再--为-1, 循环时进行小于判断即可。修改关键代码如下:
//insert需要向后挪动数据
rsize_t end = _size + 1;
while (end > pos)
{_str[end] = _str[end - 1];end--;
}
第二种解决方案更好。
(2)插入字符串
类比上面的逻辑得出:
void string::insert(size_t pos, const char* str)
{//扩容逻辑与append一样size_t len = strlen(str);if (_size + len > _capacity){size_t NewCapacity = _capacity * 2;if (_size + len > NewCapacity)//括两倍不够,则需要多少就括多少NewCapacity = _size + len;reserve(NewCapacity);}//insert需要向后挪动数据rsize_t end = _size + len;while (end != pos){_str[end] = _str[end - len];//把前len个数据向后移end--;}//插入数据for (size_t i = 0; i < len; i++){_str[pos + i] = str[i];//使用循环进行插入 }_size += len;
}
这样可能会存在越界问题:当end的落地在第二个字符,而pos的位置是第一个字符,插入的字符串的len长度为6,就会造成越界访问。
while的条件要改成 end > pos+len-1,因为当 end = pos + len时,pos = end - len,恰好是需要挪动的最后一位,然后end--,就是(pos + len)--,也就是pos + len - 1的时候就结束:
//insert需要向后挪动数据
size_t end = _size + len;
while ( end > pos + len - 1)
{_str[end] = _str[end - len];//把前len个数据向后移end--;
}
四、删除函数的实现
在定义静态变量npos时,在类中声明,类外定义(static不用写);但在头文件中进行定义与声明时,又因为头文件会在其他文件在编译时展开,就会出现同一静态变量多次定义,造成连接错误。所以要在头文件中进行声明,在cpp文件中进行定义。
const 静态变量npos就可以在类中进行声明与定义,是一个例外。但还是建议在类中声明,类外定义。
string.h文件
namespace zyb {class string{public:static size_t npos;} };
string.cpp文件
namespace zyb {size_t string::npos = -1; }
删除函数的模拟实现:
string.h文件
void erase(size_t pos, size_t len = npos);
string.cpp文件
void string::erase(size_t pos, size_t len) {assert(pos < _size);if (len >= _size - pos){_str[pos] = '\0';_size = pos;}else{size_t end = pos + len;while (end <= _size){_str[end - len] = _str[end];end++;}_size -= len;} }
五、查找函数的实现
查找函数的实现如下:
//查找
//(一)查找一个字符
size_t string::find(char ch, size_t pos = 0)
{assert(pos < _size);for (size_t i = pos; i < _size; i++){if (_str[i] == ch)return i;}return npos;
}
//(二)查找一个字符串
size_t string::find(const char* str, size_t pos = 0)
{const char* ptr = strstr(_str + pos, str);if (ptr == nullptr)return npos;elsereturn (ptr - _str);
}
六、截取函数的实现
截取函数的返回类型是string类型,涉及到拷贝构造的问题:浅拷贝与深拷贝
截取函数的实现:
string string::substr(size_t pos, size_t len)
{assert(pos < _size);if (len > (_size - pos))len = _size - pos;//更新len的长度zyb::string sub;sub.reserve(len);for (size_t i = 0; i < len; i++){sub += _str[pos + i];}return sub;
}
拷贝构造的实现:
string::string(const string& s)
{_str = new char[s._capacity + 1];strcpy(_str, s._str);_size = s._size;_capacity = s._capacity;
}
七、运算符重载
比较运算符重载到全局更好,因为可以进行string类与字符串的对比、字符串与string类的对比、string类与string类的对比,但重载到类中固定第一个操作数就是string类,没有重载到全局时的对比多。
写的时候重载string类与string类的对比就行,其他的可以靠隐式类型转换来实现即可。
string.h文件
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文件
//赋值运算符重载 string& string::operator=(const string& s) {if (this != &s)//判断是不是自己给自己赋值{delete[] _str;_str = new char[s._capacity + 1];strcpy(_str, s._str);_size = s._size;_capacity = s._capacity;}return *this; } 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 strcmp(lhs.c_str(), rhs.c_str()) > 0; } 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); }
istream 和 ostream都不支持拷贝,所以在重载流输入或流输出时,iostream类型都要使用引用。
cin和scanf都会忽略掉空格与换行,认为是多个值之间的分割。这样的话就拿不到输入的空格或换行。
解决:io流是一个类的体系,cout和cin只是类中的一个对象,可以用其他接口来完成对输入空格与换行的读取。比如io流中的get函数,不会对空格或换行进行区分,无论是什么字符都可以输入:
cin.get();
流输入与流提取的模拟实现如下:
string.h
iostream& operator<<(iostream& os, const string& s);//使用的是for循环来输出每一个字符 iostream& operator>>(iostream& is, string& s);
string.cpp文件
iostream& operator<<(iostream& os, const string& s) {for (size_t i = 0; i < s.size(); i++){os << s[i];}return os; } iostream& operator>>(iostream& is, string& s) {s.clean();char ch;ch = is.get();while (ch != ' ' && ch != '\n'){s += ch;ch = is.get();}return is; }
注意:每次使用重载的流输入都要对其内容进行清除,不然会把新输入的东西放进旧字符串中。
void clean()
{_str[0] = '\0';_size = 0;
}
八、整体代码
string.h文件
#pragma once #include<iostream> #include<assert.h> using namespace std;namespace zyb {class string{public://一、构造函数// (一)无参构造//string();// (二)带参构造string(const char* str = "");//(三)拷贝构造string(const string& s);//二、析构函数~string();//三、返回字符串_str函数c_strconst char* c_str() const{return _str;}//四、遍历操作//(一)提供下标的最大值_sizesize_t size() const{return _size;}//(二)普通版本的operatorchar& operator[](size_t i){assert(i < _size);//判断是否在合理的范围之内return _str[i];}//(三)const版本的operatorconst char& operator[](size_t i) const{assert(i < _size);return _str[i];}//(四)迭代器using iterator = char*;using const_iterator = const char*;// 1、beginiterator begin(){return _str;// begin返回首元素的迭代器}// 2、beginiterator end(){return _str + _size;// end返回末尾元素的下一个位置的迭代器}// 3、const迭代器的beginconst_iterator begin() const{return _str;}// 4、const迭代器的beginconst_iterator end() const{return _str + _size;}//五、插入函数//容量控制void reserve(size_t n);//(一)push_backvoid push_back(char ch);//(二)appendvoid append(const char* str);//(三)operator+=string& operator+=(char ch);string& operator+=(const char* str);//六、插入与删除//(一)插入void insert(size_t pos, char ch);void insert(size_t pos, const char* str);//(二)删除void erase(size_t pos, size_t len = npos);//七、查找//(一)查找一个字符size_t find(char ch, size_t pos = 0);//(二)查找一个字符串size_t find(const char* str, size_t pos = 0);//八、截取string substr(size_t pos, size_t le = npos);//九、运算符重载string& operator=(const string& s);void clean(){_str[0] = '\0';_size = 0;}private:size_t _size;size_t _capacity;char* _str;public:static size_t npos;};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);iostream& operator<<(iostream& os, const string& s);//使用的是for循环来输出每一个字符iostream& operator>>(iostream& is, string& s);}
string.cpp文件
#define _CRT_SECURE_NO_WARNINGS 1 #include"string.h"namespace zyb {size_t string::npos = -1;//一、构造函数//(一)无参构造/*string::string():_str(new char[1] {'\0'}), _size(0), _capacity(0){}*///(二)带参构造string::string(const char* str):_size(strlen(str)){_capacity = _size;_str = new char[_size + 1];strcpy(_str, str);}//(三)拷贝构造string::string(const string& s){_str = new char[s._capacity + 1];strcpy(_str, s._str);_size = s._size;_capacity = s._capacity;}//三、析构函数string::~string(){delete[] _str;_str = nullptr;//别忘了置空_size = 0;_capacity = 0;}//扩容void string::reserve(size_t n){if (n > _capacity){char* temp = new char[n + 1];//+1是给'\0'留位置strcpy(temp, _str);delete[] _str;_str = temp;_capacity = n;}}//五、插入函数//(一)push_backvoid string::push_back(char ch){if (_size == _capacity)//有效字符数与总容量相等就要进行扩容{reserve(_capacity == 0 ? 4 : _capacity * 2);//扩容,使用三目操作符,需要判断总空间是否为0的情况}_str[_size] = ch;_size++;}//(二)appendvoid string::append(const char* str){size_t len = strlen(str);if (_size + len > _capacity){size_t NewCapacity = _capacity * 2;if (_size + len > NewCapacity)//括两倍不够,则需要多少就括多少NewCapacity = _size + len;reserve(NewCapacity);}strcpy(_str + _size, str);_size += len;}//(三)operator+=string& string::operator+=(char ch){push_back(ch);return *this;}string& string::operator+=(const char* str){append(str);return *this;}//(四)insert//1、插入字符void string::insert(size_t pos, char ch){assert(pos <= _size);//扩容逻辑与push_back相同if (_size == _capacity)reserve(_capacity == 0 ? 4 : _capacity*2);//insert需要向后挪动数据rsize_t end = _size + 1;while (end > pos){_str[end] = _str[end - 1];//把前1个数据向后移end--;}//插入数据_str[pos] = ch;_size++;}//2、插入字符串void string::insert(size_t pos, const char* str){assert(pos <= _size);//扩容逻辑与append一样size_t len = strlen(str);if (_size + len > _capacity){size_t NewCapacity = _capacity * 2;if (_size + len > NewCapacity)//括两倍不够,则需要多少就括多少NewCapacity = _size + len;reserve(NewCapacity);}//insert需要向后挪动数据size_t end = _size + len;while ( end > pos + len - 1){_str[end] = _str[end - len];//把前len个数据向后移end--;}//插入数据for (size_t i = 0; i < len; i++){_str[pos + i] = str[i];//使用循环进行插入 }_size += len;}//六、删除函数void string::erase(size_t pos, size_t len){assert(pos < _size);if (len >= _size - pos){_str[pos] = '\0';_size = pos;}else{size_t end = pos + len;while (end <= _size){_str[end - len] = _str[end];end++;}_size -= len;}}//七、查找//(一)查找一个字符size_t string::find(char ch, size_t pos = 0){assert(pos < _size);for (size_t i = pos; i < _size; i++){if (_str[i] == ch)return i;}return npos;}//(二)查找一个字符串size_t string::find(const char* str, size_t pos = 0){const char* ptr = strstr(_str + pos, str);if (ptr == nullptr)return npos;elsereturn (ptr - _str);}//八、截取string string::substr(size_t pos, size_t len){assert(pos < _size);if (len > (_size - pos))len = _size - pos;//更新len的长度zyb::string sub;sub.reserve(len);for (size_t i = 0; i < len; i++){sub += _str[pos + i];}return sub;}//九、运算符重载//赋值运算符重载string& string::operator=(const string& s){if (this != &s)//判断是不是自己给自己赋值{delete[] _str;_str = new char[s._capacity + 1];strcpy(_str, s._str);_size = s._size;_capacity = s._capacity;}return *this;}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 strcmp(lhs.c_str(), rhs.c_str()) > 0;}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);}iostream& operator<<(iostream& os, const string& s){for (size_t i = 0; i < s.size(); i++){os << s[i];}return os;}iostream& operator>>(iostream& is, string& s){s.clean();char ch;ch = is.get();while (ch != ' ' && ch != '\n'){s += ch;ch = is.get();}return is;} }
以上内容仅供分享,若有错误,请多指正