【C++】STL——string类模拟实现

发布时间:2024-09-03 09:01

\"【C++】STL——string类模拟实现_第1张图片\"

目录

前言

实现框架思维导图

一、默认成员函数 

1.构造函数

2.拷贝构造

1.传统写法

2.现代写法 

3.赋值运算符重载函数 

1.传统写法 

2.现代写法 

4.析构函数

二、容量相关的函数

1.reserve()

2.resize()

3.size()和 capacity()

三、字符串的增删查改函数

1.push_back()

2.append()

3.operator+=()

4.insert()

5.swap()

6.erase()

7.clear()

8.c_str()

9.find()

四、字符串访问函数

1.operator[ ]() 

2.迭代器 

五、关系运算符重载函数 

六、流提取、流插入运算符重载

完整代码


前言

        在之前的string类的介绍中,我们重点介绍了string类常用的接口函数及使用规则。相比我们在C语言学习阶段使用的字符串函数去解决相关的题目要轻松很多,但是轻松的背后却是大神们为我们建立好的基础;学好string类的基本用法使我们入门的关键,想要了解string类的背后原理,我们还需要去简单的造轮子;本篇文章将为大家讲解string类的模拟实现。

实现框架思维导图

\"【C++】STL——string类模拟实现_第2张图片\"

一、默认成员函数 

        string的模拟实现无论是简单版还是稍健全版都需要默认成员函数:构造函数、拷贝构造、析构函数和赋值重载

1.构造函数

        在实现构造函数时,我们将其设置为缺省参数;这样的好处就在于,无参构造时,将会默认构造出空字符串。

