阅读量:0
模拟实现string类
一.命名空间与类成员变量
根据string的结构，显然可知string实质就是字符数组，但有一点区别就是，string可以扩容，再类比动态顺序表，就不难得出string的成员变量。在模拟实现string时，为了与C++标准库中的string作区分，可以给定命名空间。
成员变量：
- char* str：指向string第一个字符的指针。
- size_t size：string中有效数据的个数。
- size_t capacity：string可以存放有效数据的容量。
- static const size_t npos：静态成员。
大体结构如下：
namespace xzy { class string { private: char* _str = nullptr; size_t _size = 0; size_t _capacity = 0; static const size_t npos; //静态成员类内声明 }; const size_t string::npos = -1; //类外初始化 } 二.构造函数
class string { public: string() :_str(nullptr) ,_size(0) ,_capacity(0) {} string(const char* str) :_size(strlen(str)) , _capacity(_size) ,_str(new char[_capacity + 1]) {} const char* c_str() const { return _str; } private: char* _str; size_t _size; size_t _capacity; }; 
- 第一种由于将_str初始化为nullptr，通过C语言中的返回_str直到遇到’\0’停止打印字符串的方法，而_str为nullptr，打印nullptr导致程序崩溃。
- 第二种看似程序正常但真的是正确的吗？其实：初始化列表出现的顺序，并不是初始化的顺序，而是按照成员变量声明的顺序初始化成员变量，先初始化_str，而_capacity是随机值，导致开辟的空间不确定，导致出现错误。
正确的方法如下：
1.无参（默认）构造
由于string默认含有’\0’，可以提前开辟一个’\0’，而’\0’不是有效的数据，也不算入容量之中。
string() :_str(new char[1]{'\0'}) , _size(0) , _capacity(0) {} 2.有参构造
注意：容量中不包含’\0’，而string中有包含’\0’，所以在开辟空间时要加上一个’\0’的空间。
string(const char* str) { _size = strlen(str); _capacity = _size; _str = new char[_capacity + 1]; strcpy(_str, str); } 3.兼容无参和有参构造
string(const char* str = "") { _size = strlen(str); _capacity = _size; _str = new char[_capacity + 1]; strcpy(_str, str); } - 不传参时：用缺省值，str为空的常量字符串，strlen(str)为0，且sizeof(str)为1，含有一个隐藏的’\0’，刚好满足无参构造。
- 传参时：就用实参，满足有参构造。
4.拷贝构造
string(const string& str) { _str = str._str; _size = str._size; _capacity = str._capacity; } int main() { xzy::string s1; xzy::string s2(s1); return 0; } 
分析：当我们未提供拷贝构造时，编译器会提供拷贝构造，进行简单的值拷贝（浅拷贝），正如以上代码。但是存在很大的漏洞，s1的_str与s2的_str指向堆区同一块空间，程序结束时分别调用各自的析构函数，从而对同一块空间释放两次，这是未定义行为，导致程序崩溃。
1.传统写法
思路：先开空间，再利用strcpy拷贝，最后修改有效数据大小与容量。
string(const string& str) { _str = new char[str._capacity + 1]; strcpy(_str, str._str); _size = str._size; _capacity = str._capacity; } 2.现代写法
构造一个临时对象，进行交换。
void swap(string& str) { std::swap(_str, str._str); std::swap(_size, str._size); std::swap(_capacity, str._capacity); } string(const string& str) { string tmp(str._str); swap(tmp); } 
注意：由于没有初始化列表，不确定s2_str被初始化为nullptr，取决于编译器，可以在类成员变量声明时加上缺省值，确保s2.str为nullptr，而避免s2._str为随机值，交换给tmp变成野指针，函数结束时tmp调用析构函数释放不合法的空间导致程序崩溃。
class string { private: char* _str = nullptr; size_t _size = 0; size_t _capacity = 0; }; 三.析构函数
_str是在堆区开辟的空间，要用delete[]释放空间，否则造成内存泄漏。
~string() { delete[] _str; _str = nullptr; _size = _capacity = 0; } 四.string类对象的容量操作
1.size
size_t size() const { return _size; } 2.capacity
size_t capacity() const { return _capacity; } 3.clear
void clear() { _str[0] = '\0'; _size = 0; } 4.empty
判断有效数据是否为0即可。
bool empty() { return _size == 0; } 5.reserve
扩容时：先开辟新空间，千万记得多开一个空间保存’\0’，再将旧空间拷贝到空间，释放旧空间，修改_str指向新空间，最后修改容量。学了C++，new就取代realloc了。
void reserve(size_t n) { if (n > _capacity) { char* tmp = new char[n + 1]; strcpy(tmp, _str); delete[] _str; _str = tmp; _capacity = n; } } 6.resize
修改有效数据的个数时：先比较修改后的有效数据与原有数据的大小，若小于则修改_size，若大于再比较容量与修改后的有效数据的大小，判断是否扩容，利用memset函数初始化。
void string::resize(size_t n, char c) { if (n > _size) { // 如果newSize大于底层空间大小，则需要重新开辟空间 if (n > _capacity) { reserve(n); } memset(_str + _size, c, n - _size); } _size = n; _str[n] = '\0'; } 五.string类对象的访问及遍历操作
1.operator[]
char& operator[](int pos) { assert(pos >= 0 && pos < _size); return _str[pos]; } const char& operator[](int pos) const { assert(pos >= 0 && pos < _size); return _str[pos]; } 提供两个版本的operator[]：普通重载[]与const修饰的重载[]。若初始化一个常量字符串时：const string s(“123”); 由于存在权放大问题，就无法调用普通重载[]，而const修饰的重载[]就可以使用。
重载operator[]，本质就是函数重载，而函数的返回值是不支持函数重载条件的，为了让两个operator[]满足函数重载的条件，可以const随便修饰一个成员函数。隐藏了this指针，实际const修饰的是this所指的对象。
第一个函数的参数列表的第一个位置隐藏了string* const this；第二个函数的参数列表的第一个位置隐藏了const string* const this；函数的参数不同就满足了函数重载的条件，可以共存。
2.实现迭代器：begin+end
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; } 为了与标准库里的类似，重定义char* 为iterator。同理提供两个版本的迭代器iterator与const_iterator。
六.string类对象的增删查改操作
1.operator=
注意：operator=只能写成成员函数，不能写成成员函数。
1.传统写法
与传统写法的拷贝构造类似。
string& operator=(const string& str) { if (this != &str) { delete[] _str; _str = new char[str._capacity + 1]; strcpy(_str, str._str); _size = str._size; _capacity = str._capacity; } return *this; } 注意：如果没写 if (this != &str) 自己给自己赋值时，delete[] _str 后_str为野指针，自己给自己拷贝程序崩溃。
2.现代写法
与现代写法的拷贝构造类似。
string& operator=(const string& str) { if (this != &str) { //string tmp(str.c_str()); //调用构造 string tmp(str); //调用拷贝构造 swap(tmp); //刚好函数结束时，tmp将赋值前的空间释放，相当的完美 } return *this; } //更完美的方法：一行搞定 string& operator=(string tmp) { swap(tmp); return *this; } 2.push_back
尾插时：先检查容量，再进行尾插。注意：最后要补上'\0'。
void push_back(char ch) { if (_size == _capacity) { reserve(_capacity == 0 ? 4 : 2 * _capacity); } _str[_size] = ch; ++_size; _str[_size] = '\0'; } 3.pop_back
尾删时：先检查是否有有效数据，有效数据自减一，在赋值’\0’。
void pop_back() { assert(!empty()); --_size; _str[size] = '\0'; } 4.append
追加时：先要判断容量是否大于有效数据+所追加的字符串大小。若小于则无需扩容；若大于两倍则需要多少就扩容多少；小于两倍就按照两倍扩容。最后拷贝字符串即可。
void append(const char* str) { size_t len = strlen(str); if (_size + len > _capacity) { reserve(_size + len > 2 * _capacity ? _size + len : 2 * _capacity); } strcpy(_str + _size, str); _size += len; } 5.operator+=
- +=一个字符：直接调用push_back即可。
string& operator+=(char ch) { push_back(ch); return *this; } - +=一个字符串：直接调用append即可。
string& operator+=(const char* str) { append(str); return *this; } 6.insert
- 插入一个字符：先检查容量，再整体往后挪动一位，最后插入即可。
但是存在一些坑如下：
- 当在pos=0位置插入字符时：end=0时进入循环，- -end，由于end类型为无符号整形size_t，则end不是-1而是一个非常大的值，进入死循环。
- 就算将end修改为int ，循环条件end>=pos时，两边类型不同会进行算数转换，int转换成size_t，end转换成size_t类型，依旧进入死循环。
正确写法：
void insert(size_t pos, char ch) { assert(pos >= 0 && pos <= _size); if (_size == _capacity) { reserve(_capacity == 0 ? 4 : 2 * _capacity); } //第一种：强转size_t为int //int end = _size; //while (end >= (int)pos) //{ // _str[end + 1] = _str[end]; // --end; //} //_str[pos] = ch; //++_size; //推荐这种：end始终大于0 size_t end = _size + 1; while (end > pos) { _str[end] = _str[end - 1]; --end; } _str[pos] = ch; ++_size; } - 插入一个字符串：先检查容量，再整体往后挪动为插入的字符串预留空间，最后插入字符串即可。
void insert(size_t pos, const char* str) { assert(pos >= 0 && pos <= _size); size_t len = strlen(str); if (_size + len > _capacity) { reserve(_size + len > 2 * _capacity ? _size + len : 2 * _capacity); } //整体后移 //memmove(_str + len, _str, sizeof(char) * len); size_t end = _size + len; while (end > pos + len - 1) { _str[end] = _str[end - len]; --end; } //插入字符串 for (size_t i = 0; i < len; i++) { _str[pos + i] = str[i]; } _size += len; } 7.erase
删除时：比较要删除的子串长度与pos及其以后字符串的的大小，判断是否pos及其以后得字符全删除。
void erase(size_t pos, size_t len = npos ) { assert(pos >= 0 && pos < _size); if (len >= _size - pos) { _str[pos] = '\0'; _size = pos; } else { //memmove(_str + pos, _str + pos + len, sizeof(char) * (_size - pos - len + 1)); for (size_t i = pos; i <= _size - len; i++) { _str[i] = _str[i + len]; } _size -= len; } } 8.find
- 查找字符：找到返回下标，未找到返回npos。
size_t find(char ch, size_t pos = 0) { assert(pos >= 0 && pos < _size); for (size_t i = 0; i < _size; i++) { if (_str[i] == ch) { return i; } } return npos; } - 查找字符串：利用C语言接口strstr查找子串函数，找到返回下标，未找到返回npos。
size_t find(const char* str, size_t pos = 0) { assert(pos >= 0 && pos < _size); const char* ptr = strstr(_str + pos, str); if (ptr == nullptr) { return npos; } else { return ptr - _str; } } 9.substr
返回子串：比较要返回子串长度与pos及其以后字符串的的大小，判断是否pos及其以后得字符全返回。
注意：深浅拷贝问题；由于是返回局部string，而局部string出函数被销毁。此时会拷贝构造一个临时string作为返回，而默认的拷贝构造是浅拷贝（简单的值拷贝），局部string销毁时，临时变量string中的_str变成野指针，外面又拷贝构造接收该临时string，本身就是无效的string，程序结束前调用析构函数释放空间，重复的delete导致程序崩溃。解决方法：自己写一个深拷贝构造。
string substr(size_t pos = 0, size_t len) { assert(pos >= 0 && pos < _size); if (len > _size - pos) { len = _size - pos; } string sub; sub.reserve(len); for (size_t i = 0; i < len; i++) { sub += _str[pos + i]; } return sub; } 10.c_str
返回字符串首字符的地址：用于调用C语言接口，例如strcpy，memmove等。
const char* c_str() const { return _str; } 11.swap
调用std::swap进行对象（值）交换。
void swap(string& str) { std::swap(_str, str._str); std::swap(_size, str._size); std::swap(_capacity, str._capacity); } 七.非成员函数
1.string比较函数
只需要利用strcmp函数比较，实现两个函数，就可以调用实现多个函数。
bool operator<(const string& s1, const string& s2) { return strcmp(s1.c_str(), s2.c_str()) < 0; } bool operator>(const string& s1, const string& s2) { return !(s1 <= s2); } bool operator==(const string& s1, const string& s2) { return strcmp(s1.c_str(), s2.c_str()) == 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); } 2.流插入与流提取
在C++中，屏幕和键盘分别通过标准输出流（std::cout）和标准输入流（std::cin）来实现数据的流插入（输出）和流提取（输入）。以下是针对屏幕（输出）和键盘（输入）的流插入与流提取的详细介绍：
- 屏幕（输出）与流插入（operator<<）：流插入（operator<<）用于将数据发送到输出流中，在C++中，标准输出流std::cout是与屏幕（通常是控制台或命令行界面）相关联的。当你使用<<操作符将数据发送到std::cout时，数据会被格式化（如果需要的话）并显示在屏幕上。
- 键盘（输入）与流提取（operator>>）：流提取（operator>>）用于从输入流中读取数据，在C++中，标准输入流std::cin是与键盘（或任何标准输入设备）相关联的。当你使用>>操作符从std::cin中读取数据时，它会从键盘获取输入，并根据需要将其存储在提供的变量中。
注意：
- 流插入与流提取不推荐写成成员函数，例如ostream& operator<<(ostream& out); 因为<<左边是类对象，调用时要写成s<<out，非常别扭。
- 不需要写成友元函数，可以做到不用访问类内的私有成员，完成流插入与流提取。
ostream& operator<<(ostream& out, const string& str) { /*string::const_iterator it = str.begin(); while (it != str.end()) { cout << *it; ++it; }*/ for (auto ch : str) { out << ch; } return out; } istream& operator>>(istream& in, string& str) { str.clear(); char ch; //in >> ch; //错误，ch不会提取空白字符，陷入死循环 ch = in.get(); while (ch != ' ' && ch != '\n') { str += ch; //in >> ch; ch = in.get(); } return in; } 注意：流提取cin默认跳过空白字符（不会读取空白字符），例如：空格、换行，可以用cin.get()函数从键盘获得空白字符，类似C语言中的getc()函数。
优化方法：减少扩容，临时存放到字符数组中，等到满了时，再+=到其中。
istream& operator>>(istream& in, string& str) { str.clear(); const int N = 256; char buff[N]; int i = 0; char ch; ch = in.get(); while (ch != ' ' && ch != '\n') { buff[i++] = ch; if (i == N - 1) { buff[i] = '\0'; str += buff; i = 0; } ch = in.get(); } if (i > 0) { buff[i] = '\0'; str += buff; } return in; } 3.getline
getline函数：可以读取含有空格的字符串，将’\n’作为分隔符。
istream& getline(istream& in, string& str) { str.clear(); char ch; ch = in.get(); while (ch != '\n') { str += ch; ch = in.get(); } return in; } 八.深浅拷贝问题
1.浅拷贝
浅拷贝：也称位拷贝，编译器只是将对象中的值拷贝过来。如果对象中管理资源，最后就会导致
多个对象共享同一份资源，当一个对象销毁时就会将该资源释放掉，而此时另一些对象不知道该
资源已经被释放，以为还有效，所以当继续对资源进项操作时，就会发生发生了访问违规。
可以采用深拷贝解决浅拷贝问题，即：每个对象都有一份独立的资源，不要和其他对象共享。
2.深拷贝
3.引用计数+写时拷贝
- 当浅拷贝时存在两个问题：析构多次+一个修改影响另一个。
- 引用计数：用来记录资源使用者的个数。在构造时，将资源的计数给成1，每增加一个对象使用该资源，就给计数增加1，当某个对象被销毁时，先给该计数减1，然后再检查是否需要释放资源，如果计数为1，说明该对象时资源的最后一个使用者，将该资源释放；否则就不能释放，因为还有其他对象在使用该资源。
- 写时拷贝：当需要修改其中一个对象的指针时，为了不影响其它对象，使用深拷贝。
九.源代码
1.string.h
//#pragma once #ifndef __STRING_H__ #define __STRING_H__ #include<iostream> #include<assert.h> using namespace std; namespace xzy { 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; } //短小频繁调用的函数，可以直接定义到类里面，默认是inline string(const char* str = "") { _size = strlen(str); _capacity = _size; _str = new char[_capacity + 1]; strcpy(_str, str); } void swap(string& str) { std::swap(_str, str._str); std::swap(_size, str._size); std::swap(_capacity, str._capacity); } string(const string& str) { string tmp(str._str); swap(tmp); } //s2 = s1 /*string& operator=(const string& str) { if (this != &str) { delete[] _str; _str = new char[str._capacity + 1]; strcpy(_str, str._str); _size = str._size; _capacity = str._capacity; } return *this; }*/ string& operator=(string tmp) { swap(tmp); return *this; } string& operator=(const string& str) { if (this != &str) { string tmp(str.c_str()); swap(tmp); } return *this; } ~string() { delete[] _str; _str = nullptr; _size = _capacity = 0; } const char* c_str() const { return _str; } void clear() { _str[0] = '\0'; _size = 0; } size_t size() const { return _size; } size_t capacity() const { return _capacity; } char& operator[](int pos) { assert(pos >= 0 && pos < _size); return _str[pos]; } const char& operator[](int pos) const { assert(pos >= 0 && pos < _size); return _str[pos]; } void resize(size_t n, char c = '\0'); void reserve(size_t n); void push_back(char ch); void append(const char* str); string& operator+=(char ch); string& operator+=(const char* str); void insert(size_t pos, char ch); void insert(size_t pos, const char* str); void erase(size_t pos, size_t len = npos); size_t find(char ch, size_t pos = 0); size_t find(const char* str, size_t pos = 0); string substr(size_t pos = 0, size_t len = npos); private: char* _str = nullptr; size_t _size = 0; size_t _capacity = 0; static const size_t npos; }; bool operator<(const string& s1, const string& s2); bool operator>(const string& s1, const string& s2); bool operator==(const string& s1, const string& s2); bool operator<=(const string& s1, const string& s2); bool operator>=(const string& s1, const string& s2); bool operator!=(const string& s1, const string& s2); ostream& operator<<(ostream& out, const string& str); istream& operator>>(istream& in, string& str); istream& getline(istream& in, string& str); void test_string1(); void test_string2(); void test_string3(); void test_string4(); } #endif 2.string.cpp
#define _CRT_SECURE_NO_WARNINGS 1 #include"string.h" namespace xzy { const size_t string::npos = -1; void string::resize(size_t n, char c) { if (n > _size) { // 如果newSize大于底层空间大小，则需要重新开辟空间 if (n > _capacity) { reserve(n); } memset(_str + _size, c, n - _size); } _size = n; _str[n] = '\0'; } void string::reserve(size_t n) { if (n > _capacity) { char* tmp = new char[n + 1]; strcpy(tmp, _str); delete[] _str; _str = tmp; _capacity = n; } } void string::push_back(char ch) { if (_size == _capacity) { reserve(_capacity == 0 ? 4 : 2 * _capacity); } _str[_size] = ch; ++_size; _str[_size] = '\0'; } void string::append(const char* str) { size_t len = strlen(str); if (_size + len > _capacity) { reserve(_size + len > 2 * _capacity ? _size + len : 2 * _capacity); } strcpy(_str + _size, str); _size += len; } string& string::operator+=(char ch) { push_back(ch); return *this; } string& string::operator+=(const char* str) { append(str); return *this; } void string::insert(size_t pos, char ch) { assert(pos >= 0 && pos <= _size); if (_size == _capacity) { reserve(_capacity == 0 ? 4 : 2 * _capacity); } /*int end = _size; while (end >= (int)pos) { _str[end + 1] = _str[end]; --end; } _str[pos] = ch; ++_size;*/ size_t end = _size + 1; while (end > pos) { _str[end] = _str[end - 1]; --end; } _str[pos] = ch; ++_size; } void string::insert(size_t pos, const char* str) { assert(pos >= 0 && pos <= _size); size_t len = strlen(str); if (_size + len > _capacity) { reserve(_size + len > 2 * _capacity ? _size + len : 2 * _capacity); } //memmove(_str + len, _str, sizeof(char) * len); size_t end = _size + len; while (end > pos + len - 1) { _str[end] = _str[end - len]; --end; } for (size_t i = 0; i < len; i++) { _str[pos + i] = str[i]; } _size += len; } void string::erase(size_t pos, size_t len) { assert(pos >= 0 && pos < _size); if (len >= _size - pos) { _str[pos] = '\0'; _size = pos; } else { //memmove(_str + pos, _str + pos + len, sizeof(char) * (_size - pos - len + 1)); for (size_t i = pos; i <= _size - len; i++) { _str[i] = _str[i + len]; } _size -= len; } } size_t string::find(char ch, size_t pos) { assert(pos >= 0 && pos < _size); for (size_t i = 0; i < _size; i++) { if (_str[i] == ch) { return i; } } return npos; } size_t string::find(const char* str, size_t pos) { assert(pos >= 0 && pos < _size); const char* ptr = strstr(_str + pos, str); if (ptr == nullptr) { return npos; } else { return ptr - _str; } } string string::substr(size_t pos, size_t len) { assert(pos >= 0 && pos < _size); if (len > _size - pos) { len = _size - pos; } string sub; sub.reserve(len); for (size_t i = 0; i < len; i++) { sub += _str[pos + i]; } return sub; } bool operator<(const string& s1, const string& s2) { return strcmp(s1.c_str(), s2.c_str()) < 0; } bool operator>(const string& s1, const string& s2) { return !(s1 <= s2); } bool operator==(const string& s1, const string& s2) { return strcmp(s1.c_str(), s2.c_str()) == 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); } ostream& operator<<(ostream& out, const string& str) { /*string::const_iterator it = str.begin(); while (it != str.end()) { cout << *it; ++it; }*/ for (auto ch : str) { out << ch; } return out; } istream& operator>>(istream& in, string& str) { str.clear(); const int N = 256; char buff[N]; int i = 0; char ch; ch = in.get(); while (ch != ' ' && ch != '\n') { buff[i++] = ch; if (i == N - 1) { buff[i] = '\0'; str += buff; i = 0; } ch = in.get(); } if (i > 0) { buff[i] = '\0'; str += buff; } return in; } istream& getline(istream& in, string& str) { str.clear(); char ch; ch = in.get(); while (ch != '\n') { str += ch; ch = in.get(); } return in; } } 