C++STL的string模拟实现

前言

今天要讲string的底层实现，通过自己来实现string,我们对string的理解才能更加的深刻。
我们对string其实既熟悉又陌生，熟悉sting其实就是字符串，陌生是在于管理字符串这样一个类。

string的成员变量

namespace but
{
	class string
	{
	private:
		char* _str;
		size_t _capaicty;
		size_t _size;
	};
}

我们为了避免自己定义的string于库里面的傻傻分不清，这里我们自己用了一个命名空间把自己写的string封装起来。

成员函数

构造函数

namespace but
{
	class string
	{
	public:
		string()
			:_str(nullptr),
			_capaicty(0),
			_size(0)
		{}
		string(const char* str)
			:_str(str),
			_capaicty(strlen(str)),
			_size(strlen(str))//容量不包括'\0'
		{}
	private:
		const char* _str;//加上const,防止写构造函数时，权限放大编译不通过
		size_t _capaicty;
		size_t _size;
	};
}

简简单单写了上面的构造函数，其实这里面存在两个问题，下面我们通过一些使用来看一下。
第一个问题。

写个c_str,思考一下为什么程序会崩?

const char* c_str()
{
	return _str;
}

string s1;
string s2("hello world")；
cout << s1.c_str() << endl;//上述代码都是写在类里面
cout << s2.c_str() << endl;

流插入是自动识别类型，它识别出const char*， 然后去解引用，然后遇到‘\0’结束，这样空指针的问题就暴露出来了。

继续看第二个问题

const char& operator[](size_t pos)//按照之前写的构造函数，必须加上const
{
	assert(pos < _size);
	return _str[pos];
}

这里面有个很坑的问题，我们是呆会是要修改pos位置的字符，并且如果空间不够还需要扩容，比如+=；那这里就变得非常矛盾。

这是什么原因呢？

string s2("hello world")；

s2在常量区无法修改，扩容也无法扩。

如何解决这两个问题呢？
其实根源还是在于初始化列表，我们大多数情况下都是推荐把所有成员变量直接放到初始化列表初始化，这里比较特殊。
其次，我们要想修改pos位置的字符，还想扩容，在初始化的时候空间就不能直接赋值过去，最好new出来。

那经过修改之后，我们的代码

namespace but
{
	class string
	{
	public:
		string()
			:_str(new char[1]),//要解决第一个问题，这里就不能是空
			_capacity(0),
			_size(0)
		{
			_str[0] = '\0';
		}
		string(const char* str)
			:_capacity(strlen(str))
		{
			_size = _capacity;//没有必要重复用strlen,strlen是o(N)的接口
			_str = new char[_capacity + 1];//扩容的时候应该+1，包括\0
			strcpy(_str, str);
		}
		~string()
		{
			delete[] _str;
			_str = nullptr;
			_capacity =_size= 0;
		}
		const char* c_str()
		{
			return _str;
		}

		char& operator[](size_t pos)
		{
			assert(pos < _size);
			return _str[pos];
		}
	private:
	    char* _str;//加上const,防止写构造函数时，权限放大编译不通过
		size_t _capacity;
		size_t _size;
	};
	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;
	}
}

至此，把上面的问题都解决了。

拷贝构造还可以继续优化一下，优化成只有一个全缺省的构造函数。

//string(const char* str = nullptr)  //不可以，等下strlen解引用会崩
//string(const char* str = '\0')//不可以，类型不匹配
//string(const char* str = "\0")//可以
string(const char* str = "")//可以
	:_size(strlen(str))
{
	_capaicty = _size == 0 ? 3 : _size;
	_str = new char[_capaicty + 1];
	strcpy(_str, str);
}

拷贝构造

void test_string2()
{
	string s2("hello world");

	string s3(s2);
	cout << s2.c_str() << endl;
	cout << s3.c_str() << endl;
}

我们之前说过拷贝构造是默认成员函数，我们不写，编译器会自动生成一个，对自定义类型不做处理，对内置类型做值拷贝或浅拷贝。那我们看一下自动生成的拷贝构造。

这个是经典的值拷贝或浅拷贝问题，我们之前也讲过，接下来既然有一个具体的场景，就用调试带大家看一下。

