【C++练级之路】【Lv.6】【STL】string类的模拟实现

发布时间:2024年01月16日


欢迎各位小伙伴关注我的专栏,和我一起系统学习C语言,共同探讨和进步哦!

学习专栏

《进击的C++》


引言

关于STL容器的学习,我会采用模拟实现的方式,以此来更加清楚地了解其底层原理和整体架构。而string类更是有100多个接口函数,所以模拟实现的时候只会调重点和常见的函数进行实现,以此加强对重点函数的掌握。

一、成员变量

string类中包含了

  • str(指向动态开辟的字符数组)
  • _size(当前有效数据个数)
  • _capacity(最大有效容量)

同时,还包含了一个static修饰的静态成员变量npos,赋值为-1,因其类型为无符号整型,则表示最大值。

class string
{
private:
	char* _str;
	size_t _size;
	size_t _capacity;
	static size_t npos;
};

size_t string::npos = -1;

标准的静态成员变量,是在类内声明,类外定义。但是,这里设计出了一种奇怪的语法,加上const修饰,就可以在类内声明加定义。

static const size_t npos = -1;

二、默认成员函数

2.1 constructor

细节:

  1. 因为计算_size和_capacity都要调用strlen函数,为了防止频繁调用,在初始化列表中调用一次将_size初始化,后续再把_size赋值给_capacity
  2. _capacity初始化时,防止后续二倍扩容时_capacity为0,则加上判断,如果_size为0,初始_capacity为3
  3. 开辟空间的大小为_capacity + 1,因为要留一个空间给\0
  4. 缺省参数为空串
string(const char* str = "")
	:_size(strlen(str))
{
	_capacity = _size == 0 ? 3 : _size;
	_str = new char[_capacity + 1];
	strcpy(_str, str);
}

2.2 copy constructor

string(const string& s)
	:_size(s._size)
	, _capacity(s._capacity)
{
	_str = new char[_capacity + 1];
	strcpy(_str, s._str);
}

2.3 destructor

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

2.4 operator=

细节:

  1. 先开辟一段新空间,再释放旧空间,防止空间不足(一般空间相等的很少,所以大多数情况下不相等,直接开辟新空间)
  2. 原地赋值则什么都不做,否则释放了旧空间,就没办法拷贝字符串
string& operator=(const string& s)
{
	if (this != &s)
	{
		char* tmp = new char[s._capacity + 1];
		delete[] _str;
		_str = tmp;
		strcpy(_str, s._str);
		_size = s._size;
		_capacity = s._capacity;
	}

	return *this;
}

三、迭代器

3.1 begin

迭代器的实现和编译器有关,不同的编译器有不同的实现方式。这里简单的用指针来实现迭代器

同时,重载了普通迭代器和const迭代器。

typedef char* iterator;
typedef const char* const_iterator;

iterator begin()
{
	return _str;
}

const_iterator begin() const
{
	return _str;
}

3.2 end

迭代器遵循左闭右开的原则,begin指向首元素,end指向末元素的下一位。

typedef char* iterator;
typedef const char* const_iterator;

iterator end()
{
	return _str + _size;
}

const_iterator end() const
{
	return _str + _size;
}

悄悄告诉你范围for的底层实现,就是运用了迭代器。

四、元素访问

4.1 operator[ ]

为了方便的访问元素,我们重载了[ ]运算符。同时,也分为普通版本和const版本,对应不同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];
}

五、容量

5.1 size

获取当前有效数据个数

细节:const修饰,保证普通和const类型string类都能访问

size_t size() const
{
	return _size;
}

5.2 capacity

获取当前最大有效容量

细节:同上

size_t capacity() const
{
	return _capacity;
}

5.3 reserve

改变当前_capacity(将其变为指定大小n)

细节:

  1. 只扩容,不缩容(因为缩容也是有代价的)
  2. 异地扩容,新开辟一个新空间,将内容拷贝过去,再释放旧空间(事实上,原地扩容只占极少数,绝大部分扩容都是异地扩容)
