亲宝软件园·资讯

展开

C++ STL之string的模拟实现实例代码

李奇同学喵喵呜~ 人气:0

前言

上一章我们对string的常见接口及使用进行了讲解,接下来我们将对一些常见的接口,包括构造函数,析构函数,运算符重载等等进行模拟实现.方便我们理解string接口实现的原理.

在讲解之前先说一下string的成员变量.

首先是字符串内容_str,再是字符串的大小_size,最后是字符串的总容量大小_capacity.

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

构造函数

缺省值是一个空串,再给_str开辟空间时要多开辟一个空间存储'\0'

开好了空间最后需要把内容拷贝到_str.

		string(const char* str = "")
		{
			//这里有个细节,就是先计算出_size大小,然后再直接把_size赋值给_capacity,省了一次strlen()的调用.
			_size = strlen(str);
			_capacity = _size;
			_str = new char[_capacity + 1];
			strcpy(_str, str);
		}

析构函数

完成对string类成员的资源清理,空间释放等一些操作.

        ~string()
		{
            //释放_str的空间,并将其指向的空间置为空
			delete[] _str;
			_str = nullptr;
 
			_size = _capacity = 0;
		}

拷贝构造函数

说到string的拷贝构造函数,这里一定会涉及到深浅拷贝问题.

所以在讲解它的拷贝构造函数之前必须先了解它

浅拷贝:也称位拷贝,编译器只是将对象中的值拷贝过来。如果对象中管理资源,可能就会导致多个对象共享同一份资源,当一个对象销毁时就会将该资源释放掉,但是其他的对象不知道该资源已经被释放了,以为资源还有效,所以他们会继续对这个资源进行访问。这时就出现了违法访问。深拷贝就是为了解决浅拷贝的问题

深拷贝:就是给自己重新开辟一块空间,并将数据拷贝到新开辟的空间中,如果一个类中涉及到资源的管理,其拷贝的构造函数,赋值运算符重载以及析构函数必须要显式给出。(就是要手动写,不能用编译器自动生成的)。一般这种情况都是按照深拷贝方式提供。

所以拷贝的时候,需要重新给_str开辟一块空间.

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

这里也用图浅浅的介绍一下浅拷贝和深拷贝的区别.

operator=赋值运算符重载

正如上一个所说,=赋值运算符也同样存在深浅拷贝的问题,所以也必须进行深拷贝.

它和拷贝构造的主要区别就是:拷贝构造是对象还没有初始化时进行拷贝,而赋值运算符重载是对一个已经存在的变量进行赋值.

当然同样这里也需要深拷贝

也有一些需要注意的问题:例如s1=s2.我们把s2赋值给s1后,那么原本的s1空间该怎么办呢?

我们的解决方案是:

把原本的s1空间释放掉,然后再开辟一块和s2大小相同的空间,再把内容从s2拷贝到s1

		//= 运算符重载
		string& operator=(const string& s)
		{
			//不能自己赋值给自己
			if (this != &s)
			{//先释放掉原本的空间
				delete[] _str;
				_str = new char[s._capacity + 1];
				strcpy(_str, s._str);
				_size = s._size;
				_capacity = s._capacity;
			}
			return *this;
		}

c_str

c_str就是返回c语言风格的字符串,既返回char*类型字符串,返回字符串首地址即可.

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

为什么加const呢?

第一个const是为了使普通对象和const对象都可以调用这个函数,因为权限只可以缩小,不可以放大.

第二个const是保证函数体内的内容不会被改变,既this指针指向的内容无法被改变.

operator[]

实现[]重载,是指传过来一个下标index,返回它index下标所对应的值

目的是让字符串可以像数组一样访问每一个元素.

		char& operator[](size_t index)
		{
            //下标必须小于字符串总大小
			assert(index < _size);
 
			return _str[index];
 
		}

当然为了const对象也可以调用,我们可以再写一个const修饰的operator[].

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

size()

写一个函数,直接返回_size即可

        size_t size() const
		{
			return _size;
		}

那可能会有人想问了:既然返回_size,那我们直接调用它这个成员不就行了,为什么还有套一层函数呢?

这是因为_size是被private修饰的,我们是不能直接访问私有成员的.

所以需要实现一个公有的函数间接访问_size.

capacity()

这个所注意的和size完全一致.

		size_t capacity() const
		{
			return _capacity;
		}

empty()

只需要判断当前的size是否等于0即可.

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

operator+=

这个重载运算符我们上一章讲过是可以插入字符或者插入字符串的,这里也分别复用了push_back和append(),这两个函数后面将模拟实现.

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

扩容函数(reserve)

调整容量大小到n

先new一个n+1的新空间,再把原来的数据拷贝到新空间中去,然后释放掉原来的空间,然后将capacity设置为n.

void reserve(size_t n)
		{
			//n应该大于之前的容量
			if (n > _capacity)
			{
				//先开辟大小为n+1的空间
				char* tmp = new char[n + 1];
				//将原来的数据拷贝到tmp
				strcpy(tmp, _str);
				//释放掉原来的数据
				delete[] _str;
				
				//将扩容后的数据重新赋给_str
				_str = tmp;
				_capacity = n;
			}
		}

