【C++】string类的模拟实现

// '\0' -- 字符0，ascll码值为0 
// "\0" -- 字符串有两个\0，因为默认有一个\0
// ""   -- 有一个\0，字符串默认以\0结尾
//将无参构造函数和有参构造函数搞一块儿，整个全缺省参数的构造函数就可以直接替代前面两个构造函数了。
string(const char* str = "")
	//默认的缺省值是\0字符串，如果是\0字符，那就相当于ascll码值0，那其实就是nullptr，strlen在nullptr中找\0时就会报错，崩溃
	//:_str(str)//权限会放大，不能这样初始化。
{
	//std::string：标准中未规定需要\0作为字符串结尾。编译器在实现时既可以在结尾加\0，也可以不加。（因编译器不同）
	_size = strlen(str);
	_capacity = _size;
	_pstr = new char[_capacity + 1];//capacity存的是有效字符，只是在实际开空间的时候多开一个位置给\0

	strcpy(_pstr, str);
}
/*string()
{
	_pstr = new char[1];
	_size = _capacity = 0;
	_pstr[0] = '\0';
}*/

//string s2(s1)
/*string(const string& s)//传统写法
{
	_pstr = new char[s._capacity + 1];
	_capacity = s._capacity;
	_size = s._size;//类里面不受访问限定符private/public/protected的限制

	strcpy(_pstr, s._pstr);
}*/
string(const string& s)//现代写法
	:_pstr(nullptr)
	,_size(0)
	, _capacity(0)
{
	//重构代码:不改变代码外在行为的前提下，对代码做出修改，以改进程序的内部结构。

	string tmp(s._pstr);//调用构造函数，tmp和s有一样大的空间和一样的值
	//下面不可以用赋值，要不然tmp析构的时候，this的_pstr又变成野指针了，this被析构时又会发生问题了。
	//库 里面的swap代价太大，需要不断进行实例化swap模板
	//swap(_pstr, tmp._pstr);
	//swap(_capacity, tmp._capacity);
	//swap(_size, tmp._size);//交换之后，tmp的_pstr就变成野指针了，出了函数栈帧tmp销毁时就会野指针访问，用初始化列表可以解决。
	
	//this->swap(tmp);
	swap(tmp);//可以不用this指针调用，因为在类里面，swap默认的左边第一个参数就是this，直接调用就可以。

	//如果要交换两个对象时不要用swap(s1,s2)这个代价大，应该用s1.swap(s2)，如果用库的swap则会发生三次深拷贝。
	//总结:内置类型调算法库里面的swap，自定义类型调成员函数swap
}

//s2=s1
//string& operator=(const string& s)//传统写法
//{
//	if (this != &s)//不要自己给自己赋值
//	{
//		delete[] _pstr;//清空掉s2原有的数据，然后进行赋值
//		_pstr = new char[s._capacity + 1];
//		strcpy(_pstr, s._pstr);

//		_size = s._size;
//		_capacity = s._capacity;

//	}
//	return *this;
//}
//string& operator=(const string& s)//现代写法
//{
//	//代码重构
//	if (this != &s)
//	{
//		//string tmp(s._pstr);
//		string tmp(s);//调用拷贝构造或者构造函数
//		swap(tmp);
//	}
//	return *this;
//}
string& operator=(string s)//现代写法的另一种更为常用的写法，s是现成的打工人，身份地位和tmp一样
//传值传参不存在权限的放大和缩小，指针和引用才有权限的放大和缩小，传值只是权限的平移，无论是const还是非const，直接拷贝就行
{	
	swap(s);
	return *this;
}

~string()
{
	//delete和free内部实现中都有一个特征，他们内部会检查指针，如果指针为空，则什么都不做。所以delete[]或free空指针不会报错
	delete[] _pstr;
	_pstr = nullptr;
	_size = _capacity = 0;
}

typedef char* iterator;

