C++ String的模拟实现

一.基本框架

1.成员变量

string类的成员变量分别是存储字符串的一段空间_str，表示字符串的有效字符个数_size和表示存储有效字符空间的_capacity。

private:
    char *_str;
    size_t _size;// 有效字符的个数
    size_t _capacity;// 存储有效字符的空间

还有一个string类的特殊成员，npos表示size_t的最大值，一般表示表示string的结束位子。

private:
	char* _str;
	size_t _size;
	size_t _capacity;

public:
	const static size_t npos;
};

const size_t string::npos = -1;?

-1也可以表示size_t类型的最大值。

注意：

1. 对于【npos】这个参数，首先我们知道对于静态成员变量，它的规则是在类外定义，类里面声明，定义时不加static关键字；
2. 但如果静态成员变量有const修饰，这时它可以在类内直接进行定义，这样的特性只针对于整型，对于其他类型则是不适用的；
3. npos就是const static修饰的成员变量，可以直接在类内进行定义。

?2.构造函数

?1.2.1 全缺省构造函数

? 首先，string类的有参构造函数其实可以设计为全缺省函数，缺省值设置为空串，当没有传入参数时使用缺省值，将_str设置为空串，这样就可以不需要定义无参构造函数了。其次，如果传入了参数，就将_size和_capacity设置为形参的长度，然后开一段大小和形参相同的空间给_str，最后将值拷贝过去即可。

??

	//构造函数
	string(const char* str = "")
		:_size(strlen(str))
		, _capacity(_size)
	{
		//cout << "构造函数" << endl;
		_str = new char[_capacity + 1];
		strcpy(_str, str);
	}

1.2.2 拷贝构造函数?

?string的拷贝构造函数，关于string的拷贝构造函数，我的建议是用传入的string类型中的_str去构造一个临时变量，然后交换临时变量和当前类内部的成员变量的内容。

??

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

		//拷贝构造
		string(const string& s)
			:_str(nullptr)
			, _size(0)
			, _capacity(0)
		{
		   //cout << "拷贝构造函数" << endl;
			string tmp(s._str);
			swap(tmp);
		}

1.2.3 移动构造

??
? ?没啥好说的，直接交换右值即可。

	//移动构造
	string(string&& s) noexcept{
		//cout << "移动构造函数" << endl;
		swap(s);
	}

3 赋值重载

1.3.1 默认重载

默认重载的赋值运算符功能很简单，就是将原有对象的所有成员变量一一赋值给新对象，并且返回新对象，这和默认拷贝构造函数的功能类似。

? 因此其代码和拷贝构造函数代码差不多，只不过不用初始化，因为在构造时已经初始化完毕。

??

		//拷贝赋值
		string& operator=(const string& s) {
			//cout << "拷贝赋值函数" << endl;
			string tmp(s);
			swap(tmp);
			return *this;
		}

1.3.2 移动重载

? 直接交换资源就好。

//移动赋值
string& operator=(string&& s) noexcept {
	//cout << "移动赋值函数" << endl;
	swap(s);
	return *this;
}

4.析构函数

?把_str空间释放，置空，并且把_size和_capacity 置0?

		//析构函数
		~string() {
			delete[] _str;
			_str = nullptr;
			_size = 0;
			_capacity = 0;
		}

二 容量函数

2.1 size()

顾名思义返回字符串的长度（以字符数为单位）

size_t size() const {
	return _size;
}

2.2 capacity()

返回当前为 string 分配的存储空间的大小，以字符表示。

size_t capacity() const {
	return _capacity;
}size_t capacity() const {
	return _capacity;
}

2.3 reserve()

? 表示请求更改容量（_capacity)，使字符串容量适应计划的大小更改为最多?n?个字符。

注意是有效字符，不包含标识字符，而在具体实现的时候，我们在底层多开一个空间给\0。

