【C++】string类的模拟实现

一、 string的存储方式

1.vs下string对象的大小和底层结构

注意：下述结构是在32位平台下进行验证，32位平台下指针占4个字节。

char _buff[16];
char* ptr;
size_t size;
size_t capacity;

string总共占28个字节，64位平台下共占40字节。

当字符串长度小于16时，使用内部固定的字符数组来存放
当字符串长度大于等于16时，从堆上开辟空间

这种设计也是有一定道理的，大多数情况下字符串的长度都小于16，那string对象创建
好之后，内部已经有了16个字符数组的固定空间，不需要通过堆创建，效率高。

2.g++下string的结构

g++下，string是通过写时拷贝实现的，内部只有一个指针，该指针指向一块堆空间，用于存储字符串，内部包含如下字段。

struct _Rep_base
{size_type _M_length;size_type _M_capacity;_Atomic_word _M_refcount;
};

指向堆空间的指针，用来存储字符串

g++下，32位环境下，string大小为4字节，64位下为8字节。

关于写时拷贝，就是是在浅拷贝的基础之上增加了引用计数的方式来实现的。

引用计数：用来记录资源使用者的个数。在构造时，将资源的计数给成1，每增加一个对象使用该资源，就给计数增加1，当某个对象被销毁时，先给该计数减1，然后再检查是否需要释放资源，如果计数为1，说明该对象时资源的最后一个使用者，将该资源释放；否则就不能释放，因为还有其他对象在使用该资源。

更多了解写时拷贝。

二、string类的默认构造函数

1.构造函数

分为无参和带参这两种构造函数。无参构造函数默认构造空字符串""，所以我们只需要给一个缺省值即可。

string(const char* s = "")
{_size = strlen(s);//_size和_capacity均不包含'\0'_capacity = _size;_str= new char[_size + 1];memcpy(_str, s, _size + 1);
}

这里设计_size和_capacity均不包含’\0’。_arr的空间多new一个，用于储存’\0’。

再将形参的内存拷贝至_arr中，即可完成构造。

2.拷贝构造

2.1传统写法

string(const string& s)
{_size = s._size;//_size和_capacity均不包含'\0'_capacity = s._capacity;_str= new char[_capacity + 1];memcpy(_str, s._str, _capacity + 1);
}

2.2现在写法

void swap(string& s)
{std::swap(_str, s._str);std::swap(_size, s._size);std::swap(_capacity, s._capacity);
}
string(const string& s):_str(nullptr)//防止交换后tmp._arr为随机值，析构出错,_size(0),_capacity(0){string tmp(s._str);swap(tmp);//this->swap(tmp)}

swap问题

对于上面现代写法swap的问题：标准库有一个swap，string也有一个swap，有什么区别？

第二个swap交换代价比较大，需要三次深拷贝(拷贝+赋值+赋值)，造成空间损耗，所以我们可以提供一个成员函数swap交换string，直接交换，swap中的swap要指定作用域std::，否则需要从局部找，再去全局找，发现参数不匹配

3、赋值运算符重载

传统写法

string& operator=(const string& s)
{if (this != &s){delete[] _str;_str = new char[s._capacity + 1];strcpy(_str, s._str);_size = s._size;_capacity = s._capacity;}return *this;
}

现代写法

通过构造临时变量tmp，完成赋值。这种写法无需担心自己给自己赋值的情况，并且_arr无需初始化为nullptr。

string& operator=( string s)
{swap(s);return *this;
}

4、析构函数

~string()
{delete[] _str;_str = nullptr;_size = _capacity = 0;
}

三、常用接口

//string的size()接口
size_t size()const//右const修饰*this，这样const和非const对象均可调用
{return _size;
}
//string的c_str()接口
const char* c_str()const
{return _str;
}
//string的capacity()接口
size_t capacity()const
{return _capacity;
}
//string的clear()接口
void clear()
{_str[0] = '\0';_size = 0;
}
//string的判空
bool empty()const
{return _size == 0 ? false : true;
}

如果函数形参不发生改变的，无脑加const修饰。

只有指针和引用会有const权限问题。

四、遍历接口的实现

1.对operator[]进行重载

//普通对象：可读可写
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];
}

让字符串进行下标式的访问，需要重载两个operator[]函数，正常对象去调可读可写，const对象调用只读。

2、迭代器和范围for

迭代器有普通迭代器以及const修饰的迭代器，所以我们可以实现两种不同的迭代器，其中，const迭代器可读不可写

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;
}