void reserve(size_t n)
{
	if (n > _capacity)
	{
		char* tmp = new char[n + 1];
		strcpy(tmp, _str);
		delete[] _str;
		_str = tmp;
		_capacity = n;
	}
}

5.4 resize

改变当前_size(将其变为指定大小n),分为三种情况:

  1. n <= _size,在_size位置写入\0
  2. _size < n <= _capacity,填充指定字符ch直到_size为n,再重复步骤1
  3. n > _capacity,先扩容,再重复步骤2
void resize(size_t n, char ch = '\0')
{
	if(n > _size)
	{
		reserve(n);
		memset(_str + _size, ch, n - _size);
	}
	_size = n;
	_str[_size] = '\0';
}

六、修改

6.1 push_back

尾插一个字符

细节:

  1. 如果空间不够,则二倍扩容
  2. 插入字符后,在尾部添加\0
void push_back(char ch)
{
	if (_size + 1 > _capacity)
	{
		reserve(_capacity * 2);
	}

	_str[_size] = ch;
	++_size;
	_str[_size] = '\0';
}

6.2 append

尾插(追加)一个字符串

细节:

  1. 如果空间不够,扩容到刚好可以容纳的空间(因为二倍扩容有可能也不够)
  2. strcpy会自动把\0也拷贝过去
void append(const char* str)
{
	size_t len = strlen(str);
	if (_size + len > _capacity)
	{
		reserve(_size + len);
	}

	strcpy(_str + _size, str);
	_size += len;
}

悄悄说一句:其实这个函数写成push_back的重载函数更好哦~

6.3 operator+=

为了更加方便地使用尾插,我们重载了+=运算符,这样无论尾插字符或者字符串都极为方便。

string& operator+=(char ch)
{
	push_back(ch);
	return *this;
}

string& operator+=(const char* str)
{
	append(str);
	return *this;
}

6.4 insert

在指定位置插入一个字符

细节:

  1. 如果空间不够,二倍扩容
  2. 从pos位置开始,字符都后移一格(这里end = _size + 1 就是为了避免end == pos的判断,因为头插时pos为0,而end为无符号整数恒大于等于0,所以会导致死循环)
  3. 在pos位置插入指定字符
string& insert(size_t pos, char ch)
{
	assert(pos <= _size);

	if (_size + 1 > _capacity)
	{
		reserve(_capacity * 2);
	}

	size_t end = _size + 1;
	while (end > pos)
	{
		_str[end] = _str[end - 1];
		--end;
	}

	_str[pos] = ch;
	++_size;

	return *this;
}

其实,步骤2的字符后移,可以使用memmove函数(专门处理重叠空间的移动)

memmove(_str + pos + 1, _str + pos, _size + 1 - pos);

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

细节:

  1. 如果空间不够,扩容到刚好可以容纳的空间
  2. 从pos位置开始,字符都后移 len 格(这里len为1的时候,其实就是上一种情况)
  3. 在pos位置用strncpy插入指定字符串(不带\0)
string& 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 + 1;
	while (end > pos)
	{
		_str[end + len - 1] = _str[end - 1];
		--end;
	}

	strncpy(_str + pos, str, len);
	_size += len;

	return *this;
}

同样,步骤2的字符后移 len 格,也可以使用memmove函数。

memmove(_str + pos + len, _str + pos, _size + 1 - pos);

那么,完成了指定位置的插入,我们就可以复用代码,让push_back和append复用insert函数。

void push_back(char ch)
{
	insert(_size, ch);
}
void append(const char* str)
{
	insert(_size, str);
}

6.5 erase

在指定位置删除指定长度的字符串

细节:

  1. npos要单独判断(要不然npos加上pos会溢出)
  2. len为npos,或者pos+len >= _size,代表将删除pos位置往后的所有字符串
  3. 如果pos+len < _size,则将后面未删除的字符串用strcpy拷贝到pos位置