画图来理解一下它 

resize()

resize会有以下两种情况:

1.若n < _size,既重新调整后的大小小于原来的大小,会发生数据截断,只保留前n个字符.

2.若n > _size,这里直接复用reserve即可

既如果n<_capacity,此时_capacity不发生变化,多出的空间用ch替代.

如果n>_capacity,此时_capacity需要扩容(1.5倍速度,不一定是n),直到最接近为止.

		void resize(size_t n, char ch = '\0')
		{
			if (n > _size)
			{
				//插入数据
                //reserve会和容量进行比较以及是否需要阔人
				reserve(n);
                //多余的字符用ch替代    
				for (size_t i = _size; i < n; i++)
				{
					_str[i] = ch;
				}
                //字符串结束
				_str[n] = '\0';
				_size = n;
			}
			else
			{
				//删除数据
                 //直接将第n个数据改为'\0',这样相当于将后面的数据全部删除了.
				_str[n] = '\0';
				_size = n;
			}
		}

push_back()

push_back的作用是在原字符串后上拼接一个字符,首先我们现需要判断空间是否足够,如不够,则需要扩容,复用之前的reserve函数,再进行插入数据,最后加上'\0'.

当然还可以利用复用insert()函数进行插入,这个后面再实现.

		void push_back(char ch)
		{
			if (_size == _capacity)
			{
				reserve(_capacity == 0 ? 4 : _capacity * 2);
				_str[_size] = ch;
				++_size;
				_str[_size] = '/0';
			}
		}

还以复用insert这样插入,会使代码健壮性更强,更加简洁.

这个inser()函数后面会实现.

			insert(_size, ch);

append()

这个与push_back不同的是:push_back()只能插入一个字符,append()只可以插入一个字符串.

这里的问题就出现了,我们不知道追加的字符串长度,自然扩容的时候也不知道扩大到多少,是2倍还是3倍,所以这里要看插入的字符串的长度len,只要要让空间开到_size+len.

让空间满足最低的情况,能把所有的字符容纳下,最后利用strcpy将其数据拷贝过来即可.

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

当然同样可以复用insert函数.

    insert(_size, str);

下面就该说insert函数了.

insert()

insert也分为两种情况:插入一个字符或插入多个字符(字符串)

插入一个字符:方法类似于顺序表的插入

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

插入多个字符:

		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)
			{
				_str[end] = _str[end - len];
				--end;
			}
            //再把利用strncpy把指定长度的字符串插入
			strncpy(_str + pos, str, len);
			_size = _size + len;
 
		}

说了插入就该说删除了.

erase()

这个函数也比较巧妙,首先输入两个参数:第一个参数是要开始删除的下标,第二个参数是要删除的长度.

首先第二个参数默认缺省值是npos,npos是一个非常大的数.

首先判断len是否等于npos或者当前位置+len是否大于总长度,若是,则直接将pos位置置为'\0',后面的元素也就相当于删除了

如果不是,则把pos+len之后的元素拷贝到pos位置之后,这样就相当于删除了pos~pos+len之间的这一段字符.再把_size-len,相当于是一个覆盖的过程.

		void erase(size_t pos, 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;
			}
		}

find()

也是实现两个,利用strstr()函数来查找字符串.

1.如果查找一个字符

  如果找到,则直接返回字符所对应的下标pos,否则返回npos.

2.如果查找一个字符串

   对于这种情况,找到字符串后,我们需要返回第一个字符的下标,通过指针差值确定目标字符串的位置。

1.查找一个字符

思路很简单,就是利用循环

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

2.查找一个字符串

利用strstr函数,从第pos个位置开始查找,如果找到则返回目标字符串的首元素地址,若没有找到则返回空指针

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

substr()

 这个函数实现比较简单,复用之前实现的+=即可

首先计算出实际要切割的长度realLen = len

如果pos+len>_size或者len == npos,则需要重新计算realLen = _size - pos

然后循环realLen次,创建一个string类型的sub变量,每次利用sub+=这个字符即可.

 
		string substr(size_t pos, size_t len = npos)
		{
			assert(pos < _size);
			size_t realLen = len;
			if (len == npos || pos + len > _size)
			{
				realLen = _size - pos;
			}
			string sub;
			for (size_t i = 0; i < realLen; i++)
			{
				sub += _str[pos + i];
			}
 
			return sub;
		}

比较大小函数

实现比较大小,只需要实现两个运算符重载即可:

1. > 或 <其中任意一个

2.==

剩下的>=、<=、!=等等复用即可.

实现> 或 < 时,利用strcmp比较函数即可.

		bool operator >(const string& s) const
		{
			return strcmp(_str, s._str) > 0;
		}
 
		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);
		}
		bool operator !=(const string& s)
		{
			return !(*this == s);
		}

 这样string的模拟实现基本就完成了,下面是总代码:

