【C++STL之string类模拟

2023年 9月 28日 108.7k 0

string的模拟实现

对STL中的string类有了一个基本的认识后,本模块,我会带着你从0 ~ 1去模拟一下s库中string的这些接口,当然是比较常用的一些,代码量大概600行左右

1、前情提要

  • 首先第一点,为了不和库中的string类发生冲突,我们可以在外层包上一个名称为bit的命名空间,此时因为作用域的不同,就不会产生冲突了,如果这一块有点忘记的同学可以再去看看 namespace命名空间
namespace bit
{
	class string {
	public:
		//...
	private:
		size_t _size;
		size_t _capacity;
		char* _str;
	};
}
  • 接下去呢,就在测试的test3.cpp中包含一下这个头文件,此时我们才可以在自己实现的类中去调用一些库函数
#include 
#include 
using namespace std;

#include "string.h"

2、Member functions —— 成员函数

构造函数

好,首先第一个我们要来讲的就是【构造函数】

  • 首先我们从无参的构造函数开始讲起,看到下面的代码,你是否有想起了 C++初始化列表,我们默认给到 _size_capacity 的大小为,然后给字符数组开了一个大小的空间,并且将其初始化为
// 无参构造函数
string()
	:_size(0)
	, _capacity(0)
	,_str(new char[1])
{ 
	_str[0] = '';
}
  • 然后我们立即来测试一下,因为我们自己实现的 string类 是包含在了命名空间bit中的,那么我们在使用这个类的时候就要使用到 域作用限定符::
bit::string s1;

然后打印一下这个string对象发现是一个空串

在这里插入图片描述

  • 有无参,那一定要有带参的,可以看到这里我们在初始化_size的时候先去计算了字符串str的长度,因为_size取的就是到 为止的有效数据个数(不包含),那么【strlen】刚好可以起到这个功能
  • 然后在_str这一块,我们为其开出的空间就是 ==容量的大小 + 1==,最后的话还要在把有效的数据拷贝到这块空间中,使用到的是【strcpy】
// 有参构造函数
string(const char* str)
	: _size(strlen(str))
	, _capacity(_size)
	,_str(new char[_capacity + 1])
{
	// 最后再将数据拷贝过来
	strcpy(_str, str);	
}
  • 同样地来进行一个测试

在这里插入图片描述
💬 不过呢,我这里再给出一个改进的版本

  • 此处没有使用到初始化列表,而是在直接写在函数体内,注意观察这里的形参部分,这里运用到的知识点为 C++缺省参数,如果忘记了的同学记得去回顾一下
  • 如果外界在构造对象的时候不进行传参,此时使用的便是这个默认的参数,“”代表的是一个空的字符串,但是无论怎样,对于一个字符串来说末尾是一定有的,此刻你可以将它带入下面的表达式,发现算出后的结果与前面无参是一样的
// 构造函数
string(const char* str = "")
{
	_size = strlen(str);
	_capacity = _size;
	_str = new char[_capacity + 1];
	memcpy(_str, str, _size + 1);
}
  • 可能有的读者注意到了这个 memcpy(),如果有度过 字符串函数与内存函数 一文的话就可以清楚它们的区别在哪里了,对于strcpy()来说拷贝到就会发生终止而不会拷贝了,这是我在测试一些极端场景的时候考虑到的

可以看到换回【strcpy】的时候后面的内容就不会去进行一个拷贝了,不过这里其实体现得不是很明显,我们在下面的 拷贝构造、赋值运算符重载 中会继续提到这个

在这里插入图片描述
💬 有同学觉得上面的缺省参数很是奇妙,于是提出能不能写成下面这样

  • 这肯定是不可以的,从运行结果我们可以看出虽然运行出来也是空串的结果,但是这么写的话总归不太好
string(const char* str = "")

在这里插入图片描述

  • 但是呢对于下面这种就更不可以了,因为这在调用【strlen】的时候就会触发 ==空指针异常== 的问题
string(const char* str = nullptr)

在这里插入图片描述

拷贝构造函数