string& erase(size_t pos, size_t len = npos)
{
	assert(pos < _size);

	if(len == npos || pos + len >= _size)
	{
		_size = pos;
		_str[_size] = '\0';
	}
	else
	{
		strcpy(_str + pos, _str + pos + len);
		_size -= len;
	}

	return *this;
}

6.6 swap

交换两个string类的值

细节:使用std库中的swap函数,交换各个成员变量的值

void swap(string& s)
{
	std::swap(_str, s._str);
	std::swap(_size, s._size);
	std::swap(_capacity, s._capacity);
}

6.7 clear

清空字符串

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

七、操作

7.1 c_str

获取字符串

细节:const修饰,保证普通和const类型string类都能访问

const char* c_str() const
{
	return _str;
}

7.2 find

查找指定字符或者字符串,返回其下标

细节:

  1. 使用缺省参数pos = 0,可以从指定位置开始向后查找,如果未指定,则从头查找
  2. 查找字符串用strstr函数,找到返回指针,用指针-指针的方式得到下标
size_t find(char ch, size_t pos = 0)
{
	assert(pos < _size);

	for (size_t i = pos; i < _size; ++i)
	{
		if (_str[i] == ch)
		{
			return i;
		}
	}
	return npos;
}

size_t find(const char* str, size_t pos = 0)
{
	assert(pos < _size);
	
	char* p = strstr(_str, str);
	if (p == nullptr)
	{
		return npos;
	}
	return p - _str;
}

八、非成员函数

8.1 relational operators

重载比较关系的运算符

细节:

  1. 一般实现了两个,剩下的都可以复用
  2. this指针用const修饰,保证普通和const的string类都可以相互比较(正着比,反着比都可以)
bool operator==(const string& s) const
{
	return strcmp(_str, s._str) == 0;
}

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

bool operator>(const string& s) const
{
	return strcmp(_str, s._str) > 0;
}

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

8.2 operator<<

重载流插入运算符

细节:遍历字符串,可以采用下标+[ ]的循环形式,也可以使用范围for

ostream& operator<<(ostream& out, const string& s)
{
	for (auto& ch : s)
	{
		out << ch;
	}
	return out;
}

8.3 operator>>

重载流提取运算符

细节:

  1. 每次流插入之前,先清理字符串,防止写入的内容连接在之前的内容后面
  2. 提取字符时使用get函数。因为>>运算符在缓冲区中提取字符时,会自动忽略空格和换行,而get函数可以全部提取出来。
istream& operator>>(istream& in, string& s)
{
	s.clear();

	char ch = in.get();
	while (ch != ' ' && ch != '\n')
	{
		s += ch;
		ch = in.get();
	}
	return in;
}

以上代码是能够完成功能的实现,但是从效率的角度考虑,还是不够高效。所以,我们可以优化一下

  1. 创建一个小型字符数组buf
  2. 提取的字符先填充到buf
  3. 等buf填充满后,再将buf尾插到s
  4. 如果循环结束,buf中还有剩余字符,则再尾插到s
istream& operator>>(istream& in, string& s)
{
	s.clear();
	
	char ch = in.get();
	size_t i = 0;
	char buf[128] = { 0 };
	while (ch != ' ' && ch != '\n')
	{
		buf[i++] = ch;
		if(i == 127)
		{
			s += buf;
			i = 0;
		}
		ch = in.get();
	}

	if (i != 0)
	{
		s += buf;
	}
	return in;
}

总结

我们来模拟实现string类,不是为了造一个更好的轮子,而是熟练掌握重点函数的功能与应用,顺便巩固之前学习的C++语法。常言道,没学过STL,那你根本没学过C++!C++的梦幻之旅,才刚刚开始……

看到这里了还不给博主扣个: ?? 点赞??收藏 ?? 关注! 💛 💙 💜 ?? 💚💓 💗 💕 💞 💘 💖
拜托拜托这个真的很重要! 你们的点赞就是博主更新最大的动力! 有问题可以评论或者私信呢秒回哦。

文章来源:https://blog.csdn.net/2301_79188764/article/details/135589810
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。