【C++学习】string的模拟实现

🐱作者：一只大喵咪1201
🐱专栏：《C++学习》
🔥格言：你只管努力，剩下的交给时间！

上篇文章中本喵介绍了C++标准库中string类的使用，下面本喵来模拟实现一下string类。库中的string类是将模板实例化并且typedef后得到的类，所以我们直接实现类，而忽略模板。

🍚默认成员函数

首先就是来实现类和对象中的四大默认成员函数，构造函数，拷贝构造函数，析构函数，赋值运算符重载函数。

🍛构造函数

		//使用C字符串构造
		string(const char* str = "")
		{
			_size = strlen(str);
			_capacity = _size;
			_str = new char[_capacity + 1];

			strcpy(_str, str);
		}
1
2
3
4
5
6
7
8
9

这是使用C字符串进行的构造。

• 使用C字符串进行构造的时候，需要加一个缺省值，当创建一个空的string的时候就会使用到这个缺省值。
• _size表示的是有效字符的个数，不包括’\0’，是通过C语言中的strlen函数求出来的。
• _capacity表示的是有效空间的大小，同样不包括’\0’所占的空间，在最初构造一个string对象的时候，让_size和_capacity的大小一样。
• 使用new开辟动态空间来存放字符串的时候，开辟的空间需要比_capacity大一个，这多出来的一个是专门用来存放’\0’的，一个字符串中只有一个’\0’。

为了查看效果，需要实现一个打印字符串的成员函数：

		//字符串打印
		const char* c_str()
		{
			return _str;
		}
1
2
3
4
5

可以看到，使用C字符串，空的string，以及使用string类都可以实现一个新的string类对象的创建。

🍛拷贝构造函数

编译器自动生成的默认拷贝构造函数进行的浅拷贝，如下图：

当使用s1来拷贝构造s2的时候，就会导致如上图所示的问题，新的s2指向的动态空间和s1指向的动态空间是同一块空间，这样不仅在释放的时候会导致错误，而且在使用的时候也会在改变s2中的内容的同时将s1中的内容改变，所以对于拷贝构造函数需要进行深拷贝。

所谓深拷贝就是将内容全部复制过来，但是s1和s2使用的是两块空间：

而深拷贝的实现方式又有俩种，分别是传统方式和现代方式。

传统方式实现：

		//传统拷贝构造函数
		string(const string& s)
		{
			_size = s._size;
			_capacity = s._capacity;
			_str = new char[_capacity + 1];

			strcpy(_str, s._str);
		}
1
2
3
4
5
6
7
8
9

这种方式在新的string对象创建的时候新开辟了一个和原对象一样大小的空间，并且将原对象中的字符串拷贝过来。

现代方式实现：

		//现代拷贝构造函数
		string(const string& s)
			:_str(nullptr)
			,_size(0)
			,_capacity(0)
		{
			string tmp(s._str);
			std::swap(_str, tmp._str);
			std::swap(_size, tmp._size);
			std::swap(_capacity, tmp._capacity);
		}
1
2
3
4
5
6
7
8
9
10
11

上面的便是现代版本的拷贝构造函数实现的思想，下面本喵用图来给大家解释：

tmp通过s1中的字符串构造了一个新的string类对象，而此时s2的_str指向的空间中是随机值。
为了让s2中的内容变成和s1中的一样，只要将临时的类对象tmp中内容拿过来即可。

此时就将tmp和s2中的内容全部进行了交换，而s2也没有开辟新的空间就实现了拷贝构造的目的。

注意：

红色框中的初始化列表中，必须将s2的_str置为空，否则会编译报错。

• s2拿走了tmp中的_str，而将自己的_str给了tmp，当tmp生命周期结束的时候，会释放空间，如果不是nullptr就会释放原本不属于tmp而属于s2的空间，所以就会报错.。

swap函数的实现：

上面使用的swap是标准算法库中的swap函数，但是在string标准库中还有一个swap函数：

这俩个函数是有区别的。

• 标准算法库中的swap是一个函数模板，它会自动推演数据类型，如果使用这个函数进行俩个string类对象的交换，会发生三次拷贝构造，系统开销比较大。
• 所以在交换string类对象的时候使用string库中的swap函数比较合适。