这里我们的做法是，如果n >_capacity，那么我们就开始扩容， 先 创建一个新数组，把其大小扩容为n+1，留一个空间给 \0? ,然后将原本的 str中的内容拷贝进新数组，然后delete str开的空间，最后将str指向新空间，更新_capacity的内容。

代码如下：

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

2.4 resize()

其实它的情况大体上可以分为插入数据和删除数据两种情况。

1.对于插入数据：直接调用【reserve】提前预留好空间，然后搞一个for循环将字符ch尾插到数组里面去，最后再在数组末尾插入一个\0标识字符；
2.对于删除数据：如果 n 小于当前字符串长度，则当前值将缩短为 n ，删除第 n 个字符以后的字符，然后重置一下_size的大小为n即可。

代码如下：

	void resize(size_t n, char ch = '\0') {
		if (_size > n) {
			_str[n] = '\0';
			_size = n;
		}
		else{
			reserve(n);
			while (_size < n) {
				_str[_size] = ch;
				++_size;
			}
			_str[n] = '\0';
		}
	}

2.5 clear()

??顾名思义就是清除字符串，擦除string的内容，该内容变为空字符串（长度为?0?个字符）。

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

三 元素访问

3.1??operator[]

元素访问操作相对来说用的最多的就是operator[] .

? 对它进行调用时可能进行的是写操作，也可能进行读操作，所以为了适应const和非const对象，operator[]应该实现两个版本的函数,并且这个函数处理越界访问的态度就是assert直接断言，而at对于越界访问的态度是抛异常。

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

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

3.2 find()

??查找字符串中的第一个匹配项，?在string中搜索由其参数指定的序列的第一个匹配项。

?直接从pos位置遍历即可。

	size_t find(char ch, size_t pos = 0) {
		for (size_t i = pos; i < _size; i++) {
			if (_str[i] == ch){
				return i;
			}
		}
		//找不到返回npos
		return npos;
	}

size_t find(const char* sub, size_t pos = 0) {
	const char* p = strstr(sub + pos, sub);
	if (p) {
		return p - _str;
	}
	else {
		return npos;
	}
}

四 修改?

?4.1 push_back()

在字符串尾部插入单个数据。

首先，当我们的_size ==_capacity 的时候，我们要准备扩容，但是这里我们该如何扩容呢？

我的建议是，如果是初次扩容的时候，建议扩为四个字节，但以后我们每次都扩容为二倍，然后再_size的位置插入一个数据即可，注意补'\0',

? 在后续完成了insert的时候，也可以复用insert函数。

?代码如下：

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

4.2 append()

追加到字符串，?通过在当前值的末尾附加其他字符来扩展。

1. 我们可以直接调用strcpy接口来进行字符串的尾插，但是需要注意一点，那就是【string】类的字符串函数是不会进行自动扩容的，所以我们需要判断一下是否需要进行扩容，在空间预留好的情况下进行字符串的尾插即可实现。
2. 但注意，这里我们不能扩容两倍，假如我们扩容两倍后的空间，依旧不够追加的字符串的大小呢？我们这里建议直接扩容为 待插入的字符串长度+_size
3. 其次，如果已经实现了【insert】函数的情况下。我们可以直接复用【insert】函数也可实现对应的操作。

代码实现：

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

4.3?operator+=

追加到字符串，通过在当前值的末尾附加其他字符来扩展

在这里我们只实现添加字符和字符串的操作。

我们可以直接复用【push_back】和 【append] 的操作来实现。

代码如下：

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

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

4.4 insert()

插入到字符串中，在?pos（或?p）指示的字符之前将其他字符插入

?4.4.1 指定位置插入字符

1. 首先assert先断言，确保插入位置合法
2. 如果插入的总长度大于当前容量，就进行扩容，将容量扩展到?0或者2倍
3. 接着，从字符串的末尾开始，依次往后移，给插入字符留下足够的空间
4. 最后，使用一个循环将指定数量的字符ch插入到指定位置pos之后。

	// insert(0, 'x')
	void 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++;
	}

4.4.2?指定位置插入字符串

