【C++】：STL中的string类的增删查改的底层模拟实现

本篇博客仅仅实现存储字符(串)的string
同时由于C++string库设计的不合理，我仅实现一些最常见的增删查改接口
接下来给出的接口都是基于以下框架：

private:
		char* _str;//思考如何不用const
		size_t _size;
		size_t _capacity;
		//这样写可以
		const static size_t string::npos = -1;
		//下面这种写法也可以->和上述写法产生矛盾
		const static size_t string::npos;
	};
	//静态变量只能在类外面定义 上述两种定义容易产生矛盾

📚1.string默认构造 | 析构函数 | 拷贝构造 | 赋值重载

//无参默认构造
string()
	:_str(new char[1])
	, _size(0)
	, _capacity(0)
{
	_str[0] = '\0';
}
//有参默认构造
string(const char* str="\0")//不能写'\0'
	//->类型不匹配
	:_size(strlen(str))
{
	_capacity = _size;
	_str = new char[_capacity + 1];
	strcpy(_str, str);
}

C++string标准库中，无参构造并不是空间为0，直接置为空指针 而是开一个字节，并存放‘\0’
C++中支持无参构造一个对象后，直接在后面插入数据，也从侧面说明了这点
由于C++构造函数不管写不写都会走初始化列表的特性，所以这里也走初始化列表
string中，_capacity和_size都不包含空指针，所以带参构造要多开一个空间，用来存储’\0’

📚2.string类析构函数

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

📚3.拷贝构造

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

📚4.赋值重载

传统写法：

string& operator=(const string& s)
{
	if (this != &s)
	{
		char* tmp = new char[s._capacity + 1];
		strcpy(tmp, s._str);
		delete[] _str;
		_str = tmp;
		_size = s._size;
		_capacity = s._capacity;
	}
	return *this;
}

现代写法：

//法二
void swap(string& s)
{
	std::swap(_str, s._str);
	std::swap(_size, s._size);
	std::swap(_capacity, s._capacity);
}
string& operator=(string tmp)
{
	swap(tmp);
	return *this;
}

📚5.iterator迭代器和基于范围的for循环

在C++中，范围for在底层是通过迭代器来实现的 所以只要实现了迭代器，就支持范围for
而迭代器类似于指针，迭代器可以被看作是指针的一种泛化，它提供了类似指针的功能，可以进行解引用操作、指针运算等
以下提供了const迭代器和非const迭代器：

typedef char* iterator;
const typedef 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;
}

📚6.运算符重载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];
}

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

bool operator>(const string& s)
{
	return strcpy(_str, s._str) == 0;
}
bool operator==(const string& s)
{
	return strcpy(_str, s._str) == 0;
}
bool operator>=(const string& s)
{
	return *this > s || *this == s;
}
bool operator<(const string& s)
{
	return !(*this >= s);
	//return strcpy(_str, s._str) == 0;
}
bool operator!=(const string& s)
{
	return !(*this == s);
}

这里我用了this指针指向的是private里面的数据 然后和s对象所对应的值作比较 能和strcpy函数联合起来用 能达到同样的效果 这是一个很不错的想法

📚7.容量相关：size | resize | capacity | reserve

size_t size()const
{
	return _size;
}
size_t capacity()const
{
	return _capacity;
}

在C++中，我们一般不缩容
所以实现reserve时容量调整到n首先判断目标容量n是否大于当前容量。如果小于就不做处理，否则先开辟n+1个内存空间（多出来的一个用于存储‘\0’），然后将原有数据拷贝到新空间strcpy会将’\0’一并拷贝过去然后释放就空间，并让_str指向新空间，同时更新_capacity

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

当n<_size时，只需将下标为n的地址处的数据改为’\0’
其他情况，我们直接统一处理。直接复用reserve()函数将_capacity扩到n 然后用将[_size, n)中的数据全部初始化为ch 这里博主给ch一个初始值’\0’，但ch不一定为’\0’，所以要将下标为n处的地址初始化为’\0’