既然是string的模拟实现，所以同样也需要我们自己实现一个。

		//交换函数
		void swap(string& s)
		{
			std::swap(_str, s._str);
			std::swap(_size, s._size);
			std::swap(_capacity, s._capacity);
		}

1
2
3
4
5
6
7
8

在string中的swap同样是通过标准算法库中的swap实现的，细心的小伙伴肯定发现了一个问题，在上面代码中，使用标准算法库中的swap交换的数据都是内置类型的，而函数模板中有一个语句c(a)，也就是用a来拷贝构造c。

如果a和c都是自定义类型我们不难理解，但是此时的a和c都是内置类型。

说明：

内置类型也有拷贝构造函数以及析构函数，一般情况下是不用考虑这个的，而且在C语言中是没有的，但是为了迎合模板，就不得不有。

可以看到，内置类型也可以使用拷贝构造以及赋值运算符重载等方式来创建。

此时现代方式的拷贝构造函数就有了更加简洁的写法：

		string(string& s)
			:_str(nullptr)
			,_size(0)
			,_capacity(0)
		{
			string tmp(s._str);
			swap(tmp);
		}

1
2
3
4
5
6
7
8
9

此时就非常简洁的实现了深度拷贝。

🍛赋值运算符重载

和拷贝构造函数一样，如果使用编译器自动生成的默认赋值运算符重载函数，也是会有浅拷贝的问题，所以赋值也是需要深度拷贝的。同样的，也是有传统和现代俩种实现方式。

传统方式：

		//传统赋值运算符重载函数
		string& operator=(const string& s)
		{
			if (this != &s)
			{
				_size = s._size;
				_capacity = s._capacity;

				delete[] _str;

				_str = new char[_capacity + 1];

				strcpy(_str, s._str);
			}
			return *this;
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

和拷贝构造函数一样，也开辟一个和原本类对象一样大小的空间，然后将内容赋值过来。

• 需要判断一下是否是自己给自己赋值，如果是的话就直接返回this指向的内容。
• 给类对象赋值以后，这个类对象原本指向的空间不再使用了，因为开辟了新的空间，所以要将原本指向的空间使用delete释放掉。

现代方式：

和拷贝构造函数现代方式实现的思路一样，也是拿其他对象的构造成果，坚决不自己开辟空间。

		//现代赋值运算符重载函数
		string& operator=(string& s)
		{
			if (this != &s)
			{
				//string tmp(s._str);
				string tmp(s);
				swap(tmp);
			}
			return *this;
		}
1
2
3
4
5
6
7
8
9
10
11

使用s拷贝构造一个临时对象tmp，然后将tmp中的内容拿走，最后返回this指针的内容。

既然都是找一个中间的打工仔，而不自己实现，可以直接使用形参这个打工仔：

		string& operator=(string s)
		{
			swap(s);
			return *this;
		}
1
2
3
4
5

此时就更加的简洁，而且形参的地址必定和this中的值不同，所以都不用排除自己给自己赋值的情况。

• 现代版本的深度拷贝仅是为了代码更加简洁而不考虑效率。

🍛析构函数

析构函数没有什么要点，非常的简单：

		//析构函数
		~string()
		{
			delete[] _str;
			_size = 0;
			_capacity = 0;
		}
1
2
3
4
5
6
7

直接使用delete释放空间即可。

🍚常用的string接口

🍛[]操作符重载

在使用string的时候，可以想方法C字符串数组一样使用[]来访问string类对象中的字符，下面本喵来给大家看看它是如何实现的：

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

		//可读不可写
		const char& operator[](size_t pos) const
		{
			assert(pos < _size);
			return _str[pos];
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

操作符[]的重载有俩个重载函数，一个是可读可写的，一个是只读不可写的。

可以看到，成果的将s1中字符串的前5个字符的ASCII码都加了1。

🍛迭代器iterator

我们指定，迭代器是行为上像指针一样的东西，在string类中，迭代器就是一个指针：

typedef char* iterator;
1

此时一个迭代器类型便实现好了，有了迭代器后就需要有对应的接口来配合迭代器使用。

		//begin()
		iterator begin()
		{
			return _str;
		}

		//end()
		iterator end()
		{
			return _str + _size;
		}

1
2
3
4
5
6
7
8
9
10
11
12

此时俩个和迭代器最常用的接口便实现好了。

通过迭代器，将s1中的内容全部打印了出来。

范围for：

范围for一直给我们的映像都很神奇，现在可以揭下它的神秘面纱了。

此时范围for是正常的。

仅仅将begin函数中的b换成大写的B。

在执行的时候报了一大堆的错误，都是和begin有关的。

• 在编译的时候，编译器会将范围for的代码转换成使用迭代器的代码，然后再进行编译。
• 此时begin函数没有了，所以使用迭代器的方式就无法实现了，所以就会报错。

编译器是不认识范围for这个语法的，所以它必须进行转换以后编译器才能够认识，而且这个转换是写死了的，必须使用迭代器iterator，begin，end函数，少一个都不行。

🍛size()和capacity()

成员函数size()是用来获取效字符的个数的，capacity()是用来获取有效空间的大小的。

		//size
		size_t size() const
		{
			return _size;
		}
		//capacity()
		size_t capacity() const
		{
			return _capacity;
		}
1
2
3
4
5
6
7
8
9
10

🍚增

🍛改变容量

1. reserve()

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

				_capacity = n;
			}
		}