iterator begin()const
{
	return _pstr;
}
iterator end()const
{
	return _pstr + _size;
}

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

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

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

	for (auto ch : s1)
	{
		cout << ch << " ";
	}
	cout << endl;
	//范围for就是用迭代器实现的，在编译范围for的代码之前先将代码替换为迭代器的实现，有点类似于宏.
	//所以在实际编译的时候编译的是替换之后的迭代器的代码，替换的迭代器必须是begin和end，如果我们将自己的begin改成Begin，
	//则iterator的调用还可以进行，但范围for就无法通过，因为范围for只能调用begin()和end()，这是写死的。

	//范围for调用我们自己写的迭代器的原因是因为，它会先去局部找，然后再去全局找，局部有我们自己实现的begin和end，则范围for就会
	//自动调用。

	//只要一个容器有迭代器，那么这个容器就可以支持范围for，迭代器必须是原模原样的begin和end
}

size_t size()const//利用public的函数让类外能够访问到类中的private成员
{
	return _size;
}
size_t capacity()const
{
	return _capacity;
}

void resize(size_t n, char ch = '\0')//resize需要开空间和初始化，我们将初始化的ch默认缺省为\0
{
	//分三种情况，删除数据，不扩容增加数据，扩容增加数据，后两种情况可以合起来，因为是插入数据
	if (n > _size)//插入数据
	{
		reserve(n);//插入数据，调用扩容接口
		for (size_t i = _size; i < n; i++)
		{
			_pstr[i] = ch;
		}
		_size = n;
		_pstr[_size] = '\0';
	}
	else//删除数据
	{
		_pstr[n] = '\0';
		_size = n;
	}
}

void reserve(size_t n)
{
	//reserve尽量不要缩容，最好是扩容。
	//下面代码只有扩容，如果是缩容，则什么都不做。
	if (n > _capacity)
	{
		char* tmp = new char[n + 1];//开空间的时候多开一个给\0，n代表的是有效字符的大小
		strcpy(tmp, _pstr);
		delete[] _pstr;
		_pstr = tmp;

		_capacity = n;
	}
}

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

//普通对象:可读可写
char& operator[](size_t pos)//operator[]是可能读和可能写的，所以需要实现两个版本
{
	assert(pos < _size);
	return _pstr[pos];
}
//const对象:只读
char& operator[](size_t pos)const//只读的版本
{
	assert(pos < _size);
	return _pstr[pos];
}

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

void append(const char* str)
{
	//string系列的库函数是不会自动扩容的，都需要在有足够空间的情况下进行操作，strcat是行不通的在这里，因为空间不一定够
	size_t len = strlen(str);
	if (_size + len > _capacity)
	{
		reserve(_size + len);//这里开空间不需要加1，只需要传有效字符的个数就可以了，底层实际多开一个\0空间的工作交给reserve
	}
	strcpy(_pstr + _size, str);//strcpy会把\0也拷贝过去
	_size += len;
}

string& operator+=(char ch)
{
	push_back(ch);
	return *this;
}
string& operator+=(const char* str)
{
	append(str);
	return *this;//返回对象的引用
}

string& insert(size_t pos, char ch)//pos位置不可能是一个负数，所以我们用size_t来进行定义
{
	assert(pos <= _size);//==_size就相当于在\0位置插入数据，也就是尾插
	if (_size == _capacity)
	{
		int new_capacity = _capacity == 0 ? 4 : _capacity * 2;
		reserve(new_capacity);
	}
	//挪动数据
	/*int end = _size;
	while (end >= (int)pos)//可以用int类型的end，然后再将pos强转为int类型即可。
	{
		_pstr[end + 1] = _pstr[end];
		--end;
	}*/
	size_t end = _size + 1;//end表示需要被挪动的数据应该被挪动到的位置。
	//但如果将类型改为int，也会报错，因为会发生隐式类型转换，需要将while的判断条件调整一下
	while (end > pos)//如果进行头插，这里就会出现问题，end会减到-1，然后去end>=pos位置进行判断，但是end是size_t类型:死循环
		//如果改为int，这里会用-1和size_t的pos进行比较，int会隐式类型转换为size_t，程序会死循环
	{
		_pstr[end] = _pstr[end - 1];
		--end;
	}
	_pstr[pos] = ch;
	_size++;

	return *this;
}