1. ?首先使用assert断言来确保插入位置pos不超过当前字符串的长度_size
2. 如果插入后的总长度_size+len超过当前容量_capacity，就扩容到_size+len的长度
3. 接着，将字符串的末尾开始，依次往后移动字符，为插入字符串成留出足够的位置。
4. 然后使用一个循环将字符串中字符赋值到pos之后的指定位置
5. 最后，更新字符串的长度_size

	void insert(size_t pos, const char* str) {
		assert(pos <= _size);
		size_t len = strlen(str);
		if (len + _size > _capacity) {
			/*reserve(_capacity == 0 ? 4 : _capacity * 2);*/
			reserve(_size + len);
		}
		size_t end = _size;
		while (end >= pos&&end!=npos) {
			_str[end + len] = _str[end];
			--end;
		}
		strncpy(_str + pos, str, len);
		_size += len;

	}

注意：这里在头部插入时有可能end会等于-1 ，插入字符串时需要判断字符串长度，才能进行元素的移动和元素的写入。

4.5 erase() 函数?

意思很简单，就是从字符串中删除字符

对于删除，思路很简单，分为两种情况下的删除：

1.如果当前位置加上要删除的长度大于字符串的长度，即【 pos + len >= _size】，此时的意思即为删除pos之后的所有元素；
2.除了上述情况，就是在字符串内正常删除操作。我们只需利用strcpy来进行，将pos+len之后的字符串直接覆盖到pos位置，这样实际上就完成了删除的工作。

代码如下：
?

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

五 字符串操作

? 5.1 c_str()

获取等效的 C 字符串，返回指向一个数组的指针，该数组包含以 null 结尾的字符序列（即 C 字符串），表示string对象的当前值

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

?5.2 比较操作

直接上代码吧。

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) const {
	return !(*this == s);
}

5.3 substr

从字符串中提取子字符串

1. 首先，使用断言assert验证起始位置pos是否小于字符串的长度，避免越界。
2. 如果len为npos或者pos+len超过了字符串的长度，n被设置为从pos到字符串末尾的长度
3. 接下来，创建一个临时的字符串对象tmp，并使用reserve()为该字符串分配足够的容量以容纳字符串
4. 然后，使用一个循环，依次将pos到pos+n的字符添加到tmp字符串中
5. 最后，返回存储子字符串tmp字符串对象

		//截取string中的一段
		string substr(size_t pos, size_t len = npos) {
			string s;
			size_t end = pos + len;
			if (len == npos || pos + len > _size) {
				len = _size - pos;
				end = _size;
			}
			s.reserve(len);
			for (size_t i = pos; i < len; i++) {
				s += _str[i];
			}
			return s;
		}

六 非成员函数重载

6.1 operator<<

?将字符串插入流，?将符合?str?值的字符序列插入到 os?中。

1. 函数的参数是一个输出流对象和一个常量字符串引用
2. 遍历每一个字符，将字符依次输出到给定的流对象中
3. 最后，函数返回输出流对象的引用

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

		return out;
	}

6.2?operator>>

从流中提取字符串，?从输入流中提取字符串，将序列存储在 str 中，该序列被覆盖（替换 str?的先前值）

1. 函数的参数是一个输入流对象和一个字符串引用
2. 首先清空字符串，然后读取输入流中的字符
3. 在处理输入之前，函数会检查并跳过缓存区前面的空格或者换行符
4. 然后，将字符一个接一个添加到字符缓冲区中，直到遇到换行符或者空格为止
5. 如果字符缓冲区已满，将缓冲区的内容追加到字符串中，并清空缓冲区
6. 最后，函数将最后一个字符缓冲区的内容追加到字符串中（如果缓冲区不为空）。函数返回输入流对象的引用。