string的迭代器是字符指针，写完迭代器就可以用迭代器实现访问、修改了。

范围for的底层也是一个迭代器，但是范围for底层只认begin()和end(),如果和自己实现的迭代器接口名称对不上，那么范围for将无法使用。

五、reserve和resize

reserve
在已知开多少空间是调用，避免频繁扩容，具体实现要开辟新的空间，在进行拷贝，对旧空间进行释放

//sring的reserve接口, 如果预开空间小于现有空间，将不会改变容
//在已知开多少空间是调用，避免频繁扩容，具体实现要开辟新的空间，在进行拷贝，对旧空间进行释放
void reserve(size_t n)
{if (n > _capacity){char* tmp = new char[n + 1];strcpy(tmp,_str);delete[] _str;_str = tmp;_capacity = n;}
}

resize需要分情况：

1.元素个数大于容量，需要扩容，多出来的用’\0’（默认情况下）来进行填充

2.元素个数小于原有的，需要删除

void resize(size_t n, char ch = '\0')
{if (n > _capacity){reserve(n);memset(_str+ _size, c, n - _size);_size = n;}else{_str[n] = '\0';_size = n;}
}

六、插入删除查找相关接口

1、push_back、append、+=

string& push_back(const char c)
{//判断容量if (_size == _capacity){size_t newCapacity = _capacity == 0 ? 4 : _capacity * 2;//防止出现空串的情况reserve(newCapacity);}_str[_size++] = c;return *this;
}
string& append(const char* s)
{//判断容量size_t len = strlen(s);if (_size + len > _capacity){reserve(_size + len);}strcpy(_str+ _size, s);_size += len;return *this;
}
string& operator+=(const char c)
{push_back(c);return *this;
}
string& operator+=(const char* s)
{append(s);return *this;
}

写push_back要考虑到原对象为空串的情况（即_capacity为0）。

+=可以复用push_back和append。

2、insert和erase

string& insert(size_t pos, char c)
{assert(pos < _size);//判断容量if (_size == _capacity){reserve(_capacity + 1);}//挪动数据for (size_t i = _size; i > pos; --i){_str[i] = _str[i - 1];}_str[pos] = c;++_size;return *this;
}
string& insert(size_t pos, const char* s)
{size_t len = strlen(s);//判断容量if (len + _size > _capacity){reserve(len + _size);}//挪动数据for (size_t i = _size + len; i > pos + len - 1; --i){_str[i] = _str[i - len];}memcpy(_str+ pos, s, len);_size += len;return *this;
}

说到erase，自然要跟npos联系起来，npos是string类的静态成员变量，静态成员变量要在类外定义的：

size_t string::npos = -1

普通成员对象可以给缺省值，在构造函数初始化列表完成初始化，但是静态成员变量不会在初始化列表阶段进行初始化，静态成员变量不属于某个具体的对象，属于整个类，所以需要在类外初始化。

但是有一个特例，const静态成员变量可以在声明时定义(只针对整型)：

private:char* _str;size_t _size;size_t _capacity;const static size_t npos = -1;

erase实现：

1.如果len太长，直接把pos之后的删除即可

2.只需要删除部分，挪动数据

string& erase(size_t pos,size_t len = npos)
{assert(pos < _size);if (len == npos||pos+len>=_size){_str[pos] = '\0';_size = pos;}//挪动数据else{strcpy(_str + pos, _str + pos + len);_size -= len;}return *this;
}

总结：

1.insert接口在挪动数据时，从最后一个元素的后一个（后len个）位置开始覆盖，可以保证不出现size_t 类型越界的情况。2erase接口，需要分类讨论字符串是否删到底。注意，这个pos是const static成员，C++语法中，只有指针和整型的const static成员是可以在类中进行初始化的。

3、find

从pos处开始查找字符或者字符串，找到返回下标值，没找到则返回npos

对于字符串的查找可以调用strstr

size_t string::find(char c, size_t pos) const
{for (int i = pos; i < size(); ++i){if (_str[i] == c){return i;}}return npos;
}size_t string::find(const char* s, size_t pos) const
{assert(pos < _size);const char* ptr = strstr(_str + pos, s);if (ptr == nullptr){return npos;}else{return ptr - _str;}
}

七、比较运算符

