C++模拟string类的底层实现-前言: 本篇模拟string类的底层实现,只会调一些重要的接口实现,结尾附上完整代码。

时间:2024-04-09 12:05:27

1.成员变量

	private:
		//const char* _str
		//不使用const修饰,string类的字符串是可以修改的,而且例如扩容的时候也需要修改指针的指向
		// 然后就是_str的初始化是最好new出来的,如果直接初始化为空指针,例如在流插入的时候需要解引用,就不行了。		
		char* _str;
		size_t _capacity;
		size_t _size;

		//static const size_t npos=-1;//静态成员变量要在类外声明初始化,不能给缺省值,但是如果加上const,又支持这样给缺省值的语法了
		static const size_t npos;

首先注意的就是_str,不能是const类型的,因为我们的string字符串是可以改的,而且如果是const类型的,在扩容等也需要改变指针的指向;而且我们在流插入的时候解引用,所以在初始化的时候最好是new出来的。

静态成员常量npos需要在类外声明初始化,注意的是,本来静态成员变量是不能给缺省值的,但是加上了const就又可以给缺省值了。

 

2.构造函数与拷贝构造函数

		string(const char* str="")//strlen遇到字符0就停了,这样传参数也正好,无参的size也是0,或者写成"\0",但是不能写成'\0'类型不匹配
			:_size(strlen(str))//strlen内部获取字符串长度是需要解引用的,所以最好初始化不要给空指针,
		{
			_capacity = _size == 0 ? 3 : _size;
			_str = new char[_capacity + 1];//+1给字符0准备,实际capacity没有字符0
			strcpy(_str, str);
		}

	    string(const string& st)
			:_size(st._size)
			,_capacity(st._capacity)
		{
			_str = new char[st._capacity + 1];//+1给字符0准备,实际capacity没有字符0
			strcpy(_str, st._str);
		}

构造的参数这样写是因为这样传参数相当于无参的构造只有一个字符0,正好符合strlen计算长度的规则,无参的时候_size就是0了。

_capacity需要判断是否为0,不然什么都没有直接二倍扩容会出错。

_str的容量加1是给字符0准备的,但是实际_size与_capacity是没有计算字符0的,而且在调试的时候也看不到,但是还是要加上。

构造的思路就是根据传参字符串的的容量开一块新的空间,进行拷贝完成初始化。

拷贝构造就是深拷贝了,所以就是根据要拷贝的对象的大小开一块空间,再让空间拷贝给给调用的对象,注意容量与大小也要变。

3.析构函数

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

注意配套使用delete就行。

 

4.赋值重载

		string& operator=(const string& st)
		{
			//这样写如果new出错了,原来的对象也被破坏了
			//delete[] _str;
			//_str = new char[st._capacity + 1];
			//strcpy(_str, st._str);
			//_capacity = st._capacity;
			//_size = st._size;


			if (this != &st)
			{
				char* tmp = new char[st._capacity + 1];
				strcpy(tmp,st._str);
				delete[] _str;
				_str = tmp;

				_capacity = st._capacity;
				_size = st._size;

				return *this;
			}
		}

赋值重载就要考虑空间的问题了,同时也是一个深拷贝。

假设s1=s2,如果s1容量多,直接将s2赋值过去没问题,但是会造成空间的浪费。

如果s1的空间少,此时再将s2赋值就会出现问题了,所以综合一下:先让原空间也就是被赋值的空间给释放掉,然后再根据赋值的内容开辟空间,让被赋值的指向这块新的空间,再进行拷贝,并完成大小和容量的更新。

上面的为注释的写法,但是还有一点问题,如果new失败了,那被赋值的空间早已被释放了,这就破坏了原来的空间,所以为了不破坏原有的空间,先根据赋值的内容开一块空间,再将赋值的内容拷贝给这块空间,此时再释放旧空间,再将旧空间指向新空间即可。

注意要判断自己不能给自己赋值。

5.[]重载

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

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