马上,我们就来聊聊有关【拷贝构造函数】的内容

  • 在 深度探索类的六大天选之子 中我们有提到过若是一个类在没有显示定义拷贝构造对于内置类型不做处理,而对于自定义类型会去调用 类中默认提供的拷贝构造函数 此时就会造成浅拷贝的问题

在这里插入图片描述

  • 我们可以通过调试来浅浅地看一下,便可以看出浅拷贝所带来的危害,光是在调用析构这一块就出现了 ==二次析构== 的问题

在这里插入图片描述

  • 所以我们要自己去做一个实现,可以看到我们这里在进数据的拷贝时也是使用到了memcpy()
string(const string& s)
{
	_str = new char[s._capacity + 1];
	memcpy(_str, s._str, s._size);
	_size = s._size;
	_capacity = s._capacity;
}
  • 通过调试再去观察的话,我们可以发现,此时 对象s1 和 对象s2 中的数据存放在不同的空间中,此时去修改或者是析构的话都不会受到影响

在这里插入图片描述

下面呢还有一个新的版本,这一块我放到【赋值重载】去进行讲解

// 拷贝构造函数(新版本)
string(const string& s)
	: _str(nullptr)
	, _size(0)
	, _capacity(0)
{
	string tmp(s._str);
	// tmp出了当前函数作用域就销毁了,和this做一个交换
	this->swap(tmp);
}

赋值运算符重载

对于赋值运算符重载这一块我们知道它也是属于类的默认成员函数,如果我们自己不去写的话类中也会默认地生成一个

  • 但是呢默认生成的这个也会造成一个 ==浅拷贝== 的问题。看到下面图示,我们要执行s1 = s3,此时若不去开出一块新空间的话,那么s1s3就会指向一块同一块空间,此时便造成了下面这些问题
    • 在修改其中任何一者时另一者都会发生变化;
    • 在析构的时候就也会造成二次析构的;
    • 原先s1所指向的那块空间没人维护了,就造成了内存泄漏的问题

在这里插入图片描述

  • 那么此时我们应该自己去开出一块新的空间,将s3里的内容先拷贝到这块空间中来,然后释放掉s1所指向这块空间中的内容,然后再让s1指向这块新的空间。那么这个时候,也就达成了我们所要的【深拷贝】,不会让二者去共同维护同一块空间
  • 最后的话不要忘记去修改一下s1的【_size】和【_capacity】,因为大小和容量都发生了改变

在这里插入图片描述
下面是具体的代码,学习过 类的六大天选之子 的同学应该不陌生

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

但是呢,就上面这一种写法并不是最优的,我们来看看下面的这种写法

  • 很多同学非常地震惊,为何这样子就可以做到【深拷贝】呢?
// 赋值重载(pua版本)
string& operator=(const string& s)
{
	if (this != &s)
	{
		string tmp(s);
		this->swap(tmp);
	}
	return *this;
}
  • 有关这个swap()函数,本来是应该下面讲的,既然这里使用到了,那就在这里讲吧,这个接口我在上面并没有介绍到,但是在讲 C++模版 的时候有提到过库中的这个 swap() 函数,它是一个函数模版,可以 根据模版参数的自动类型推导去交换不同类型的数据
  • 可以看到在我们自己实现的这个swap(string& s) 函数中就去调用了std标准库中的函数然后交换一个string对象的所有成员变量
void swap(string& s)
{
	std::swap(_str, s._str);
	std::swap(_size, s._size);
	std::swap(_capacity, s._capacity);
}
  • 接下去来解释一下这里的原理,我们在这个赋值重载的函数内部调用了拷贝构造去获取到一个临时对象tmp,然后再通过swap()函数去交换当前对象和tmp的指向,此时s1就刚好获取到了赋值之后的内容,而tmp呢则是一个临时对象,出了当前函数的作用域后自动销毁,那么原本s1所维护的这块空间刚好就会销毁了,也不会造成内存泄漏的问题