void resize(size_t n, char ch='\0')
{
	if (n <= _size)
	{
		_str[n] = '\0';
		_size = n;
	}
	else
	{
		reserve(n);
		while (_size < n)
		{
			_str[_size] = ch;
			_size++;
		}
		_str[_size] = '\0';
	}
}

📚8.数据相关：push_back | append | operator+= | insert | erase

尾插：push_back
尾插首先检查扩容，在插入数据

void push_back(char ch)
{
	//扩容
	if (_size == _capacity)
	{
		reserve(_capacity == 0 ? 4 : _capacity * 2);
	}
	//插入数据
	_str[_size] = ch;
	_size++;
	_str[_size] = '\0';

}

append尾部插入字符串

void append(const char* str)
{
	size_t len = strlen(str);
	if (_size + len > _capacity)
	{
		reserve(_size + len);
	}
	strcpy(_str + _size, str);
	//strcat(_str, str);
	_size += len;
}

operator+=()字符/字符串
operator+=()字符、字符串可以直接复用push_back和append

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

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

insert插入字符/字符串
下面给出各位初学者容易犯的错误：

void insert(size_t pos, char ch)
{
	assert(pos <= _size);
	//扩容
	if (_size == _capacity)
	{
		reserve(_capacity == 0 ? 4 : _capacity * 2);
	}
	//挪动数据
	size_t end = _size;
	while (end >= pos)
	{
		_str[end+1] = _str[end];
		end--;
	}
	_str[pos] = ch;
	_size++
}

假设是在头插字符，end理论上和pos(即0)比较完后就减到-1，在下一次循环条件比较时失败，退出循环 但遗憾的是end是size_t类型，始终>=0, 会导致死循环
解决办法如下
从end从最后数据的后一位开始，每次将前一个数据移到当前位置。最后条件判断就转化为end>pos，不会出现死循环这种情况

void insert(size_t pos, char ch)
{
	assert(pos <= _size);
	//扩容
	if (_size == _capacity)
	{
		reserve(_capacity == 0 ? 4 : _capacity * 2);
	}
	//挪动数据
	size_t end = _size+1;
	while (end > pos)
	{
		_str[end] = _str[end-1];
		end--;
	}
	//插入数据，更新_size
	_str[pos] = ch;
	_size++;
}

insert插入字符串

void insert(size_t pos, const char* str)
{
	int 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;
}

erase
erase分两种情况：
从pos开始，要删的数据个数超过的字符串，即将pos后序所有数据全部情况 直接将pos处数据置为’\0’即可
从pos开始，要删的数据个数没有超出的字符串。所以只需要从pos+len位置后的所有数据向前移动从pos位置覆盖原数据即可

void erase(size_t pos, size_t len = npos)
{
	//len==nppos意思是字串全部删除
	if (len==npos || pos + len >= _size)
	{
		//有多少，删多少
		_str[pos] = '\0';
		_size = pos;
	}
	else
	{
		size_t begin = pos + len;
		while (begin <= _size)
		{
			_str[begin - len] = _str[begin];
			begin++;
		}
		_size -= len;
	}
}

📚9.关系操作符重载：< | == | <= | > | >= | !=

bool operator>(const string& s)
{
	return strcpy(_str, s._str) == 0;
}
bool operator==(const string& s)
{
	return strcpy(_str, s._str) == 0;
}
bool operator>=(const string& s)
{
	return *this > s || *this == s;
}
bool operator<(const string& s)
{
	return !(*this >= s);
	//return strcpy(_str, s._str) == 0;
}
bool operator!=(const string& s)
{
	return !(*this == s);
}

📚10.find查找字符 | 字符串 | substr

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

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

strsub()模拟实现
strsub目标长度可能越界string，也可能还有没有。但不管是那种情况，最后都需要拷贝数据。所以这里我们可以先将len真实长度计算出来，在拷贝数据