namespace hmylq
{
	class string
	{
	public:
		typedef char* iterator;
		typedef const char* const_iterator;
 
		string(const char* str = "")
		{
			_size = strlen(str);
			_capacity = _size;
			_str = new char[_capacity + 1];
			strcpy(_str, str);
		}
		//拷贝构造 - - - 1
		string(const string& s)
			:_str(new char[s._capacity + 1])
			, _size(s._size)
			, _capacity(s._capacity)
		{
			strcpy(_str, s._str);
		}
		//拷贝构造 - - - 2
	/*	string(const string& s)
			:_str(nullptr)
			, _size(0)
			, _capacity(0)
		{
			string tmp(s._str);
			swap(_str, tmp._str);
			swap(_size, tmp._size);
			swap(_capacity, tmp._capacity);
		}*/
 
		//析构函数
		~string()
		{
			delete[] _str;
			_str = nullptr;
			_size = _capacity = 0;
		}
		
		iterator begin()
		{
			return _str;
		}
 
		iterator end()
		{
			return _str + _size;
		}
 
		const_iterator begin() const
		{
			return _str;
		}
 
		const_iterator end() const
		{
			return _str + _size;
		}
 
		/
		void push_back(char ch)
		{
			/*if (_size == _capacity)
			{
				reserve(_capacity == 0 ? 4 : _capacity * 2);
				_str[_size] = ch;
				++_size;
				_str[_size] = '/0';
			}*/
			insert(_size, ch);
		}
 
	
		string& operator += (char ch)
		{
			push_back(ch);
 
			return *this;
		}
 
		void append(const char* str)
		{
			/*size_t len = strlen(str);
			if (_size + len > _capacity)
			{
				reserve(_size + len);
			}
			strcpy(_str + _size, str);
			_size = _size + len;*/
			insert(_size, str);
		}
 
		string& operator += (const char* str)
		{
			append(str);
 
			return *this;
		}
 
 
 
		//= 运算符重载
		string& operator=(const string& s)
		{
			if (this != &s)
			{
				delete[] _str;
				_str = new char[s._capacity + 1];
				strcpy(_str, s._str);
				_size = s._size;
				_capacity = s._capacity;
				return *this;
			}
		}
 
 
	
		void clear()
		{
			_str[0] = '\0';
			_size = 0;
		}
 
		void swap(string& tmp)
		{
			::swap(_str, tmp._str);
			::swap(_size, tmp._size);
			::swap(_capacity, tmp._capacity);
		}
 
		const char* c_str() const
		{
			return _str;
		}
		//
		size_t size() const
		{
			return _size;
		}
 
		size_t capacity() const
		{
			return _capacity;
		}
		
		bool empty() const
		{
			return _size == 0;
		}
 
		void resize(size_t n, char ch = '\0')
		{
			if (n > _size)
			{
				reserve(n);
				for (size_t i = _size; i < n; i++)
				{
					_str[i] = ch;
				}
				_str[n] = '\0';
				_size = n;
			}
			else
			{
				_str[n] = '\0';
				_size = n;
			}
		}
 
		void reserve(size_t n)
		{
			if (n > _capacity)
			{
				char* tmp = new char[n + 1];
				strcpy(tmp, _str);
				delete[] _str;
 
				_str = tmp;
				_capacity = n;
			}
		}
		
		/
		char& operator[](size_t index)
		{
			assert(index < _size);
 
			return _str[index];
 
		}
 
		const char& operator[](size_t index) const
		{
			assert(index < _size);
 
			return _str[index];
		}
 
		//
 
		bool operator >(const string& s) const
		{
			return strcmp(_str, s._str) > 0;
		}
 
		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);
		}
		bool operator !=(const string& s)
		{
			return !(*this == s);
		}
 
		
 
		size_t find(char ch, size_t pos = 0)
		{
			assert(pos < _size);
			for (size_t i = pos; i < _size; i++)
			{
				if (ch == _str[i])
				{
					return i;
				}
			}
			return npos;
		}
		size_t find(const char* sub, size_t pos = 0)
		{
			assert(sub);
			assert(pos < _size);
 
			const char* ptr = strstr(_str + pos, sub);
			if (ptr == nullptr)
			{
				return npos;
			}
			else
			{
				return ptr - _str;
			}
		}
 
		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;
		}
 
		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)
			{
				_str[end] = _str[end - len];
				--end;
			}
			strncpy(_str + pos, str, len);
			_size = _size + len;
 
		}
 
		void erase(size_t pos, 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;
			}
		}
 
	
 
 
		string substr(size_t pos, size_t len = npos)
		{
			assert(pos < _size);
			size_t realLen = len;
			if (len == npos || pos + len > _size)
			{
				realLen = _size - pos;
			}
			string sub;
			for (size_t i = 0; i < realLen; i++)
			{
				sub += _str[pos + i];
			}
 
			return sub;
		}
 
 
	private:
		char* _str;
		int _size;
		int _capacity;
		const static size_t npos = -1;
	};
}

总结

加载全部内容

相关教程
猜你喜欢
用户评论