在这里插入图片描述
💬 那有同学就说:这个妙啊!太妙了!

  • 哈哈,不知读者有没有听过最近很火的一个词叫做【PUA】
“PUA”的原理,就是打击你的自尊,摧毁你的独立思考能力,让你觉得自己一无所事,
然后对方趁虚而入,让你产生依赖,让你觉得只有对方才能帮助自己,从而被对方操控。
  • 泡面🍜的话相信大家都有吃过,假设说呢有这么一个场景:你呢是家里的哥哥,你还有一个弟弟,这一天的中午你很想吃冰箱里的那桶泡面,但是呢妈妈又不让吃,于是你就和你弟弟说:“冰箱里有一桶很好吃的泡面,你快去泡一下试试看”。那此时你傻傻的弟弟就立马去做了,当他泡完的时候呢你再去找你的妈妈告状,于是这个时候弟弟就被狠狠地骂了一顿(╯▔皿▔)╯
  • 此时这碗泡面就没人吃了,于是这个时候你就乘虚而入把这碗泡面给吃了,但是呢又不想洗碗,于是又把你弟弟给叫了过来,说:“要不你把这个碗去洗了,晚上我给你买雪糕吃🍦”。听到雪糕后你的弟弟又精神起来了,马上就把碗去给洗了

在这里插入图片描述

  • 透过上面这个小例子读者应该对新的这种拷贝构造有了一定的理解:反正你这个tmp对象出了作用域也要销毁的,你手上呢刚好有我想要的东西,那我们换一下吧,此时我得到了我想要的东西,你呢拿到了我的东西,这块地址中的内容刚好就是要销毁的,那tmp在出了作用域后顺带就销毁了,这也就起到了【一石二鸟】的效果

好,我们通过这个调试来观察一下,可以看到就是这个“PUA技术”,很好地达成了我们的目标

在这里插入图片描述
💬 但是呢,我觉得上面的这种PUA还不够,还可以再 “精妙” 一些,我们一起来看一下下面这个版本

  • 可以看到,真的是非常简洁,两行代码就足够了,那为什么可以起到这样的效果呢?原因其实就在于这个形参部分,可以看到我并没有使用像上面那样的【引用传参】,而是直接使用的传值传参
  • 那仔细学习过【类和对象】的同学一定可以知道对于【传值传参】的话会先去调用拷贝构造拷贝出一个临时的对象,那么这不就是我们在写上面一个版本的时候在函数内部去调用拷贝构造所做的事吗?那么当外界在给这个函数传递参数对象的时候,此时这个tmp便是外面这个对象的一个临时拷贝,我们直接去操作这个对象的时候也可以到达同样的效果
// 赋值重载(究极pua版本)
string& operator=(string tmp)
{
	this->swap(tmp);
	return *this;
}

一样,我们通过调试来看就可以看得很清晰,一开始按F11的时候我们可以看到进入到了拷贝构造函数内部,这个时候其实就是因为传值传参去调用拷贝构造的缘故

在这里插入图片描述

💬 此时我们就可以去谈谈在一模块所讲到的这个【新版本的拷贝构造函数】

  • 这里我把代码再放一遍,读者在看到赋值重载之后再来看这个应该就没有那么陌生了
// 拷贝构造函数(新版本)
string(const string& s)
	: _str(nullptr)
	, _size(0)
	, _capacity(0)
{
	string tmp(s._str);
	// tmp出了当前函数作用域就销毁了,和this做一个交换
	this->swap(tmp);
}
  • 我在这边主要想讲的还是这个初始化列表的问题,读者一定知道如果我们没有手动地去初始化成员变量的话,对于内置类型编译器是不做处理的,对于自定义类型则会去调用默认生成的拷贝构造,那交给编译器去做安全吗?当然是极度地不安全
