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 1int end = _size;// 从 '\0' 开始往后挪while (end >= (int)pos){_str[end + 1] = _str[end];--end;}_str[pos] = ch;_size +=  1;// version 2size_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 **。