【C++杂货铺】探索string的底层实现

Love The Way You Lie 2023-10-15 09:10 58阅读 0赞

![在这里插入图片描述][56139bb1214c4db1b27627316f0d5883.gif_pic_center]

#### 文章目录 ####

*  一、成员变量
 *  二、成员函数
 *   *  2.1 默认构造函数
     *  2.2 拷贝构造函数
     *  2.3 operator=
     *  2.4 c\_str()
     *  2.5 size()
     *  2.6 operator\[ \]
     *  2.7 iterator
     *  2.8 reserve
     *  2.9 resize
     *  2.10 push\_back
     *  2.11 append
     *  2.12 operator+=
     *  2.13 insert
     *  2.14 erase
     *  2.15 find
     *  2.16 substr
     *  2.17 operator<<
     *  2.18 operator>>
     *  2.19 operator<
     *  2.20 operator==
     *  2.21 <=、>、>=、!=
 *  三、结语

## 一、成员变量 ##

private:
    		char* _str;//用来存储字符串
    		size_t _size;//用来表示有效字符数
    		size_t _capacity;//用来表示可以存储有效字符的容量
    public:
    		static size_t npos;//要在类外面定义

`string`本质上是一个动态顺序表，它可以根据需要动态的扩容，所以字符串一定是通过在堆上动态申请空间进行存储的，因此`_str`指向存储字符串的空间，`_size`用来表示有效字符数，`_capacity`用来表示可以存储有效字符的容量数。

## 二、成员函数 ##

### 2.1 默认构造函数 ###

string(const char* str = "")
    	:_str(new char[strlen(str) + 1])//strlen计算的是有效字符的个数，而我们存储的时候要在字符串的最后存一个'\0'
    	,_size(strlen(str))
    	,_capacity(_size)
    {
        
    	//memcpy(_str, str, _size);
    	//strcpy(_str, str);//常量字符串就是遇到'\0'终止，所以直接用strcpy也可以
    	memcpy(_str, str, strlen(str) + 1);
    }

**注意**：默认构造函数需要注意的地方是：首先形参必须加上 `const` 修饰，这样才能用 C 语言中的常量字符串来初始化 `string` 类对象，形参的的缺省值直接给一个空字符串即可，注意空字符串是用`""`表示，该字符串只有结尾默认的一个 `'\0'`，`"\0"`并不表示空字符串，它表示该字符串有一个字符 `'\0'` ，它的结尾还有一个默认的 `'\0'`，因此有两个 `'\0'`，`nullptr`也不能表示空字符串，他表示的是空指针。其次需要注意初始化列表的顺序，应该严格按照成员变量的出现顺序。`strlen` 计算的是字符串中有效字符的个数，不算 `'\0'`，而常量字符串的结尾默认有一个 `'\0'`，因此在用 `new`开辟空间的时候需要多开一个用来存储结尾的 `\0`。`_capacity`表示的是可以存储有效字符的容量，而字符串结尾默认的 `'\0'` 并不算作有效字符，因此最初的 `_capacity` 就是形参 `str` 的长度。最后记得在构造函数体内将形参 `str` 的字符拷贝到动态申请的空间中。

**小Tips**：涉及到字符串拷贝的地方，建议使用 `memcpy`，`strcpy` 默认遇到 `\0` 就终止，但是不排除 `\0` 就是 `string` 对象中的有效字符。但是 `strcpy` 会默认在结尾加 `\0`，而 `memcpy` 不会，因此使用 `memcpy` 的时候需要注意拷贝得到的字符串结尾是否有 `\0`。

### 2.2 拷贝构造函数 ###

//传统写法
    string(const string& str)
    	:_str(new char[str._size + 1])
    	,_size(str._size)
    	,_capacity(_size)
    {
        
    	memcpy(_str, str._str, str._size + 1);
    }
    
    //现代写法
    string(const string& str)
    	:_str(nullptr)
    	, _size(0)
    	,_capacity(0)
    {
        
    	string tmp(str._str);
    	swap(tmp);
    }