string substr(size_t pos, size_t len = npos)const
{
	string s;
	size_t end = pos + len;
	//目标字符越界string,更新len
	if (len == npos || end >= _size)
	{
		len = _size - pos;
		end = _size;
	}
	//拷贝数据
	s.reserve(len);
	for (size_t i = pos; i < end; i++)
	{
		s += _str[i];
	}
	return s;
}

📚11.流插入和流提取<< | >>

由于前面我们实现了迭代器，所以最简单的方式就是范围for

ostream& operator<<(ostream& out, const string& s)
{
	/*for (size_t i = 0; i < s.size(); i++)
	{
		out << s[i];
	}*/
	for (auto ch : s)
		out << ch;
	return out;
}

流提取>>
流提取比较特殊。在流提取前需要将原有数据全部清空。同时由于>>无法获取空字符和换行符()(都是作为多个值之间的间隔)，直接流提取到ostream对象中，没法结束类似于C语言中scanf, 换行符和空字符仅仅只是起到判断结束的作用，但scanf无法获取到它们
所以这里博主直接调用istream对象中的get()函数类似于C语言中的getchar()函数

class string
{
	void clear()
	{
		_str[0] = '\0';
		_size = 0;
	}
private:
	char* _str;
	size_t _capacity;
	size_t _size;
};

