C++STL详解（二）——string类的模拟实现

  • 开发
  • 16

首先，我们为了防止命名冲突，我们需要在自己的命名空间内实现string类。

一.string类基本结构

string类的基本结构和顺序表是相似的，结构如下：

//.h
namespace kuzi
{
	class string
	{
	private:
		char* _str;//字符串
		size_t _size;//长度
		size_t _capacity;//容量
	};
}

这里我们采取类内声明，类外实现的方式。

若不加声明，本文代码默认在cpp文件中实现。 

二.构造函数以及析构函数外加赋值运算符重载

首先，我们应该写构造函数和析构函数以及赋值运算符重载的头文件。

	//.h
        public:
		string(const char* str);
		string(const string& str);
		~string();
        string& operator=(const string& str)

我们在这里实现一个析构函数以及两个构造函数

这两个构造函数分别是：

  • 字符串构造
  • string类对象构造

对于构造函数的实现，我们不采取手写字符串拷贝的方式，直接用C语言库中的stycpy即可。

2.1字符串构造 

现在我们来实现第一个构造函数

我们可以很轻易的写出如下代码：

	string::string(const char* str)
		:_str(new char [strlen(str)+1])//多开一个空间给/0
		, _size(strlen(str))//不算\0
		, _capacity(strlen(str))//不算\0
	{
		strcpy(_str, str);
	}

但是这样实现的话，strlen就需要计算三次了，这显然是我们不想看到的。

因此我们这样子便行不通了。

因此，我们使用如下的方法来完成这个函数：

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

此外，由于我们还需要解决空字符串的问题

空字符串：只有一个‘\0’的字符串。

在这里我们可以通过给缺省值的方式解决。

//.h		
string(const char* str="");//字符串中默认有\0

在这里值得大家注意的是，我们不可给'\0'作为缺省值。

string(const char* str=‘\0’);

这是因为‘\0’无法隐式转换为const char*，只能隐式转换为int，也就是转换为了整型的0.

在这里会出现空指针的问题。

下面我们来实现字符串类对象构造：

2.2字符串类对象构造

有了上个构造函数的基础，我们可以很容易的写出如下代码： 

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

这样，便可以完成对字符串类对象的构造。

2.3析构函数

对于析构函数的实现也是相当简单的，我们直接释放空间然后再将析构的对象的成员置0即可

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

2.4赋值运算符重载函数

 赋值运算符重载函数和构造函数不同的地方是，我们需要清空原字符串中的字符，然后再进行赋值。因此我们可以写出如下代码：

	string& string::operator=(const string& s)
	{
		char* tmp = new char[s._capacity + 1];
		strcpy(tmp, s._str);
		delete[] _str;//赋值需要清空原字符串
		_str = tmp;
		_size = s._size;
		_capacity = s._capacity;
		return *this;
	}

三.返回成员相关函数

在这里我们实现如下四个函数：

		//.h
        const char* c_str()const;
		size_t size() const;
		char& operator[](size_t pos);
		const char& operator[](size_t pos) const;

这些函数是极其容易实现的：

	const char* string::c_str()const
	{
		return _str;
	}
	size_t string::size() const
	{
		return _size;
	}
	char& string::operator[](size_t pos)
	{
		return _str[pos];
	}
	const char& string::operator[](size_t pos) const
	{
		return _str[pos];
	}

四.迭代器以及迭代器相关函数的实现

4.1迭代器的实现

这里我们采取一种简单的方式来实现迭代器

//.h
typedef char* iterator;
typedef const char* const_iterator;

我们这里直接typedef一下指针来模拟实现迭代器。

4.2迭代器相关函数实现

下面我们来模拟实现几个与迭代器相关的函数：

		//.h
        iterator begin();
		iterator end();
		const_iterator begin()const;
		const_iterator end()const;

大家在这里需要注意的是，我们返回的是指针。

由于我们的_str是char*类型的，因此我们可以直接返回。

然后返回end位置时，我们可以通过指针运算来完成。

因此我们可以实现出如下代码：

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

 五.字符串的增删查函数

在这里，我们要具体实现如下函数： 

