c++编程（11）——string类的模拟实现

欢迎来到博主的专栏——c++编程
博主ID：代码小豪

---

前言

本片的string类的模拟实现不涉及模板，泛型编程并不是本专栏的重点内容，本专栏的主要目的是了解c++面向对象编程的特性，以及STL的部分使用方法。因此本博客模拟的string类是为了让读者了解类的封装方法、接口设计。

string类的模拟实现

string的成员对象

一个类需要设计该类的属性和行为。属性是成员对象，而行为则是成员函数，string类是字符序列的类。

c++是基于C语言扩展而成，因此c++当中的字符序列和c语言的如出一撤，即字符序列的字符在内存中连续存储，再用一个char*的指针指向字符序列。c++称这种字符序列为c-string。

如果要将字符串封装起来，那么我们还需要提供其他的属性来显示这个字符序列的状态，比如当前字符串的长度。

我们还想要这个字符串可以自动的扩大存储。那么最好的方法就是使用动态内存来管理这个字符序列。因此还需要为其设计容量这一属性。方便用户（即类的使用者）查看当前字符序列的可存储内存。

那么根据上述理论，我们可以确定一个基本的string类应该封装这么三个对象：c-string，大小，可存储容量。

class mystring
{
private:
	char* _str;//c-string
	size_t _size;//当前的字符长度
	size_t _capacity;//容量
};

c++的string类还存在一个特殊的static const成员常量npos，我们也将其设计在类中，但是要注意static成员变量要声明在类中，定义在类外。

