【C++干货基地】解构C++标准库中string的内存自动释放分配的设计与实现原理

举报
鸽芷咕 发表于 2024/04/30 12:32:27 2024/04/30
【摘要】 C++ string类是如何完美解决自动扩容与缩小的,其设计原理和实现源码大致是怎样?今天我们就带大家进一步模拟实现string的底层实现。

引入

  哈喽各位铁汁们好啊,我是博主鸽芷咕《C++干货基地》是由我的襄阳家乡零食基地有感而发,不知道各位的城市有没有这种实惠又全面的零食基地呢?C++ 本身作为一门篇底层的一种语言,世面的免费课程大多都没有教明白。所以本篇专栏的内容全是干货让大家从底层了解C++,把更多的知识由抽象到简单通俗易懂。

一、string的介绍

以往我们C语言中字符串存储一般都是在数组中,但字符数组的空是固定的如果想要使用堆空间还要我们自己对内存来进行控制。一不留神就容易出现bug,而string就提前为什么封装好了所有接口让我们无需对这些关心。

在这里插入图片描述

string是C++中专门为字符封装的一个标准库,是一个专门用于存储字符的顺序表,或者叫线性表。

  • 它可以自动实现扩容检查越界,自动申请内存等等

二、string的实现原理

2.1 string结构有哪些

STL发展这么长时间,每一个厂商都对STL的设计大不相同,比如微软的 vs 与 Linux 下的 GCC 编译器库的实现方式就不一样但是实现的接口功能都是一样的。

  •  所以我们今天就选择可读性更高的设计来进行封装string
class string
	{

	private:
		char* _str;
		int _size;
		int _capacity;
	};

2.2 string的成员函数

构造函数的实现

构造函数的实现,一般我们使用 string 都是用字符串去创建的或者创建一个空对象。

  • 所以我们把这俩种情况都写生缺省参数合并到一起。
  • 要注意实际的容量比capacity +1 这个一是用来存放"\0"的;
class string
	{
	public:
		string(const char* str= "")
			:_size(strlen(str))
		{
			_capacity = _size;
			_str = new char[_capacity + 1];
			strcpy(_str, str);
		}


	private:
		char* _str = nullptr;
		int _size = 0;
		int _capacity = 0;
	};

析构函数

析构函数就很简单只需要把我们前面所申请的空间释放就可以了

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

拷贝构造

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

2.3 成员变量的访问

string的大小size()

size_t size()
{
	return _size;
}

string的容量capacity()

size_t capacity()const
{
	return _capacity;
}

c_str() 返回 C形式的string指针

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

operator[ ]方括号访问

这里就要注意好 const类型的string 访问和非 const string 对象的访问和重载了。

char& operator[](int pos) 
{
	assert(pos < _size);
	return _str[pos];
}

const char& operator[](int pos) const
{
	assert(pos < _size);
	return _str[pos];
}

operator= 赋值操作

这里我们注意好深拷贝以及俩种重载情况

string& operator=(const char* str)
{
	int len = strlen(str);
	if (_capacity < (_size + len))
	{
		reserve(_size + len);
	}

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

	return *this;
}

string& operator=(string& str)
{
	int len = str.size();
	if (_capacity < (_size + len))
	{
		reserve(_size + len);
	}

	_size = _size + len;
	strcpy(_str, str._str);
	
	return *this;
}

2.3 string的遍历

迭代器的底层实现

迭代器是一种行为上类似的指针的的东西,其具体的实现方法并不是指针。但是string较为简单所以我们选择使用指针来实现迭代器

begin() && end()

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.4 容量相关操作

reserve 扩容

reserve这个接口我们会经常使用,如果请求的长度大于 _capacity 就会为其扩容如果小于 _capacity 的话就不进行操作


void reserve(int newCapacity)
{
	if (_capacity < newCapacity)
	{
		char* tmp = new char[newCapacity];
		strcpy(tmp, _str);
		delete[] _str;
		_str = tmp;
		_capacity = newCapacity;
	}
}

resize 将字符串缩小n个大小

resize的作用是如果我们输入的n 小与 string的大小就会缩短字符串到n的大小。

  • 还可以让字符串大小扩大,其中扩大的空间填充指定字符
void resize(size_t n,char c = '\0')
		{
			if (n < _size)
			{
				_str[n] = '\0';
				_size = n;
			}
			else
			{
				reserve(n);
				while (_size < n)
				{
					_str[_size++] = c;
				}
				_str[_size] = '\0';
			}
		}

clear() 清除当前字符串

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

empty 判空

bool empty()
{
	return _size == 0;
}

2.5 修改方面的实现

