【C++之STL】摸清 string 的模拟实现（上）

1. 为什么要模拟实现？

可能有人觉得STL既然已经提供了功能如此丰富的string类，就没有必要再学习它的底层，但这显然是错误的看法。
原因有2：

1. 找工作时面试官很喜欢让求职者回答STL一些容器的模拟实现的思路。
2. 学习底层有助于巩固知识，还能帮助我们更好地理解这个容器，使用时能更加得心应手。

2. 基本框架搭建

首先，我们要实现一个string类，就不可避免地会和库中string冲突，这时就需要用到命名空间，将自己实现的这个类放进一个和std不同的命名空间中就能避免冲突。

string是对字符数组的封装，尽管一些编译器在具体实现时会加上一些其它的东西来进行优化，但我们先不考虑这些。这里我们实现的string类的成员变量就只有一个字符指针 char* _str;。

string的实现可以模仿数据结构初阶中的顺序表，还要有_size和_capacity两个成员变量。

另外，虽然字符串的长度可以用strlen这个库函数获取，但这个函数的时间复杂度是O(N)，会导致代码效率降低，不如创建一个变量存储起来。

这样我们就可以搭建出最基本的框架：

// 我们实现的 string 不是模板类，可以声明与定义分离。
namespace test
{
	class string
	{
	private:
		char* _str;
        size_t _capacity;
		size_t _size;
	};
}

当然这个基础和实际上的库中的string类是有差别的。

这是cplusplus上给出的string的定义：

typedef basic_string<char> string;

可以看到库中的 string 是对一个类模版basic_string指定类型char得到的，实际上这个类可以得到四个类：

也就是其他不同的字符类型，不是很常用，而且使用方式和string完全相同，就不介绍了。

除此之外，如果你使用的是VS2022编译器，在监视窗口也可以发现VS2022中除了这个字符指针之外还添加了一个16个字节大小Buf数组：

当这个Buf数组存满之后，才会将数据转移到_Ptr中，然后进行可能的扩容操作，这是VS编译器独特（应该）的优化方式。

当然gcc下string的定义也不是我们像我们写的这样简单，它用到了写时拷贝，这一点在本文最后面会补充。

3. 构造函数

注：只会实现最常用的构造函数，其它的构造函数原理也差不多。

3. 1 默认构造/from c_str

在类和对象（中）中说过，我们应该显示地实现一个默认构造，最好是全缺省的，所以我们就实现一个全缺省的默认构造。

// string.h
string(const char* str="");

// string.c
// 声明与实现分离时，实现中不能写出缺省值
string::string(const char* str)
    :_capacity(strlen(str))
{
    // 初始化列表是按照类模版中变量声明的顺序走的，所以需要注意顺序。不如把其他放在函数体内初始化，防止出错
    // 当然，把 _size 和 _str 都在初始化列表初始化也是可以的，但是一定要注意顺序
    _size = _capacity;	
    _str = new char[_capacity + 1];
    // 这里一定要注意要把 str 的内容拷贝到 _str 中，千万不能 _str = str 完事
    strcpy(_str, str);
}

构造string对象的时候，不要让_str为nullptr，不然可能会导致报错，不如直接初始化为""来得方便。

3. 2 拷贝构造

这样写可以吗？

//string::string(const string s);	// 会导致循环构造
string::string(string& s)
    :_size(s.size)
    , _capacity(s._capacity)
{
    _str = s._str;
}

这里就不得不提关于深浅拷贝的问题了。

3. 2. 1 深浅拷贝

1. 浅拷贝：也称位拷贝，编译器只是将对象中的值（包括指针）直接拷贝过来。如果对象中有动态资源就会导致多个对象同时操作一个空间的内容。并且当一个对象销毁时就会将该资源释放掉，而此时另一些对象不知道该资源已经被释放，以为还有效，就会继续对资源进行操作，发生野指针访问。

2. 如果一个类中涉及到资源的管理，其拷贝构造函数、赋值运算符重载以及析构函数必须要显式给出。并且一般情况都要用深拷贝方式实现。

像上面那样直接_str = s._str就是典型的浅拷贝。

如果要实现string的深拷贝，可以使用strcpy函数，将s._str中的数据挨个复制到_str中，这样_str就和s._str完全无关了。

因此拷贝构造要这么写：

string::string(const string& s)
    :_capacity(s._capacity)
    ,_size(s._size)
{
    // 记得申请空间
    _str = new char[_capacity + 1];
    strcpy(_str, s._str);
}

3. 3 fill

string::string(size_t n, char c)
    :_capacity(0)
    , _size(0)
{
    for (int i = 0; i < n; i++)
        push_back(c);
}

这里用到了push_back()，可以节省不必要的代码，体现了复用的思想。

3. 4 迭代器区间构造

在此之前，我们先讲一下怎么实现迭代器：

typedef char* iterator;	//切记迭代器必须是这个名字!!!

现代编译器中迭代器的实现远比这个复杂，但功能上并没有差异，并且早期的STL版本中随机迭代器（string的迭代器就是随机迭代器，迭代器的其他种类以后介绍）就是这样的实现。

既然迭代器就是一个指针，那么使用它进行构造也就算不上难事了。