istream& operator>>(istream& in, string& s)
{
	s.clear();
	char buff[129]{};
	size_t i = 0;

	char ch;
	ch = in.get();
	while (ch != ' ' && ch != '\n')
	{
		buff[i++] = ch;
		if (i == 128)
		{
			buff[i] = '\0';
			s += buff;
			i = 0;
		}
		ch = in.get();
	}

	if (i != 0)
	{
		buff[i] = '\0';
		s += buff;
	}

	return in;
}

七 完整代码+ 测试代码

#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstring>
#include<assert.h>
using namespace std;


namespace My {
	class string
	{
	public:

		typedef char* iterator;
		typedef const char* const_iterator;

		iterator begin(){
			return _str;
		}

		iterator end(){
			return _str + _size;
		}

		const_iterator begin() const{
			return _str;
		}

		const_iterator end() const{
			return _str + _size;
		}




		//构造函数
		string(const char* str = "")
			:_size(strlen(str))
			, _capacity(_size)
		{
			//cout << "构造函数" << endl;
			_str = new char[_capacity + 1];
			strcpy(_str, str);
		}

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

		//拷贝构造
		string(const string& s)
			:_str(nullptr)
			, _size(0)
			, _capacity(0)
		{
		   //cout << "拷贝构造函数" << endl;
			string tmp(s._str);
			swap(tmp);
		}

		//拷贝赋值
		string& operator=(const string& s) {
			//cout << "拷贝赋值函数" << endl;
			string tmp(s);
			swap(tmp);
			return *this;
		}

		//移动构造
		string(string&& s) noexcept{
			//cout << "移动构造函数" << endl;
			swap(s);
		}

		//移动赋值
		string& operator=(string&& s) noexcept {
			//cout << "移动赋值函数" << endl;
			swap(s);
			return *this;
		}

		//析构函数
		~string() {
			delete[] _str;
			_str = nullptr;
			_size = 0;
			_capacity = 0;
		}



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

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

		size_t capacity() const {
			return _capacity;
		}

		size_t size() const {
			return _size;
		}

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

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

		void resize(size_t n, char ch = '\0') {
			if (_size > n) {
				_str[n] = '\0';
				_size = n;
			}
			else{
				reserve(n);
				while (_size < n) {
					_str[_size] = ch;
					++_size;
				}
				_str[n] = '\0';
			}
		}

		size_t find(char ch, size_t pos = 0) {
			for (size_t i = pos; i < _size; i++) {
				if (_str[i] == ch){
					return i;
				}
			}
			//找不到返回npos
			return npos;
		}

		size_t find(const char* sub, size_t pos = 0) {
			const char* p = strstr(sub + pos, sub);
			if (p) {
				return p - _str;
			}
			else {
				return npos;
			}
		}

		//截取string中的一段
		string substr(size_t pos, size_t len = npos) {
			string s;
			size_t end = pos + len;
			if (len == npos || pos + len > _size) {
				len = _size - pos;
				end = _size;
			}
			s.reserve(len);
			for (size_t i = pos; i < len; i++) {
				s += _str[i];
			}
			return s;
		}

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

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

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

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

		// insert(0, 'x')
		void 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++;
		}