istream& operator>>(istream& in, string& s)
	{
		s.clear();
		char ch;
		//in >> ch;
		ch = in.get();

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

📚12.完整代码

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<list>
#include<string>
#include<assert.h>
using namespace std;
namespace success
{
	class string
	{
	public:
		typedef char* iterator;
		iterator begin()
		{
			return _str;
		}
		iterator end()
		{
			return _str + _size;
		}
		string()
			:_str(new char[1])
			, _size(0)
			, _capacity(0)
		{
			_str[0] = '\0';
		}
		string(const char* str="\0")//不能写'\0'
			//->类型不匹配
			:_size(strlen(str))
		{
			_capacity = _size;
			_str = new char[_capacity + 1];
			strcpy(_str, str);
		}
		const char* c_str()
		{
			return _str;
		}
		string(const string& str)
			:_size(str._size)
		{
			_capacity = str._capacity;
			_str = new char[str._capacity + 1];
			strcpy(_str, str._str);
		}
		char& operator[](size_t pos) const
		{
			assert(pos < _size);
			return _str[pos];
		}
		size_t size()
		{
			return _size;
		}
		string& operator=(const string& str)
		{
			if (this != &str)
			{
				delete[] _str;
				_str = new char[str._capacity + 1];
				_size = str._size;
				_capacity = str._capacity;
				strcpy(_str, str._str);
			}
			return *this;
		}
		~string()
		{
			delete[] _str;
			_str = nullptr;
			_size = 0;
			_capacity = 0;
		}
		bool operator>(const string& s)
		{
			return strcpy(_str, s._str) == 0;
		}
		bool operator==(const string& s)
		{
			return strcpy(_str, s._str) == 0;
		}
		bool operator>=(const string& s)
		{
			return *this > s || *this == s;
		}
		bool operator<(const string& s)
		{
			return !(*this >= s);
			//return strcpy(_str, s._str) == 0;
		}
		bool operator!=(const string& s)
		{
			return !(*this == s);
		}
		void resize(size_t n, char ch = '\0');
		void reserve(size_t n)
		{
			char* tmp = new char[n + 1];
			strcpy(tmp, _str);
			delete[] _str;
			_str = tmp;
			_capacity = n;
		}
		void push_back(char ch)
		{
			if (_size + 1 > _capacity)
			{			
				reserve(_capacity * 2);
			}
			_str[_size] = ch;
			++_size;
			_str[_size] = '\0';
		}
		void append(const char* str)
		{
			size_t len = strlen(str);
			if (_size + len > _capacity)
			{
				reserve(_size + len);
			}
			strcpy(_str + _size, str);
			//strcat(_str, str);
			_size += len;
		}
		void insert(size_t pos, char ch)
		{
			assert(pos <= _size);
			if (_size + 1 > _capacity)
			{
				reserve(2 * _capacity);
			}
			size_t end = _size;
			while (end >= pos)
			{
				_str[end + 1] = _str[end];
				--end;
			}
			_str[pos] = ch;
			++_size;
		}
		void insert(size_t pos, const char* str)
		{
			int 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;
		}
		void erase(size_t pos, size_t len = npos)
		{
			//len==nppos意思是字串全部删除
			if (len==npos || pos + len >= _size)
			{
				//有多少，删多少
				_str[pos] = '\0';
				_size = pos;
			}
			else
			{
				size_t begin = pos + len;
				while (begin <= _size)
				{
					_str[begin - len] = _str[begin];
					begin++;
				}
				_size -= len;
			}
		}
	private:
		char* _str;//思考如何不用const
		size_t _size;
		size_t _capacity;
		//这样写可以
		const static size_t string::npos = -1;
		//下面这种写法也可以->和上述写法产生矛盾
		const static size_t string::npos;
	};
	//静态变量只能在类外面定义 上述两种定义容易产生矛盾
	void test_string1()
	{
		string s1("hello bit");
		string s2("hello bit.");
		cout << s1.c_str() << endl;
		cout << s2.c_str() << endl;
		s2[0]++;
		cout << s2.c_str() << endl;
	}
	void test_string2()	
	{
		string s3 = ("hello bit");
		string s4("hello bit.");
		cout << s3.c_str() << endl;
		cout << s4.c_str() << endl;
		string s5(s3);
		cout << s5.c_str() << endl;
		s3[0]++;
		s4 = s3;
		cout << s3.c_str() << endl;
		cout << s5.c_str() << endl;
	}

	void test_string3()
	{
		string s1 = "hello bit";
		string::iterator it = s1.begin();
		while (it != s1.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}
}

#include"string.h"
#include<Windows.h>
#include<iostream>
using namespace std;
int main()
{
	try
	{
		success::test_string2();
	}
	catch (const exception& e)
	{
		cout << e.what() << endl;
	}
	success::test_string1();
	success::test_string2();
	success::test_string3();
	//string a = "hello world";
	//string b = a;//在用一个表达式中 构造+拷贝构造
	//->编译器优化成一次构造
	//a.c_str() == b.c_str()比较的是存储字符串位置的地址
	//if (a.c_str() == b.c_str())
	//{
	//	cout << "true" << endl;
	//}
	//else cout << "false" << endl;//案1
	//string c = b;
	//c = "";
	//if (a.c_str() == b.c_str())	
	//{
	//	cout << "true" << endl;
	//}
	//else cout << "false" << endl;
	//a = "";
	//if (a.c_str() == b.c_str())
	//{
	//	cout << "true" << endl;
	//}
	//else cout << "false" << endl;、
	
	
	//string str("Hello Bit.");
	//str.reserve(111);
	//str.resize(5);
	//str.reserve(50);
	//cout << str.size() << ":" << str.capacity() << endl;
	//str.reserve(111); //调整容量为111
	//str.resize(5);   //调整元素个数为5
	//str.reserve(50);  //调整容量为50，由于调整的容量小于已有空间容量，故容量不会减小
	//所以size = 5 capacity = 111


	//string strText = "How are you?";
	//string strSeparator = " ";
	//string strResult;
	//int size_pos = 0;
	//int size_prev_pos = 0;
	//while ((size_pos = strText.find_first_of(strSeparator, size_pos)) != string::npos)
	//{
	//	strResult = strText.substr(size_prev_pos, size_pos - size_prev_pos);
	//	cout << strResult << " ";
	//	size_prev_pos = ++size_pos;
	//}
	//if (size_prev_pos != strText.size())
	//{
	//	strResult = strText.substr(size_prev_pos, size_pos - size_prev_pos);
	//	cout << strResult << " ";
	//}
	//cout << endl;
	system("pause");
	return 0;
}

// 为了和标准库区分，此处使用String
class String
{
public:
/*String()
:_str(new char[1])
{*_str = '\0';}
*/
//String(const char* str = "\0") 错误示范
//String(const char* str = nullptr) 错误示范
String(const char* str = "")
{
// 构造String类对象时，如果传递nullptr指针，可以认为程序非
if (nullptr == str)
{
assert(false);
return;
}
_str = new char[strlen(str) + 1];
strcpy(_str, str);
}
~String()
{
if (_str)
{
delete[] _str;
_str = nullptr;
}
}
private:
char* _str;
};
// 测试
void TestString()
{
String s1("hello bit!!!");
String s2(s1);
}

说明：上述String类没有显式定义其拷贝构造函数与赋值运算符重载，此时编译器会合成默认的，当用s1构造s2时，编译器会调用默认的拷贝构造。最终导致的问题是，s1、s2共用同一块内存空间，在释放时同一块空间被释放多次而引起程序崩溃，这种拷贝方式，称为浅拷贝
浅拷贝
浅拷贝：也称位拷贝，编译器只是将对象中的值拷贝过来。如果对象中管理资源，最后就会导致多个对象共享同一份资源，当一个对象销毁时就会将该资源释放掉，而此时另一些对象不知道该资源已经被释放，以为还有效，所以当继续对资源进项操作时，就会发生发生了访问违规
深拷贝
如果一个类中涉及到资源的管理，其拷贝构造函数、赋值运算符重载以及析构函数必须要显式给出。一般情况都是按照深拷贝方式提供

传统版写法的String类

class String
{
public:
String(const char* str = "")
{
// 构造String类对象时，如果传递nullptr指针，可以认为程序非
if (nullptr == str)
{
assert(false);
return;
}
_str = new char[strlen(str) + 1];
strcpy(_str, str);
}
String(const String& s)
: _str(new char[strlen(s._str) + 1])
{
strcpy(_str, s._str);
}
String& operator=(const String& s)
{
if (this != &s)
{
char* pStr = new char[strlen(s._str) + 1];
strcpy(pStr, s._str);
delete[] _str;
_str = pStr;
}
return *this;
}
~String()
{
if (_str)
{
delete[] _str;
_str = nullptr;
}
}
private:
char* _str;
};

现代版写法的String类

class String
{
public:
String(const char* str = "")
{
if (nullptr == str)
{
assert(false);
return;
}
_str = new char[strlen(str) + 1];
strcpy(_str, str);
}
String(const String& s)
: _str(nullptr)
{
String strTmp(s._str);
swap(_str, strTmp._str);
}
// 对比下和上面的赋值那个实现比较好？
String& operator=(String s)
{
swap(_str, s._str);
return *this;
}
/*
String& operator=(const String& s)
{
if(this != &s)
{
String strTmp(s);
swap(_str, strTmp._str);
}
return *this;
}
*/
~String()
{
if (_str)
{
delete[] _str;
_str = nullptr;
}
}
private:
char* _str;
};

写时拷贝就是一种拖延症，是在浅拷贝的基础之上增加了引用计数的方式来实现的
引用计数：用来记录资源使用者的个数。在构造时，将资源的计数给成1，每增加一个对象使用该资源，就给计数增加1，当某个对象被销毁时，先给该计数减1，然后再检查是否需要释放资源，如果计数为1，说明该对象时资源的最后一个使用者，将该资源释放；否则就不能释放，因为还有其他对象在使用该资源
文章来源地址https://www.toymoban.com/news/detail-753754.html

到了这里，关于【C++】：STL中的string类的增删查改的底层模拟实现的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！