注意断言,下标位置不能等于_size,_size指向最后一个字符的下一个也就是字符0,但是实际库中的string的字符0我们是可以访问到的,这里主要表示有效数据的访问。

要提供两个版本,方便const对象调用。 

6.比较关系重载

		 //string比较
		 bool operator>(const string& st) const
		 {
			 return strcmp(_str, st._str) > 0;
		 }

		 bool operator==(const string& st) const
		 {
			 return strcmp(_str, st._str) == 0;
		 }
		 
		 bool operator>=(const string& st) const
		 {
			 return *this > st || *this == st;//如果不用const修饰==的重载,这里调用就不能st==*this了,因为st是const类型的		 
		 }

		 bool operator<(const string& st) const
		 {
			 return !(*this >= st);
		 }

		 bool operator<=(const string& st) const
		 {
			 return !(*this > st);
		 }

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

这个没什么好说的了,就是写两个复用就完了。

注意没有修改成员变量的成员函数最好还是就是const,像>=复用==的逻辑的时候,如果==不是const的成员函数,就不能倒过来写了。 

7.reserve

		 void reserve(size_t n)
		 {
			 if (n > _capacity)//如果n小于这块空间,相当于缩容了,原字符串再拷贝给缩容的空间就越界了
			 {
				 char* tmp = new char[n + 1];//这里一样是放在原对象被破坏,+1用来存放字符0
				 strcpy(tmp, _str);
				 delete[] _str;
				 _str = tmp;

				 _capacity = n;//但是capacity实际还是没有字符0的
			 }

注意判断扩容的大小不能小于原有的容量,不然就是缩容了,缩容再拷贝数据就越界了。

8.resize

		 void resize(size_t n, char ch = '\0')
		 {
			 if (n <= _capacity)
			 {
				 //保留前n个数据
				 _size = n;
				 _str[_size] = '\0';
			 }
			 else
			 {
				 if (n > _capacity)
				 {
					 reserve(n);
				 }

				 size_t i = _size;//直接在后面补初始化的数据
				 while (i < n)
				 {
					 _str[i] = ch;
					 ++i;
				 }

				 _size = n;
				 _str[_size] = '\0';
			 }
		 }

如果扩容大小小于容量,那就保留前n个数据,末尾改成字符0。

如果大,那就扩容,原有数据不变,扩容后面的数据都默认初始化为字符0。如果传的有参数,就往末尾补数据,最后别忘了更新size,还要在最后补字符0。

9.push_back,append和重载+=

		 void push_back(char ch)
		 {
			 if (_size + 1 > _capacity)
			 {
				 reserve(_capacity * 2);
			 }

			 _str[_size] = ch;
			 ++_size;
			 _str[_size] = '\0';//插入完了,字符串后面的字符0就找不到了,所以size更新完后再补一个字符0

			 //复用insert
			 //insert(_size,ch)
		 }

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

			 strcpy(_str + _size, str);//正好覆盖了原字符串的字符0
			 _size += len;

			 //复用insert
			 //insert(_size,str)
		 }
		 string& operator+=(char ch)
		 {
			 push_back(ch);
			 return *this;
		 }

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

注意尾插一个字符时的字符0的补充以及扩容即可。 

 

10.insert

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

		 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 + len;
			 while (end >pos+len-1)
			 {
				 _str[end] = _str[end - len];
				 --end;
			 }
			 strncpy(_str + pos, str, len);
			 _size += len;
			 return *this;

		 }

这个建议画图理解,也一样先扩容。

注意断言,在等于size的时候插入就是尾插入,不用添加字符0,直接交换了,注意pos是下标。 

11.erase

		 string& erase(size_t pos, size_t len = npos)//删除pos位置(包括pos位置)后的len个字符,如果不够删,就删完
		 {
			 assert(pos < _size);
			 if (len == npos || pos + len >= _size)
			 {
				 _str[pos] = '\0';//pos也被删了
				 _size = pos;
			 }
			 else
			 {
				 strcpy(_str + pos, _str + pos + len);
				 _size -= len;
			 }

			 return *this;
		 }