看两个地址完全一摸一样。

这样会带来两个问题。
1.一个修改影响另外一个。
2.同一块空间会析构两次。

那我们需要自己写一个深拷贝的拷贝构造，怎么写呢？

//拷贝构造也有初始化列表
string(const string& s)
			:_size(s._size)
			, _capaicty(s._capaicty)
		{
			_str = new char[s._capaicty + 1];
			strcpy(_str, s._str);
		}

赋值重载

赋值重载和拷贝构造也一摸一样，我们不写的话，编译器自动生成的会出问题。
写成这样，那就考虑的太不全面了

string& operator=(const string& s)
{
	_size = s._size;
	_capacity = s._capacity;
	_str = new char[s._capacity + 1];
	strcpy(_str, s._str);
	return *this;
}

我们知道拷贝构造是一块已经存在的空间给另一块还没存在的空间。
而赋值重载是两块都已经存在的空间，所以赋值重载还需要从空间的角度去分析问题。

从空间大小考虑，总共有三种情况

但是存在一个问题，如果s3空间特别大，s1又非常小，把s1直接赋值过去，s3就会浪费很多空间，所以比较好的方式就是再开一块空间。
我们库里面的string实现不会这么麻烦，直接把旧的空间释放掉，开一块一样大的空间。

还要处理自己给自己赋值，以免造成不必要的麻烦。

string& operator=(const string& s)
		{
			if (this != &s)
			{
				//这种写法稍微不好一点
				//抛异常的时候会把s1给破坏掉
				/*delete[] _str;
				_str = new char[s._capaicty + 1];
				strcpy(_str, s._str);
				_size = s._size;
				_capaicty = s._capaicty;*/

				char* tmp = new char[s._capaicty + 1];
				strcpy(tmp, s._str);
				delete[] _str;
				_str = tmp;

				_size = s._size;
				_capaicty = s._capaicty;
			}

模拟实现string各种接口

print

这里为什么报错？

这也涉及到我们之前讲过的。** cosnt成员变量不能调用非const成员函数，这样会权限放大。**

紧接着这里报错又怎么解决？
这说明我们需要两个【】,一个是给const对象调用的，不允许修改。
一个是给普通对象调用的，可以修改。它们构成函数重载，因为它们函数名相同参数不一样。
虽然普通对象也可以调用const成员函数，但是编译器非常聪明，他会调用最匹配的哪个。

迭代器

遍历的方式我们还可以用迭代器，这里我们再写一个迭代器

普通迭代器

要实现一个迭代器其实不难。

我们支持了迭代器，其实也就支持了范围for

for (auto ch : s1)
{
	cout << ch << " ";
}

const迭代器

const迭代器能不能修改？
可以修改，只是指向的内容不能修改。

string::const_iterator it = s1.begin();
while (it != s1.end())
{
	//*it = 'x';//不能修改，只能读不能改
	++it;
}
cout << endl;

反向迭代器这里先不讲，后面再讲，要用一个适配器来实现。

string比较大小

怎样比较大小？
比较ascll值，一个一个比。

// 不修改成员变量数据的函数，最好都加上const
		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;
			return *this > s || s == *this;
		}

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

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

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

push_back

空间不够扩容的时候不能用realloc，那就和c++交叉了，容易出问题。

void push_back(char ch)
{
	if (_size + 1 > _capaicty)
	{
		reserve(_capaicty * 2);
	}
	_str[_size] = ch;
	++_size;

	_str[_size] = '\0';
}

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

	strcpy(_str + _size, str);
	//strcat(_str, str);//为什么不用strcat?strcat很挫自己要去找\0，\0就在size位置，能不用就不用
	_size += len;
}

我们喜欢使用的还是+=，直接复用push_back;

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

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

凡是你的扩容，析构上代码崩了，一般都是内存问题。

insert 和 erase

问个小小的问题，静态成员变量能不能给缺省值？
不能，因为缺省值是给初始化列表用的。静态列表不是在初始列表初始化的。
它属于整个类，不是属于某个对象。

insert

插入字符
insert有个巨坑给大家看一下下面的代码？