bool string::operator<(const string& s)
{return strcmp(this->c_str(), s.c_str()) < 0;
}bool string::operator<=(const string& s)
{return *this < s || *this == s;
}bool string::operator>(const string& s)
{return !(*this <= s);
}bool string::operator>=(const string& s)
{return *this > s || *this == s;
}bool string::operator==(const string& s)
{return strcmp(this->c_str(), s.c_str()) == 0;
}bool string::operator!=(const string& s)
{return !(*this == s);
}

比较运算符的重载可以利用函数复用，提高代码效率。

八、流插入和流提取

对于 << ：

ostream& operator<<(ostream& out, const string& s){for (size_t i = 0; i < s.size(); ++i){out << s[i];}return out;}

对于<<和c_str()的区别：<<按照size进行打印，跟\0没有关系，而c_str()遇到\0结束：

对于 >> ：

inline istream& operator>>(istream& in, string& s)
{s.clear();//用之前先清空s//in >> c;//流提取不会识别空格和换行char c = in.get();char buff[128] = { '\0' };//防止频繁扩容size_t i = 0;while (c != ' ' && c != '\n'){if (i == 127){s += buff;i = 0;}buff[i++] = c;c = in.get();}if (i > 0){buff[i] = '\0';s += buff;}return in;
}

因为string提供了访问私有的接口，所以流插入和流提取可以不用重载成string类的友元函数。

对于流提取，如果频繁的尾插，会造成频繁扩容。而且C++的扩容和C语言的扩容不一样，C++使用new不能原地扩容，只能异地扩容，异地扩容就会导致新空间的开辟、数据的拷贝、旧空间释放。为了防止频繁扩容，我们可以创建一个可以存储128字节的数组，在这个数组中操作，这个数组满了就尾插至对象s中。

为什么不能用getline，而是要一个字符一个字符尾插呢？因为流提取遇到空格和’\n’会结束提取，剩余数据暂存缓冲区，如果是getline的话，遇到空格是不会停止读取的。

九、总体代码

#pragma once#include <iostream>
using namespace std;
#include <assert.h>namespace fx
{class string{friend ostream& operator<<(ostream& _cout, const bit::string& s);friend istream& operator>>(istream& _cin, bit::string& s);public:typedef char* iterator;typedef const char* const_iterator;string(const char* str = ""){_size = strlen(str);// _capacity不包含\0_capacity = _size;_str = new char[_capacity + 1];strcpy(_str, str);}string(const string& s){_str = new char[s._capacity + 1];strcpy(_str, s._str);_size = s._size;_capacity = s._capacity;}string(const string& s){string tmp(s._str);swap(tmp);}string& operator=(const string& s){if (this != &s){delete[] _str;_str = new char[s._capacity + 1];strcpy(_str, s._str);_size = s._size;_capacity = s._capacity;}return *this;}string& operator=( string s){swap(s);return *this;}~string(){delete[] _str;_str = nullptr;_size = _capacity = 0;}//// iteratoriterator begin() const{return _str;}iterator end() const{return _str + _size;}/// modifyvoid push_back(char c);string& operator+=(char c);void append(const char* str);string& operator+=(const char* str);void clear(){_str[0] = '\0';_size = 0;}void swap(string& s){std::swap(_str, s._str);std::swap(_size, s._size);std::swap(_capacity, s._capacity);}const char* c_str()const{return _str;}/// capacitysize_t size()const{return _size;}size_t capacity()const{return _capacity;}bool empty()const{return _size == 0;}void resize(size_t n, char c = '\0');void reserve(size_t n);/// accesschar& operator[](size_t index){assert(index < _size);return _str[index];}const char& operator[](size_t index)const{assert(index < _size);return _str[index];}///relational operatorsbool operator<(const string& s);bool operator<=(const string& s);bool operator>(const string& s);bool operator>=(const string& s);bool operator==(const string& s);bool operator!=(const string& s);// 返回c在string中第一次出现的位置size_t find(char c, size_t pos = 0) const;// 返回子串s在string中第一次出现的位置size_t find(const char* s, size_t pos = 0) const;// 在pos位置上插入字符c/字符串str，并返回该字符的位置void insert(size_t pos, char c);void insert(size_t pos, const char* str);// 删除pos位置上的元素，并返回该元素的下一个位置void erase(size_t pos, size_t len);string substr(size_t pos = 0, size_t len = npos);private:char* _str;size_t _capacity;size_t _size;static const size_t npos;};ostream& operator<<(ostream& out, const string& s);istream& operator>>(istream& in, string& s);}