1
2
3
4
5
6
7
8
9
10
11
12
13

该函数的作用就是在扩容，和C语言中的realloc的作用相似，但是C++中并没有realloc这样的函数，所以扩容就需要我们手动扩容，就在新开辟一块空间，并且将旧空间中的内容拷贝进去，再将旧空间释放掉。

2. resize()

		//resize()
		void reszie(size_t n, char ch = '\0')
		{
			if (n <= _size)
			{
				_size = n;
				_str[_size] = '\0';
			}
			else
			{
				reserve(n);
				for (int i = _size; i < n; ++i)
				{
					_str[i] = ch;
				}
				_size = n;
				_str[_size] = '\0';
			}
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

resize分三种情况：

• n小于等于原本的_size，此时是在缩容，只需要将_size的值改为n，并且将下标为n的位置处放一个’\0’。
• n大于原本的_size，并小于原本的_capacity，此时不需要进行扩容只需要将原本的_size设置成n即可，并且将相比于原本字符多出来的位置用形参ch来填充，如果没有传ch，就使用缺省值’\0’。
• n大于原本的_capacity，此时需要进行扩容，之后的操作和上面的一样。

运行结果符号预期。

🍛插入

1. push_back()

		//push_back()
		void push_back(char ch)
		{
			if (_size == _capacity)
			{
				size_t newcapacity = _capacity == 0 ? 4 : _capacity * 2;
				reserve(newcapacity);
			}
			_str[_size++] = ch;
			_str[_size] = '\0';
		}
1
2
3
4
5
6
7
8
9
10
11

尾插插入的只有一个字符串，而且是在字符串的末尾插入，在插入之前需要判断容量是否够用，如果不够则需要扩容。

• 当原本的容量就是0的时候，就不能简单二倍扩容，因为0乘2以后还是0，就需要给定一个初始容量，这里本喵给的初始容量是4。

2. append()

		//append()
		void append(const char* str)
		{
			size_t len = strlen(str);
			if (_size + len > _capacity)
			{
				reserve(_size + len);
			}
			strcpy(_str + _size, str);
			_size += len;
		}
1
2
3
4
5
6
7
8
9
10
11

尾部插入字符串。同样需要判断是否需要扩容，之后在原本的’\0’位置处开始，放入插入的字符串，因为插入的字符串自带’\0’，所以插入以后不需要自己再写’\0’。

3. +=

		//+=一个字符
		string& operator+=(char ch)
		{
			push_back(ch);
			return *this;
		}

		//+=字符串
		string& operator+=(const char* str)
		{
			append(str);
			return *this;
		}
1
2
3
4
5
6
7
8
9
10
11
12
13

最常使用的就是+=，因为它的可读性高，而它实现的原理就是在运算符重载的时候复用了push_back和append函数。

+=一个字符和一个字符串都实现了。

4. insert

• 在指定位置插入一个字符
  
  挪动数据的时候有俩中方式，如上图中的红色框。

• 第一个红色框中的方法，如果不将pos强转为int类型的话，当在0位置插入字符的时候，就会在while的条件判断时发生隐式类型转换，int类型的end提升成size_t，此时就不会出现负数，就会造成死循环。

• 在指定位置插入一个字符串

在挪动数据的时候同样有俩种方式，其中第一种和上面的插入一个字符时的注意点一样。

下面本喵来画图分析一下，插入的过程：

• end就等于_size+len，从下标为end处开始，将end-len位置的元素移动过去，直到将pos位置处的元素也移动走。
• 这个过程中会有元素的覆盖，但是是使用前面的元素覆盖后面的元素，所以不存在问题。

• 移动完数据以后，将要插入的字符串，除’\0’以外的所有字符复制到pos位置开始的空间中，如上图中黄色线。

和我们分析的结果一致。

🍛删除

1. erase()
   
   在这里我们定义一下npos，这是一个静态成员变量，在类中进行声明的时候，给它一个缺省值-1，在定义的时候就会使用到这个缺省值。

• 静态成员变量的声明在类中，定义必须在类外，但是有一个特殊类型，整型家族的静态成员就可以在声明的时候给一个缺省值。
• 由于是size_t类型的-1，所以它的实际大小就是32个1的二进制，转换成十进制大致是42亿9千万。

npos也代表值string类对象字符串的末尾。

		//erase
		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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

如果要删除的字符串长度已经超出了现有字符串的长度，那么就从指定位置开始全部删除完，否则就需要将对应位置以后相应长度的字符串删除后，再将剩下的字符移动到前面。

2. clear()

		//clear()
		void clear()
		{
			_size = 0;
			_str[_size] = '\0';
		}
1
2
3
4
5
6

clear是情况所有字符串，但是不改变容量。

对应的结果是符号我们的预期的。

🍛查找

		//find()
		//查找一个字符
		size_t find(char ch, size_t pos = 0) const
		{
			assert(pos < _size);
			while (pos < _size)
			{
				if (_str[pos] == ch)
				{
					return pos;
				}
				pos++;
			}
			return npos;
		}

		//查找一个字符串
		size_t find(const char* str, size_t pos = 0) const
		{
			assert(pos < _size);
			const char* ptr = strstr(_str + pos, str);
			if (ptr == nullptr)
			{
				return npos;
			}
			else
			{
				return ptr - _str;
			}
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

这是查找一个字符和一个字符串的代码，找到了就返回下标，找不到就返回npos的值，在查找字符串的时候，使用了C语言中的strstr查找字串的函数。

结果也符合我们的预期。

🍚流插入(<<)流提取(>>)运算符重载

在前面本喵已经实现过一次了，这里再提及一下。

1. 流插入(<<)运算符重载

ostream& operator<<(ostream& out, const string& s)
	{
		for (size_t i = 0; i < s.size(); ++i)
		{
			out << s[i];
		}
		return out;
	}
1
2
3
4
5
6
7
8

2. 流提取(>>)运算符重载

istream& operator>>(istream& in, string& s)
	{
		s.clear();
		char ch = in.get();
		while (ch != ' ' && ch != '\n')
		{
			s += ch;
			ch = in.get();
		}
		return in;
	}
1
2
3
4
5
6
7
8
9
10
11

• cin和scanf一样，当遇到空格或者换行符时，自动将字符串分割
• 如果输入的内容很多的话，就会不停地+=，也会导致不停扩容，导致系统开销较大。

改进：

istream& operator>>(istream& in, string& s)
{
    s.clear();
    char buff[128] = { '\0' };
    size_t i = 0;
    char ch = in.get();
    while (ch != ' ' && ch != '\n')
    {
        if (i == 127)
        {
            s += buff;
            i = 0;
        }
        buff[i++] = ch;
        ch = in.get();
    }
    if (i >= 0)
    {
        buff[i] = '\0';
        s += buff;
    }
    return in;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

先开辟一个数组，将输入的字符放在数组中，当数组满了后进行一次扩容，此时即使输入很长的字符串，扩容的频率也不会很高。

🍚总结

我们自己模拟实现的string并不是要和标准库中的完全一样，只是为了了解string的底层原理，让我们在使用起来更加得心应手。