程序运行结果。

调试的时候发现这样，扯淡了。

因为end的类型是size_t;

void insert(size_t pos, char ch)
{
	assert(pos <= _size);
	if (_size + 1 > _capacity)
	{
		reserve(2 * _capacity);
	}
	//int end=_size;//这样也不行，会发生类型转换，一般有符号转化为无符号。
	//改pos也不好,pos的类型一般规定都是size_t
	size_t end = _size;
	//while(end>=pos(int))//强转也不推荐
	//while (end >= pos)
	//{
	//	_str[end + 1] = _str[end];
	//	--end;
	//}
	size_t end = _size + 1;
	while (end > pos)
	{
		_str[end] = _str[end-1];
		--end;
	}

	_str[pos] = ch;
	++_size;
}

我们最好的解决思路，巧妙的避开了小于0；

插入字符串

一定要画图，不然很容易出错。

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;
	}
	
	//这个比较简单，完美避开了循环结束条件的难题
	/*size_t end = _size;
	for (size_t i = 0; i < _size + 1; ++i)
	{
		_str[end + len] = _str[end];
		--end;
	}*/

	// 拷贝插入
	strncpy(_str + pos, str, len);
	_size += len;

	return *this;

}

erase

erase比较简单，从pos位置删除数据就可以了。

我们浅浅分析一下所有的情况

erase也是不考虑缩容的。

string& 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);//不需要考虑覆盖的问题，所以可以直接用strcpy
		_size -= len;
	}
	return *this;
	}

白盒测试，把三种情况都验证一遍

reserve和resize

reserve

看一下我们之前写的扩容有什么问题？

它是没有考虑缩容的。继续看这样子就报错了。

为什么报错呢？
strcp的时候越界了。

简单修改一下代码就变成这样了。

void reserve(size_t n)
{
	if (n > _capacity)
	{
		char* tmp = new char[n + 1];
		strcpy(tmp, _str);
		delete[] _str;
		_str = tmp;

		_capacity = n;
	}
}

resize

resize缩容吗？
不缩容。缩荣的代价还是很大的，首先是异地缩，先开另一块空间，然后把数据拷贝过去，接着把之前的空间释放掉。
待会插入数据空间不够又要扩容，这样就很麻烦。

接下来实现resize，我们得分情况讨论，以及明白resize功能上的一些细节。

void resize(size_t n, char ch = '\0')
{
	if (n < _size)
	{
		// 删除数据--保留前n个
		_size = n;
		_str[_size] = '\0';
	}
	else if (n > _size)
	{
		if (n > _capacity)
		{
			reserve(n);
		}
		//如果调用系统的接口，我们可以用memset
		size_t i = _size;
		while (i < n)
		{
			_str[i] = ch;
			++i;
		}

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

swap

我们实现 一下swap,其实就知道库里面的swap和类里面的效率差距有多大

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

find

size_t find(char ch, size_t pos = 0)
		{
			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)
		{
			assert(pos < _size);
			char* p = strstr(_str + pos, str);
			if (p == nullptr)
			{
				return npos;
			}
			else
			{
				return p - _str;
			}
		}

cout和cin

现在我有一个问题，cout和cin必须实现成友元函数？这句话对不对
不对，我们可以写一些函数来访问私有成员变量。

cout

首先，我们实现cout, 它不是成员函数。

能不能直接这样搞？

我们之前说过c_str()和cout是有区别的，它们最大的区别就是c_str()打印时是遇到\0终止，cout是根据size来打印的。

ostream& operator<<(ostream& out, const string& s)
{
	for (auto ch : s)
	{
		out << ch;
	}
	return out;
}

cin

这样为什么不行？
调试一下就知道了，空格和换行不会进入缓冲区。为什么？
它会认为你输入的时候多个字符之间的间隔。

我们可以改成这样

仔细看一下上面的代码，功能是完善了但还有什么弊端。

这是没有把之前的数据清理掉。

还有一个问题有个流插入的数据比较长，那它会影响效率，那有没有什么方法能解决这个问题？
开小了不够，开多了浪费。这里有一个参考方式。
相当于换成字符串，可以这样理解。

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