		void insert(size_t pos, const char* str) {
			assert(pos <= _size);
			size_t len = strlen(str);
			if (len + _size > _capacity) {
				/*reserve(_capacity == 0 ? 4 : _capacity * 2);*/
				reserve(_size + len);
			}
			size_t end = _size;
			while (end >= pos&&end!=npos) {
				_str[end + len] = _str[end];
				--end;
			}
			strncpy(_str + pos, str, len);
			_size += len;

		}

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

		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) const {
			return !(*this == s);
		}

		void clear(){
			_str[0] = '\0';
			_size = 0;
		}
	private:
		char* _str;
		size_t _size;
		size_t _capacity;

	public:
		const static size_t npos;
	};

	const size_t string::npos = -1;

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

		return out;
	}

	istream& operator>>(istream& in, string& s)
	{
		s.clear();
		char buff[129]{};
		size_t i = 0;

		char ch;
		ch = in.get();
		while (ch != ' ' && ch != '\n')
		{
			buff[i++] = ch;
			if (i == 128)
			{
				buff[i] = '\0';
				s += buff;
				i = 0;
			}
			ch = in.get();
		}

		if (i != 0)
		{
			buff[i] = '\0';
			s += buff;
		}

		return in;
	}

	void test_string1()
	{
		string s1("hello world");
		cout << s1.c_str() << endl;

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

		for (size_t i = 0; i < s1.size(); i++)
		{
			cout << s1[i] << " ";
		}
		cout << endl;

		string::iterator it = s1.begin();
		while (it != s1.end())
		{
			(*it)++;
			cout << *it << " ";
			++it;
		}
		cout << endl;

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

		cout << s1.c_str() << endl;
	}

	void test_string2()
	{
		string s1("hello world");
		cout << s1.c_str() << endl;
		s1.push_back(' ');
		s1.append("hello bit hello bit");

		cout << s1.c_str() << endl;

		s1 += '#';
		s1 += "*********************";
		cout << s1.c_str() << endl;

		string s2;
		s2 += '#';
		s2 += "*********************";
		cout << s2.c_str() << endl;
	}

	void test_string3()
	{
		string s1("hello world");
		cout << s1.c_str() << endl;

		s1.insert(5, '%');
		cout << s1.c_str() << endl;

		s1.insert(s1.size(), '%');
		cout << s1.c_str() << endl;

		s1.insert(0, '%');
		cout << s1.c_str() << endl;
	}

	void test_string4()
	{
		string s1("hello world");
		string s2("hello world");

		cout << (s1 >= s2) << endl;

		s1[0] = 'z';
		cout << (s1 <  s2) << endl;

		cout << s1 << endl;
		cin >> s1;
		cout << s1 << endl;

		/*char ch1, ch2;
		cin >> ch1 >> ch2;*/
	}

	void test_string5()
	{
		string s1("hello world");
		s1.insert(5, "abc");
		cout << s1 << endl;

		s1.insert(0, "xxx");
		cout << s1 << endl;

		s1.erase(0, 3);
		cout << s1 << endl;

		s1.erase(5, 100);
		cout << s1 << endl;

		s1.erase(2);
		cout << s1 << endl;
	}

	void test_string6()
	{
		string s1("hello world");
		cout << s1 << endl;

		s1.resize(5);
		cout << s1 << endl;

		s1.resize(25, 'x');
		cout << s1 << endl;
	}

	void test_string7()
	{
		string s1("test.cpp.tar.zip");
		//size_t i = s1.find('.');
		//size_t i = s1.rfind('.');

		//string s2 = s1.substr(i);
		//cout << s2 << endl;

		string s3("https://legacy.cplusplus.com/reference/string/string/rfind/");
		//string s3("ftp://www.baidu.com/?tn=65081411_1_oem_dg");
		// 协议
		// 域名
		// 资源名

		string sub1, sub2, sub3;
		size_t i1 = s3.find(':');
		if (i1 != string::npos)
			sub1 = s3.substr(0, i1);
		else
			cout << "没有找到i1" << endl;

		size_t i2 = s3.find('/', i1 + 3);
		if (i2 != string::npos)
			sub2 = s3.substr(i1 + 3, i2 - (i1 + 3));
		else
			cout << "没有找到i2" << endl;

		sub3 = s3.substr(i2 + 1);

		cout << sub1 << endl;
		cout << sub2 << endl;
		cout << sub3 << endl;
	}

	void test_string8()
	{
		string s1("hello world");
		string s2 = s1;
		cout << s1 << endl;
		cout << s2 << endl;

		string s3("xxxxxxxxxxxxxxxxxxx");
		s2 = s3;

		cout << s2 << endl;
		cout << s3 << endl;
	}

	void test_string9()
	{
		string s1("hello world");
		cin >> s1;
		cout << s1 << endl;
		cout << s1.size() << endl;
		cout << s1.capacity() << endl;
	}
}