**注意**：现代写法不需要我们亲自去申请空间初始化，而是调用构造函数去帮我们完成。最后再将初始化好的 `tmp` 交换过来，这里一定要通过初始化列表对 `*this` 进行初始化，不然交换给 `tmp` 后，里面都是随机值，最终出了作用域 `tmp` 去销毁的时候就会出问题。现代写法的坑点在于，如果 `string` 对象中有 `'\0'`，只会把 `'\0'` 前面的字符拷贝过去。

### 2.3 operator= ###

//传统写法
    string& operator=(const string& s)
    {
        
    	if (this != &s)
    	{
        
    		char* tmp = new char[s._capacity + 1];
    		memcpy(tmp, s._str, s._size + 1);
    		delete[] _str;
    		_str = tmp;
    		_size = s._size;
    		_capacity = s._capacity;
    	}
    
    	return *this;
    }

**注意**：这种写法需要我们自己去开辟空间新空间 `tmp`，自己去释放旧空间 `_str`，下面将对这种写法加以改进，通过已有的接口来帮我们完成这些工作。

//现代写法
    string& operator=(const string& s)
    {
        
    	if (this != &s)
    	{
        
    		string tmp(s);//通过调用拷贝构造来创建空间
    		//tmp是局部变量，出了作用于会自动销毁，把待销毁的资源通过交换，给tmp
    		std::swap(_str, tmp._str);
    		std::swap(_size, tmp._size);
    		std::swap(_capacity, tmp._capacity);
    		//std::swap(*this, tmp);//错误的写法
    	}
    
    	return *this;
    }
    
    //现代写法优化
    void swap(string& s)
    {
        
    	std::swap(_str, s._str);
    	std::swap(_size, s._size);
    	std::swap(_capacity, s._capacity);
    }
    string& operator=(string s)
    {
        
    	swap(s);
    	return *this;
    }
    //优化版本，连拷贝构造函数也不需要我们自己去调用啦，直接通过形参去调用

**注意**：这种写法通过调用拷贝构造来帮我们申请空间，在利用局部对象出了作用就会被销毁的特点，将需要释放的资源通过 `swap` 交换给这个局部变量，让这个局部变量帮我们销毁。这里不能直接用 `swap` 交换两个 `string` 类对象，会导致栈溢出，因为 `swap` 函数中会调用赋值运算符重载，而赋值运算符重载又要调用 `swap` 成了互相套娃。我们可以不用库里面的 `swap`，自己实现一个 `Swap` 用来交换两个 `string` 对象。

### 2.4 c\_str() ###

char* c_str() const
    {
        
    	return _str;
    }

**注意**：记得加上 `const`，这样普通的 `string` 类对象可以调用，`const` 类型的 `string` 类对象也可以调用，普通对象来调用就是权限的缩小。

### 2.5 size() ###

size_t size() const
    {
        
    	return _size;
    }

### 2.6 operator\[ \] ###

//读写版本
    char& operator[](size_t pos)
    {
        
    	assert(pos < _size);
    	return _str[pos];
    }

//只读版本
    const char& operator[](size_t pos) const
    {
        
    	assert(pos < _size);
    	return _str[pos];
    }

**注意**：这两个运算符重载函数构成函数重载，对象在调用的时候会走最匹配的，普通对象会调用读写版本，`const` 对象会调用只读版本。

### 2.7 iterator ###

`iterator` 是 `string` 类的内嵌类型，也可以说是在 `string` 类里面定义的类型，在一个类里面定义类型有两种方法，`typedef` 和 内部类。`string` 类的 `iterator` 是通过前者来实现的，即对字符指针 `char*` 通过 `typedef` 得到的。

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

### 2.8 reserve ###

void reserve(size_t n = 0)
    {
        
    	if (n > _capacity)
    	{
        
    		char* tmp = new char[n + 1];
    		//strcpy(tmp, _str);
    		memcpy(tmp, _str, _size + 1);
    		_capacity = n;
    		delete[] _str;
    		_str = tmp;
    	}
    }

### 2.9 resize ###

