六、string类
7. string类的模拟实现
我们之前讲了实现 insert ，但是那个插入函数仅仅是在 pos 位置插入一个字符而且，我们并没有实现在 pos 位置插入一个字符串。所以我们现在将其补充上。
// 在 pos 位置插入一个字符串 void insert(size_t pos, const char* str) { assert(pos <= _size); size_t len = strlen(str); // 空间不够需要扩容 if (_size + len > _capacity) { reserve(_size + len); } size_t end = _size + len; while (end >= pos + len) { _str[end] = _str[end - len]; --end; } strncpy(_str + pos, str, len); }
当难以理解的时候，记得画图哦，我们来看看结果：
#include"string.h" using namespace my; int main() { string s("hello,world"); s.insert(4, "AAAAAAA"); std::cout << s.c_str() << std::endl; return 0; }
没问题。其实我们发现，有了 insert 之后，前面的 push_back() 和 append 好像可以复用这的代码，我们来调整一下。
void push_back(char ch) { //if (_size == _capacity) //{ // // 扩容2倍 // reserve(_capacity == 0 ? 4 : 2 * _capacity); //} //_str[_size] = ch; //++_size; //_str[_size] = '\0'; 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(_size, str); }
接下来我们再把 swap 给实现一下，有人会说哈，swap 在库里面就有，为啥还要我们手动实现呢？我给大家看看库里的 swap 是怎样的。
我们发现，库里的swap整整调用了3次拷贝和1次析构，虽然能用，但是它非常搓，所以我们要实现一个对我们来说更加好用的 swap 。
void swap(string& s) { // 调用库里的swap，直接交换成员即可，不需要创建一个新的对象 std::swap(_str, s._str); // 加上std:: 是让其直接去std域找，避免找到当前的成员函数swap std::swap(_size, s._size); std::swap(_capacity, s._capacity); }
#include"string.h" using namespace my; int main() { string s("hello,world"); string s1("1234567890"); s.swap(s1); std::cout << s.c_str() << std::endl << s1.c_str() << std::endl; return 0; }
既然库里的 swap 对我们来说很挫，但是我们应该怎样才能防止别人使用库里的函数呢？
库里面有个 swap ，成员函数有个 swap ，这里怎么还有一个非成员函数的 swap ？
这里的 swap 原来直接调用的是成员函数 swap ，那么非成员函数的 swap 是全局的，库里的 swap 是全局的，为啥没发生冲突？为啥就会先用非成员函数的 swap ？我在模板那篇提到过，因为 库里的 swap 是模板。当有现成的函数时，优先使用现成的。这下就完美解决了使用库里的swap了。
// string类外 void swap(string& x, string& y) { x.swap(y); }
接下来实现 find 函数。
// 查找一个字符 size_t find(char ch, size_t pos = 0) const { 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 { assert(pos < _size); const char* p = strstr(_str + pos, sub); // 找到了 if (p) { return p - _str; } // 没找到 return npos; }
接下来实现 substr 函数。
string substr(size_t pos = 0, size_t len = npos) { string sub; if (len >= _size - pos) { for (size_t i = pos; i < _size; ++i) { sub += _str[i]; } } else { for (size_t i = pos; i < pos + len; ++i) { sub += _str[i]; } } return sub; }
验证验证：
#include"string.h" using namespace my; int main() { string s("hello,world"); size_t pos = s.find(','); std::cout << s.substr(pos, 3).c_str() << std::endl; return 0; }
再就是重载比较。
// 重载成全局函数 bool operator==(const string& s1, const string& s2) { // strcmp 若是相等则返回0 int ret = strcmp(s1.c_str(), s2.c_str()); return ret == 0; } bool operator<(const string& s1, const string& s2) { int ret = strcmp(s1.c_str(), s2.c_str()); return ret < 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); }
实现流插入和流提取：
using namespace std; ostream& operator<<(ostream& out, const string& s) { // 没有访问私有成员，不需要友元 for (auto ch : s) { out << ch; } return out; } istream& operator>>(istream& in, string& s) { // 需要将其内容清空 s.clear(); char ch; // cin 读取不到 ' ' 和 '\n' ch = in.get(); // 减少扩容 char buff[128]; size_t i = 0; while (ch != ' ' && ch != '\n') { buff[i++] = ch; if (i == 127) { buff[127] = '\0'; s += buff; i = 0; } ch = in.get(); } if (i > 0) { buff[i] = '\0'; s += buff; } return in; }
顺便实现 clear 。
// 成员函数 void clear() { _size = 0; _str[_size] = '\0'; }
检验检验：
#include"string.h" using namespace my; int main() { // 刚刚展开了std，这里避免冲突 my::string s; cin >> s; cout << s; return 0; }
很好，空格前的都被读取到了。
再来实现 getline 。getline就是读取一行嘛，相信实现了流提取运算符，实现一个 getline 肯定非常轻松。
istream& getline(istream& in, string& s) { // 需要将其内容清空 s.clear(); char ch; // cin 读取不到 ' ' 和 '\n' ch = in.get(); // 减少扩容 char buff[128]; size_t i = 0; while (ch != '\n') { buff[i++] = ch; if (i == 127) { buff[127] = '\0'; s += buff; i = 0; } ch = in.get(); } if (i > 0) { buff[i] = '\0'; s += buff; } return in; }
再来检验：
#include"string.h" using namespace my; int main() { my::string s; getline(cin, s); cout << s; return 0; }
在实现拷贝构造函数时，我们写了一个非常传统的写法，这里再给大家实现一种新式写法：
// 传统写法 string(const string& s) { _str = new char[s._capacity + 1]; strcpy(_str, s._str); _size = s._size; _capacity = s._capacity; } // 新式写法 string(const string& s) { string tmp(s._str); swap(tmp); }
这里新式写法本质上就是调用构造函数，然后让 this指针 指向新的构造的 sring 类 。同样，赋值重载也能使用新式写法。
// 传统写法 string& operator=(const string& s) { char* tmp = new char[s._capacity + 1]; strcpy(tmp, s._str); delete[] _str; _str = tmp; _size = s._size; _capacity = s._capacity; return *this; } // 新式写法 string& operator=(const string& s) { string tmp(s); swap(tmp); return *this; }
这里赋值重载的新式写法还能优化（行数），既然在函数内部要调用拷贝构造，为什么不在传参的时候直接调用拷贝构造呢？
string& operator=(string s) { swap(s); return *this; }
8. string类的模拟实现的完整代码
string.h头文件
#pragma once #include<iostream> #include<assert.h> using namespace std; namespace my { class string { 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(const char* str = "") :_size(strlen(str)) { _capacity = _size; _str = new char[_capacity + 1]; strcpy(_str, str); } //string(const string& s) //{ // _str = new char[s._capacity + 1]; // strcpy(_str, s._str); // _size = s._size; // _capacity = s._capacity; //} string(const string& s) { string tmp(s._str); swap(tmp); } //string& operator=(const string& s) //{ // char* tmp = new char[s._capacity + 1]; // strcpy(tmp, s._str); // // delete[] _str; // _str = tmp; // _size = s._size; // _capacity = s._capacity; // return *this; //} string& operator=(string s) { swap(s); return *this; } ~string() { delete[] _str; _str = nullptr; _size = _capacity = 0; } // 加 const 使其成为 const 成员函数，使 const 对象也能调用这个函数 size_t size() const { return _size; } // 引用返回，可读可写 inline char& operator[](size_t pos) { assert(pos < _size); return _str[pos]; } // 针对 const对象 的可读不可写，加 & 是为了减少拷贝 inline const char& operator[](size_t pos) const { assert(pos < _size); return _str[pos]; } size_t capacity() const { return _capacity; } void reserve(size_t n) { // 只有要扩容的大小比当前容量大才能扩容 if (n > _capacity) { char* tmp = new char[n + 1]; strcpy(tmp, _str); delete[] _str; _str = tmp; _capacity = n; } } void push_back(char ch) { //if (_size == _capacity) //{ // // 扩容2倍 // reserve(_capacity == 0 ? 4 : 2 * _capacity); //} //_str[_size] = ch; //++_size; //_str[_size] = '\0'; 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(_size, str); } string& operator+=(char ch) { push_back(ch); return *this; } string& operator+=(const char* str) { append(str); return *this; } char* c_str() const { return _str; } // 在 pos 位置插入一个字符 void insert(size_t pos, char ch) { assert(pos <= _size); if (_size == _capacity) { // 扩容2倍 reserve(_capacity == 0 ? 4 : 2 * _capacity); } size_t end = _size + 1; while (end > pos) { _str[end] = _str[end - 1]; --end; } _str[pos] = ch; ++_size; } // 在 pos 位置插入一个字符串 void insert(size_t pos, const char* str) { assert(pos <= _size); size_t len = strlen(str); // 空间不够需要扩容 if (_size + len > _capacity) { reserve(_size + len); } size_t end = _size + len; while (end >= pos + len) { _str[end] = _str[end - len]; --end; } strncpy(_str + pos, str, len); } // 从 pos 开始，删除 len 个字符，如果 len 是 npos ，则全删 void erase(size_t pos, size_t len = npos) { assert(pos < _size); // pos + len >= _size 可能会溢出 if (len == npos || len >= _size - pos) { _str[pos] = '\0'; _size = pos; } strcpy(_str + pos + len, _str + pos); _size -= len; } void resize(size_t n, char ch = '\0') { if (n <= _size) { _str[n] = '\0'; _size = n; } else { reserve(n); for (size_t i = _size; i < n; ++i) { _str[i] = ch; } _str[n] = '\0'; _size = n; } } void swap(string& s) { // 直接交换成员即可 std::swap(_str, s._str); std::swap(_size, s._size); std::swap(_capacity, s._capacity); } size_t find(char ch, size_t pos = 0) const { 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 { assert(pos < _size); const char* p = strstr(_str + pos, sub); // 找到了 if (p) { return p - _str; } // 没找到 return npos; } string substr(size_t pos = 0, size_t len = npos) { string sub; if (len >= _size - pos) { for (size_t i = pos; i < _size; ++i) { sub += _str[i]; } } else { for (size_t i = pos; i < pos + len; ++i) { sub += _str[i]; } } return sub; } void clear() { _size = 0; _str[_size] = '\0'; } private: char* _str; size_t _size; size_t _capacity; public: static const int npos; }; // 静态成员变量在类外部定义 const int string::npos = -1; // string类外 void swap(string& x, string& y) { x.swap(y); } bool operator==(const string& s1, const string& s2) { // strcmp 若是相等则返回0 int ret = strcmp(s1.c_str(), s2.c_str()); return ret == 0; } bool operator<(const string& s1, const string& s2) { int ret = strcmp(s1.c_str(), s2.c_str()); return ret < 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); } ostream& operator<<(ostream& out, const string& s) { // 没有访问私有成员，不需要友元 for (auto ch : s) { out << ch; } return out; } istream& operator>>(istream& in, string& s) { // 需要将其内容清空 s.clear(); char ch; // cin 读取不到 ' ' 和 '\n' ch = in.get(); // 减少扩容 char buff[128]; size_t i = 0; while (ch != ' ' && ch != '\n') { buff[i++] = ch; if (i == 127) { buff[127] = '\0'; s += buff; i = 0; } ch = in.get(); } if (i > 0) { buff[i] = '\0'; s += buff; } return in; } istream& getline(istream& in, string& s) { // 需要将其内容清空 s.clear(); char ch; // cin 读取不到 ' ' 和 '\n' ch = in.get(); // 减少扩容 char buff[128]; size_t i = 0; while (ch != '\n') { buff[i++] = ch; if (i == 127) { buff[127] = '\0'; s += buff; i = 0; } ch = in.get(); } if (i > 0) { buff[i] = '\0'; s += buff; } return in; } }
test.c源文件
#include"string.h" using namespace my; int main() { // return 0; }
9. string收尾
我们来看看下面一段程序：
#include"string.h" using namespace my; int main() { std::string s("11111"); cout << sizeof(s) << endl; return 0; }
库里的 string 是多少空间呢？
嗯？如果是我们写的 string ，那么应该是 12 啊（32位下，64位是 24），为什么库里的 string 是 28呢？其实是因为编译器做了相关的优化，它在原有的基础上还新增了一个 buff[16] 数组，当数据较小的时候会存到 buff 里，比较大才会存到 _str 在堆上开辟的空间里。因为栈上开辟空间比在堆上开辟空间快。这仅仅是在 vs 编译器下是这样的，其他编译器不一定是这样。
写时拷贝
我们知道，拷贝构造不能是浅拷贝，假如是浅拷贝，那么会导致两个指针指向同一块空间，一个修改另一个也会发生变化，多次析构的问题。所以只能是深拷贝。但是库里的 string 类真的是这样的吗？库里的 string 类的构造函数其实是浅拷贝，但是它有个引用计数，代表有几个对象指向这块空间，如果有对象要修改（写），则重新深拷贝一个空间给其使用，析构的时候则判断引用计数是否为1，不为1则不析构。这样做其实就是赌有的对象不去修改内容，只要有这样的对象，那么就算是一种优化。