//构造函数
string(const char* str = \"\")
	:_size(strlen(str))  //使用初始化成员列表初始化
	, _capacity(_size)   //起始的空间大小和_size是一样的
{
	_str = new char[_capacity + 1]; 
    //为存储字符串开辟空间,这里多开一个空间是因为_capacity计算的是有效空间的长度,要给\'\\0\'预留一个空间
	strcpy(_str, str);
}

2.拷贝构造

对于拷贝构造,我们首先要了解一下深浅拷贝的概念:

浅拷贝:

        又称值拷贝,拷贝出来的对象和原来的对象同时指向了一块空间,当进行析构函数时,这个空间被释放了两次或多次;拷贝出来的对象的修改也会影响到原来的对象;

深拷贝:

        又称位拷贝,拷贝出来的对象与原对象的内容是一样的,但是属于另一块空间,这两块空间各自的操作都不会影响到另一个空间;

\"【C++】STL——string类模拟实现_第3张图片\"

1.传统写法

         传统写法的思路:开辟一个和原来对象同样的大的空间,然后将原对象的内容拷贝过去;

//拷贝构造 --- 传统写法
//str2(str1)
string(const string& s)
	:_size(s._size)
	, _capacity(s._capacity)
{
	_str = new char[_capacity + 1];
	strcpy(_str, s._str);
}

2.现代写法 

        现代写法的思路: 先去构造出一个和原来对象相同的tmp对象,然后将tmp对象与待拷贝对象数据进行交换;

//拷贝构造 --- 现代写法
//str2(str1)
string(const string& s)
	:_str(nullptr)
	, _size(0)
	, _capacity(0)
{
	string tmp(s._str);
	//this->swap(tmp);
	swap(tmp);
}

3.赋值运算符重载函数 

        赋值重载和拷贝构造类似,也是通过一个已有对象构造新对象,也会涉及到深浅拷贝的问题

1.传统写法 

        赋值重载函数的传统写法:两个已有对象要完成赋值操作(str2 = str1)我们可以开辟一个和str1同样大小的空间tmp,然后将其数据拷贝到tmp中,先将str2原来的空间进行释放,让str2指向tmp;

//赋值重载 --- 传统写法
//str2 = str1
string& operator=(const string& s)
{
	if (this != &s) //防止自己给自己赋值
	{
		char* tmp = new char[s._capacity + 1];//开辟一块和_str1一样的空间tmp
		strcpy(tmp, s._str);   //将_str1的数据拷贝给tmp
		delete[] _str;         //释放str2原来的空间
		_str = tmp;            //让str2指向新的空间
		_size = s._size;       //调整_size
		_capacity = s._capacity;//调整_capacity
	}
	return *this;
}

2.现代写法 

        赋值重载函数的现代写法: 采用了值传参而非引用传参,它会去调用构造函数,让构造函数来创建一个和str1一样对象s,再将其与待赋值的对象str2进行交换,达到赋值的目的,相比传统写法简单很多。

//赋值重载 --- 传统写法
//str2 = str1
string& operator=(string s)
{
	swap(s);
	return *this;
}

4.析构函数

        string类的析构函数需要我们自己去写,默认生成的析构函数是不会对堆上开辟的空间进行释放,我们使用的是new开辟空间的,为了规范使用,我们采用delete进行释放空间;

//析构函数
~string()
{
	delete[] _str;
	_str = nullptr;
	_size = _capacity = 0;
}

二、容量相关的函数

1.reserve()

reserve增容:

        1.当 n > _capacity 时,将capacity扩大到n;

        2.当 n < _capacity 时,不进行任何操作;

模拟实现思路:

        1. 开辟一块n大小的空间tmp(要多开一个,给\\0)

        2. 将原有数据拷贝到新开辟的空间tmp中

        3. 释放原来的空间,让原来指针指向新的空间

        4. 调整好现在的_capacity的大小

void reserve(size_t n)
{
	if (n > _capacity)
	{
		char* tmp = new char[n + 1];//这里加1是为了给\'\\0\'一个空间
		strcpy(tmp, _str);
		delete[]_str;
		_str = tmp;
		_capacity = n;
	}
}

2.resize()

resize增容:

        1.当 n <= _size 时,表明数据个数减少,但是容量不变(库中实现的也是如此)

        2.当 n > _size时:

                ①n > _capacity:需要增容,可以复用reserve函数,然后采用memset函数按字节设置

                ②n <= _capacity:不需要增容,直接memset

注意:因为字符串是有 \'\\0\' 的,最后都需要添加一个 \'\\0\' 

void resize(size_t n, char ch = \'\\0\')
{
	if (n <= _size)
	{
		_size = n;
		_str[_size] = \'\\0\';
	}
	else
	{
		if (n > _capacity)
		{
			reserve(n);
		}
		memset(_str + _size, ch, n - _size);//内存设置:从_str+_size位置开始向后 n-_size个字节设置成ch
		_size = n;
		_str[_size] = \'\\0\';
	}
}

3.size()和 capacity()

 size函数和capacity函数实现比较简单,返回的就是时时更新的数据个数和空间大小

//有效数据个数
size_t size() const
{
	return _size;
}

//有效空间大小(\\0不算在内)
size_t capacity() const
{
	return _capacity;
}

三、字符串的增删查改函数

1.push_back()

        push_back函数的作用就是在当前字符串的尾部插入一个字符(不能是字符串)。插入字符,我们就需要对其容量进行判断,容量足够可以直接插入,容量不够则需要增容;我们一开始的容量是为0的,如果以2倍的方式增容,是不行的,我们要给到一个起始容量,可以采用三目运算符;

//尾插字符
void push_back(char ch)
{
	if (_size == _capacity) //判断数据个数是否与容量相等
	{
		reserve(_capacity == 0 ? 4 : _capacity * 2); //以2倍扩容
	}
	_str[_size] = ch;
	++_size;
	_str[_size] = \'\\0\'; //末尾需要加上\'\\0\'

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

2.append()

        append函数是用来尾插字符串的。也需要判断容量是否足够,当原有数据个数和需要追加的字符串个数之和大于_capacity是,需要增容;

//尾插字符串
void append(const char* str)
{
	size_t len = strlen(str);    //计算需要尾插的字符串的长度
	if (_size + len > _capacity) //不需要考虑给\\0空间
	{
		reserve(_size + len);    //增容
	}
	strcpy(_str + _size, str);   //拷贝数据--连\'\\0\'一起拷贝
	_size += len;

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

3.operator+=()

        这个函数可以完成字符、字符串的尾插,尾插字符可以复用push_back函数,尾插字符串可以复用append函数;

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

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

4.insert()

        insert函数可以用来在字符串的pos位置插入一个字符或字符串。既然是插入数据,当然也需要进行容量的判断,在pos位置插入字符时,其过程就是将pos位置及以后的字符向后挪动一位

//在pos位置插入字符
string& insert(size_t pos, char ch)
{
	assert(pos <= _size);   //检查pos是否合法(如:pos=-1)
	if (_size == _capacity) //判断容量是否足够
	{
		reserve(_capacity == 0 ? 4 : _capacity * 2);
	}

	size_t end = _size + 1; //定义后一个end指向\'\\0\'的下一个位置
	while (end > pos) //找pos位置,未找到向后挪动数据
	{
		_str[end] = _str[end - 1];
		--end;
	}

	_str[pos] = ch;//找到了,插入字符
	++_size;       //更新一下_size
	return *this;
}

insert在pos插入字符串(len个),将pos及以后的字符向后挪动len个位置;

需要注意:在插入字符串时我们可以采用strncpy函数,不能使用strcpy函数,因为会将 \'\\0\' 插入进去

//在pos位置插入字符串
string& insert(size_t pos, const char* s)
{
	assert(pos <= _size);         //检查pos的合法性
	size_t len = strlen(s);       //计算待插入的字符串的有效长度
	if (_size + len > _capacity)  //判断是否需要增容
	{
		reserve(_size + len);
	}

	size_t end = _size + len;     //定义end在_size+len的位置
	while (end >= pos + len)
	{
		_str[end] = _str[end - len];
		--end;
	}
	strncpy(_str + pos, s, len);  //从pos位置开始拷贝,拷贝len个
	_size += len;
	return *this;
}

5.swap()

        模拟实现swap函数,为了避免自己实现的swap函数名和库当中的swap冲突,需要加上std::

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

6.erase()

erase函数是用来从pos位置开始删除n个字符串:

        1. 从pos位置开始向后全部删除;

        2. 从pos位置开始向后删除一部分;

string& erase(size_t pos = 0, size_t len = npos)//npos=-1(size_t)整形的最大值
{
	assert(pos < _size);
	if (len == npos || pos + len >= _size)//当len超过了有效字符个数或就是npos(从pos向后删除全部)
	{
		_str[pos] = \'\\0\';//直接在pos位置加上\'\\0\',就达到删除的目的,访问只能访问到\'\\0\'
		_size = pos;     //更新_size
	}
	else //删除一部分
	{
		strcpy(_str + pos, _str + pos + len);//将需要保留的字符串去覆盖要删除的字符串
		_size -= len;  //更新_size
	}
	return *this;
}

7.clear()

clear函数是用来字符串置空的,只需要将字符串的第一位置为\'\\0\',再将_size置0;

//清空字符串
void clear()
{
	_str[0] = \'\\0\';
	_size = 0;
}

8.c_str()

 c_str函数是用来返回C形式的字符串,可以直接返回对象的成员变量_str;

//返回C形式的字符串
const char* c_str() const
{
	return _str;
}

9.find()

find函数是正向查找第一个匹配的字符

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

find函数是正向查找第一个匹配的字符串

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

四、字符串访问函数

1.operator[ ]() 

[ ]运算符重载是为了让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];
}

2.迭代器 

        相比其他容器的迭代器,string类的迭代器相对简单,实际上是char*的typedef;函数后面的const表示的是this不能被修改;


typedef char* iterator;
typedef const char* const_iterator;

iterator begin()
{
	return _str;//返回字符串第一个位置
}
iterator end()
{
	return _str + _size;//返回\'\\0\'的地址
}

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

五、关系运算符重载函数 

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

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

//实现两种比较其他的可以复用
bool operator<=(const string& s1, const string& s2)
{
	return s1 < s2 || s1 == s2;
}

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

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

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

六、流提取、流插入运算符重载

//流插入 <<
ostream& operator<<(ostream& out, const string& s)
{
	//方式一
	for (auto ch : s)
	{
		out << ch;
	}
	//方式二
	for (size_t i = 0; i < s.size(); ++i)
	{
		out << s[i];
	}
	//方式三 
	//out << s.c_str();//不能这样写
	return out;
}

//流提取 >>
istream& operator>>(istream& in, string& s)
{
	s.clear();
	char ch = in.get();
	while (ch != \' \' && ch != \'\\n\')//利用循环可以连续输入
	{
		s += ch;
		ch = in.get();
	}
	return in;
}

完整代码

namespace mlxg3
{
	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 = \"\")
			:_size(strlen(str))
			, _capacity(_size)
		{
			_str = new char[_capacity + 1];
			strcpy(_str, str);
		}

		

		/******************拷贝构造********************/
		//s2(s1)
		//传统写法
		/*
		string(const string& s)
			:_size(s._size)
			, _capacity(s._capacity)
		{
			_str = new char[_capacity + 1];
			strcpy(_str, s._str);
		}
		*/
		

		/******************赋值重载********************/

		/*
		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);
		}
		//s2(s1)
		string(const string& s)
			:_str(nullptr)
			, _size(0)
			, _capacity(0)
		{
			string tmp(s._str);
			//this->swap(tmp);
			swap(tmp);
		}

		string& operator=(string s)
		{
			swap(s);
			return *this;
		}
		

		/******************析构函数********************/
		~string()
		{
			delete[] _str;
			_str = nullptr;
			_size = _capacity = 0;
		}

		/******************增删查改、增容********************/
        //返回c形式的字符串
		const char* c_str() const
		{
			return _str;
		}
        //返回有效字符的个数
		size_t size() const
		{
			return _size;
		}

        //返回有效容量的大小
		size_t size() const
		{
			return _size;
		}

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

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

        //reserve增容
		void reserve(size_t n)
		{
			if (n > _capacity)
			{
				char* tmp = new char[n + 1];//这里加1是为了给\'\\0\'一个空间
				strcpy(tmp, _str);
				delete[]_str;
				_str = tmp;
				_capacity = n;
			}
		}

        //resize增容
		void resize(size_t n, char ch = \'\\0\')
		{
			if (n <= _size)
			{
				_size = n;
				_str[_size] = \'\\0\';
			}
			else
			{
				if (n > _capacity)
				{
					reserve(n);
				}
				memset(_str + _size, ch, n - _size);
				_size = n;
				_str[_size] = \'\\0\';
			}
		}

        //尾插字符
		void push_back(char ch)
		{
			/*
			if (_size == _capacity)
			{
				//增容
				reserve(_capacity == 0 ? 4 : _capacity * 2);
			}
			_str[_size] = ch;
			++_size;
			_str[_size] = \'\\0\';
			*/
            
			insert(_size, ch);//复用
		}

		//尾插字符串 
		void append(const char* str)
		{
			/*
			size_t len = strlen(str);
			if (_size + len > _capacity)//不需要考虑给\\0空间
			{
				reserve(_size + len);
			}
			strcpy(_str + _size, str);
			_size += len;
			*/
			insert(_size, str);//复用
		}

		//尾插字符 --- +=重载
		string& operator+=(char ch)
		{
			push_back(ch);
			return *this;
		}

		//尾插字符串 --- +=重载
		string& operator+=(const char* str)
		{
			append(str);
			return *this;
		}

		//查找第一个匹配的字符
		size_t find(char ch)
		{
			for (size_t i = 0; i < _size; ++i)
			{
				if (ch == _str[i])
				{
					return i;
				}
			}
			return npos;
		}

		//查找第一个匹配的字符串
		size_t find(const char* s, size_t pos = 0)
		{
			const char* ptr = strstr(_str + pos, s);
			if (ptr == nullptr)
			{
				return npos;
			}
			else
			{
				return ptr - _str;
			}
		}

		//在pos位置插入一个字符
		string& 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;
			}

			_str[pos] = ch;
			++_size;
			return *this;
		}

		//在pos位置插入一个字符串
		string& insert(size_t pos, const char* s)
		{
			assert(pos <= _size);
			size_t len = strlen(s);
			if (_size + len > _capacity)
			{
				reserve(_size + len);
			}

			size_t end = _size + len;
			while (end >= pos + len)
			{
				_str[end] = _str[end - len];
				--end;
			}
			strncpy(_str + pos, s, len);
			_size += len;
			return *this;
		}

		//从pos位置开始删除字符
		string& erase(size_t pos = 0, size_t len = npos)
		{
			assert(pos < _size);
			if (len == npos || pos + len >= _size)
			{
				_str[pos] = \'\\0\';
				_size = pos;
			}
			else
			{
				strcpy(_str + pos, _str + pos + len);
				_size -= len;
			}
			return *this;
		}

		//将字符串置空
		void clear()
		{
			_str[0] = \'\\0\';
			_size = 0;
		}

	private:
		char* _str;
		size_t _size;
		size_t _capacity;//有效字符的空间数
		static const size_t npos;
	};

    //定义npos(为了和库一致)
	const size_t string::npos = -1;

	/*
	   字符串s1      字符串s2
		\"abcd\"   和   \"abcd\"    ----false
		\"abcd\"   和   \"abcde\"   ----true
		\"abcde\"   和   \"abcd\"   ----false
	*/
    //字符串的比较 --- 关系运算符的重载
	bool operator<(const string& s1, const string& s2)
	{
		return strcmp(s1.c_str(), s2.c_str()) < 0;
	}

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

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

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

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

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

    //流插入重载 
	ostream& operator<<(ostream& out, const string& s)
	{
		//方式一
		for (auto ch : s)
		{
			out << ch;
		}
		//方式二
		for (size_t i = 0; i < s.size(); ++i)
		{
			out << s[i];
		}
		//方式三 
		//out << s.c_str();//不能这样写
		return out;
	}

    //流提取重载 
	istream& operator>>(istream& in, string& s)
	{
		s.clear();
		char ch = in.get();
		while (ch != \' \' && ch != \'\\n\')
		{
			s += ch;
			ch = in.get();
		}
		return in;
	}
}

ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网,如有侵权请联系:561261067@qq.com

桂ICP备16001015号