void resize(size_t n, char ch = '\0')
    {
        
    	if (n < _size)
    	{
        
    		erase(n);
    	}
    	else
    	{
        
    		reserve(n);
    		for (size_t i = _size; i < n; i++)
    		{
        
    			_str[i] = ch;
    		}
    
    		_size = n;
    		_str[_size] = '\0';
    	}
    }

**注意**：`reserve` 函数不会进行缩容，因此在扩容前要先进程判断，只有当形参 `n` 大于当前容量的时候才扩容。

### 2.10 push\_back ###

void push_back(char ch)
    {
        
    	//先检查容量，进行扩容
    	if (_size == _capacity)
    	{
        
    		reserve(_capacity == 0 ? 4 : _capacity * 2);
    	}
    	_str[_size++] = ch;
    	_str[_size] = '\0';
    }

**注意**：需要注意对空串的追加，空串的 `_capacity = 0` ，因此在调用`reserve` 函数进行扩容的时候，不能简单传递 `_capacity*2`，要先进行判断，当 `capacity == 0` 的时候，给它一个初始大小。

### 2.11 append ###

void append(const char* str)
    {
        
    	if (_size + strlen(str) > _capacity)
    	{
        
    		reserve(_size + strlen(str));
    	}
    	//strcpy(_str + _size, str);//常量字符串就是遇到'\0'终止，所以直接用strcpy也可以
    	memcpy(_str + _size, str, strlen(str) + 1);
    	_size += strlen(str);
    }

### 2.12 operator+= ###

//追加一个字符串
    string& operator+=(const char* str)
    {
        
    	append(str);
    	return *this;
    }
    //追加一个字符
    string& operator+=(char ch)
    {
        
    	push_back(ch);
    	return *this;
    }

**注意**：+= 需要有返回值。

### 2.13 insert ###

//插入n个字符
    void insert(size_t pos, size_t n, char ch)
    {
        
    	assert(pos <= _size);
    	//检查容量，扩容	
    	if (_size + n > _capacity)
    	{
        
    		reserve(_size + n);
    	}
    	//挪动数据
    	size_t end = _size;
    	while (end != npos && end >= pos)
    	{
        
    		_str[end + n] = _str[end--];
    	}
    
    	//插入数据
    	size_t i = pos;
    	while (i < pos + n)
    	{
        
    		_str[i++] = ch;
    	}
    
    	_size += n;
    }

**注意**：这里需要注意挪动数据时的判断条件，因为 `end` 和 `pos` 都是 `sizt_t` 类型，所以当 `pos = 0` 的时候 `end >= pos` 永远成立，此时就会有问题，只把 `end` 改成 `int` 也解决不了问题，在比较的时候会发生整形提升，最终还是永远成立。一种解决方法就是想上面一样，加一个 `size_t` 类型的成员变量 `npos`，把它初始化成 -1，即整形最大值，判断 `end` 是否等于 `npos`，等于说明 `end` 已经减到 -1 了，就应该停止挪动。解决上面的问题还有一种方法，上面的问题出现在 `pos = 0` 时，`end` 会减到 -1，最终变成正的无穷大，导致判断条件永远成立，那我们可以将 `end` 初始化成 `_size + n`，把 `end - n` 上的字符挪到 `end` 位置上，此时计算 `pos = 0`，也不会出现 `end` 减到 -1 的情况，代码如下：

//插入n个字符
    void insert(size_t pos, size_t n, char ch)
    {
        
    	assert(pos <= _size);
    	//检查容量，扩容	
    	if (_size + n > _capacity)
    	{
        
    		reserve(_size + n);
    	}
    	//挪动数据
    	size_t end = _size + n;
    	while (end >= pos + n)
    	{
        
    		_str[end] = _str[end - n];
    		--end;
    	}
    
    	//插入数据
    	size_t i = pos;
    	while (i < pos + n)
    	{
        
    		_str[i++] = ch;
    	}
    
    	_size += n;
    }

**小Tips**：`npos`作为一个静态成员变量，必须在类外面进行初始化（定义），并且不能在声明时给默认值，默认值是给初始化列表用的，而静态成员变量属于该类所有对象共有，并不会走初始化列表。但是！但是！！，整形的静态成员变量变量在加上 `const` 修饰后就可以在声明的地方给默认值，注意！仅限整形。其他类型的静态成员变量在加 `const` 修饰后仍需要在类外面定义。

