MyString:string类的模拟实现
前言:
为了区分标准库中的
string
,避免编译冲突,使用命名空间 MyString。
namespace MyString { class string { private: char* _str; size_t _size; size_t _capacity; const static size_t npos = -1;// C++标准库支持的特殊用法 };
以下都在 MyString
内实现!
一、构造函数,析构函数,拷贝构造
1.1 构造函数
标准库中,构造string类的常见写法:
string s1; // 1 string s2("hello world"); // 2
public: string() :_str(new char[1])// 给一个字节的空间作为标识 ,_size(0) ,_capacity(0) { _str[_size] = '\0'; } string(const char* str) { _size = strlen(str); _capacity = _size; _str = new char[_capacity + 1];// 多给一个空间,存'\0' strcpy(_str, str); }
实际上,对第二个构造函数的参数进行缺省,可以实现两种写法的完美统一。
string(const char* str = "") // 字符串末尾有隐藏的'\0',不需要我们在缺省值加上'\0' { _size = strlen(str); _capacity = _size; _str = new char[_capacity + 1]; strcpy(_str, str); }
1.2 析构函数
public: ~string() { delete[] _str; _str = nullptr; _size = _capacity = 0; }
1.3 拷贝构造(重点)
string类的拷贝构造需要实现深拷贝,否则会造成资源的二次释放。
public: string(const string& s) { _str = new char[s._capacity + 1]; strcpy(_str, s._str); _size = s._size; _capacity = s._capacity; }
二、迭代器
public: typedef char* iterator; typedf 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; }
范围for
本质是对迭代器的“傻瓜式”替换,一旦对 begin()
end()
的函数名做修改,则无法调用,如:begin() ——> Begin() 。
三、reserve() 与 尾插(重点)
3.1 reserve()
【1】 reserve() 是对 _capacity 进行操作 (不对 _str 操作),而 _capacity 只计算有效字符个数,不包括字符串末尾的 ‘\0’ 。
【2】 在设计 reserve() 时,要考虑多开一个空间,用于存 ‘\0’ ;要对 _capacity 校正。
【3】 在使用 reserve() 进行扩容时,只需要考虑 有效字符个数 即可。
public: void reserve(size_t n) { if (n > _capacity) { char* tmp = new char[n + 1];// strcpy(tmp, _str); delete[] _str; _str = tmp; _capacity = n; } }
- n > _capacity 时,才需要调整
char* tmp = new char[n + 1]
多开一个空间,用于存 ‘\0’ 。
3.2 尾插一个字符:push_back()
public: void push_back(const char ch) { if (_size == _capacity) { size_t newCapacity = _capacity == 0 ? 4 : 2 * _capacity; reserve(newCapacity); // _capacity = newCapacity; // reserve中 已经对 _capacity 做过调整了 } _str[_size] = ch; ++_size; _str[_size] = '\0'; }
- 插入字符后,应在字符串末尾加上 ‘\0’ ,否则通过 _str 访问字符串元素时会出现异常。
3.3 尾插字符串:append()
public: void append(const char* str) { int len = strlen(str); if (_size + len > _capacity) { reserve(_size + len); // reserve(_size + len + 1); // reserve中 已考虑在字符串末尾加上'\0' } strcpy(_str + _size, str);// str 末尾有隐藏的 '\0' _size += len; }
- str 末尾有隐藏的 ‘\0’
3.4 += 重载
- s1 += “x”;
public: string& operator+=(const char ch) { push_back(ch); return *this; }
- s1 += “xxxx”;
public: string& operator+=(const char* str) { append(str); return *this; }
四、 insert(), erase(), find(), substr()(重点)
4.1 insert()
- 在 pos 位置,插入字符
public: void insert(size_t pos, const char ch) { assert(pos <= _size); if (_size == _capacity) { size_t newCapacity = _capacity == 0 ? 4 : 2 * _capacity; reserve(newCapacity); } // version 1 int end = _size;// 从 '\0' 开始往后挪 while (end >= (int)pos) { _str[end + 1] = _str[end]; --end; } _str[pos] = ch; _size += 1; // version 2 size_t end = _size; while (end > pos) { _str[end] = _str[end - 1]; --end; } _str[pos] = ch; ++_size; _str[_size] = '\0'; }
- 在 pos 位置,插入字符串
public: void insert(size_t pos, const char* str) { assert(pos <= _size); size_t len = strlen(str); if (_size + len > _capacity) { reserve(_size + len); } int end = _size; while (end >= (int)pos) { _str[end + len] = _str[end]; --end; } strncpy(_str + pos, str, len); // strncpy(_str + pos, str); // error _size += len; }
4.2 erase()
public: void erase(size_t pos, size_t len = npos) { assert(pos <= _size); if (len == npos || pos + len >= _size) { _size = pos; _str[_size] = '\0'; } else { strcpy(_str + pos, _str + pos + len);// strcpy 会拷贝字符串末尾'\0' _size -= len; // _str[_size] = '\0'; } }
此接口实现的重点在于检查 _str + pos + len 范围,或者说,从 pos 位置删到尾的情形。
len == npos
与pos + len >= _size
4.3 find()
- find 一个字符
public: size_t find(const 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; }
- find 字符串
size_t find(const char* str, size_t pos = 0) { assert(pos <= _size); char* ptr = strstr(_str + pos, str); if (ptr == nullptr) { return npos; } return ptr - _str; }
4.4 substr()
public: string substr(size_t pos = 0, size_t len = npos) { assert(pos <= _size); string tmp; if (len == npos || pos + len >= _size) { len = _size - pos; tmp.reserve(len); } for (size_t i = 0; i < len; i++) { tmp += _str[pos + i]; } return tmp; }
此处检查操作的思想与 erase() 相同。
五、运算符重载 [], =, <<, >>(重点)
5.1 operator[]
public: char& operator[](size_t pos) { assert(pos <= _size); return _str[pos]; } char& operator[](size_t pos) const { assert(pos <= _size); return _str[pos]; }
- 返回值类型为
char&
。按照标准库中的重载,我们能够通过 [] 对元素进行修改;如果此处的返回值类型为 char ,则对返回值的修改并不影响 _str[pos] 。 - 需要重载一个 const 版本。避免出现如:
const string s1("hello world");
s1[pos];
出现权限放大的情况。(const ——> 非const)
5.2 operator=
public: string& operator=(const string& s) { if (this != &s) { char* tmp = new char[s._capacity + 1]; delete[] _str; _str = tmp; _size = s._size; _capacity = s._capacity; _str[_size] = '\0'; } return *this; }
- 深拷贝 ,避免资源二次释放(与拷贝构造相同)。
5.3 operator<<
public: ostream& operator<<(ostream& out, const string& s) { for (auto ch : s) { out << ch; } return out; }
由于 流插入<<重载 不涉及对私有成员的访问,因此不需要写成友元函数。
5.4 operator>>
// Version 1
public: istream& operator>>(istream& in, string& s) { char ch; cin >> ch; while (ch != ' ' && ch != '\n') { s += ch; cin >> ch; } return in; }
由于 cin
与 scanf
无法读入 ' '
与 '\n'
,在使用此版本 >> 时,会发现 “根本停不下来”!!!
// Version 2
istream& operator>>(istream& in, string& s) { char ch = in.get(); while (ch != ' ' && ch != '\n') { s += ch; ch = in.get(); } return in; }
in.get()
能很好地解决 Version 1 中的问题。但同样面临另一个问题,随着一个字符一个字符地插入,一次一次扩容,效率太低了。
// Version 3
istream& operator>>(istream& in, string& s) { char ch = in.get(); char buff[128] = { 0 }; int i = 0; while (ch != ' ' && ch != '\n') { buff[i++] = ch; if (i == 127) // i == 128 // error { s += buff; i = 0; } ch = in.get(); } if (i > 0) { buff[i] = '\0'; s += buff; } return in; }
- 使用 buff数组 存储 ch,满足一定条件再对 s 进行尾插,可以增大效率。
- 循环中,检查 i == 127 ,在 buff 末尾保留 ‘\0’ 避免越界插入。
- 循环结束 i > 0 ,buff[i] = '\0' ,避免把 i 之后元素位置中,**之前写入的元素再次尾插进 s **。