当等于缺省值的时候或者要删的字符正好删到了最后一个有效数据,直接就是在pos的位置放字符0,更新size就行了(注意pos位置的值也被删了)。

如果没有删完,就将删除后右边的子串与原字符串连接起来,更新size。 

12.find

		 size_t find(char ch, size_t pos=0)//pos为0就是代表找这个字符出现的第一个位置,返回下标;为1就是返回出现第二次的位置的下标
		 {
			 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)
		 {
			 char* p = strstr(_str + pos, str);//找子串可以使用暴力的kmp,但是实际作用不大,还有BM算法;strstr使用的是暴力的算法
			 if (p == nullptr)
			 {
				 return npos;
			 }
			 else
			 {
				 return p - _str;
			 }
		 }

 查找字符就是遍历一遍就行了,查找字符串需要使用strstr或者算法,也就是查找子串,strstr返回的是子串的首元素位置。

 

14.迭代器

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

对指针的重命名,后面容器的实现更复杂,后面再说。

注意还有const迭代器,供const对象调用,这里分开划分const成员与非const成员函数主要是因为我们使用普通迭代器大部分会修改数据。 

15.流插入,流提取重载

	ostream& operator<<(ostream& out, const string& s)
	{
		for (auto ch : s)
		{
			out << ch;//有些编译器会让字符0打印成空格
		}

		return out;
	}

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

			ch = in.get();
		}

		if (i != 0)//防止后面还有数据没填
		{
			buff[i] = '\0';
			s += buff;
		}

		return in;
	}

注意不是友元,没有访问类的成员。 

16.swap

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

直接复用即可,如果直接写调用要写成s1.swap(s2),会有两个对象三个深拷贝。 

17.c_str

		const char* c_str()
		{
			return _str;
		}

直接返回首字符地址,注意是const类型的。 

18.完整代码+测试

#pragma once
#include <string>
#include <string.h>
#include <assert.h>
#include <iostream>

using namespace std;

namespace my_string
{
	class string
	{
	public:
		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;
		}

		string(const char* str="")//strlen遇到字符0就停了,这样传参数也正好,无参的size也是0,或者写成"\0",但是不能写成'\0'类型不匹配
			:_size(strlen(str))//strlen内部获取字符串长度是需要解引用的,所以最好初始化不要给空指针,
		{
			_capacity = _size == 0 ? 3 : _size;
			_str = new char[_capacity + 1];//+1给字符0准备,实际capacity没有字符0
			strcpy(_str, str);
		}

	    string(const string& st)
			:_size(st._size)
			,_capacity(st._capacity)
		{
			_str = new char[st._capacity + 1];//+1给字符0准备,实际capacity没有字符0
			strcpy(_str, st._str);
		}

		string& operator=(const string& st)
		{
			//这样写如果new出错了,原来的对象也被破坏了
			//delete[] _str;
			//_str = new char[st._capacity + 1];
			//strcpy(_str, st._str);
			//_capacity = st._capacity;
			//_size = st._size;


			if (this != &st)
			{
				char* tmp = new char[st._capacity + 1];
				strcpy(tmp,st._str);
				delete[] _str;
				_str = tmp;

				_capacity = st._capacity;
				_size = st._size;

				return *this;
			}
		}

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

		const char* c_str()
		{
			return _str;
		}

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

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

		 size_t size() const//size和capacity实际都没有算字符0,但是在string里面实际是有这个字符0的,但是调试是看不到的
		 {
			 return _size;
		 }

		 size_t capacity() const
		 {
			 return _capacity;
		 }

		 //string比较
		 bool operator>(const string& st) const
		 {
			 return strcmp(_str, st._str) > 0;
		 }

		 bool operator==(const string& st) const
		 {
			 return strcmp(_str, st._str) == 0;
		 }
		 
		 bool operator>=(const string& st) const
		 {
			 return *this > st || *this == st;//如果不用const修饰==的重载,这里调用就不能st==*this了,因为st是const类型的		 
		 }

