前言
本文带你进入string的模拟实现，对于string，是我们深入学习STL的必要途径。
一、string的成员变量
我在模拟实现string时，成员变量如下：
private: size_t _size; size_t _capacity; char* _str;
二、string默认成员函数
1.构造函数
1.1 无参构造(默认构造)
构造时不进行任何初始化，则默认为空字符串
比如：
bit::sring s1;
string() :_size(0) ,_capacity(0) ,_str(new char[1]) { _str[0] = '\0'; }
1.2 普通构造
- 思路：
- 1.先新申请一块空间
- 2.把原数据拷贝到新空间
- 3.释放原空间
- 4._str指向新空间
//构造函数，无参和全缺省可以合并 string(const char* str = "") : _size(strlen(str)) , _capacity(_size) { _str = new char[_capacity + 1]; //必须是_capacity + 1，多开的空间要给'\0' //strcpy(_str, str);//strcpy默认只拷贝到'\0'终止，但有些情况是要拷贝完全，包括'\0' memcpy(_str, str, _size + 1); //包括'\0'也需要拷贝 }
解析：
1.新申请的空间往往会多申请一个，用来存放’\0’
2.使用memcpy而不是使用strcpy的原因：
如果使用strcpy，这样的情况会出现问题：
“hello\0xxxxx”
strcpy默认只拷贝到’\0’,memcpy按照字节数拷贝，包括’\0’也会拷贝
1.3无参构造和全缺省构造可以合并
合并后结果如下：
string(const char* str = "") : _size(strlen(str)) , _capacity(_size) { _str = new char[_capacity + 1]; //必须是_capacity + 1，多开的空间要给'\0' //strcpy(_str, str);//strcpy默认只拷贝到'\0'终止，但有些情况是要拷贝完全，包括'\0' memcpy(_str, str, _size + 1);//包括'\0'也需要拷贝 }
如果没有传参，默认是空字符串，如果传参，则使用该参数。
浅拷贝和深拷贝
浅拷贝：也称位拷贝，编译器只是将对象中的值拷贝过来。如果对象中管理资源，最后就会导致多个对象共享同一份资源，当一个对象销毁时就会将该资源释放掉，而此时另一些对象不知道该资源已经被释放，以为还有效，所以当继续对资源进项操作时，就会发生发生了访问违规。
一句话来说：一块空间由多个对象共同管理。
深拷贝：
每个对象有自己独立的空间，不会和其他对象共享，他们之间互不影响。
2.拷贝构造
在string的库实现中，拷贝构造是深拷贝的，所以我们需要实现深拷贝。
- 思路：1.开辟跟原字符串一样大小的空间。
- 2.将原字符串的内容拷贝到新的字符串。
下面给出拷贝构造传统写法
string(const string& s) : _size(strlen(s._str)) , _capacity(s._capacity) { _str = new char[s._capacity + 1]; //必须是_capacity + 1，多开的空间要给'\0' //strcpy(_str, s._str); memcpy(_str, s._str, s._size + 1);//包括'\0'也需要拷贝 }
实际上，拷贝构造还有现代写法如下：
string(const string& s) :_str(nullptr) ,_size(0) ,_capacity(0) { string tmp(s._str); swap(tmp); }
现代写法实现拷贝构造还有一些要注意的问题，比如：
在调用赋值运算符重载(operator=)时会讲到。
3.赋值运算符重载
对于赋值来说，如s2 = s1
思路如下：
- 1.先用s拷贝构造一个临时对象。
- 2.释放原str的空间
- 3.将str指针指向临时对象，此时str就是s的拷贝了。
- （tmp临时对象在结束调用该函数之后编译器会自动调用析构函数进行销毁）
- 4.返回*this
传统写法如下：
//传统写法 string& operator=(const string& s) { if (this != &s) { bit::string tmp(s); delete[] _str; _str = tmp._str; _size = tmp._size; _capacity = tmp._capacity; } return *this; }
同样，赋值重载也有现代写法：
- 思路:
先将s拷贝一份给tmp，然后tmp和this的成员变量进行交换，出了作用域后，tmp会带着之前this的那块空间自动销毁。
string& operator=(const string& s) { //不能自己给自己赋值 if (this != &s) { bit::string tmp(s); std::swap(_str, tmp._str); std::swap(_size, tmp._size); std::swap(_capacity, tmp._capacity); //不能这样写： //std::swap(*this, tmp); //swap的就是赋值交换，又会调用赋值重载，无限死循环。 } return *this; }
相当于tmp是个打工人一样，别人pua一下tmp，tmp就帮别人泡泡面，吃完了还帮别人收拾。
还有一个更加现代的写法：
void swap(string& s) { std::swap(_str, s._str); std::swap(_size, s._size); std::swap(_capacity, s._capacity); } string& operator=(string tmp) { if (this != &tmp) { //this->swap(tmp); swap(tmp); } return *this; }
要注意这样的问题：
s2= s1为例，
调用赋值之前，先传参进行拷贝构造，再交换。
- 1、传参时s1会调用拷贝构造给tmp，如果拷贝构造没有初始化的话，拷贝构造完成后，tmp是未初始化的对象，和this交换后，会调用析构函数释放指向不属于自己空间的野指针，出现问题。
- 2.如果是拷贝"hello\0world"，现代写法只会拷贝到’\0’之前，而库的实现是拷贝完全。
综上，在拷贝构造方面使用现代写法不如传统写法好。
4.析构函数
~string() { //有可能刚构造出空stirng类就析构了，释放空指针没有意义 if (_str) { delete[] _str; _str = nullptr; _size = _capacity = 0; } }
三、[]的下标访问和iterator迭代器
1.operator[]重载
普通[]
char& operator[](size_t pos) { //_size 的位置是'\0' assert(pos < _size); return _str[pos]; }
const修饰的[]
const char& operator[](size_t pos) const { assert(pos < _size); return _str[pos]; }
2.begin迭代器
typedef char* iterator; typedef const char* const_iterator;
iterator begin() { iterator it = _str; return it; } const_iterator begin() const { iterator it = _str; return it; }
3.end迭代器
iterator end() { iterator it = _str; return (it + _size); } const_iterator end() const { iterator it = _str; return (it + _size); }
四、对容器空间操作
1.size()
返回size即可。
size_t size() const { return _size; }
2.capacity()
不用再多说了。
size_t capacity() const { return _capacity; }
3.empty()
bool empty() const { return _size == 0; }
4.reserve()——重要
reserve函数是对对象进行扩容操作的。
思路：
- 1.如果需要扩容的空间小于原空间，则不会进行缩容操作。
- 2.否则，进行扩容操作。
- 先申请一块新的空间，然后将原空间的数据拷贝到新空间
- 再释放原空间，将原空间的指针指向新空间。
- 更新capacity即可。
void reserve(size_t n) { //不仅仅append，push_back会用到，其他地方也可能用到reserve，不会缩容 //如果是缩容的情况的话，不允许发生 if (n > _capacity) { char* tmp = new char[n + 1]; //留给'\0' //strcpy(tmp, _str); memcpy(tmp, _str,n + 1); delete[] _str;//如果不销毁，就会出现内存泄露。 _str = tmp; _capacity = n; // 不能等于 n + 1，容量不包含'\0' } }
注意：我们需要用memcpy拷贝更合理，因为实际情况会出现诸如"hello\0world"的情况
5.resize()——重要
resize是对对象进行扩容，然后同时将size提升到指定的数据大小的。
库的实现是：将对象调整空间到指定大小，如果比原容量大，且不给指定需要填充的字符，多出来的空间默认填充为’\0’。
思路：
- 1.如果要调整的大小小于或者等于当前容量，则不会进行缩容，只会让size调整，默认用’\0’填充size位置即可。
- 2.如果要调整的大小大于当前容量，则调用reserve函数进行扩容，如果不给指定的字符，则默认将后面的空间填充成’\0’即可。
void resize(size_t n, char c = '\0') { if (n < _size) { _size = n; _str[_size] = '\0'; } else { //先扩容 reserve(n); //将后面的空间全部填充成c for (size_t i = _size; i < n; i++) { _str[i] = c; } _size = n; _str[_size] = '\0'; } }
五、增删查改工作
1、push_back（）
push_back在库中的实现是，向字符串末尾插入一个字符。
思路：
- 1.首先需要检查容量，如果容量不足则需要扩容。
- 2.再将最后一个字符插入到’\0’位置
- 3.size++，然后将size位置放置’\0’
void push_back(char c) { //满了，要扩容 if (_size == _capacity) { reserve(_capacity == 0 ? 4 : 2 * _capacity);//不需要再+1,reserve的扩容机制是会自己多给几个空间 } //在'\0'后面尾插 _str[_size] = c; ++_size; //记得要在后面+'\0' _str[_size] = '\0'; }
2.append（）
append函数是在字符串末尾追加一个字符串。
思路：
- 1.检查容量
- 2.在字符串末尾开始拷贝要追加的字符串即可。
- 需要注意的问题是，检查容量时，扩容不能扩2倍，因为可能追加的字符串比2倍的容量还长，具体请看代码。
void append(const char* str) { size_t len = strlen(str); if (_size + len > _capacity) { //追加一个字符串，扩二倍不一定够，所以至少扩容到_size + len; reserve(_size + len); //不需要再+1,reserve的扩容机制是会自己多给几个空间。 } //strcpy(_str + _size, str); memcpy(_str + _size, str,len +1);//memcpy默认会拷贝'\0' _size += len; _str[_size] = '\0'; }
3.operator+=
对于这个运算符重载，有两种情况
- 1.+=一个字符
- 2.+=字符串
我们直接复用push_back函数和append函数即可。
string& operator+=(char c) { push_back(c); return *this; } string& operator+=(const char* str) { append(str); return *this; }
4.insert（）
在库中的insert函数如上，它有多个版本，这里我们实现最常用的两个版本。
版本1：
在pos位置插入n个字符c。
思路：
- 1.插入数据前先检查容量。
- 2.将pos及其之后的数据往后挪动。
- 3.在pos位置插入字符。
- 4.更新size的大小，并在size位置添加’\0’
// 在pos位置上插入n个字符c/字符串str void insert(size_t pos,size_t n , char c) { //pos位置可以在'\0' assert(pos <= _size); //扩容，至少为_size + n if (_size + n > _capacity) { reserve(_size + n); } //扩容后，先将pos位置之后字符后移，再插入。 size_t end = _size - 1; while (end >= pos && end != npos) //如果没有后面这个条件，头插会出问题。 // npos是-1，但它是size_t类型，是Int_MAX { _str[end + n] = _str[end]; --end; } for (size_t i = pos; i < pos + n; i++)//注意，n是长度，不是下标 { _str[i] = c; } _size += n; _str[_size] = '\0'; }
版本2：
在pos位置插入一个字符串
思路：
- 1.检查容量
- 2.将数据往后挪
- 3.在pos位置插入数据
- 4.更新size位置，并将size位置置为’\0’
void insert(size_t pos, const char* str) { assert(pos <= _size); size_t len = strlen(str); if (_size + len > _capacity) { reserve(_size + len); } //bit::string::iterator it = this->end(); //挪动数据 size_t end = _size - 1; while (end >= pos && end != npos) //如果没有后面这个条件，头插会出问题。 // npos是-1，但它是size_t类型，是Int_MAX { _str[end + len] = _str[end]; --end; } //插入 for (size_t i = 0; i < len; i++)//注意，n是长度，不是下标 { _str[i + pos] = str[i]; } _size += len; _str[_size] = '\0'; }
5.erase（）
删除pos位置开始的len个字符。
如果不给参数，默认从0开始删除所有字符。
注意：npos表示无穷大
思路：
- 情况1：
- 如果要删除所有元素，直接将size置为0，然后将size位置设置成’\0’即可。
- 情况2：
- 在pos位置删除len个字符。
- 将pos位置开始的len个字符从前往后挪动即可，（'\0’也需要挪动）
void erase(size_t pos = 0, size_t len = npos) { assert(pos <= _size); //pos位置开始全部删完 if (pos == npos || pos + len >= _size) { _str[pos] = '\0'; _size = pos; } else { size_t end = pos + len; while (end <= _size)// '\0'也要挪 { _str[pos++] = _str[end++]; } _size -= len; } }
6.find（）
这里有多种版本，我们实现常用的即可。
版本1：在字符串中找出第一次出现的字符c，返回该位置下标。
size_t find(char c, size_t pos = 0) const { assert(pos < _size); for (size_t i = pos; i < _size; i++) { if (_str[i] == c) return i; } return npos; }
版本2：在字符串中找出一个指定的子串，返回第一次出现的位置。
使用strstr函数即可，可以不用再追求KMP算法。
size_t find(const char* s, size_t pos = 0) const { assert(pos < _size); //strstr(str1,str2),在str1中找到str2 char* ret = strstr(_str, s); if (ret) { return ret - _str; // 指针-指针，返回指针直接的元素个数 } else { return npos; //没找到 } }
7. substr（）
该函数的功能是：从pos位置开始，返回len个字符组成的字符串。
相当于返回一个特定的子串。
思路：
- 如果字符串的长度len大于size，则查找范围是从pos位置开始直到末尾。
- 否则，设置临时对象tmp，拷贝从pos位置开始的len个字符，返回该对象的临时拷贝。
string substr(size_t pos = 0, size_t len = npos) const { assert(pos < _size); size_t n = len; if (len == npos || pos + len > _size) { n = _size - pos; } string tmp; tmp.reserve(n); for (size_t i = pos; i <pos + n; i++) { tmp += _str[i]; } return tmp; }
六、比较运算符重载
1.operator<
个人建议：
- 1.先模拟实现memcmp函数。
- 模拟完成后才知道如何更好实现operator<运算符重载。
- 2.此时字符串分为3种情况。
- （1）“hello” 和 “helloxxx”
- （2）“hello” 和"hello"
- （3）“helloxxx” 和"hello"
- 只有情况1返回true，其余返回false
bool operator<(const string& s) { //可以模拟实现一下memcmp怎么比的 //size_t i1 = 0, i2 = 0; //while (i1 != _size && i2 != s._size) //{ // if (_str[i1] >= s._str[i2]) // { // return false; // } // i1++; // i2++; //} //return i1 == _size && i2 != s._size; int ret = memcmp(_str, s._str, _size < s._size ? _size : s._size); // ret == 0 : == // ret < 0 : < // ret > 0 : > //hello ,helloxxx :true //hello hello :false //helloxxx hello :false return ret == 0 ? _size < s._size : ret < 0; }
2. operator==
思路：
- 1.只要两个字符串相等，则它们的size必定相等。
- 2.用memcmp比较即可。
bool operator==(const string& s) { if (_size != s._size) return false; return memcmp(_str, s._str, _size) == 0; }
3. operator<=,>,>=,!=
复用前面两个函数的实现即可。
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); } bool operator!=(const string& s) { return !(*this == s); }
七、流插入和流提取
注意：流插入和流提取均为全局函数，不是类对象的成员函数。
1.流插入<<（流插入和c_str()的区别）
库的流插入的实现是，完整地打印出字符串的所有内容，包括’\0’
而c_str()函数是返回字符串的首地址，那么就可以通过首地址打印，然而会遇到’\0’停止。
ostream& operator<<(ostream& out, const bit::string& s) { for (auto ch : s) { out << ch; } return out; } const char* c_str() const { return _str; }
2.流提取
- 库的实现是：
- 1.遇到在遇到字符之前遇到的空格’ ‘和斜杠n换行符’\n’，都会刷新缓冲区，会重新进行读取。
- 所以可以在这里使用get函数进行缓冲区的刷新，get函数会一直读取，遇到空格或者换行不会停止。
- 2.在遇到字符之后，如果再遇到空格’ ‘或者斜杠n换行符’\n’，默认是多字符串的输入。
- 3.使用buf数组来减少扩容的代价。
- 本意为：先使用一个128字节大小的buffer数组来保存输入的值，如果数组满了，再将数组的数据存入字符串s中。
- 如果数组没满，在遇到空格或者换行后，也同样将数组的数据存入字符串s中。
istream& operator>>(istream& in, bit::string& s) { s.clear();//每次进行输入必须初始化，否则会遗留上一次的字符 char ch = in.get(); // get解决了当读取到' '或者'\n'的问题。 //在c语言/c++，默认读取到' '或者'\n'为分隔符号 //使用buf数组减少扩容的代价 char buf[128]; //处理前缓冲区的空格和换行 while (ch == ' ' || ch == '\n') { ch = in.get(); //把空格或换行刷掉 } int i = 0; //如果是这样的情况： (在此之前有多个空格)hello world，cin只会读取到hello，world不会读取，后面遇到空格默认是多字符串的输入了 while (ch != ' ' && ch != '\n') { buf[i++] = ch; if (i == 127) //数组满了 { buf[i] = '\0'; s += buf; i = 0; } ch = in.get(); } //数组中仍有剩下的字符，继续存入 if (i != 0) { buf[i] = '\0'; s += buf; } return in; }
总结
string常用接口的模拟实现就到这里。