//.h
void resever(size_t n);
void push_back(char ch);
string& operator+=(char ch);
string& operator+=(const char* str);
void append(const char* str);//权限不可放大
void insert(size_t pos, char ch);
void insert(size_t pos, const char* str);
void erase(size_t pos, size_t len = npos);
size_t find(char ch, size_t pos = 0);
size_t find(const char* str, size_t pos = 0);

可能大家对为什么要把resever放在这块实现表示疑惑。

对于字符串进行增删，也就需要更改字符串的空间。

因此我们实现一个resever，就可以提高代码的耦合性。

5.1reserve的实现

由于大多数编译器都不实现缩容，因此我们在这里也不实现缩容。

由于我们很难实现原地扩容，因此我们这里采用异地扩容的方式。

我们首先开辟一块有n+1那么大的空间，然后将原字符串拷贝到这块空间即可。

需要大家注意的是：我们需要将原空间的字符串释放，否则将会导致出现空指针。

我们可以很容易的实现出如下代码：

	 void string::resever(size_t n)
	 {
		 if (_capacity < n)
		 {
			 char* tmp = new char[n + 1];
			 strcpy(tmp, _str);
			 delete[] _str;
			 _str = tmp;
			 _capacity = n;
		 }
	 }

5.2字符串尾插相关函数的实现

我们在这里需要实现的函数如下：

void push_back(char ch);
string& operator+=(char ch);
string& operator+=(const char* str);
void append(const char* str);//权限不可放大
5.2.1pushback的实现

我们先检查一下空间，然后我们再开空间即可完成对空间的操作

然后我们直接尾插该字符并再追加一个\0即可。

	 void string::push_back(char ch)
	 {
		 if (_size == _capacity)
		 {
			 size_t newcapacity = _capacity == 0 ? 4 : 2 * _capacity;
			 resever(newcapacity);
		 }
		 _str[_size] = ch;
		 _str[_size + 1] = '\0';
		 ++_size;
	 }
5.2.2append的实现

append是尾插一个字符串的函数，因此我们的实现逻辑和pushback的逻辑有略微不同。

首先，我们应计算出该字符串的函数，然后通过计算来判断需不需要扩容。

之后，我们可以通过C库中的字符串追加函数将字符追加到原字符串的结尾。

但是这个函数需要我们遍历一遍原字符串，时间复杂度为O（N）；

而字符串拷贝函数的时间复杂度为O（N）!!!

所以我们这里通过将字符串拷贝到原字符串的末尾来解决该问题。

因此，我们可以写出如下代码： 

     void string::append(const char* str)
	 {
		 size_t len = strlen(str);
		 if (_size+len> _capacity)
		 {
			 size_t newcapacity = _capacity == 0 ? 4 : 2 * _capacity;
			 resever(newcapacity);
		 }
		 //方式1
		 //strcat(_str, str);
		 //方式2
		 strcpy(_str + _size, str);
	 }

5.3+=操作符的重载

这里我们+=一个字符直接调用pushback；+=字符串直接调用append即可。

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

5.4insert函数的实现

我们先实现插入一个字符的insert函数

5.4.1插入一个字符

有了上面的基础，我们可以很容易的得到如下代码： 

	 void string::insert(size_t pos, char ch)
	 {
		 //检查空间
		 if (_size == _capacity)
		 {
			 size_t newcapacity = _capacity == 0 ? 4 : 2 * _capacity;
			 resever(newcapacity);
		 }
		 //插入
		 size_t end = _size;
		 while (end >= pos)
		 {
			 _str[end + 1] = _str[end];
			 end--;
		 }
		 _str[pos] = ch;
		 _size++;
	 }

很遗憾的是，这段代码是跑不过去的。

当我们在第一个位置插入字符时，发现end已经等于-1了，但是我们又进入了下一次循环。

这是为什么呢？

这是因为无符号的-1是整型最大值。
如果是在第一个位置插入，那么pos==0
end==0时可以进去，等到end==-1时依旧可以进去

这样下去就形成了一个死循环，也就是说这段代码就跑不过去了。

那么我们应该如何处理呢？

处理方式1：

