如何详细解析String类及其模拟实现过程？

本文共计2857个文字，预计阅读时间需要12分钟。

定义和结构 + 字符串的使用和操作频繁，在C++中，为了便于对字符串进行管理，引入了string类。string类是basic_string模板的一个实例：有typedef basic_string。

定义和结构

对字符串的使用和操作往往非常频繁，在C++中，为了便于对字符串进行管理，引入了string类。string类是basic_string类模板的一个实例：有typedef basic_string<char, char_traits, allocator> string。string类的存储结构其实是一个顺序表，与C语言传统字符串的使用相比，用string类对字符串进行管理，往往更加简单、方便、快捷和安全。因为字符串使用频繁，string的出现比STL更早，并在后续发展中对其进行了重写，本文通过模拟实现string类及其部分常用的接口以深入体会和理解string类的使用。

class string { private: size_t _size; size_t _capacity; char* _str; /*…………*/

同时要在类域中声明一个静态成员变量npos作为某些操作的操作范围标识：

static const size_t npos; /*…………*/ const size_t string::npos = -1;

迭代器

在STL中，容器和算法是分别设计的，而迭代器是二者之间的胶合剂，便于两者之间更好地配合。迭代器提供了一种统一的方式拿到容器的数据，而无需暴露容器的底层实现。从使用上看，任何容器都支持迭代器，并且用法相似。

string维护的是一个连续线性空间，普通指针可以作为string的迭代器而满足所有的必要条件，例如对迭代器的加减操作(operator++，operator--)和解引用操作(operator*)等，这些操作普通指针可以天然满足，string支持随机存取，普通指针同样可以做到。

public: typedef char* iterator; typedef const char* const_iterator; ////迭代器 iterator begin() { return _str; } iterator end() { return _str + _size; } const_iterator cbegin() const { return _str; } const_iterator cend() const { return _str + _size; }

构造&析构和内存管理

C++标准库中提供了多种string的构造方式，本文实现以字符串构造的方式和拷贝构造。

需要注意的是，string中成员变量_capacity和_size只将有效字符考虑在内，而不包括'\0'，但是为了兼容C语言，依然要为 '\0' 分配空间。

////构造&析构 //注意初始化列表的成员变量初始化顺序要与定义顺序一致 string(const char* str = "") :_size(strlen(str)), _capacity(_size), _str(new char[_size + 1]) //+ 1是为了给'\0'预留空间 { //因为str一定是一个以'\0'结尾的字符串，所以使用strcpy即可 strcpy(_str, str); } //深拷贝 string(const string& s) { _str = new char[s._capacity + 1]; //使用memcpy,将'\0'考虑在内 memcpy(_str, s._str, s._size + 1); //_size + 1，为'\0'预留空间 _size = s._size; _capacity = s._capacity; } ~string() { delete[] _str; _str = nullptr; _size = _capacity = 0; }

在C语言中，'\0'是字符串结束的标志，C语言库中对字符串的各种操作函数，例如strlen、strcpy等也是以 '\0' 作为字符串操作终止标志的，但是在string中，序列中的'\0'不一定标识对象的结束。即在string中，有效字符的范围是以_size进行标识的，而与序列中的'\0'无关，'\0'可能成为string中的有效字符。因为这一点，在实现一些接口时，不能简单地复用C库中的str系列函数，而需使用mem系列函数对内存进行操作，否则就会造成一些问题。

reserve()是一个对string容量进行操作的成员函数，在元素操作时，为了保证内存空间充足，会频繁调用这个接口。reserve的实现有三步：配置新空间、数据移动和释放旧空间。

void reserve(size_t n) { if (n > _capacity) { char* tmp = new char[n + 1]; //为'\0'多开一个字节空间 //考虑'\0'在内 memcpy(tmp, _str, n + 1); delete[] _str; _str = tmp; _capacity = n; } }

元素访问和操作

Access

string可以支持下标操作，这主要得益于对下标访问操作符的重载。下标访问操作符根据对象是否为const对象被设计成两个函数的重载。

为了与C语言更好的兼容，设计一个c_str()接口返回序列的字符串数据部分。

//针对普通对象，可读可写 char& operator[](size_t pos) { assert(pos < _size); return _str[pos]; } //针对const对象，只读 const char& operator[](size_t pos) const { assert(pos < _size); return _str[pos]; } const char* c_str() const { return _str; }

Add

void push_back(char ch) { if (_size == _capacity) { //push之前有可能是空串，_capacity为0 reserve(_capacity == 0 ? 4 : _size * 2); } _str[_size++] = ch; _str[_size] = '\0'; //末尾补'\0' } void append(const char* str) { int len = strlen(str); //判断_size + len与_capacity的关系 if (_size + len > _capacity) { reserve(_size + len); } strcpy(_str + _size, str); _size += len; } string& insert(size_t pos, size_t n, char ch) { assert(pos < _size); //检查pos的合法性 //检查容量 if (_size + n > _capacity) { reserve(_size + n); } //挪动数据 size_t end = _size; while (end >= pos && end != npos) { _str[end + n] = _str[end]; --end; } //插入数据 for (int i = 0; i < n; ++i) { _str[pos + i] = ch; } _size += n; //注意不要忘记调整_size return *this; } string& insert(size_t pos, const char* str) { assert(pos < _size); //检查容量 int len = strlen(str); if (_size + len > _capacity) { reserve(_size + len); } //挪动数据 size_t end = _size; //由于end在与pos比较时会被提升至size_t类型，所以要额外判断end与npos的关系 while (end >= pos && end != npos) { _str[end + len] = _str[end]; --end; } //插入数据 for (int i = 0; i < len; ++i) { _str[pos + i] = str[i]; } //调整_size _size += len; return *this; }

在进行push操作时，往往更加习惯使用+=操作符，故而对+=运算符进行重载以简化push的使用：

string& operator+=(char ch) { push_back(ch); return *this; } string& operator+=(const char* str) { append(str); return *this; }

Delete

iterator erase(size_t pos = 0, size_t len = npos) { assert(pos < _size); //从pos位置清理至最后 if (len == npos || pos + len >= _size) { _str[pos] = '\0'; } else { //挪动数据，包括'\0' size_t end = pos + len; while (end <= _size) { _str[pos++] = _str[end++]; } } //注意不能直接_size -= len,len 可能是npos _size = pos; return _str + pos; } void clear() { if (_size != 0) { erase(); } }

Search

size_t find(char ch, size_t pos = 0) { assert(pos < _size); //遍历搜索指定字符 for (int i = pos; i < _size; ++i) { if (_str[i] == ch) { return i; } } return npos; } size_t find(const char* str, size_t pos = 0) { assert(pos < _size); char* ret = strstr(_str, str); if (ret) { return ret - _str; } else { return npos; } }

在上述第二个接口寻找子串时，由于使用的是strstr，所以当在_str中遇到'\0'时就停止搜索了，由上文可知，这对于string中含多个'\0'的情况可能会造成一些问题。为了避免问题，可以手动实现一个定制的strstr。关于字符串匹配，请参考BP算法和KMP算法。

截取和判断

string substr(size_t pos = 0, size_t len = npos) { assert(pos < _size); string tmp; //从pos位置截取到最后 if (len == npos || len + pos > _size) { for (int i = pos; i < _size; ++i) { tmp += _str[i]; } } else { for (int i = pos; i < pos + len; ++i) { tmp += _str[i]; } } return tmp; } void resize(size_t n, char ch = '\0') { if(n <= _size) { _str[_size] = '\0'; } //n > _size，判断并调整容量后添加字符 else { reserve(n); for (int 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); } bool empty() { return _size == 0; }

运算符重载

赋值运算符重载

string的赋值运算符重载有两种写法，一种是传统的深拷贝写法，分为开新空间、移动数据两个步骤；另一种写法将这两个步骤委托给拷贝构造进行，可以简化重载函数的书写。

//传统写法 string& operator=(const string& s) { reserve(s._capacity); memcpy(_str, s._str, s._size + 1); _size = s._size; return *this; } //现代写法的参数是一个临时的类对象，该类对象是右值对象调用拷贝构造所得 //将tmp临时对象与this对象交换，可以达到赋值的目的 //tmp的生命周期在本函数域内，会自动调用析构释放空间 string& operator=(string tmp) { swap(tmp); return *this; }

类似的，拷贝构造也有一种现代写法，利用构造函数来简化拷贝构造的书写：

//现代写法 //写初始化列表，防止因this对象的随机内容在swap时产生问题 string(const string& s) :_size(s._size), _capacity(s._capacity), _str(nullptr) { string tmp(s._str); swap(tmp); }

现代写法的拷贝构造利用构造函数拷贝了已有对象的内容，并将其交还给this对象以达到拷贝构造的目的。这种写法的拷贝构造有一个缺陷，即当已有对象的有效数据部分含'\0'时，tmp只会构造出 '\0' 之前的部分数据。综合来说，不建议用这种方式写拷贝构造函数。

比较和判断

bool operator>(const string& s) { //hello helloxxx true //helloxxx hello false //hello hello false int ret = memcmp(_str, s._str, _size < s._size ? _size : s._size); return ret == 0 ? _size > s._size : ret > 0; } bool operator==(const string& s) { return _size == s._size && memcmp(_str, s._str, _size) == 0; } bool operator!=(const string& s) { return !(*this == s); } bool operator>=(const string& s) { return (*this > s || *this == s); } bool operator<(const string& s) { return !(*this >= s); } bool operator<=(const string& s) { return !(*this > s); } };

流运算符重载

////输入输出 std::ostream& operator<<(std::ostream& cout, const shr::string& s) { for (int i = 0; i < s.size(); ++i) { cout << s[i]; } return cout; } std::istream& operator>>(std::istream& cin, shr::string& s) { s.clear(); //clear实现数据覆盖 //get可以读取单个字符 char ch = cin.get(); //清空缓冲区中的前置空格和换行 while (ch == ' ' || ch == '\n') { ch = cin.get(); } //先将输入的字符放入buff中，buff满后再放入对象中 //减少扩容次数 char buff[128]; int i = 0; while (ch != ' ' && ch != '\n') { buff[i++] = ch; buff[i] = '\0'; if (i == 127) { s += buff; i = 0; } ch = cin.get(); } if (i != 0) { s += buff; i = 0; } return cin; }

string类的引用计数和写时拷贝

当进行拷贝构造时，总是进行深拷贝，适用于需要对对象进行读写操作的情况。因为存在只对某些对象进行读操作的情况，多余的深拷贝便会占据多余的内存空间，解决办法便是进行浅拷贝。

浅拷贝有两个问题：对同一块内存的重复释放和对同一块内存数据的操作冲突。对于第一个问题，可以使用引用计数解决，对于每一块内存空间，用一个整型记录本块内存空间目前被引用的次数，当进行拷贝构造时，进行浅拷贝，被引用次数加一；对象销毁时，不释放空间，被引用次数减一；当被引用次数减至0时，释放内存空间。对于第二个问题，可以进行写时拷贝，拷贝构造时进行浅拷贝，此时对于只读情况完全适用，当对对象进行写操作时，进行深拷贝，以避免对原内存空间数据的修改。

通过引用计数和写时拷贝，可以尽量节省不必要的内存消耗。对于对对象进行只读操作的情况，无需开辟额外空间，而是在进行写操作时才进行深拷贝申请必要的内存空间。