为了更好的使用C++中的标准库,下面是对string一些比较重要的接口进行模拟实现,有需要借鉴即可。
这里给出string文档地址链接,方便对照:LINK
1.string结构的设计
string底层我们使用字符数组来实现,即顺序表,惟一与顺序表做区分的是我们的string后面默认有个\0,这个需要注意的。
class string { private: char* _str; size_t _size; size_t _capacity; };
2.string构造函数
string构造函数的模拟实现有两种实现方式,
- 1.分开写无参构造函数和有参构造函数
- 2.只写一个通用的构造函数,即全缺省构造函数
下面来介绍两种不同的写法:
2.1构造函数分开写
//分开写的情况下: //无参构造器 string() :_str(new char)//这里写nullptr可以吗?不可以,因为这样用于结合c_str的接口特性。 , _size(0) , _capacity(0) { _str[0] = '\0'; } //有参构造器 string(const char* str) :_size(strlen(str)) { _capacity = _size;//capacity和size计算给值 _str = new char[_size + 1];//给空间 strcpy(_str, str);//拷贝过去,这里自带\0不用担心 } */
思考:开空间时候为什么多开一个?
答:为\0预留位置。在上面无参构造器种开一个空间即是这个道理
思考:为什么要在string末尾多加一个\0?
我们说,C语言喜欢把字符串末尾多加一个\0,这是因为C语言没有标识字符串的长度,用\0来标识字符的结尾。但是我们string是有_size来进行维护的呀,怎么还需要用\0呢?
答:其实这个问题是string要与C字符串相兼容的缘故,正因为是C++要兼容C也是一样的道理。
2.2构造函数一块写
string(const char* str = "")//这个地方的缺省参数用什么? :_size(strlen(str))//看一下有一个字符 { _capacity = _size;//标识该字符的长度,空间大小,标识情况下并不包含capacity的大小 _str = new char[_capacity + 1];//开空间 strcpy(_str, str);//把临时变量的值拷贝过去 }
思考:str为什么给缺省值?
答:因为这主要是有时候是充当无参构造器来用的。
思考:这个str的缺省值为什么给两个引号?
答:这里并不是两个引号的意思,而是一个字符串,这个字符串是有一个字符的,为\0。
拷贝构造函数怎么写?这个地方涉及到深浅拷贝问题,所以需要自己另开空间才行
2.3拷贝构造函数的传统写法
string(string& s) { _capacity = s._capacity; _size = s._size; _str = new char[_capacity + 1]; strcpy(_str, s._str); }
2.4拷贝构造函数的现代写法
//现代写法 string(string& s) { string temp(s._str);//这个地方会去调用构造函数,构造出一个新的堆过来。 swap(temp); }
思考:拷贝构造函数的传统写法和现代写法哪个更好?
答:他俩是基本一样的,只不过第二种把第一种那一段代码用构造函数等效掉了。
2.5赋值运算符重载
string& operator=(const string& s) { _capacity = s._capacity; _size = s._size; delete[] _str; char* temp = new char[_capacity + 1]; _str = temp; strcpy(_str, s._str); return *this; }
思考:什么时候编译器会调用赋值运算符重载,又什么时候调用拷贝构造函数呢?
答:切忌不能单看是不是写的等于号哈,如果string s已存在,string sc正在创建,那调用的就是拷贝构造,如果s和sc都已经存在了,那就是调用的是赋值运算符重载。
其实赋值运算符重载也有现代写法,说白了算是一种复用吧:
//传统写法 /* string& operator=(const string& s) { _capacity = s._capacity; _size = s._size; delete[] _str; char* temp = new char[_capacity + 1]; _str = temp; strcpy(_str, s._str); return *this; } */ /* //现代写法 string& operator=(const string& s) { string temp(s.c_str()); swap(temp); return *this; } */ //极简版 string& operator=(string temp) { swap(temp); return *this; }
说完了构造函数的实现,我们再来说一下析构函数的写法
3.析构函数
~string() { delete[] _str; _str = nullptr; _capacity = _size = 0; }
析构函数这里很简单,不再多说。
4.遍历
遍历是string种常用的功能之一。string的遍历方式主要有三种,其一曰方括号,其二曰迭代器,其三曰范围for;
下面依次介绍三种string遍历的模拟实现:
4.1operator[]重载
char& operator[](size_t pos) { assert(pos < _size);//越界检查,传统的C语言数组检查是一种抽查 return _str[pos]; }
检查方式的进步:
注:这里需要注意一点的是方括号的函数重载的越界检查,这个越界检查是用assert实现的,更加全面安全;相对于C语言来说,因为C语言的越界检查是一种“抽查”,有时候读越界的时候是检查不出来的。
思考:这里返回值为什么用char&
答:效率更加高效,第二就是更加方便对string字符值的修改。因为遍历支持可读可写。
当然,为了适应不可修改的const string,我们也提供了const []重载
const char& operator[](size_t pos) const { return _str[pos]; }
这个函数后面为什么加const呢?
答:
1.防止在函数内对string字符做修改
2.构成函数重载
3.便于编译器调用const或非const的函数匹配
4.2迭代器
string的迭代器是一种像指针的遍历方式,使用上很像指针,但是具体内部是不是指针这就看具体是怎么实现的了。
typedef char* iterator;//必须要统一名称 + 类域 iterator begin() { return _str; } iterator end() { return _str + _size; }
我们还提供了const版本,以供const string使用
typedef const char* const_iterator; const_iterator begin() const { return _str; } const_iterator end() const { return _str + _size; }
4.3范围for
这个范围for最开始压根不是C++的语法,不过后来随着Python的崛起,C++觉得这玩意挺好使,然后就直接抄过来了,但是C++底层是用迭代器替换的方式支持范围for使用的。
也就是说,这个范围for在编译完了就是迭代器,编译器给你代码替换掉了而已。
typedef char* iterator;//必须要统一名称 + 类域 iterator begin() { return _str; } iterator end() { return _str + _size; }
typedef const char* const_iterator; const_iterator begin() const { return _str; } const_iterator end() const { return _str + _size; }
上面遍历方式说完了,咱们再来说一下字符/字符串插入这个话题
5.字符/字符串插入
这个地方库中是实现了很多的函数重载的,支持各种场景下的字符/字符串插入。
这个地方我为了简化只实现了其中的几个,库中实现的很多函数大体上是一样的。
5.1尾插一个字符
void push_back(char ch) { //扩容,扩大2倍 if (_capacity == _size) { reserve(_capacity == 0 ? 4 :2*_capacity); } _str[_size++] = ch; _str[_size] = '\0'; }
5.2尾插一个字符串
string& append(const char* str) { size_t len = strlen(str); //扩大s的长度倍数 if (len + _size > _capacity) { reserve(_capacity + len); } //拷贝数据 strcpy(_str + _size, str); //更新_size _size += len; return *this; }
5.3+=字符串
string& operator+=(const char* s) { this->append(s); return *this; }
5.4任意位置插入字符
string& insert(size_t pos,char ch) { assert(pos <= _size); if (_size == _capacity) { reserve(_capacity == 0 ? 4 : 2 * _capacity); } //坑1: //size_t end = _size; //while (end >= pos) //{ // _str[end + 1] = _str[end]; // end--; //} //坑2: //int end = _size; //while (end >= pos) //{ // _str[end + 1] = _str[end]; // end--; //} //修改1: int end = _size; while (end >= (int)pos) { _str[end + 1] = _str[end]; end--; } //修改2: /*int end = _size + 1; while (end > pos) { _str[end] = _str[end - 1]; end--; } */ _str[pos] = ch; _size++; return *this; }
这里有一些“大坑”哈,所以我这里来强调一下:
坑1:size_t end,这种写法,如果pos == 0,这种情况下end需要是-1才会停止循环,但是end是无符号数字
坑2:有人说我把end类型改成int就好了,但其实还不行,因为end与pos在if中进行比较的,这里会发生隐式类型转换,所以实际上还是size_t,只不过生成了一个临时对象与其进行比较而已
这个地方怎么修改呢?
第一种就是我没有注释掉的这种写法,强制类型转换
第二种就是改变while结束循环的条件即可。
5.5任意位置插入字符串
string& insert(size_t pos, const char* str) { assert(pos <= _size); size_t len = strlen(str); if (len + _size > _capacity) { //扩容 reserve(_size + len); } //挪动数据 int end = _size; while (end >= (int)pos) { _str[end + len] = _str[end]; end--; } //插入数据 int start = 0; while (len--) { _str[pos] = str[start]; pos++; start++; } //返回 return *this; }
说白了这个地方基本是一样的,能独立实现后两个我觉得问题基本不大。
6.erase函数
这个函数是“清理”的意思,第一个pos是从哪开始清理,len是清理删除字符的长度。
void erase(size_t pos, size_t len = npos) { assert(pos <= _size); if (len == npos || pos + len >= _size) { _str[pos] = '\0'; } else { strcpy(_str + pos, _str + pos + len); } }
注:pos + len >=len 在极端情况下可能会有溢出问题,这个时候可以用 pos >= _size - len;
7.resize函数接口
这个函数是干啥的呢?重新设置_size大小的。
resize:LINK
void resize(size_t n,char c = '\0') { if (n < _size) { _str[n] = '\0'; } else { reserve(n); for (size_t i = _size; i < n; i++) { _str[i] = c; } _str[n] = '\0'; } _size = n; }
注:参数char c 给缺省值主要是因为库中规定原size不够时候默认用\0进行填充。
8.swap交换
这个地方有两个swap交换的,第一个就是默认的C++算法库有一个swap模板,第二个是string里也实现了一个swap交换。
对于算法库中的swap,是一个模板哈。全能,但是消耗比较大;对于string中的swap,只能满足string之间的交换,但是效率高。
下面是模拟实现的string中swap函数(下面两个本质是同一个函数,区别在于一个是全局的,另一个是在类内的而已):
void swap(string& s) { std::swap(_str, s._str); std::swap(_capacity, s._capacity); std::swap(_size, s._size); }
//全局函数 void swap(string& s1, string& s2) { s1.swap(s2); }
9.取子串函数接口substr
在这里这个函数模拟实现会用到c_str()这个接口,所以先模拟实现一个c_str()函数,如下:
char* c_str() const { return _str; }
下面是substr函数的模拟实现:
string substr(size_t pos, size_t len = npos) { assert(pos < _size); string s; if (len == npos || pos + len >= _size) { s += _str + pos; } else { for (size_t i = 0; i < len; i++) { s.insert(i, _str[i + pos]); } } return s; }
注意:npos是不可修改静态全局变量,其值为-1,其声明包含于类内,在类外进行定义。
其声明如下:
static const int npos;
具体定义如下:
//类内静态成员变量必须要指明类域 const int string::npos = -1;
10.operator==赋值重载及其它判断符重载
这个很简单,如下:
bool operator==(const string& s1, const string& s2) { int cmp = strcmp(s1.c_str() , s2.c_str()); return cmp == 0; }
思考:为什么s1和s2在前面加上const?
缩小权限,满足非const string和const string的调用
思考:这个判断函数重载可以实现为类内函数吗?
答:可以,但是这个地方存在一个问题,如果一个非const,和另外一个const string进行比较可以进行比较吗?不是全部可以的。原因看下面代码:
string s1("hello world"); string s2("hello world"); //但是这种实现方式有缺陷: cout << (s1 == s2) << endl; cout << (s1 == "hello world") << endl;//right,隐式类型转换 cout << ("hello world" == s2) << endl;// == error,because it is not string //"hello world" == s2 ,即是hello world.operator==(s2); //为了弥补这个缺陷,c++将其实现成了全局函数 //实现为全局函数主要是为了支持char*的隐式类型转换
实现两个,剩下的复用就行了。
bool operator<(const string& s1, const string& s2) { int cmp = strcmp(s1.c_str(), s2.c_str()); return cmp < 0; } bool operator<=(const string& s1, const string& s2) { return s1 == s2 || s1 < s2; } 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); }
11.流插入和流提取接口
11.1流插入接口
//流插入重载 ostream& operator<<(ostream& out, const string& str) { for (auto ch : str) { out << ch << " "; } cout << endl; return out; }
这个地方为什么要实现为全局函数啊?
答:如果实现为类内函数,那么this指针是固定第一个的,那么调用的时候不得不写成 s << cout 这样调用有点怪怪的。
11.2流提取接口
下面这个函数模拟,在解决流提取时候一次开几个空间问题是一个比较好的思路,注意借鉴一下。
//流提取重载 istream& operator>>(istream& in, string& str) { str.clear(); char ch; char buff[128]; ch = in.get(); size_t i = 0; while (ch != ' ' && ch != '\n') { buff[i++] = ch; if (i == 127) { str[127] = '\0'; str += buff; i = 0; } ch = in.get(); } if (i > 0) { str[i] = '\0'; str += buff; } return in; }
12.getline接口
这个接口与流插入的思路是一样的,结束条件无非改成了\n而已。
istream& getline(istream& in, string& str) { str.clear(); char ch; ch = in.get(); while (ch != '\n') { str += ch; ch = in.get(); } return in; }
13.find接口
13.1在一个字符串中找一个字符
size_t find(const char ch, size_t pos = 0) const { assert(pos < _size); for (size_t i = 0; i < _size; i++) { if (_str[i] == ch) { return i; } } return npos; }
13.2在一个字符串中找一个子串
size_t find(const char* str, size_t pos = 0) const { assert(pos < _size); char* temp = strstr(_str, str); if (temp) { return temp - _str; } else { return npos; } }
这个地方用到了指针- 指针的操作可以注意一下。
14.所有代码一览
#define _CRT_SECURE_NO_WARNINGS 1 #include<assert.h> #include<iostream> using std::cout; using std::endl; using std::ostream; using std::istream; using std::cin; class string { private: char* _str = nullptr; size_t _size = 0; size_t _capacity = 0; static const int npos; public: //分开写的情况下: //无参构造器 /* string() :_str(new char)//这里写nullptr可以吗?不可以,因为这样用于结合c_str的接口特性。 , _size(0) , _capacity(0) { _str[0] = '\0'; } //有参构造器 string(const char* str) :_size(strlen(str)) { _capacity = _size;//capacity和size计算给值 _str = new char[_size + 1];//给空间 strcpy(_str, str);//拷贝过去,这里自带\0不用担心 } */ string(const char* str = "")//这个地方的缺省参数用什么? :_size(strlen(str))//看一下有一个字符 { _capacity = _size;//标识该字符的长度,空间大小,标识情况下并不包含capacity的大小 _str = new char[_capacity + 1];//开空间 strcpy(_str, str);//把临时变量的值拷贝过去 } //传统写法 /*string(string& s) { _capacity = s._capacity; _size = s._size; _str = new char[_capacity + 1]; strcpy(_str, s._str); }*/ //现代写法 string(string& s) { string temp(s._str);//这个地方会去调用构造函数,构造出一个新的堆过来。 swap(temp); } ~string() { delete[] _str; _str = nullptr; _capacity = _size = 0; } char* c_str() const { return _str; } size_t size()const { return _size; } size_t capacity()const { return _capacity; } char& operator[](size_t pos) { assert(pos < _size);//越界检查,传统的C语言数组检查是一种抽查 return _str[pos]; } const char& operator[](size_t pos)const { return _str[pos]; } typedef char* iterator;//必须要统一名称 + 类域 iterator begin() { return _str; } iterator end() { return _str + _size; } typedef const char* const_iterator; const_iterator begin() const { return _str; } const_iterator end() const { return _str + _size; } void reserve(size_t n) { if (n > _capacity) { char* temp = new char[n + 1]; strcpy(temp, _str); delete[] _str;//这个地方需要销毁_str的,因为temp是临时变量,不需要销毁 _str = temp; _capacity = n;//预留\0的位置 } } void push_back(char ch) { //扩容,扩大2倍 if (_capacity == _size) { reserve(_capacity == 0 ? 4 :2*_capacity); } _str[_size++] = ch; _str[_size] = '\0'; } string& append(const char* str) { size_t len = strlen(str); //扩大s的长度倍数 if (len + _size > _capacity) { reserve(_capacity + len); } //拷贝数据 strcpy(_str + _size, str); //更新_size _size += len; return *this; } string& operator+=(const char* s) { this->append(s); return *this; } 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--; //} //int end = _size; //while (end >= pos) //{ // _str[end + 1] = _str[end]; // end--; //} int end = _size; while (end >= (int)pos) { _str[end + 1] = _str[end]; end--; } /*int end = _size + 1; while (end > pos) { _str[end] = _str[end - 1]; end--; } */ _str[pos] = ch; _size++; return *this; } string& insert(size_t pos, const char* str) { assert(pos <= _size); size_t len = strlen(str); if (len + _size > _capacity) { //扩容 reserve(_size + len); } //挪动数据 int end = _size; while (end >= (int)pos) { _str[end + len] = _str[end]; end--; } //插入数据 int start = 0; while (len--) { _str[pos] = str[start]; pos++; start++; } //返回 return *this; } void erase(size_t pos, size_t len = npos) { assert(pos <= _size); if (len == npos || pos + len >= _size) { _str[pos] = '\0'; } else { strcpy(_str + pos, _str + pos + len); } } void resize(size_t n,char c = '\0') { if (n < _size) { _str[n] = '\0'; } else { reserve(n); for (size_t i = _size; i < n; i++) { _str[i] = c; } _str[n] = '\0'; } _size = n; } //传统写法 /* string& operator=(const string& s) { _capacity = s._capacity; _size = s._size; delete[] _str; char* temp = new char[_capacity + 1]; _str = temp; strcpy(_str, s._str); return *this; } */ /* //现代写法 string& operator=(const string& s) { string temp(s.c_str()); swap(temp); return *this; } */ //极简版 string& operator=(string temp) { swap(temp); return *this; } void swap(string& s) { std::swap(_str, s._str); std::swap(_capacity, s._capacity); std::swap(_size, s._size); } size_t find(const char ch, size_t pos = 0) const { assert(pos < _size); for (size_t i = 0; i < _size; i++) { if (_str[i] == ch) { return i; } } return npos; } size_t find(const char* str, size_t pos = 0) const { assert(pos < _size); char* temp = strstr(_str, str); if (temp) { return temp - _str; } else { return npos; } } string substr(size_t pos, size_t len = npos) { assert(pos < _size); string s; if (len == npos || pos + len >= _size) { s += _str + pos; } else { for (size_t i = 0; i < len; i++) { s.insert(i, _str[i + pos]); } } return s; } string& operator+=(const char ch) { push_back(ch); return *this; } void clear() { _size = 0; _str[0] = '\0'; } }; bool operator==(const string& s1, const string& s2) { int cmp = strcmp(s1.c_str() , s2.c_str()); return cmp == 0; } bool operator<(const string& s1, const string& s2) { int cmp = strcmp(s1.c_str(), s2.c_str()); return cmp < 0; } bool operator<=(const string& s1, const string& s2) { return s1 == s2 || s1 < s2; } 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); } //全局函数 void swap(string& s1, string& s2) { s1.swap(s2); } //流插入重载 ostream& operator<<(ostream& out, const string& str) { for (auto ch : str) { out << ch << " "; } cout << endl; return out; } //流提取重载 istream& operator>>(istream& in, string& str) { str.clear(); char ch; char buff[128]; ch = in.get(); size_t i = 0; while (ch != ' ' && ch != '\n') { buff[i++] = ch; if (i == 127) { str[127] = '\0'; str += buff; i = 0; } ch = in.get(); } if (i > 0) { str[i] = '\0'; str += buff; } return in; } istream& getline(istream& in, string& str) { str.clear(); char ch; ch = in.get(); while (ch != '\n') { str += ch; ch = in.get(); } return in; } //类内静态成员变量必须要指明类域 const int string::npos = -1; //string构造函数的编写 void test1() { string s1; string s2("123456"); s1.c_str(); s2.c_str(); cout << s1.c_str() << endl; cout << s2.c_str() << endl; } //遍历 void test2() { //重载[]遍历 //string s("1234564"); /* //可读 for (int i = 0; i < s.size(); i++) { cout << s[i] << " "; } cout << endl; //可写 for (int i = 0; i < s.size(); i++) { ++s[i]; cout << s[i] << " "; } cout << endl; const string s3("4399"); //仅可读 for (int i = 0; i < s3.size(); i++) { cout << s3[i] << " "; //s3[i]++;//不可写 } */ //string s3("hello world"); //for (int i = 0; i < s3.size(); i++) //{ // ++s3[i];//不可写 // cout << s3[i] << " "; //} //迭代器遍历 /*string::iterator it = s.begin(); while (it != s.end()) { cout << *it << " "; it++; } cout << endl;*/ //范围for遍历,范围for是一种替换机制,C++底层是把范围for替换为迭代器 /*for (auto ch : s) { cout << ch << " "; } cout << endl; const string s6("123456"); for (auto ch : s6) { cout << ++ch << " "; }*/ } void test3() { string s("hello world"); //1.push_back /*s.push_back('6'); s.push_back('6'); s.push_back('6'); s.append("zzg"); cout << s.c_str() << endl;*/ //2.+=重载 /*s += "you to be"; cout << s.c_str() << endl;*/ //3.insert s.insert(1, 'x'); s.insert(0, 'x'); cout << s.c_str() << endl; } //erase测试 void test4() { string s("hello the world"); s.erase(1,3); cout << s.c_str() << endl; } void test5() { /*string s("123456789"); s.resize(5); cout << s.c_str() << endl; s += "6789"; s.resize(12,'x'); cout << s.c_str() << endl; cout << s.size() << endl;*/ string s("hello world"); s.insert(6,"xxx"); cout << s.c_str() << endl; } void test6() { string s("123456"); string copys(s); cout << copys.c_str() << endl; } void test7() { string s("4399"); string s2("888"); s2 = s; cout << s.c_str() << endl; cout << s2.c_str() << endl; } void test8() { string s1("123456"); string s2("987654"); s1.swap(s2); cout << s1.c_str() << endl; cout << s2.c_str() << endl; swap(s1, s2); cout << s1.c_str() << endl; cout << s2.c_str() << endl; } void test9() { string s("21312313"); cout << s.substr(6).c_str() << endl; } void test10() { string s1("hello world"); string s2("hello world"); //但是这种实现方式有缺陷: cout << (s1 == s2) << endl; cout << (s1 == "hello world") << endl;//right,隐式类型转换 cout << ("hello world" == s2) << endl;// == error,because it is not string //"hello world" == s2 ,即是hello world.operator==(s2); //为了弥补这个缺陷,c++将其实现成了全局函数 //实现为全局函数主要是为了支持char*的隐式类型转换 const string d1("12344151"); const string d2("12344151"); cout << (d1 == d2) << endl; } void test11() { string s("hello world"); cout << s << endl; cin >> s; cout << s << endl; } void test12() { string s("123456"); string copy(s); } int main() { //test1();//string构造函数的编写 //test2();//遍历 //test3();//字符串的追加 //test4();//erase测试 //test5();//resize测试 //test6();//拷贝构造函数 //test7();//赋值运算符重载 //test8();//swap交换 //test9();//取子串 //test10();//==运算符重载 //test11();//流插入,流提取重载,getline实现 //test12();//现代写法拷贝构造函数 return 0; }
EOF