string(const string& s)
{
	string tmp(s._str);
	// tmp出了当前函数作用域就销毁了,和this做一个交换
	this->swap(tmp);
}
  • 通过调试我们可以观察到,当直接去调用拷贝构造的时候,编译器对当前的对象做了一个初始化的工作,于是在析构的时候就没有出现问题,但是继续执下去到达我们上面的赋值=的时候,因为传值传参的缘故首先会去调用这个拷贝构造拷贝一份临时对象,但是呢在调试的时候可以发现编译器并没有去对当前对象中的成员变量做一个初始化的工作,在执行swap()函数后这个没被初始化的对象就交给tmp来进行维护了,但是呢tmp在出了作用域之后又要销毁,那么此时在执行析构函数的时候便会出问题了,去释放了一块并没有初始化的空间,一定会出现问题的!

在这里插入图片描述
💬 所以我们还是不能去相信编译器所做的一些工作,而是要自己经手去做一些事,避免不必要的麻烦

析构函数

最后的话就是析构函数这一块,前面在调试的过程中我们已经看到很多遍了,此处不再细述

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

2、Element access —— 元素访问

基本的成员函数我们已经讲完了,string对象也构造出来了,接下去我们来访问一下对象里面的内容吧

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];
}
  • 里面我们就通过循环来访问一下,这里的size()函数和流插入我们会在下面讲到

在这里插入图片描述

  • 此时我们去调用的时候可读可写的版本,是可以在边访问的时候去做一个修改的,效果如下

在这里插入图片描述

  • 但是呢,如果我在定义这个对象的时候在前面加上一个const的话此时这个对象就具有常性了,在调用operator[]的时候调用的便是 可读不可写 的那一个,所以此刻我们去做一个修改操作的话就会出问题了
const bit::string s2("world");

在这里插入图片描述

  • 通过调试我们可以观察到编译器在调用这一块会默认去匹配最相近的重载函数非常得智能

在这里插入图片描述

3、Iterator —— 迭代器

那经过上面的学习我们可以知道,要去遍历访问一个string对象的时候,除了【下标 + []】的形式,我们还可以使用迭代器的形式去做一个遍历

  • 而对于迭代器而言我们也是要去实现两种,一个是非const的,一个则是const的
typedef char* iterator;
typedef const char* const_iterator;
  • 这里的话我就实现一下最常用的【begin】和【end】,首位的话就是_str所指向的这个位置,而末位的话则是_str + _size所指向的这个位置
iterator begin()
{
	return _str;
}

iterator end()
{
	return _str + _size;
}
  • 实现了普通版本的迭代器之后,我们再来看看常量迭代器。很简单,只需要修改一下返回值,然后在后面加上一个【const成员】,此时就可以构成函数重载了
const_iterator begin() const
{
	return _str;
}

const_iterator end() const
{
	return _str + _size;
}
  • 首先我们来看一下这个普通的迭代器,成功地遍历了这个string对象

在这里插入图片描述

  • 那么对于常对象来说的话,就要使用常量迭代器来进行遍历,但你是否觉得这个迭代器的长度过于长了呢?

在这里插入图片描述

  • 这一点我们在上面也讲到过了,使用C++11中的auto关键字进行自动类型推导即可
auto cit = s2.begin();

之前我们有讲过,一个类只要支持迭代器的话那一定支持范围for,马上我们来试试看吧

  • 分别去遍历一下这两个 string对象 ,可以看到都不成问题
for (auto ch : s1)
{
	cout  _capacity)
		{
			reserve(newSize);
		}
		// 如果newSize = pos)
{
	_str[end + n] = _str[end];
	--end;
}
  • 不过呢,我们在这里还要考虑一种极端的情况,如果这个pos == 0的话,也就是在这个位置开始插入数据,那也就相当于头插,此时需要将全部的数据向后进行挪动,可是呢当这个end超出pos的范围时,也就减到了-1,但是呢这个end的数据类型则是【size_t】,为一个无符号整数,我们知道对于无符号整数来说是不可能为负数的,那么这个时候就会发生一个轮回,变成最大的无符号正数

在这里插入图片描述

  • 我们可以来看看当这个end在不断减少直至减到0的时候就会突然变成一个很大的数字,这个其实就是npos的值了,此时就会造成一个死循环,导致程序崩溃

在这里插入图片描述

  • 所以我们应该在循环的结束条件中加上一个end != npos才对