```cpp
class mystring
{
private:
	char* _str;//c-string
	size_t _size;//当前的字符长度
	size_t _capacity;//容量
	static const size_t npos;
};
const size_t mystring::npos = -1;

构造、赋值、析构

一个类想要正常的使用，那么为其设计合理的构造、析构、赋值成员函数时必不可少的，即使你粗心的遗忘了某个部分，编译器都会为你生成这些函数，因此，想要设计好一个类，这个模块是必不可少的。

我们希望string类的构造能支持下面三种初始化形式：默认初始化成空string，也可以用c-string初始化这个string，还可以用string对象初始化string。因此我们需要设计这么三个函数。默认构造、拷贝构造、和c-string作为参数的构造。

class mystring
{
public:
	mystring();//默认构造
	mystring(const mystring& str);//拷贝构造
	mystring(const char* str);//c-string构造
private:
	char* _str;//c-string
	size_t _size;//当前的字符长度
	size_t _capacity;//容量
};

我们最好将声明和定义分离在两个编程单元当中，这是为了减少链接问题。由于篇幅问题博主就不详细声明了，博主将会在c++杂谈中提到这个。

string的默认构造，默认构造是构造一个空字符串。空字符串长度为0，但是内存并不为0，因为空字符串并不是没有字符，而是开辟了一个只有‘\0’的字符串。

mystring::mystring()
{
	_size = 0;
	_capacity = 0;
	_str = new char[_capacity + 1] {0};
}

为什么申请的空间要比_capacity多一个呢？这是因为容量不需要注意\0的管理，我们设计的容量是为了记录可存储有效字符的容量，但是在申请空间的时候需要比容量多申请一个，这个位置是留给\0的。

拷贝构造还是为了拷贝c-string的。因此不仅仅string对象中的_str指向的字符序列与c-string一致，而且_size和_capacity都要与c-string一致。

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

博主这里使用了C语言的库函数strlen和strcpy，C语言的在string类的模拟实现中大量使用，主要原因还是博主懒，如果大家想了解strlen和strcpy的使用逻辑，那么可以去看博主在C语言进阶指南（14），里面有相对应的模拟实现。（模拟实现是为了让自己能够对最近的知识进行一次实践、而不是造轮子，博主当前的阶段还能写string类能比设计标准库大佬好？这当然不可能）。

拷贝构造函数是，将待拷贝的mystring对象的所有属性都拷贝过来。

mystring::mystring(const mystring& str)
{
	_size = str._size;
	_capacity = str._capacity;
	//这里是深拷贝
	_str = new char[_capacity + 1];
	strcpy(_str, str._str);
}

析构函数则是将申请的空间进行释放，由于字符序列不再存在有效字符，因此_size和_capacity置为0。

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

赋值重载函数的本质也是将对象参数进行拷贝，与拷贝构造的原理相同。但是要将申请的空间进行销毁。

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

访问成员对象的接口

mystring中的成员对象都被隐藏了起来，如果我们想要让用户知道这些数据，可以为其设计访问的接口，方便用户进行操作，而不破坏类的封装性。

	size_t size() { return _size; }
	size_t capacity() { return _capacity; }
	void reserve(size_t n);//扩容函数
	void clear();//清空clear

reserve的目的是让用户可以手动的为mystring对象进行扩容。当然，我们也可以在成员函数当中调用这个函数完成扩容，可谓是一举两得。

由于c++并没有给出像realloc这种可以原地扩容的关键字，因此博主在reserve当中使用的是异地扩容。

void mystring::reserve(size_t n)
{
	if (n > _capacity)
	{
		size_t newcapacity = _capacity == 0 ? 4 : 1.5 * _capacity;
		//异地扩容
		char* tmp = new char[newcapacity + 1] {0};
		strcpy(tmp, _str);
		delete[] _str;
		_str = tmp;

		_capacity = newcapacity;
	}
}

clear是将字符串里的有效字符清空，我们不需要修改容量，只需要修改大小，并且将字符序列的起始字符换成‘\0’就行了。（因为_str的本质是c-string，而c-string的定义就是从起始字符开始到第一个遇到的’\0’为c-string）。

void mystring::clear()
{
	_str[0] = '\0';
	_size = 0;
}

访问字符串中的元素

mystring对象时一个字符序列，因此我们需要考虑用户该如何访问字符序列的元素。由于_str是一个c-string，那么我们可以考虑C语言的做法，用下标访问符[]访问元素。这就需要我们为mystring重载一个下标访问符的函数了。

	char& operator[](size_t pos) { return _str[pos]; }
	const char& operator[](size_t pos)const { return _str[pos]; }

由于我们需要考虑到const对象和non-const对象调用此函数的不同效果，因此需要将其重载一个const对象的调用版本，和一个非const对象的调用版本。

迭代器

迭代器是一个用来在容器、对象当中遍历或者访问元素的接口。由于c-string可以用char的指针来遍历或访问元素。因此我们不妨将char的指针作为mystring的迭代器。

	typedef char* iterator;
	typedef const char* const_iterator;
	iterator begin() { return _str; }//返回对象的起始迭代器
	iterator end() { return _str + _size; }//返回对象的末尾迭代器
	const_iterator end() const{ return _str + _size; }//返回const对象的末尾迭代器
	const_iterator begin() const{ return _str + _size; }//返回const对象的起始迭代器

对字符序列的插入、删除元素操作

我们设计为字符序列的相关修改函数，字符序列本身是一个顺序表的数据结构，因此我们设计插入、删除元素的函数时可以参考顺序表的插入、删除元素的算法。

        void push_back(char c);//追加字符
		void append(const mystring& str);//追加字符串
		mystring& operator+=(const mystring& str);//追加字符串
		mystring& operator+=(char c);//追加字符
		void insert(size_t pos, char ch);//在pos的位置，插入字符
		void insert(size_t pos, const char*str);//在pos的位置，插入字符
		void erase(size_t pos = 0, size_t len = npos);//删除pos位置后len个长度的字符
		void swap(mystring& s);//交换字符串

追加字符或字符串的操作可以参考顺序表的尾插法。尾插是在字符串的末尾加入元素。

追加的过程中要注意mystring对象的容量可能满了，注意为该对象进行扩容。

	void mystring::push_back(char c)
	{
		if (_size == _capacity)//扩容
		{
			size_t newcapacity = _capacity == 0 ? 4 : 1.5 * _capacity;
			reserve(newcapacity);
			_capacity = newcapacity;
		}
		_str[_size++] = c;
		_str[_size] = '\0';
	}

	void mystring::append(const mystring& str)
	{
		size_t len = strlen(str._str);
		while (_size + len >= _capacity)//扩容
		{
			size_t newcapacity = _capacity == 0 ? 4 : 1.5 * _capacity;
			reserve(newcapacity);
			_capacity = newcapacity;
		}

		size_t end = _size + len;
		size_t i = 0;

		strcpy(_str,str._str);
	}

	mystring& mystring::operator+=(const mystring& str)
	{
		append(str);//这里我们直接复用追加函数
		return *this;
	}

	mystring& mystring::operator+=(char c)
	{
		push_back(c);//复用追加函数
		return *this;
	

插入操作也是和顺序表的插入算法一致，因为字符序列的本质就是一个顺序表。

void mystring::insert(size_t pos, char ch)
	{
		assert(_size >= pos);//检测合法性
		if (_size == _capacity)//扩容
		{
			size_t newcapacity = _capacity == 0 ? 4 : 1.5 * _capacity;
			reserve(newcapacity);
			_capacity = newcapacity;
		}
		size_t end = _size;
		while (end > pos)//挪动数据
		{
			_str[end] = _str[end - 1];
			end--;
		}
		_str[pos] = ch;//插入数据
		_size++;
	}

	void mystring::insert(size_t pos, const char* str)
	{
		assert(_size >=pos);//判断合法性
		size_t len = strlen(str);//判断插入字符的有效字符个数
		size_t newsize = _size + len;
		while (newsize >= _capacity)//扩容
		{
			size_t newcapacity = _capacity == 0 ? 4 : 1.5 * _capacity;
			reserve(newcapacity);
			_capacity = newcapacity;
		}
		size_t end = newsize;
		while (end >= pos+len)//挪动数据
		{
			_str[end] = _str[end - len];
			end--;
		}
		while (len--)//插入数据，不会插入‘\0’
		{
			_str[pos + len] = str[len];
		}

		_size = newsize;

	}

删除数据则是将该范围的数据被后面的数据覆盖就行

void mystring::erase(size_t pos, size_t len )
	{
		assert(pos <= _size);
		if(_size -pos <= len)
		{
			_str[pos] = '\0';
			_size = pos;
		}
		else
		{
			size_t end = _size;
			size_t begin = pos + len;
			while (begin <= end)
			{
				_str[begin - len] = _str[begin];
				begin++;
			}
			_size -= len;
		}
	}

mystring类的相关操作

我们希望mystring类可以用于C语言的函数，换句话说就是让mystring中的_str拿出来是用于C语言设计的函数。

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

我们还可以设计一个查找函数，方便我们查找字符或字符串在mystring对象当中的位置。

	size_t mystring::find(char ch, size_t pos )const
	{
		assert(pos <= _size);
		while (_str[pos] != '\0')
		{
			if (_str[pos] == ch)//查找字符
			{
				return pos;
			}
			pos++;
		}
		return npos;//返回字符
	}

	size_t mystring::find(const char* str, size_t pos )const
	{
		assert(pos <= _size);
		const char* substr;
		substr = strstr(_str+pos, str);//查找字符串
		if (substr == nullptr)
		{
			return npos;
		}
		return substr-_str;//返回字符串
	}

查找字符串会用到复杂的算法，比如KMR查找算法，这里博主不多讲述，所以用strstr这个C语言函数，并且利用指针相减的特性取巧的解决了这个问题。

我们还可以重载io流，使得cout和cin可以对mystring类的对象进行操作，注意这两函数是定义成非成员函数的。

	istream& operator>> (istream& is, mystring& str);
	ostream& operator<< (ostream& os, const mystring& str);

	istream& operator>> (istream& is, mystring& str)
	{
		str.clear();

		char ch=0;
		ch=is.get();
		while (ch != '\n' && ch != ' ')
		{
			str += ch;
			ch = is.get();
		}
		return is;
	}

	ostream& operator<< (ostream& os, const mystring& str)
	{
		os << str.c_str();
		return os;
	}

mystring类的所有模拟实现以及测试案例

博主将mystring类的模拟实现的所有代码以及测试案例都放在博主本人的代码仓库当中。欢迎查阅。
博主的gitee：代码小豪的代码仓库