归根结底，size_t类型是无符号整型，它是不可能小于0的。

也就是说，size_t类型的数是一定>=0的。

所以，我们只要是能够绕过>=就可以了。

那么我们如何绕过>=呢？

这里我们让end等于最后一个字符的后一个字符。

然后我们不断地把前一个字符赋给后一个字符即可

		 size_t end = _size + 1;
		 while (end > pos)//1>0   0!>0
		 {
			 _str[end] = _str[end - 1];
			 end--;
		 }
		 _str[pos] = ch;
		 _size++;

处理方式2：

既然无符号整型不行，那么我们直接不用无符号整型了，我们用int不就行了吗！

		 int end = _size;
		 while (end >= (int)pos)
		 {
			 _str[end + 1] = _str[end];
			 end--;
		 }
		 _str[pos] = ch;
         _size++;
5.4.2指定位置插入字符串

 同样的，这里我们也可以通过以上两种方式来控制字符串的插入

代码如下：

 void string::insert(size_t pos, const char* str)
 {
	 //检查空间
	 size_t len = strlen(str);
	 if (_size + len > _capacity)
	 {
		 size_t newcapacity = _capacity == 0 ? 4 : 2 * _capacity;
		 resever(newcapacity);
	 }
     //控制方法2
	 //int end = _size;
	 //while (end > (int)pos)
	 //{
		// _str[end+len] = _str[end];
		// --end;
	 //}
     //控制方法1
	 size_t end = _size + len;
	 while (end > pos+len-1)//hello
	 {
		 _str[end] = _str[end-len];
		 --end;
	 }
	 memcpy(_str +pos,str,len);
 }

在这里需要我们大家注意控制方法1，以下是图解。 

因此我们需要end>pos+len-1。 

5.5字符串指定位置删除函数的实现

如果我们要删除的字符长度大于len前面字符个数时，我们将那些字符全删掉即可。(直接加\0)

否则，我们直接将pos+len后的字符拷贝到前面即可。（会拷贝\0）

	 void string::erase(size_t pos, size_t len = -1)
	 {
		 //len大于前面字符个数时，全删掉。
		 if (len == -1 || len > _size - pos)
		 {
			 _str[pos] = '\0';
			 _size = pos;
		 }
		 else
		 {
			 strcpy(_str + pos, _str + pos + len);
		 }
	 }

值得注意的是，len的默认值是-1,也就是整形的最大值。 

5.6字符串从指定位置查找函数的实现

5.6.1查找字符

直接遍历查找即可。 

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

比较复杂的KMP算法以及BM算法会在后续文章介绍。 