// 挪动数据
size_t end = _size;
while (end >= pos && end != npos)
{
	_str[end + n] = _str[end];
	--end;
}
  • 当这个挪动的逻辑结束后,我们就可以从pos这个位置去插入n个字符了。最后再去更新一下这个_size的大小即可
// 插入n个字符
for (size_t i = 0; i < n; i++)
{
	_str[pos + i] = ch;
}
_size += n;

在这里插入图片描述

从pos位置开始插入一个字符串

void insert(size_t pos, const char* s)
  • 对于在【pos位置插入一个字符串】来说,其他逻辑和上面这个接口都是一样,也是要经过 扩容、移位、放数据 这些操作,只是这里在放数据的时候换成了字符串而言
// 插入字符串
for (size_t i = 0; i < len; i++)
{
	_str[pos + i] = s[i];
}
_size += len;

删除从pos位置开始的len个有效长度字符

void erase(size_t pos, int len = npos)
  • 意思很简单,就是从pos位置开始去删,删除len个有效长度的字符,那这几个字符就相当于是不要了,但是呢后面的字符串还是要的,所以有的同学就会想到用这个 拼接 的方法去完成
  • 但是呢没必要这样,这只会增加算法的复杂性,对于【erase】来说更多地还是去做一个 ==移位覆盖==

读者可以通过下面的算法分解图去思考一下代码该如何书写,我们是从【w】这个位置开始删除长度为3的有效字符

在这里插入图片描述

  • 但是呢,我们还要考虑到一些特殊的情况,例如说我们要取的长度len很大很大,甚至是最大的无符号整数npos,或者呢在pos + len之后的长度超出了当前_size的大小,此时我们可以直接对pos之后的字符去做一个截断的操作,让这个位置变成新的_size

在这里插入图片描述
下面就是具体的代码展示,对于正常的情况而言,最后呢不要忘记了在覆盖字符后去改变一下这个_size的大小

