String的增删查【C++】

前言

从这里开始可以算是进入了STL的学习中。

由于前面摸鱼摸得太狠了，国庆将会进行疯狂的补习。

这次就先带来string的实现。

这篇博客的本心主要是为了带大家了解string的底层逻辑
并不是对string的完美模拟实现

所以这里就打算挑几个比较常用的进行实现

string的增删查改

想要进行string的功能实现
首先就应该对string的类结构进行了解。

string在使用的过程中有点类似于动态的字符数组
能对字符串进行删除和增加数据。

说起动态的数组实现，我们应该能自然的想到顺序表。

能进行扩容和计数，在内存上也是连续存储，符合数组的存储方式。

所以以顺序表为原型

namespace my_str
{
	class string
	{
		public:
	

		private:
		size_t _size;
		size_t _capacity;
		char* _str;
	};
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

构造与析构

设计好结构后，就可以进行功能的实现了

首先肯定是构造和析构了

构造string(const char* str = “”)

当我们平常使用string时

大部分人可能都是这样去进行构造的把（这里就先不考虑流提取）
string s1("asd");

就是用常量字符串对string进行初始化。

那这样我们就可以写出构造函数的声明形式了。

string(const char* str = "")
给个缺省值，这样同时还能实现无参数的初始化。
string s1;

然后我们就能进行实现了。

string(const char* str = "")
//初始化列表
	:_size(strlen(str))//用常量字符串的长度进行赋值
	, _capacity(_size)//用常量字符串的长度进行赋值
	, _str(new char[_size + 1])//new一个新的char数组
{
	strcpy(_str, str);//将常量字符串的值拷贝给char数组中完成初始化。
}
1
2
3
4
5
6
7
8

这其实和顺序表的初始化顺序大差不差

就是多了一个strcpy对char数组初始化

——————————————————————————————————

赋值构造string(const string& s1)

复制构造也和顺序表一样。

不能用浅拷贝，而是要用深拷贝，因为向栈区申请了新的空间。

string(const string& s1)
{
	_capacity = s1._capacity;
	_str = new char[_capacity + 1];//申请新的空间
	_size = s1._size;
	strcpy(_str, s1._str);
}
1
2
3
4
5
6
7

赋值重载

string& operator=(string& s1)

按照常规来说，实现的方法
1.创建一个一样大的空间
2.拷贝数组内容
3.复制_size,_capacity

但是这里带来个更好的方法

在std中，自带了一个深度拷贝的交换函数。

所以我们可以用赋值对象构造新的一个对象。

然后用新对象赋值给老对象