5.6.2查找字符串

 查找字符串直接用C库中的strstr查找即可。

	size_t string::find(const char* str, size_t pos = 0)
	{
		char* poss = strstr(_str + pos, str);
		return poss - _str;

六.比较操作符函数重载

在这里，我们要实现如下六个函数： 

//操作符函数
bool operator>(const string& s)const;
bool operator>=(const string& s)const;
bool operator<(const string& s)const;
bool operator<=(const string& s)const;
bool operator==(const string& s)const;
bool operator!=(const string& s)const;

我们可以通过C库中的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 string::operator>=(const string& s)const
	 {
		 return *this > s || *this == s;
	 }
	 bool string::operator<(const string& s)const
	 {
		 return !(*this >= s);
	 }
     bool string::operator<=(const string& s)const
	 {
		 return *this < s || *this == s;
		 
	 }
	 bool string::operator!=(const string& s)const
	 {
		 return !(*this == s);
	 }

七.流操作符重载

	//.h
	istream& operator>>(istream& in, string& s);
	ostream& operator<<(istream& out, string& s);

由于我们的流操作符需要调整参数的顺序，因此我们需要在类外声明 

7.1流插入操作符重载

对于流插入操作符，我们使用的方法是极其简单的。

直接一个一个的将字符输出即可。 

	 ostream& operator<<(istream& out, string& s)
	 {
		 for (size_t i = 0; i <= _str.size(); i++)
		 {
			 out << str[i];
		 }
		 return out;
	 }

7.2流提取操作符重载

对于流提取操作符，我们首先应将原字符串的字符清除。

因此，我们在这里选择再在类内声明一个clear函数，并实现。

之后，我们使用get函数，将字符一个一个的拷贝至string对象中。

代码如下：

void string::clear()
{
	_str[0] = '\0';
	_size = 0;
}
istream& operator>>(istream& in, string& s)
{
 s.clear();
 char ch = in.get();
 while (ch != ' ' && ch != '\n')
 {
	 s += ch;
	 ch = in.get();
 }
 return in;
}

这个代码需要频繁的扩容，有人给出了如下的优化版代码：

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

 八.其他函数

这里我们实现两个函数，分别是交换函数以及取子串函数 

        //.h
		void swap(string& s);
		string substr(size_t pos = 0, size_t len=-1);

实现如下：

//std库中的swap代价特别大
	//拷贝构造和两次赋值都是深拷贝
	//交换指针来解决
	void string::swap(string& s)
	{
		std::swap(_str, s._str);
		std::swap(_size, s._size);
		std::swap(_capacity, s._capacity);
	}
	//取子串
	string string::substr(size_t pos = 0, size_t len)
	{
		if (len > _size - pos)//len大于剩余长度
		{
			string sub(_str + pos);
			return sub;
		}
		else
		{   
			string sub;
			sub.resever(len);
			for (size_t i = 0; i < len; i++)
			{
				sub += _str[pos + i];
			}
			return sub;
		}
	}

九.现代思想

在现代思想中，我们采取交换的方式来完成string类的构造，但本质没有变化。

//现代写法
string(const string& s)
	:_str(nullptr)
	, _size(0)
	, _capacity(0)
{
	string tmp(s._str); //调用构造函数，构造字符串。
	swap(tmp); //交换s和tmp
}

	//传统写法
    string::string(const string& str)
	{
		_str = new char[str._capacity + 1];
        strcpy(_str, str._str);
		_size = str._size;
		_capacity = str._capacity;
	}

十.为什么要使用const成员

可能大家对成员函数中的参数为什么要用const对象表示疑惑

我们在这里进行解释：

const的对象是常的，常量是只可读不可写的。

非const的对象是可读可写的。

权限是不可以放大的，只能平移和缩小。

  • 传非const的对象。

权限变化：可读可写-->可读（权限的缩小）

  • 传const的对象

权限变化：可读-->可读（权限的平移）

阅读全部

相关推荐

  5. string类的模拟实现

    2024-07-19 20:04:02       24 阅读

  7. 【c++】string类的模拟实现

    2024-07-19 20:04:02       32 阅读

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-19 20:04:02       67 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-19 20:04:02       72 阅读

  9. 在Django里面运行非项目文件

    2024-07-19 20:04:02       58 阅读

  19. Python语言-面向对象

    2024-07-19 20:04:02       69 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2024-07-19 20:04:02       64 阅读

热门阅读

  3. 【WiFi】DFS Vs ZW-DFS

    2024-07-19 20:04:02       16 阅读

  6. 深度学习落地实战：基于GAN（生成对抗网络）生成图片

    2024-07-19 20:04:02       18 阅读

  7. 前端使用webSocket与后台建立连接并进行心跳监测机制

    2024-07-19 20:04:02       20 阅读

  13. 【代码随想录|第十一章 图论part01 | 797.所有可能的路径 】

    2024-07-19 20:04:02       20 阅读

  15. Vue 3.0 所采用的 Composition Api 与 Vue 2.x使用的Options Api 有什么区别

    2024-07-19 20:04:02       20 阅读

  16. 蓝牙新篇章：WebKit的Web Bluetooth API深度解析

    2024-07-19 20:04:02       23 阅读

  18. Solana开发之Anchor框架-部署到 Devnet

    2024-07-19 20:04:02       17 阅读

  23. 快速上手绿联私有云UGOS Pro系统Docker

    2024-07-19 20:04:02       20 阅读

  24. 跟ChatGPT学习go语言--int 类型如何转化成string

    2024-07-19 20:04:02       17 阅读

  28. C语言相关知识点（不定期更新内容）

    2024-07-19 20:04:02       22 阅读