// 删除从pos位置开始的len个有效长度字符
void erase(size_t pos, int len = npos)
{
	if (len == npos || pos + len > _size)
	{
		_size = pos;
		_str[_size] = '';
	}
	else
	{
		size_t end = pos + len;
		while (end  _size的情况

在这里插入图片描述

  • 那如果第二个参数不传递呢?那使用的便是缺省值【npos】,这就是len == npos的情况

在这里插入图片描述

swap

  • 对于【swap】函数我们在上面已经有讲解过了,此处不再过度赘述
void swap(string& s)
{
	std::swap(_str, s._str);
	std::swap(_size, s._size);
	std::swap(_capacity, s._capacity);
}

6、String Operations —— 字符串操作

然后再来讲讲有关字符串的一些操作

c_str

  • 首先的话就是这个【c_str】,可以看到上面我在测试完一个结果后都会去cout >(istream& in, string& s)
    {
    s.clear();
    char ch = in.get();
    // 处理前缓冲区前面的空格或者换行
    while (ch == ' ' || ch == 'n')
    {
    ch = in.get();
    }

    char buf[128];
    int i = 0;
    while (ch != 'n') // 以换行作为分隔符
    {
    buf[i++] = ch;
    // 不能等到128再去判断,要为最后的留空间
    if (i == 127)
    {
    buf[i] = '';
    s += buf;
    i = 0;
    }
    ch = in.get();
    }
    // 若是有数据且不到127的话,进行倒入
    if (i != 0)
    {
    buf[i] = '';
    s += buf;
    }
    return in;
    }

    然后再去测试一下上面的两个场景,就发现什么问题了

    在这里插入图片描述

    四、写时拷贝(了解)

    最后我们再来介绍一个东西叫做【写时拷贝】

    1、概念理解

    • 前面我们有谈到过什么是 ==深拷贝==,而 ==浅拷贝== 又会引发怎样的问题,这边再来回顾一下
      • 浅拷贝会导致一块空间被析构两次
      • 浅拷贝会导致一个对象修改也引发另一个对象一并修改
    • 此时我们只有使用 深拷贝 才能解决问题,但是你是否有想过深拷贝所带来的代价呢?我们每去创建一个对象就进行一个深拷贝,但是呢在后面这个对象去不会去做任何的修改,那么深拷贝的意义其实没有多大,还多浪费了一块内存空间,虽然这对操作系统来说算不得什么,但若是你在长期运行这个代码所跑起来的程序时,则会造成内存枯竭💀

    所以呢有人就提出了这么一个东西,叫做【写时拷贝】,全称叫做【引用计数 · 写时拷贝】

    • 看到下面的图示, s2 呢是 s1 的一份临时拷贝,并且在这个地方我们使用的就是浅拷贝,二者指向的是同一块空间,此处我们会引入一个变量作为引用计数,每当构建出来一个对象的时候,计数器 + 1,所以在当 s2 拷贝完后这个计数器即为【2】
    • 那么此时在析构的时候其所采用的机制便是:当一个对象去进行析构的时候,会先去看这个计数器的值是否为【1】,如果>= 1的话,说明这块空间的维护者不止它一个,那么其就不可以去释放掉这块空间,而是将计数器--,那么此时这个计数器就变成了【1】;接下去当另一个对象再去调用析构函数的时候,发现这个计数器的值是为【1】,表示现在只有它在维护这块空间,其便会去释放掉这块空间
    • 那对于上面的这种机制你可以认为是 ==最后一个走的关灯==

    在这里插入图片描述

    当然除了解决析构两次的问题,面对拷贝修改这一块它也做了一些文章

    • 当我们要对一个对象中的空间做修改的时候,此时再去执行一个 深拷贝 的逻辑,重新开出一块空间来,把原本的数据拷贝过来,让其指向这块新的空间,然后就在这个新的空间中做修改。最后在将这个计数器--
    • 可以看到这个机制就很好地防止了同时修改的问题

    在这里插入图片描述
    💬 那有的同学说:那反正这最后不还是要去做一个深拷贝的,直接深拷贝不就完了,有什么意义呢?

    • 其实你可以认为这是编译器是在做一个【博弈】,因为在不修改的情况下我们所执行的都是 浅拷贝,那么即可能很多对象都在维护同一块空间,此时如果这几个对象都不会去做写操作的话,那其实我们就是赚的,大家都展示同一块空间的内容即可,共同维护同一块空间,无需再多的开销
    • 而只有当我们对这个对象去进行写操作的时候,才去开辟出一块新的空间进行修改,随开随用,此时也不算太晚。==所以只要你浅拷贝了但是不去修改我就是赚的==

    💬 其实读者可以这么来理解

    • 如果有读者像博主一样喜欢健身的话,就可以知道一般去健身房都是需要办卡的,只有当办卡的人数到达一定量的时候,老板才是赚的,为什么呢?原因就在于很多人办了健身卡后一般很少会来,甚至是不来,那么这个时候老板一定是赚的,如果每个会员每天都来的话,这健身器材都要不够了😓
    • 那么老板赌的这个【办了卡不来】和我们上面所聊【拷贝了但是不修改】是一个道理的

    在这里插入图片描述

    2、双平台对比

    清楚了什么叫做【写时拷贝】,我们现在就来测试一下

    首先我们现到Linux平台下去看看

      1 #include
    2 #include
    3 #include
    4 using namespace std;
    5
    6 int main(void)
    7 {
    8 string s1("abc");
    9 string s2(s1);
    10
    11 printf("Show copyn");
    12 printf("%pn", s1.c_str());
    13 printf("%pn", s2.c_str());
    14 cout

相关文章

JavaScript2024新功能:Object.groupBy、正则表达式v标志
PHP trim 函数对多字节字符的使用和限制
新函数 json_validate() 、randomizer 类扩展…20 个PHP 8.3 新特性全面解析
使用HTMX为WordPress增效:如何在不使用复杂框架的情况下增强平台功能
为React 19做准备:WordPress 6.6用户指南
如何删除WordPress中的所有评论

发布评论