const static size_t npos = -1;//可以
    //const static double db = 1.1//不可以

//插入一个字符串
    void insert(size_t pos, const char* str)
    {
        
    	assert(pos <= _size);
    	size_t len = strlen(str);
    	if (_size + len > _capacity)
    	{
        
    		reserve(_size + len);
    	}
    
    	//挪动
    	size_t end = _size + len;
    	while (end >= pos + len)
    	{
        
    		_str[end] = _str[end - len];
    		--end;
    	}
    
    	//插入
    	for (size_t i = 0; i < len; i++)
    	{
        
    		_str[pos + i] = str[i];
    	}
    
    	_size += len;
    }

### 2.14 erase ###

void erase(size_t pos, size_t len = npos)
    {
        
    	assert(pos < _size);
    	if (len == npos || pos + len >= _size)//
    	{
        
    		_str[pos] = '\0';
    		_size = pos;
    	}
    	else
    	{
        
    		//挪动覆盖
    		size_t end = pos + len;
    		while (end <= _size)
    		{
        
    			_str[end - len] = _str[end++];
    		}
    		_size -= len;
    	}
    }

**注意**：`pos` 将整个数组划分成两部分，\[0,pos-1\]是一定不需要删除的区域，\[pos,\_size-1\]是待删除区域，一定不需要删除的区域有 `pos` 个元素，我们希望删除 `len` 个字符，当一定不会删除的字符数加我们希望删除的字符数如果大于或等于全部的有效字符数，那就说明待删除区域的所有字符都要删除，即当 `pos + len >= _size` 的时候就是要从 `pos` 位置开始删除后面的所有字符，删完后加的把 `pos` 位置的字符置为 `\0`。

### 2.15 find ###

//查找一个字符
    size_t find(char ch, size_t pos = 0)
    {
        
    	assert(pos < _size);
    	for (size_t i = 0; i < _size; i++)
    	{
        
    		if (_str[i] == ch)
    		{
        
    			return i;
    		}
    	}
    
    	return npos;
    }
    //查找一个字符串
    size_t find(const char* str, size_t pos = 0)
    {
        
    	assert(pos < _size);
    	const char* ptr = strstr(_str, str);
    	if (ptr == NULL)
    	{
        
    		return npos;
    	}
    	else
    	{
        
    		return ptr - _str;
    	}
    }

### 2.16 substr ###

string substr(size_t pos = 0, size_t len = npos)
    {
        
    	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 = 0; i < n; i++)
    	{
        
    		tmp += _str[i + pos];
    	}
    
    	return tmp;
    }

### 2.17 operator<< ###

ostream& operator<<(ostream& out, const wcy::string& str)
    {
        
    	for (auto e : str)
    	{
        
    		out << e;
    	}
    	return out;
    }

**注意**：因为涉及到竞争左操作数的原因，流插入和流提取运算符重载要写在类外面。其次，不能直接打印 `str._str` 或者通过 `str.c_str()` 来打印，因为 `string` 对象中可能会有 `\0` 作为有效字符存在，前面两种打印方法，遇到 `\0` 就停止了，无法完整将一个 `string` 对象打印出来，正确的做法是逐个打印。

**小Tips**：无论是形参还是返回值，只要涉及到 `ostream` 或 `istream` 都必须要用引用，因为这俩类不允许拷贝或者赋值的。

### 2.18 operator>> ###

istream& operator>>(istream& in, wcy::string& str)
    {
        
    	if (str._size != 0)
    	{
        
    		str.erase(0);
    	}
    	//in >> str._str;//这样写是错的，空间都没有
    	char ch;
    	ch = in.get();
    	while (ch == ' ' || ch == '\n')//清除缓冲区
    	{
        
    		ch = in.get();
    	}
    	while (ch != ' ' && ch != '\n')
    	{
        
    		str += ch;
    		ch = in.get();
    	}
    	return in;
    }