		 bool operator<(const string& st) const
		 {
			 return !(*this >= st);
		 }

		 bool operator<=(const string& st) const
		 {
			 return !(*this > st);
		 }

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

		 void reserve(size_t n)
		 {
			 if (n > _capacity)//如果n小于这块空间,相当于缩容了,原字符串再拷贝给缩容的空间就越界了
			 {
				 char* tmp = new char[n + 1];//这里一样是放在原对象被破坏,+1用来存放字符0
				 strcpy(tmp, _str);
				 delete[] _str;
				 _str = tmp;

				 _capacity = n;//但是capacity实际还是没有字符0的
			 }
		 }

		 void push_back(char ch)
		 {
			 if (_size + 1 > _capacity)
			 {
				 reserve(_capacity * 2);
			 }

			 _str[_size] = ch;
			 ++_size;
			 _str[_size] = '\0';//插入完了,字符串后面的字符0就找不到了,所以size更新完后再补一个字符0

			 //复用insert
			 //insert(_size,ch)
		 }

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

			 strcpy(_str + _size, str);//正好覆盖了原字符串的字符0
			 _size += len;

			 //复用insert
			 //insert(_size,str)
		 }

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

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

		 void resize(size_t n, char ch = '\0')
		 {
			 if (n <= _capacity)
			 {
				 //保留前n个数据
				 _size = n;
				 _str[_size] = '\0';
			 }
			 else
			 {
				 if (n > _capacity)
				 {
					 reserve(n);
				 }

				 size_t i = _size;//直接在后面补初始化的数据
				 while (i < n)
				 {
					 _str[i] = ch;
					 ++i;
				 }

				 _size = n;
				 _str[_size] = '\0';
			 }
		 }

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

		 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 + len;
			 while (end >pos+len-1)
			 {
				 _str[end] = _str[end - len];
				 --end;
			 }
			 strncpy(_str + pos, str, len);
			 _size += len;
			 return *this;

		 }

		 string& erase(size_t pos, size_t len = npos)//删除pos位置(包括pos位置)后的len个字符,如果不够删,就删完
		 {
			 assert(pos < _size);
			 if (len == npos || pos + len >= _size)
			 {
				 _str[pos] = '\0';//pos也被删了
				 _size = pos;
			 }
			 else
			 {
				 strcpy(_str + pos, _str + pos + len);
				 _size -= len;
			 }

			 return *this;
		 }

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

		 size_t find(char ch, size_t pos=0)//pos为0就是代表找这个字符出现的第一个位置,返回下标;为1就是返回出现第二次的位置的下标
		 {
			 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)
		 {
			 char* p = strstr(_str + pos, str);//找子串可以使用暴力的kmp,但是实际作用不大,还有BM算法;strstr使用的是暴力的算法
			 if (p == nullptr)
			 {
				 return npos;
			 }
			 else
			 {
				 return p - _str;
			 }
		 }
		 
		 void clear()
		 {
			 _str[0] = '\0';
			 _size = 0;
		 }
	private:
		//const char* _str
		//不使用const修饰,string类的字符串是可以修改的,而且例如扩容的时候也需要修改指针的指向
		// 然后就是_str的初始化是最好new出来的,如果直接初始化为空指针,例如在流插入的时候需要解引用,就不行了。		
		char* _str;
		size_t _capacity;
		size_t _size;

		//static const size_t npos=-1;//静态成员变量要在类外声明初始化,不能给缺省值,但是如果加上const,又支持这样给缺省值的语法了
		static const size_t npos;

	};

	const size_t string::npos = -1;

	ostream& operator<<(ostream& out, const string& s)
	{
		for (auto ch : s)
		{
			out << ch;//有些编译器会让字符0打印成空格
		}

		return out;
	}

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

			ch = in.get();
		}

		if (i != 0)//防止后面还有数据没填
		{
			buff[i] = '\0';
			s += buff;
		}

		return in;
	}

	void test_string1()
	{
		string s1;
		string s2("hello world");

		cout << s1.c_str() << endl;
		cout << s2.c_str() << endl;

		s2[0]++;
		cout << s2.c_str() << endl;
	}

	void test_string2()
	{
		string s1;
		string s2("hello world");
		string s3(s2);//经典的浅拷贝问题
		//对于自定义类型,去调用默认的拷贝构造,但由于空间是new出来的,所以s2和s3指向的空间是一样的
		//会造成两个问题:两次析构和修改的时候互相影响
		//如何深拷贝?先拷贝下来一块空间,再让值拷贝下来,再让被拷贝的对象指向这块空间
		cout << s1.c_str() << endl;
		cout << s2.c_str() << endl;
		cout << s3.c_str() << endl;

		s1 = s3;//赋值和拷贝构造类似,默认生成的也是浅拷贝
		cout << s1.c_str() << endl;
		cout << s3.c_str() << endl;
	}

	void Print(const string& s)//传值传参会调拷贝构造,也要深拷贝;const对象,调用的函数也要是const
	{
		for (size_t i = 0; i < s.size(); ++i)
		{
			cout << s[i] << " ";
		}
		cout << endl;


		string::const_iterator it = s.begin();//再使用范围for就OK了
		while (it != s.end())
		{
			//cout << (*it)-- << " ";只能读,不能写
			++it;
		}
		cout << endl;

		/*for (auto ch : s)//这里就用不了了,因为范围for是替换的迭代器,这里用迭代器也不行,这里是const对象,而普通的迭代器会修改内容,权限被放大了
		{
			cout << ch << " ";
		}
		cout << endl;*/

	}

	void test_string3()
	{
		string s1("hello world");
		for (size_t i = 0; i < s1.size(); ++i)
		{
			s1[i]++;
		}
		cout << endl;
		Print(s1);

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

		it = s1.begin();
		while (it != s1.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;

		for (auto ch : s1)//实现了迭代器就能用范围for,因为它的底层就是宏,替换的迭代器,迭代器begin改成Begin就不能用范围for了
		{
			cout << ch << " ";
		}
		cout << endl;
	}

	void test_string4()
	{
		string s1("hello world");
		string s2("hello world");
		string s3("xx");

		cout << (s1 < s2) << endl;//比较ascii码
		cout << (s1 == s2) << endl;
		cout << (s1 >= s2) << endl;
	}

	void test_string5()
	{
		string s1("hello world");
		//s1.push_back(' ');
		//s1.append("xxxxxxxxxxxxxxxxxxxx");


		s1 += ' ';
		s1 += "xxxxxxxxxxxxxxxxx";
		cout << s1.c_str() << endl;

		s1.insert(5, 'x');
		cout << s1.c_str() << endl;
	}

	void test_string6()
	{
		string s1("hello world111111111111111111111111");
		cout << s1.capacity() << endl;
		s1.reserve(10);
		cout << s1.capacity() << endl;
	}

	void test_string7()
	{
		string s1;
		s1.resize(20, 'x');
		cout << s1.c_str() << endl;
		s1.resize(30, 'y');
		cout << s1.c_str() << endl;

		s1.resize(10);
		cout << s1.c_str() << endl;
	}

	void test_string8()
	{
		string s1("hello world");
		s1.insert(0, 'x');
		cout << s1.c_str() << endl;
		s1.insert(0, "yyy");
		cout << s1.c_str() << endl;

		s1.erase(5, 1);
		cout << s1.c_str() << endl;
		s1.erase(5, 30);
		cout << s1.c_str() << endl;

	}
	//流插入重载必须实现成友元函数?不对,没有访问类中的成员,不需要
	void test_string9()
	{
		string s1("hello world");
		s1 += '\0';
		s1 += "xxxxxxxxx";
		cout << s1 << endl;
		cout << s1.c_str() << endl;

		string s2;
		cin >> s2;
		cout << s2 << endl;
	}

}