		string& operator=(string& s1)
		{
			if (this != &s1)
			{
				string tmp(s1);
				std::swap(_str, tmp._str);
				std::swap(_size, tmp._size);
				std::swap(_capacity, tmp._capacity);
			}
			return *this;       
		}
1
2
3
4
5
6
7
8
9
10
11

这样可以说是更加方便。

析构函数

析构函数也和顺序表一样，没有啥特别的难度。

~string()
{
	_size = 0;
	_capacity = 0;
	delete[] _str;
	_str = NULL;
}
1
2
3
4
5
6
7

增

讲完了构造和析构
终于到了功能的实现。

reserve

当然在讲增加之前
最重要的扩容可不能落下了。

可以说扩容是表动态的前提。

这里讲一下扩容的思路

向堆区申请一块新的空间
然后将原数组的内容进行拷贝。
再将原数组进行释放就可以了。

void reserve(size_t n//需要多少空间)//扩容
{
	if (n > _capacity)//判断新开辟的空间是否大于原空间
	{
		char* new_ptr = new char[n + 1];//申请新空间
		strcpy(new_ptr, _str);//拷贝内容
		delete[] _str;//释放原数组
		_str = new_ptr;
		_capacity = n;

	}
}
1
2
3
4
5
6
7
8
9
10
11
12

push_back

接下来就到了激动人心的尾插环节了。

这个就是基本思路了。

比顺序表多了个\0
所以对\0进行考虑

	void push_back(char a)// 二倍扩容
	{
		if (_capacity == _size)
		{
			reserve(_capacity * 2);
		}
		_str[_size] = a;//赋上需要的值
		_size++;
		_str[_size] = '\0';//补上\0
	}
1
2
3
4
5
6
7
8
9
10

append

append功能就是进行字符串的尾插。

比如

my_str::string s1("asd");
s1.append("asd");
1
2

就是对s1字符串的尾部插入asd

类似于push_back的实现方法，但是两个字符串相接有一个好处：
就是不用考虑最后的’‘\0’’
只需要把前一个字符串的尾部的零覆盖掉就行了

		void append(const char* a="")//扩到新字节+_size
		{
			size_t len = strlen(a);//提取要插入的字符串长度
			if (len + _size > _capacity)//进行扩容判断
			{
				reserve(_size + len);
			}
			strcpy(_str + _size, a);//进行覆盖
			_size += len;//++size
		}
1
2
3
4
5
6
7
8
9
10

+=

+=可以说是append和push_back的集大成者。

但这也说明了+=可以通过append和push_back进行实现。

		string& operator+=(const char* str)
		{
			append(str);
			return *this;
		}
		string& operator+=(const char ch)
		{
			push_back(ch);
			return *this;
		}
		string& operator+=(const string& str)
		{
			append(str);
			return *this;
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

这实现的也是十分方便

insert

insert就是选定位置进行插入

这里我们向实现这个功能的话，可以用这个思路。

先是最基本的检查是否扩容

将插入位置后的字符进行后移

	void insert(size_t pos, const char* s)
	{
		assert(pos <= _size);//防止插入位子大于字符串长度
		size_t n = strlen(s);//记录插入字符串的长度
		if (n + _size > _capacity)//进行扩容检查
		{
			reserve(n + _size);
		}
		size_t end = size();
		while (pos <= end)//将字符串进行后移
		{
			_str[end + n] = _str[end];
			end--;
		}
		_size += n;//扩展size
		for (int i = 0; i < n; i++)//将插入字符串拷贝至位置处
		{
			_str[pos + i] = s[i];
		}

	}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

这上面算是完成实现了

但其实这里还有个隐藏bug。

size_t pos;
size_t end;
while (pos <= end)
1
2
3

当要插入的位置为0时

也就是说 pos=0，

再看看end和pos的类型

都是size_t的类型

试想一下，当end不停自减，当end为0，下一次就要变成-1，跳出循环的时候。

就会发现程序还在继续运行

这是因为end为size_t类型，所以不会变为-1。

这个时候就需要用到npos这个成员变量了

namespace my_str
{
	class string
	{
		public:
	

		private:
		size_t _size;
		size_t _capacity;
		char* _str;
		const static size_t npos = -1;//添加了一个npos静态变量
	};
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

STL中的string同时也是这样实现的。

接下来只要把判断条件稍微加一下就行了
while (pos <= end && end != npos)
这样就会发现可以正常运行了

最后代码

void insert(size_t pos, const char* s)
{
	assert(pos <= _size);
	size_t n = strlen(s);
	if (n + _size > _capacity)
	{
		reserve(n + _size);
	}
	size_t end = size();
	while (pos <= end && end != npos)
	{
		_str[end + n] = _str[end];
		end--;
	}
	_size += n;
	for (int i = 0; i < n; i++)
	{
		_str[pos + i] = s[i];
	}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

删

相比于查有着如此多的成员函数，剩下的就比较少了

erase

删除的话有两种情况

当要删除的量大于剩下量或者没有输入需要删除的量
将删除位置之后的所有量全都删除。
那再删除位置，简简单单加个‘\0’不就ok了

当要删除的量小于剩下字符量
则需要进行删除位置的控制，就是说不能随便添加’\0’。
需要同时保留删除后面的数据
实现方法和上面的插入很像，就是将后面的不停向前插入，来达到删除的效果

void erase(size_t pos, size_t len = npos//判断是否给了删除长度)
{
	if (len == npos || len + pos >= _size)//需要删除的长度大于剩下的字符
	{
		_str[pos] = '\0';//直接添加'\0'即可
		_size = pos;
	}
	else//需要删除的量小于剩下的量
	{
		int n = 0;
		while ((_str + pos + len + n) != end())//控制删除的量
		{
			//讲后面的不停前移
			_str[pos + n] = _str[pos + len + n];
			n++;
		}
		_size -= len;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

查

查找就十分简单了，在以前的C中就有自带的查找函数——strstr

		size_t find(const char* str, size_t pos = 0//从什么位置开始查找)
		{
			assert(pos <= _size);
			const char* ptr = strstr(_str + pos, str);//调用函数进行查找
			if (ptr)//判断是否有结果
			{
				return ptr - _str;
			}
			else
				return npos;

		}
1
2
3
4
5
6
7
8
9
10
11
12

直接使用即可

迭代器

由于以前没有给迭代器出过博客，这里就小小讲一下

迭代器可以理解为STL中的指针

因为成员变量中的指针一般都是私有成员
无法达到数据在各个容器中互通。

但是迭代器可以

	vector<char> v1;
	string s1("asdasdasdasd");
	string::iterator it = s1.begin();
	while(it!=s1.end())
	{
		v1.push_back(*it);
		it++;
	}

1
2
3
4
5
6
7
8
9

这里就用迭代器将string中的每一个丢进了vctor中。

这里通过迭代器使两个不同类产生互动。
这个我们在string中也要实现。

typedef char* iterator;
typedef const char* const_iterator;
1
2

在命名域内通过强转类型，将char*转为iterator。
所以不要看起来觉得它非常高大上，但其实就强转一下的事。

剩下的就很简单了

iterator begin()
{
	return _str;
}
iterator end()
{
	return _str + _size;
}

const_iterator begin()const
{
	return _str;
}
const_iterator end()const
{
	return _str + _size;
}
			
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

直接return对应的地址就行了

范围for
还记得之前的语法糖吗

string s1;
for(auto i:s1)
{

} 
1
2
3
4
5

其实它的底层就是迭代器实现的。

当你完成迭代器的时候就能发现范围for也能使用了

流插入流提取

流插入没啥特别的难度，所以这里就直接实现了。

流插入

std::ostream& operator<<(std::ostream& out, const string& s1)
{
	for (auto i : s1)
	{
		cout << i;
	}
	return out;   
	
}
1
2
3
4
5
6
7
8
9

流提取

流提取按照以前我们的惯性思维来说

应该是用这样的方式进行实现的。

std::istream& operator>>(std::istream& in, my_str::string& s1)
{
	char ch;
	cin >> ch;
	while (ch != ' ' && ch != '\n')//遇到空格和换行停止
	{
		s1 += ch;
		cin >> ch;
	}
	return in;
}
1
2
3
4
5
6
7
8
9
10
11

但是进行运行测试的时候

会发现程序在函数体内无限循环，无法停止了。

原因就是在C++中默认空格和分行就是用来进行隔断输入内容的。
所以用cin无法进行读取

这里就需要用到in自带的一个函数：

in.get()

	std::istream& operator>>(std::istream& in, my_str::string& s1)
{
	char ch;
	ch=in.get();
	while (ch != ' ' && ch != '\n')//遇到空格和换行停止
	{
		s1 += ch;
		ch=in.get();
	}
	return in;
}

1
2
3
4
5
6
7
8
9
10
11
12

这样的话基本功能是实现了，但是还有几个问题在：
1.多次引用+=，申请空间，严重影响效率

我们知道+=的实现引用了reverse，但是reverse进行扩容的时候需要进行拷贝和申请空间并且销毁原空间，多次引用会严重影响效率。

2.如果在前面添加了空格和换行之类的，就不能进行提取了。

首先是第一个问题，我们可以自己申请一个数组，然后将提取出来的内容放进数组里面，最后将数组赋值给对象。

	std::istream& operator>>(std::istream& in, my_str::string& s1)
	{
		s1.clear();
		char buff[128];
		char ch = in.get();
		int i = 0;
		while (ch != ' ' && ch != '\n')
		{
			buff[i++] = ch;
			if (i == 127)//判断数组是否满
			{
				buff[i] = '\0';//添加\0
				s1 += buff;//添加至数组
				i = 0;
			}
			ch = in.get();
		}
		if (i != 0)//检查数组是否满了
		{
			buff[i] = '\0';'尾部添上'\0'
			s1 += buff;
		}
		return in;

	}

}



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

接下来就是第二个问题。

while (ch==' '||ch=='\n')
{
	ch = in.get();
}
1
2
3
4

直接在前面添加一个循环用来专门提取空格和换行就可。

最后代码

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

	}

}



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34