insert 插入

string& insert(size_t pos, const char* ch)
{
	assert(pos <= _size);
	int len = strlen(ch);
	if (_size + len > _capacity)
	{
		reserve(_size + len);
	}
	
	int end = _size + len;
	while (end > pos + len - 1)
	{
		_str[end--] = _str[end-len];
	}

	for (int i = 0; i < len; i++)
	{
		_str[pos++] = ch[i];
	}
	return *this;

}

string& insert(size_t pos, const string& str)
{
	assert(pos <= _size);
	int len = str.size();
	if (_size + len > _capacity)
	{
		reserve(_size + len);
	}

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

	for (int i = 0; i < len; i++)
	{
		_str[pos++] = str[i];
	}

	return *this;

}

string& insert(size_t pos, const char c)
{
	assert(pos <= _size);
	if (_size == _capacity)
	{
		reserve(_capacity == 0 ? 4 : _capacity * 2);
	}

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

	_str[pos] = c;
	return *this;
}

append 追加

追加就很简单了,我们可以直接复用 insert 来进行追加

string& append(const char* str)
{
	insert(_size, str);
	return *this;
}
string& append(const string& str)
{
	insert(_size, str);
	return *this;

}
string& append(const char c)
{
	insert(_size, c);
	return *this;
}

assgin 为字符串赋一个新的值

string& assign(const string& str)
{
	string tmp(str);
	swap(tmp);

	return *this;
}

push_back

string& push_back(const char c)
		{
			insert(_size, c);
			return *this;
		}

replace 替换

string& replace(size_t pos, size_t n, const char* s)
		{
			int len = strlen(s);
			if (_size + len > _capacity)
			{
				reserve(_size + len);
			}

			int end = _size + len - n;
			while (end > pos + len-n)
			{
				_str[end--] = _str[end - len + n];
			}

			for (int i = 0; i < len; i++)
			{
				_str[pos++] = s[i];
			}

			return *this;
			
		}

erase 消除一部分字符

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

	return *this;
}

2.6 string字符串操作

find() 查找

size_t find(const char c,int pos = npos)  const
{
	for (int i = 0; i < _size; i++)
	{
		if (_str[i] == c)
		{
			return i;
		}
	}
	return pos;
}

size_t find(const char* sub, size_t pos = 0) const
{
	assert(pos < _size);

	char* p = strstr(_str + pos, sub);
	if (p)
	{
		return p - _str;
	}
	else
	{
		return npos;
	}
}

substr 返回一个子串的 string 对象

string substr(size_t pos = 0, size_t len = npos) const
{
	string sub;
	if (len > _size - pos)
	{
		for (int i = pos; i < _size; i++)
		{
			sub  += _str[i];
		}
	}
	else
	{

		for (size_t i = pos; i < pos + len; i++)
		{
			sub += _str[i];
		}
	}

	return sub;
}

string比较


	bool operator==(string& s1, string& s2)
	{
		bool ret = strcmp(s1.c_str(), s2.c_str());
		return ret;
	}
	bool operator<(string& s1, string& s2)
	{
		bool ret = strcmp(s1.c_str(), s2.c_str());
		return ret;
	}

	bool operator<=(string& s1, string& s2)
	{
		
		return s1 < s2 || s1 == s2;
	}
	bool operator!=(string& s1, string& s2)
	{

		return !(s1 == s2);
	}
	bool operator > (string& s1, string& s2)
	{

		return !(s1 <= s2);
	}
	bool operator>=(string& s1, string& s2)
	{

		return !(s1 < s2);
	}

<< >> 插入输出流重载

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

		return out;
	}

	
	istream& operator>> (istream& in, string& str)
	{
		str.clear();

		char ch;
		ch = in.get();
		char buff[128];
		size_t i = 0;
		while (ch != '\n' && ch != ' ')
		{
			buff[i++] = ch;
			if (i == 127)
			{
				buff[127] = '\0';
				str += buff;
				i = 0;
			}
		}

		if (i > 0)
		{
			buff[i] = '\0';
			str += buff;
		}

		return in;
	}

getline 读取字符串

istream& getline(istream& in, string& s)
	{
		s.clear();

		char ch;
		//in >> ch;
		ch = in.get();
		char buff[128];
		size_t i = 0;
		while (ch != '\n')
		{
			buff[i++] = ch;
			// [0,126]
			if (i == 127)
			{
				buff[127] = '\0';
				s += buff;
				i = 0;
			}

			ch = in.get();
		}

		if (i > 0)
		{
			buff[i] = '\0';
			s += buff;
		}

		return in;
	}

在这里插入图片描述

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。