三、string类的模拟实现
💦 经典的string类问题
💨 string.h
#pragma once namespace bit { class string { public: string(char* str) //:_str(str) :_str(new char[strlen(str) + 1] { strcpy(_str, str); } ~string()//当生命周期结束，程序会自动调用析构函数释放资源。 { delete[] _str; _str = nullptr; } char& operator[](size_t pos) { return _str[pos];//_str[pos]同*(_str + pos) } private: char* _str; }; void test_string1() { string s1("hello"); s1[0] = 'x'; string s2(s1); s2[0] = 'y'; } }
💨 string.cpp
#include"string.h" int main() { bit::test_string1(); return 0; }
📝说明
注意这里对于新一点的编译器会报错(这里是 VS2017)，需要使用 const 来修饰 _str。这里因为要演示，所以就不使用了。
这里 hello 是常量字符串，存储在常量区，然后调了构造函数初始化 _str，然后 s1 [0] = ‘x’ 就会报错(运行时错误)。
所以这里我们要改就要把常量字符串拷贝到 new 的一块空间，s1[0] = ‘x’ 才对。
这里没有写拷贝构造函数，编译器会默认生成，对于内置类型，字节序的浅拷贝；自定义类型，会去调用它的拷贝构造完成拷贝，程序结束，调用析构函数，对同一块空间释放两次，程序崩溃，这就是浅拷贝所带来的问题。其中析构两次空间只是其中一个问题，拷贝构造 s2 后，再去 s2[0] = ‘y’; ，s1 也会跟着修改。
解决方法就是 s2 必需是一块独立的空间，也就是深拷贝。
💦 浅拷贝
由如上代码我们了解了浅拷贝会带来两个问题：
- 析构两次空间
- 其中一个去修改，会影响另一个
浅拷贝也称为位拷贝，编译器只是将对象中的值拷贝过来，如果对象中管理资源，最后就会导致多个对象共享同一份资源，当一个对象销毁时就会将该资源释放掉，而此时另一个对象不知道该资源已经释放，以为该空间还有效，所以继续对资源进行操作时，就会发生访问违规。所以要解决浅拷贝问题，C++ 引入了深拷贝。同时要明白一个问题，string 做拷贝时，其实是深拷贝，也就意味着要尽量减少它的拷贝构造，因为它除了拷贝值过来，还需要开空间，代价较大，只有迫不得已的时候才用。
浅拷贝只关注美人鱼的上半身，而深拷贝探索到了美人鱼不为人知的下半身：
💦 深拷贝
深拷贝会新开辟一块与原对象一样大的空间，再把原对象空间上的值拷贝过来。
1、深拷贝的传统版写法的string类
💨 string.h
#pragma once namespace bit { class string { public: string(char* str) :_str(new char[strlen(str) + 1] { strcpy(_str, str); } //s2(s1) string(const string& s) :_str(new char[strlen(s.str) + 1]) { strcpy(_str, s._str); } //s1 = s3 string operator=(const string& s) { if(this != &s)//防止自己赋值 { /*delete[] _str;//this->_str _str = new char[strlen(s._str) + 1];*/ char* tmp = new char[strlen(s._str) + 1]; delete[] _str; _str = tmp; strcpy(_str, s._str); } return *this; } ~string() { delete[] _str; _str = nullptr; } char& operator[](size_t pos) { return _str[pos]; } private: char* _str; }; void f1(string s) {} void f2(const string& s) {} template<class T> void f3(T x) {} void f3(const T& x) {} void test_string1() { string s1("hello"); s1[0] = 'x'; string s2(s1); s2[0] = 'y'; string s3("hello bit"); s1 = s3; f1(s1); f2(s2); } }
💨 string.cpp
#include"string.h" int main() { try { bit::test_string1(); } catch(exception& e) { cout << e.what() << endl; } return 0; }
📝说明
引用的价值更进一步得以体现：f1 是传值传参，这里使用 s1 构造 s，是一个拷贝构造，并且这个拷贝构造是深拷贝；f2 是引用传参，s 是 s2 的别名，不需要拷贝构造。
对于模板也是一样：f3 里 T 是 int、double 都无所谓，但如果它是一个 string、vector、map 呢，那这要走深拷贝，代价是极大的。所以对于 f3 这种写法是极其不推荐的。
注意 s1 和 s2 所指向的空间大小不一定相同。实现：直接拷贝不一定对，因为它们各自所指向的空间大小不一定相同，比如 s1 是 6 个有效字符的空间，s2 是 10 个有效字符的空间，直接拷贝就会导致越界。比如 s1 是 100 个有字符的空间，s2 是 5 个有效字符的空间，可以直接拷贝，但是浪费空间。最好的方法就是把 s1 指向的空间释放掉，重新开辟一块与 s2 所指向的空间一样大的空间，再把 s2 所指向的数据拷贝至新空间，最后让 s1 指向新空间
目前我们写的赋值重载仍有问题：对于如上代码中所有的 new，当 new 失败时，我们没有去捕获异常，对于赋值重载中的 new，如果失败了，还把 s1 给破坏了，赔了夫人又折兵，所以这里可以先 new 空间，再 delete。虽然异常我们还没涉及，但是这里先完善下，不然显然咱不专业。
2、深拷贝的现代版写法的string类
//s2(s1) string(const string& s) :_str(nullptr); { string tmp(s._str); swap(_str, tmp._str); } //s1 = s3//版本一 string& operator=(const string& s) { if(this != &s) { string tmp(s._str); swap(_str, tmp._str); } return *this; } //s1=s3//版本二 string& operator=(string s) { swap(_str, s._str); return *this; }
📝说明
至此如上代码还有一点问题：虽然已经达到深拷贝的效果，但是这里的 tmp 是一个局部对象，出了作用域，生命周期结束，它会调用析构函数，而此时 tmp 是一个随机值，这里再释放就会报错，所以说我们在一开始得把它指向空(free 和 delete 释放空都不会有问题)。
现代写法的精髓就是让别人替自己干活，有什么特别的价值呢 ❓
实际上在以后我们写深拷贝时，大部分用的都是现代写法 —— 这里拷贝的是一个数组，如果拷贝的是更复杂的东西时，自己去开空间、拷贝，代价就很大。
相比版本一这是更正宗的现代写法，版本一已经说过了，就不理解了。版本二是使用传值传参，s3 传给 s，s 就充当了 tmp 的作用 —— string s(s3) 拷贝构造。为什么这里不判断自己赋值给自己呢 ？？？因为已经深拷贝出来了，判断也已经没有意义了。注意这里并没有改变 s3，因为这里是传值。也就是说，后面在写赋值时，所有的深拷贝都可以用这样的一段代码解决。
传统写法 | 现代写法 ❓
它们俩的效率是一样的。但是：
- 传统写法，可读性高，便于理解，但操作性较低
- 现代写法，代码更加简洁高效，但是逻辑更加复杂
在以后我们都更倾向于现代写法。
💦 写时拷贝(了解)
写时拷贝就是一种拖延症，是在浅拷贝的基础之上增加了引用计数的方式来实现的。
引用计数：用来记录资源使用者的个数。在构造时，将资源的计数给成1，每增加一个对象使用该资源，就给计数增加 1，当某个对象被销毁时，先给该计数减 1，然后再检查是否需要释放资源，如果计数为 1，说明该对象时资源的最后一个使用者，将该资源释放；否则就不能释放，因为还有其他对象在使用该资源。
当然这种方案也有不好的地方，具体可以参考如下的文章，所以说可以认为这种技术已经脱轨了。
证明标准库里没有使用这种技术 ❓
这里有个函数 c_str，它返回指向字符串的指针，如果 _str 不一样的就是深拷贝，一样就是写时拷贝(除非去修改它，触发深拷贝)。注意这里输出地址时不能用 cout，要用 printf，因为 c_str 返回的是 char*。
Visual Studio 2017：
Linux g++：
写时拷贝是在需要修改时在去深拷贝 ❗
Visual Studio 2017：
Linux g++：
📝小结
早期 Linux 选择了写时拷贝的技术，而 VS 下选择了直接深拷贝的技术。它们本质都是深拷贝，只是说 Linux 下先做浅拷贝，如果不写就不做深拷贝，写了再去做深拷贝，并且是谁写谁做。我这里 g++ 的版本是 gcc version 4.8.5 20150623，之前好像听说最新的版本已经放弃写时拷贝了，有兴趣的可以去验证下。
💦 string类的模拟实现
💨 string.h
#pragma once namespace bit { public: typedef char* iterator; typedef const char* const_iterator; iterator begin() { return _str; } iterator end() { return _str + _size; } const_iterator begin() const { return _str; } const_iterator end() const { return _str + _size; } /*string() :_str(new char[1]) ,_size(0) ,_capacity(0) { *_str = '\0'; }*/ //string(char* str = "\0") string(char* str = "") :_size(strlen(str)) ,capacity(_size); { _str(new char[_capacity + 1]);//预留\0 strcpy(_str, str); } //s1.swap(s2) void swap(string& s) { //注意这里的swap不算重载，重载要求的是在同一作用域，就像string和vector里都有push_back，它们函数名、返回值、参数可能都是相同的，那它们俩能同时存在的原因就是它俩在不同的作用域 ::swap(_str, s._str); ::swap(_size, s._size); ::swap(_capacity, s._capacity); } //s2(s1) string(const string& s) :_str(nullptr); { string tmp(s._str); swap(tmp)//this->swap(tmp); } //s1=s3 string& operator=(string s) { swap(s);//this->swap(s); return *this; } ~string() { delete[] _str; _str = nullptr; } //读写 char& operator[](size_t pos) { assert(pos < _size); return _str[pos]; } //读 const char& operator[](size_t pos) const { assert(pos < _size); return _str[pos]; } //增容 void reserve(size_t n) { if(n > _capacity) { char* tmp = new char[n + 1]; strcpy(tmp, _str); delete[] _str; _str = tmp; _capacity = n; } } void resize(size_t n, char ch = '\0') { if(n <= _size) { _size = n; _str[_size] = '\0'; } else { if(n > _capacity)//一次性增容，避免频繁增容所带来的消耗 { reserve(n); } for(size_t i = _size; i < n; i++) { _str[i] = ch; } _size = n; _str[_size] = '\0'; } } void push_back(char ch) { /*if(_size >= _capacity)//扩容 { size_t newcapacity = _capacity == 0 ? 4 : _capacity * 2; reserve(newcapacity); } _str[_size] = ch; ++_size; _str[_size] = '\0';*/ //实现insert后直接复用 insert(_size, ch); } void append(const char* str) { /*size_t len = strlen(str); if(_size + len > _capacity)//扩容 { reserve(_size + len); } strcpy(_str + _size, str); _size += len;*/ //复用insert insert(_size, str); } string& operator+=(char ch) { push_back(ch);//this->push_back(ch); return *this; } string& operator+=(const char* str) { append(str); return *this; } string& operator+=(const string& s) { *this += s._str; return *this; } size_t size() const { return _size; } size_t capacity() const { return _capacity; } size_t find(char ch, size_t pos = 0) { for(size_t i = pos; i < _size; ++i) { if(_str[i] == ch) { return i; } } return npos; } size_t find(const char* sub, size_t pos = 0) { const char* p = strstr(_str + pos, sub); if(p == nullptr) { return npos; } else { return p - _str; } return npos; } string& insert(size_t pos, char ch) { assert(pos <= _size); if(_size == _capacity) { size_t newcapacity = _capacity == 0 ? 4 : _capacity * 2; reserve(newcapacity); } /*int end = _size; while(end >= (int)pos) { _str[end + 1] = _str[end]; --end; }*/ size_t 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 == 0)//空串直接返回 { return *this; } if(len + _size > _capacity) { reserve(len + _size); } size_t end = _size + len; while(end >= pos + len) { _str[end] = str[end - len]; --end; } for(size_t i = 0; i < len; ++i) { _str[pos + i] = str[i]; } _size += len; return *this; } const char* c_str() { return _str; } string& erase(size_t pos, size_t len = npos) { assert(pos < _size); //1、pos后删完 //2、pos后删一部分 if(len == npos || pos + len >= _size) { _str[pos] = '\0'; _size = pos; } else { strcpy(_str + pos, _str + pos + len);//这里直接调用strcpy即可 _size -= len; } return *this; } void print(const string& s) { for(size_t i = 0; i < s.size(); ++i) { //s[i] = 'x'//err cout << s[i] << " "; } cout << endl; string::const_iterator it = s.begin(); while(it != s.end()) { cout << *it << " "; } cout << endl; } void clear() { _str[0] = '\0'; _size = 0; } private: char* _str; size_t _size; size_t _capacity;//不包含最后做标识的\0 static const size_t npos; }; static size_t string::npos = -1; string operator+(const string& s1, char ch) { string ret = s1; ret += ch; return ret; } string operator+(const string& s1, const char* str) { string ret = s1; ret += str; return ret; } ostream& operator<<(ostream& out, const string& s) { for(size_t i = 0; i < s.size(); ++i) { out << s[i]; } return out; } istream& operator>>(istream& in, string& s) { s.clear(); char ch; //in >> ch; ch = in.get(); while(ch != ' ' || ch != '\n') { s += ch; //in >> ch; ch = in.get(); } return in; } istream& getline>>(string& s) { s.clear(); char ch; ch = in.get(); while(ch != '\n') { s += ch; ch = in.get(); } return in; } bool operator>(const string& s1, const string& s2) { size_t i1 = 0, i2 = 0; //“abc" "aa" //"aa" "abc" while(i1 < s1.size() && i2 < s2.size()) { if(s1[i1] > s2[i2]) { return true; } else if(s1[i1] < s2[i2]) { return false; } else { ++i1; ++i2; } } //"abc" "abc" -> false //"abcd" "abc" -> true //"abc" "abcd" -> false if(i1 == s1.size()) { return false; } else { return true; } } bool operator==(const string& s1, const strint& s2) { size_t i1 = 0, i2 = 0; while(i1 < s1.size() && i2 < s2.size()) { if(s1[i1] != s2[i2]) { return false; } else { ++i1; ++i2; } } if(i1 == s1.size() && i2 == s2.size()) { return true; } else { return false; } } inline bool operator!=(const string& s1, const string& s2) { return !(s1 == s2); } inline bool operator>=(const string& s1, const string& s2) { return s1 > s2 || s1 == s2; } inline bool operator<(const string& s1, const string& s2) { return !(s1 >= s2) } inline bool operator<=(const string& s1, const string& s2) { return !(s1 > s2) } void test_string1() { string s1("hello"); s1.push_back(' '); s1.append("world"); s1 += ' '; s1 += "world"; string s2(s1); s2.resize(3); s2.resize(8, 'x'); s2.resize(20, 'x'); } void test_string2() { //遍历打印 //1、 string s1("hello world"); for(size_t i = 0; i < s1.size(); ++i) { s1[i] += 1;//普通迭代器可读写 cout << s1[i] << " "; } cout << endl; //2、 string::iterator it = s.begin(); while(if != s1.end()) { *it -= 1; cout << *it << endl; ++it; } cout << endl; //3、 for(auto e : s1) { cout << e << " "; } cout << endl; print(s1); } void test_string3() { string s1("hello world"): s1.insert(5, 'x'); cout << s1.c_str() << endl; string s2("helloworld"); s2.insert(5, "bit"); cout << s2.c_str() << endl; s2.insert(0, "hello"); cout << s2.c_str() << endl; string s3("helloworld"); s3.erase(5, 3); cout << s3.c_str() << endl; s3.erase(5); cout << s3.c_str() << endl; } void test_string4() { string s1("hello"); cin >> s1; cout << s1 << endl; cout << s1.c_str() << endl; //以上两种cout的差别点 string s2("hello"); s2.resize(20); s2[19] = 'x'; cout << s1 << endl; cout << s1.c_str() << endl; string s3; cin >> s3; cout << s3 << endl; } void test_string5() { //string s1; //cin >> s1; //cout << s1 << endl; getline(cin, s1); cout << s1 << endl; } }
💨 string.cpp
#include"string.h" int main() { try { bit::test_string1(); bit::test_string2(); bit::test_string3(); bit::test_string4(); bit::test_string5(); } catch(exception& e) { cout << e.what() << endl; } return 0; }
📝说明
对于默认构造函数，我们之前说过写无参的不如写全缺省的，这里的缺省值可以给 “” 或 “\0”。_str 需要支持增删查改，所以得把原来的空间拷贝到新开的一块空间上进行操作，需要注意的是 _capacity 不包含 \0，也就是说 10 个字符需要有 11 个空间。
对于普通数组而言，越界读一般是检查不出来的，越界写是抽查，可能会检查出来，可能的意思是数组后面有一个标志位，如果修改了它就会报错，但不可能数组之后都是标志位，所以就可能就会出现往后越界一个位置会报错，往后越界二个位置不会报错的情况。这个在之前有说过，感兴趣的可以去测试下。 但是在 string 里无论是越界读还是越界写都会报错。
为什么到了 string，[ ] 就查的这么严 ？？？因为 [ ] 是一个函数调用，它对这里的参数进行了严格的检查。
当 _capacity 满了，push_back 直接扩二倍是可以的，但是 append 扩二倍不一定能满足，因为 append 尾插的是一个字符串。
对于 resize，string 里有两个版本，第一个版本如果没给值，它默认是用 \0 初始化，第二个版本是用指定字符初始化。其实第一个版本有点累赘了，这里我们直接把第二个版本的第二个参数设为缺省值为 \0 即可，其中我们在实现 resize 时又分为几种情况：
💨 hello\0：_size = 5
- n <= _size：_size = 3
- n > _size && n < _capacity：_size = 8
- n > _capacity：_size = 15
对于第 3 种，我们也有很多种方法实现，比如去循环复用 +=，当 n 远大于当前空间时效率就很低，可能只需要一步到位的代码，却需要频繁增容，如果你不知道 string 的底层你根本不知道要这样写。这也就是我们为什么要去模拟实现 string 的原因。
对于第 2、3 种，我们的循环里的结束条件不能为 i <= n，因为这里要分情况，如果没传 ch，这里写 i <= n 是没问题的，但是如果传的是 x，就不行了，需要在循环后面补 \0，所以干脆 i < n，再在循环后被 \0。
可以看到迭代器的实现并不难，其实相比 string 和 vector 的迭代器，list 的迭代器就要复杂许多了。string::iterator 就是告诉编译器 iterator 去全局去找是找不到的，要到 string 这个域里去找，迭代器它是一个内嵌类型，所以说它要指定类域。注意这里是一个左闭右开的区间，它是一个普通迭代器，支持读写。
可以看到我们也没实现范围 for，为什么它依然可以完成呢，其实范围 for 的原理就是被替换成迭代器，范围 for 的语法是说取 s1 里的每个数据，赋值给 e，然后它会自动走，自动判断结束。所谓的这些自动其实没这么神奇，就像模板好像很牛逼，写一个 swap，其它地方都可以用，其实是把一些工作交给编译器去做了。这里也是一样，你可以认为这里的 e 是定义的一个变量，然后把 *it 赋值给 e，所以对 e 的改变不会影响 s1，需要加上引用才行。所以范围 for 的原理就是被替换成迭代器。
当然空口无凭，这里我们把 begin 改成了 Begin，报错了，以上就能说明范围 for 会被原模原样的替换成迭代器，但是迭代器得跟着规范去走，得用 begin。
print 就会用到 const 迭代器，对于 const 对象还要去实现一个 const 版本的 operator[]，迭代器也要去实现 const 迭代器。注意对于普通对象和 const 对象，operator[] 和迭代器就必须实现两份，而像 size() 实现一份 const 版本就可以满足了。
注意这里实现的 insert 有问题，当 s1.insert(0, ‘x’) 时，当 end 减到 -1 时，本来应该结束了，但是它还会走，因为这里当无符号和有符号比较时，进行整型提升了，这里的 -1 会被提升为一个很大的正数。解决方法：
- 将参数的 size_t pos 改成 int pos，但不符合设计的意义
- 在 while 循环里比较时，将 pos 强转为 int
- 将 end 的值改成 _size + 1，具体见详细代码
这里就非常考验 C语言的基本功了，如果你不知道这个提升机制，甚至你在调试的时候都会怀疑是编译器的 bug。
对于erase 的实现，它的第二个参数我们给的是一个缺省值 npos，它是无符号的 -1。
一般我们重载流提取、流插入都是全局的。在实现日期类时，我们也写过，那里需要使用到友元，但是流提取和流插入必须是友元这句话是不对的，日期类里的友元，是要突破封装访问日期类的年月日，这里不一定要去访问。比如流插入的 operator[] 是公有的，流提取提供的 += 是公有的。
对于上面的 operator<<，我们发现它并不能提取我们输入的字符。其实这里的 in 是拿不到换行符或空格的，C语言中的 scanf 也是这样的，对于 C语言它可以使用 getchar 来解决，这里我们可以看到 C++ 中 cin 对象里也有类似的接口 get。
其次 operator>> 里还有个问题，当对 s1 字符串继续 cin >> s1 时，新输入的字符串会补在原字符串的后面，所以这里我们还要提供一个 clear 接口，在 operator>> 的第一行 clear。
以上两种 cout 有无区别 ？？？
一般情况下没有啥区别，但在某种场景下有区别，这种场景很不容易被发现。这里对 s2 resize 后，它会变成 hello\0\0\0\0…x，此时第一个 cout 会全部输出，因为它是按 _size 走的；第二个 cout 不会输出，因为它遇到 \0 就终止。所以大部分情况我们都用第一种 cout，因为它有保障。
这里我们输入 hello world，但只获取到了 hello，这个原因是 cin 是以空格或换行结束的，它认为 hello 和 world 是给两个对象的，所以这里就实现了 getline>>。注意这里的实现和 operator>> 是一样的，不同的地方是 getline 遇到换行才结束。
对于 operator> 写成成员或全局都可以，我们这里根据库里来实现写成全局。注意这里比较的是 ASCII 码。这里比较有如下情况：
- “abc” “aa”
- “aa” “abc”
- “abc” “abc”
- “abcd” “abc”
- “abc” “abcd"
当我们实现了 operator>、operator==，那么其它的就可以直接复用了，且实现为 inline，避免建立函数栈帧所带来的开销。
注意 operator+ 尽量少用，因为它内部需要两次深拷贝。
对于 find 我们这里只实现查找字符和查找字符串
💦 补充
如下 s1 和 s2 对象的大小为什么是 28 字节 ❓
根据我们实现的 string 类，应该只有 12 字节，凭空多出的 16 字节是怎么来的 ？
这其实是 VS 下面的一个技术优化(也可以说是 PJ 版本自己考虑的)，调试发现除了 size、capacity、指针，还多了很多东西。
也就是说你的字符个数小于 16，它不会去堆上开空间，而是存储在 _Buf 数组里；如果字符个数大于等于 16，它就会存储在 _str 指向的堆上。这种方式的好处就是对于小空间不用去系统去申请了，减少内存碎片。
Linux 下 s1 和 s2 的大小 ❗