string& insert(size_t pos, const char* str)
{
	//1.判断空间是否足够，不够就扩容
	size_t len = strlen(str);
	if (_size + len > _capacity)
	{
		reserve(_size + len);//这里开空间不需要加1，只需要传有效字符的个数就可以了，底层实际躲开一个\0空间的工作交给reserve
	}
	//2.挪动数据然后插入字符串。
	// (1)还是用下面强转的方式简单
	int end = _size;//用int就是为了防止end为-1时，循环还能继续进行从而发生死循环
	while (end >= (int)pos)//这样的代码是可以支持头插的。因为end是int，pos也被强转为int了。
	{
		_pstr[end + len] = _pstr[end];
		end--;
	}
	//(2)这个思考起来太麻烦了
	//size_t end = _size + len;//end表示数据将要被向后挪动到的位置。
	//while (end > pos + len - 1)//end位置和pos原有数据应该被挪动到的位置进行比较
	//while (end >= pos + len)//也可以，因为这里的等于时end位置不会为0，进入循环结束之后，就会跳出循环，而不是变为-1继续判断
	//{
	//	_pstr[end] = _pstr[end - len];
	//	end--;
	//}
	//  不要用strcpy，因为strcpy会把\0也拷贝进去。可以使用strncpy或者memcpy，memmove比memcpy可以多处理内存重叠的情况。
	//但如果是两个字符串的拷贝，就不存在内存重叠的情况，直接用memcpy就够了，不用memmove
	strncpy(_pstr + pos, str, len);

	_size += len;//不要忘了将_size+=，如果不+=，那么扩容就无法正常进行
	return *this;
}

string& erase(size_t pos, size_t len = npos)
{
	assert(pos <= _size);
	if (len == npos || len + pos >= _size )//pos代表pos位置之前还有几个有效数据
	{
		_pstr[pos] = '\0';
		_size = pos;
	}
	else
	{
		strcpy(_pstr + pos, _pstr + pos + len);
		_size -= len;
	}
	return *this;
	//如果不搞引用返回的话，则会发生浅拷贝因为我们没写拷贝构造，临时对象离开函数会被销毁，则对象s1指向空间为OS，越界访问。
}

class string
{
public:

private:
		//类模板不支持分离编译，因为用的地方进行了实例化，但用的地方只有声明没有定义，而有定义的地方却没有实例化，所以发生链接错误
		//1.如果在定义的地方进行了实例化，则通过.h文件找到方法之后，方法已经发生实例化了，那么就不会发生链接错误。
		//2.或者直接将声明和定义放到.hpp文件中，只要用的地方包含了.hpp文件，则类定义的地方就会进行实例化。
		char* _pstr;
		size_t _size;//理论上不可能为负数，所以我们用size_t类型进行定义
		size_t _capacity;
		//如果在调用构造函数的时候没有显示传参初始化成员变量，则成员变量会利用C++11的缺省值在构造函数的初始化列表进行初始化

		const static size_t npos = -1;
		//静态成员变量在类中声明，定义必须在类外面，因为它属于整个类。但const修饰的静态成员变量可以直接在类中进行定义，算特例。
		//但const修饰静态成员变量在类中可以进行定义的特性，只针对于整型类型，换个类型就不支持了。***给整型开绿灯***

		//const static double X ;
	};

void swap(string& str)
{
	std::swap(_pstr, str._pstr);
	std::swap(_capacity, str._capacity);
	std::swap(_size, str._size);
}

size_t find(const char ch, size_t pos = 0)const
{
	assert(pos < _size);
	while (pos < _size)//一般来说不会查找空字符，所以这里就不加=
	{
		if (_pstr[pos] == ch)
		{
			return pos;
		}
		pos++;
	}
	return npos;//找不到返回npos
}
size_t find(const char* str, size_t pos = 0)const
{
	assert(pos < _size);
	const char* p = strstr(_pstr + pos, str);
	if (p == nullptr)
		return npos;
	return p - _pstr;
}