// 注意，迭代器的类型各不相同，要使用模板（尽管string的构造一般也只会使用string的迭代器）
template<class InputIterator>
string(InputIterator first, InputIterator end)
    :_str(nullptr)
    , _size(0)
    ,_capacity(0)	// 对成员变量进行初始化
{
    reserve(end - first);	// 先预留足够的空间，减少损耗
    while (first != end)
    {
        push_back(*first);	// 直接使用push_back()，减少重复的代码量，当然也可以不使用push_back()而是直接插入
        first++;
    }
}

这里要特别说明一下为什么用while (first != end)而不是while (first < end)，因为迭代器不只有这一种类型，比如说链表也有迭代器，尽管说通过操作符重载也能实现和string的迭代器差不多的功能，但是链表的每个节点都是动态开辟的，而动态开辟的地址的大小是不确定的，所以first不一定小于end，为了兼容所有类型的迭代器，在需要对迭代器进行遍历操作时，我们统一都使用first != end作为循环的结束条件。

4. 容量操作

4. 1 size()和capacity()和empty()

前两个直接返回_size()和_capacity就可以了。

size_t string::size()const
{
    return _size;
}

size_t string::capacity()const
{
    return _capacity;
}

而empty()就是返回_size是否为0.

bool string::empty()const
{
    return _size == 0;
}

别忘了在函数名后面加上const来兼容不可修改的实例化对象。

4. 2 clear()

将有效字符全部删除，大小置为0。

其实直接修改_size的大小，并在第一位加上'\0'就可以了。

void string::clear()
{
    _size = 0;
    _str[0] = '\0';
}

4. 3 resize()

void resize(size_t n, char c = '\0');

resize()需要处理两种情况：

1. 新的大小>原来的大小：用字符c填补，还要判断容量是否足够。
2. 新的大小<=原来的大小：缩减字符串的大小到新的大小。

void string::resize(size_t n, char c)
{
    // 第一种情况
    if (n > _size)
    {
        // 判断是否需要扩容
        if (n + _size > _capacity)
        {
            // 扩容，因为我们的构造函数不会吧_capacity置为0，而是2或其他值，所以不用判空
            size_t newcapacity = n + _size > 2 * _capacity ? n + _size : 2 * _capacity;
            reserve(newcapacity);
            _capacity = newcapacity;
        }
		// 插入字符 c，使 _size == n
        for (size_t i = _size; i < n + _size; i++)
            _str[i] = c;
        // 添加'\0'
        _str[n + _size] = '\0';
        // 更新数组大小
        _size += n;
    }
    else
    {
       	// 这个和clear()很像，只是不是把大小置为0而是n
        _str[n] = '\0';
        _size = n;
    }
}

但是第一种情况的书写未免太过复杂，有没有办法简化？

后面我们写push_back()的时候就会发现，其实第一种情况和push_back()的代码是高度重合的，我们可以直接对push_back()进行复用，这是string现代写法，本文会有一章来介绍所谓的现代写法。

4. 4 reserve()

void reserve (size_t n = 0);

用于预留空间。

需要注意的是，reserve()在扩容时一般不是n给多少就扩容到多少，我们先来看这个代码：

#include<string>
#include<iostream>
using namespace std;
int main()
{
	string s("");
	int last = 0;
	int i = 0;
	while (last < 1000)
	{
		s.reserve(i++);
		if (s.capacity() != last)
		{
			last = s.capacity();
			cout << last << endl;
		}
	}
	return 0;
}

这个程序可以输出当string对象的容量变化时的新容量。

VS2022上的输出结果为：

devc++（5.11，gcc4.9.2）的输出结果为：

可以发现reserve()在VS2022上是以1.5倍的大小进行扩容（第一扩容是二倍，因为第二章中提到的_Buf数组），只有当新的容量大于现在的容量的1.5倍，才会进行扩容操作。

而devc++是2倍扩容，但是会在一些情况下缩小容量。

为了简化，我们采用简化版的VS2022的实现。

1. n<=_capacity

这个函数不会做任何举动。

2. n>_capacity

如果 n <= 1.5 * _capacity，就直接扩容至1.5倍，如果n <= 1.5 * _capacity，就扩容至n。

void string::reserve(size_t n)
{
    // 如果 n < _capacity 就不做任何操作
    if (n > _capacity)
    {
        int newcapacity = 0;
        // 如果 n <= 1.5 * _capacity，就直接扩容至1.5倍，如果 n <= 1.5 * _capacity ，就扩容至 n
        if (n < _capacity * 1.5)
            newcapacity = _capacity * 1.5;
        else
            newcapacity = n;
		// 创建新的字符指针，注意要动态开辟
        char* newstr = new char[newcapacity + 1]; // +1是为了给'\0'留位置
        // 拷贝数据
        strcpy(newstr, _str);
        // 释放原空间
        delete[] _str;
        // 修改成员变量
        _str = newstr;
        _capacity = newcapacity;
    }
}

剩余内容请看：（本文发布后3天内更新）
string模拟实现下

谢谢你的阅读，喜欢的话来个点赞收藏评论关注吧！
我会持续更新更多优质文章