**注意**：空格符 `' '` 和换行符 `\n` 作为输入时分割多个 `string` 对象的标志，是不能直接用 `istream` 对象来读取的，即 `cin >> ch` 是读不到空格符和换行符。需要借助 `get()` 成员函数才能读取到空格符和换行符。其次库中对 `string` 进行二次流提取的时候会进行覆盖，所以我们在插入前也要先进行判断。上面这种写法，在输入的字符串很长的情况下会多次调用 `reserve` 进行扩容，为了解决这个问题，我们可以对其进行优化。

//优化版本
    istream& operator>>(istream& in, wcy::string& str)
    {
        
    	/*if (str._size != 0)
    	{
    		str.erase(0);
    	}*/
    	//in >> str._str;//这样写是错的，空间都没有
    	str.clear();
    	char buff[128] = {
         '\0' };
    	char ch;
    	ch = in.get();
    	while (ch == ' ' || ch == '\n')
    	{
        
    		ch = in.get();
    	}
    	size_t i = 0;
    	while (ch != ' ' && ch != '\n')
    	{
        
    		buff[i++] = ch;
    		if (i == 127)
    		{
        
    			str += buff;
    			i = 0;
    		}
    		ch = in.get();
    	}
    
    	if (i != 0)
    	{
        
    		buff[i] = '\0';
    		str += buff;
    	}
    	return in;
    }

**注意**：这里的做法是，先开辟一个数组，将输入的字符存储到数组中，然后从数组中拷贝到 `string` 对象当中。

### 2.19 operator< ###

bool operator<(const string& s) const
    {
        
    	size_t i1 = 0;
    	size_t i2 = 0;
    	while (i1 < _size && i2 < s._size)
    	{
        
    		if (_str[i1] < s[i2])
    		{
        
    			return true;
    		}
    		else if (_str[i1] > s[i2])
    		{
        
    			return false;
    		}
    		else
    		{
        
    			i1++;
    			i2++;
    		}
    	}
    
    	if (i1 == _size && i2 == s._size)
    	{
        
    		return false;
    	}
    	else if (i1 < _size)
    	{
        
    		return false;
    	}
    	else
    	{
        
    		return true;
    	}
    }

**注意**：`string` 类对象是按照 ASCII 进行比较的。其次，这里不能直接复用 `strcmp` 或者 `memcmp`，前者遇到 `'\0'` 就会终止，后者只能比较长度相等的部分。所以我们可以自己来写比较逻辑，也可以复用 `memcmp` 然后进行补充。

//复用memcpy
    bool operator<(const string& s) const
    {
        
    	int ret = memcmp(_str, s._str, _size < s._size ? _size : s._size);
    
    	return ret == 0 ? _size < s._size : ret < 0;
    }

### 2.20 operator== ###

bool operator==(const string& s) const
    {
        
    	return _size == s._size
    		&& memcmp(_str, s._str, _size < s._size ? _size : s._size) == 0;
    }

有了 < 和 ==，剩下的直接复用即可。

### 2.21 <=、>、>=、!= ###

bool operator<=(const string& s) const
    {
        
    	return *this < s || *this == s;
    }
    
    bool operator>(const string& s) const
    {
        
    	return !(*this <= s);
    }
    
    bool operator>=(const string& s) const
    {
        
    	return !(*this < s);
    }
    
    bool operator!=(const string& s) const
    {
        
    	return !(*this == s);
    }

## 三、结语 ##

今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下，[春人的主页][Link 1]还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是春人前进的动力！

![在这里插入图片描述][edc78985d03043828f98dcd5a8d2983e.gif_pic_center]

[56139bb1214c4db1b27627316f0d5883.gif_pic_center]: https://img-blog.csdnimg.cn/56139bb1214c4db1b27627316f0d5883.gif#pic_center
[Link 1]: https://blog.csdn.net/weixin_63115236?spm=1000.2115.3001.5343
[edc78985d03043828f98dcd5a8d2983e.gif_pic_center]: https://img-blog.csdnimg.cn/edc78985d03043828f98dcd5a8d2983e.gif#pic_center