const char* c_str()
{
	return _pstr;
}

ostream& operator<<(ostream& out, const string& s)
{
	//返回值是ostream&，这样可以连续使用cout
	//流插入和流提取必须重载成全局的，而且得是友元。(这句话是错误的，必须是全局但不一定得是友元因为可以用public函数获取private)
	for (auto ch : s)//会被替换为迭代器，*迭代器拿到ch的值
	{
		out << ch;
		ch++;
	}
	/*for (size_t i = 0; i < s.size(); i++)
	{
		out << s[i];
	}*/
	return out;
}

istream& operator>>(istream& in, string& s)//这里不能用const了，因为要将控制台输入后的内容拷贝到对象s里面
{
	s.clear();//上来就清空一下，这样就可以支持已初始化对象的流提取了

	/*char ch;
	in >> ch;*/

	//流提取就是从语言级缓冲区中拿数据，但是他拿不到空格和换行符，因为istream类的流提取重载就是这么规定的
	//所以要解决的话，我们就不用流提取重载，我们改用istream类的get()函数来一个一个获取缓冲区里面的每个字符。
	char ch = in.get();
	while (ch != ' ' && ch != '\n')
	{
		s += ch;//如果输入到缓冲区里的字符串非常非常的长，那么+=就需要频繁的扩容，则效率就会降低。
	//	//in >> ch;
		ch = in.get();//C++的get()和C语言的getchar()的功能是一样的，都是获取缓冲区的字符
	}

	//方法1.reserve解决方案
	//reserve大了，空间浪费，如果小了，一旦字符串又过大，则还会需要频繁的扩容，reserve可以，但是不是特别好的方法。

	//方法2.开辟buff数组
	/*如果你输入的字符个数过于少，有效字符的个数不到127的话，跳出while循环之后，我们还需要另外判断，
	再将buff中还没有满的数据 += 到对象s里面去。
	如果输入的字符个数过于多，无需担心，我们以127个有效字符为一组，每组满了就将这一组的数据 += 到对象s里面去，
	库里面大概就是这么实现的。*/
	char buff[128] = { '\0' };
	size_t i = 0;
	char ch = in.get();
	while (ch != ' ' && ch != '\n')
	{
		//if (i < 127)//这里的大小必须是127，最后得留一个位置给\0，要不然没有标识字符，字符串的结尾具体在哪里找不到，打印出错
		//{
		//	buff[i++] = ch;
		//}
		//else
		//{
		//	s += buff;
		//	i = 0;
		//}
		//ch = in.get();

		//上面这种逻辑，输入的有效字符个数超过127或者更大的时候，实际存到s里面的字符个数会变少，下面的逻辑是正确的。
		
		if(i == 127)
		{
			s += buff;//+=的字符串buff是以\0结尾的
			i = 0;
		}
		buff[i++] = ch;
		ch = in.get();
	}
	if (i >= 0)//i代表已经插入的有效字符的个数，个数对应的下标位置正好是最后一个有效元素的下一个位置。
	{
		buff[i] = '\0';
		s += buff;//将上面插入的\0之前的字符串+=到对象s里。
	}
	return in;
}

istream& getline(istream& in, string& s)
//vs编译器会将istream类的默认构造自动删除，防止出现浅拷贝等不确定问题，所以需要用引用或者自己定义深拷贝的拷贝构造函数。
{
	char ch = in.get();
	while (ch != '\n')
	{
		s += ch;
		ch = in.get();//get()一点一点从缓冲区里面拿字符，直到遇到\n，这才是getline，遇到空格和\n的应该是>>
	}
	return in;
}

template <class T> void swap ( T& a, T& b )
{
  T c(a); a=b; b=c;
}
void test_string9()
{
	//下面这样的写法是为了支持函数模板，有时候模板参数可能是自定义类型或内置类型，所以为了兼容内置类型，就搞了这样的写法。
	int i(10);//等价于int i = 10;
	int j = int();//匿名对象的赋值重载
}