C++ 模拟实现string类

目录

在C++中，string类是一个非常重要的数据类型，它提供了一系列的方法来处理字符串。然而，你有没有想过string类是如何实现的呢？在这篇文章中，我们将模拟实现一个简化版的string类，这可以更好地理解其内部工作原理。

一、类的定义

我们首先定义了一个名为Byte::string的类，它包含了一些私有成员变量和公有成员函数。

namespace Byte
{
    class string
    {
    private:
        char* _str;
        size_t _capacity;
        size_t _size;

        static const size_t npos;
        //static const size_t npos = -1;//也可以
    public:
        // ...
    };
    const size_t string::npos = -1;
}

在这个类中，我们有三个私有成员变量：_str，_capacity和_size。_str是一个字符指针，用于存储字符串的内容；_capacity表示字符串的容量，即可以存储的字符数量；_size表示当前字符串的长度。此外，我们还定义了一个静态常量npos，它的值为-1，通常用于表示“不存在”的位置。

二、初始化&销毁

1、构造函数

string(const char* str = "")
	:_size(strlen(str))
{
	_capacity = _size == 0 ? 3 : _size;
	_str = new char[_capacity + 1];
	strcpy(_str, str);
}

1. 构造函数string(const char* str = "")使用了全缺省的方式，使用全缺省的构造函数，可以有以下几种调用方式：

   1. 不传递任何参数：string s;，这将创建一个空字符串的string对象。

   2. 传递一个空字符串：string s("");，这将创建一个空字符串的string对象。

   3. 传递一个非空字符串：string s("Hello");，这将创建一个包含指定字符串的string对象。

   4. 传递一个空指针：string s(nullptr);，这将创建一个空字符串的string对象。

2. _size(strlen(str)): 这是一个初始化列表，它将_size成员变量初始化为传入字符串str的长度。这是通过使用C标准库函数strlen来实现的。

3. _capaicty = _size == 0 ? 3 : _size;: 这行代码设置了_capacity成员变量的值。如果_size为0（也就是说，如果传入的字符串为空），那么_capacity被设置为3。否则，_capacity被设置为_size的值。

4. _str = new char[_capaicty + 1];: 这行代码在堆上为_str分配了足够的内存来存储字符串。分配的内存大小为_capacity + 1，额外的1用于存储字符串的空字符终止符\0。

5. strcpy(_str, str);: 这行代码将传入的字符串str复制到_str指向的内存中。这是通过使用C标准库函数strcpy来实现的。

2、辨析三种定义 

		string(const char* str = nullptr)  不可以
		string(const char* str = '\0')	 不可以
		string(const char* str = "\0")	 可以

• string(const char* str = nullptr): 这个构造函数版本不可行，因为nullptr不能被strlen和strcpy处理，这会导致未定义的行为。

• string(const char* str = '\0'): 这个构造函数版本也不可行，因为'\0'是一个字符，而不是一个字符串。它不能被赋值给const char*类型的参数。

• string(const char* str = "\0"): 这个构造函数版本是可行的，因为"\0"是一个包含空字符的字符串。然而，它与string(const char* str = "")的行为是相同的，因为在C++中，字符串总是以空字符终止。

3、析构函数

析构函数则负责释放_str指向的内存，并将所有成员变量重置为初始状态。 

~string()
{
    delete[] _str;
    _str = nullptr;
    _size = _capaicty = 0;
}

三、赋值 

1、拷贝构造函数

拷贝构造函数的目的是创建一个与参数对象s具有相同字符串和相同容量的新string对象。

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

1. string(const string& s): 这是复制构造函数的声明。它接受一个对已存在的字符串对象的引用作为参数。使用引用是为了避免无限递归，因为如果不使用引用，那么在创建新的字符串对象时会再次调用复制构造函数，如此无限循环下去。

2. _size(s._size): 这是初始化列表的一部分，它将新字符串对象的 _size 成员变量设置为传入的字符串对象的 _size。

3. _capaicty(s._capaicty): 同样是初始化列表的一部分，它将新字符串对象的 _capaicty 成员变量设置为传入的字符串对象的 _capaicty。

4. _str = new char[s._capaicty + 1];: 这行代码为新字符串对象的 _str 成员变量分配内存。它创建一个新的字符数组，大小为传入的字符串对象的 _capaicty 加 1。这里加 1 是为了留出空间存储字符串的结束字符 ‘\0’。

5. strcpy(_str, s._str);: 这行代码将传入的字符串对象的 _str 成员变量的内容复制到新字符串对象的 _str 成员变量中。

2、赋值运算符

这段代码是C++中的赋值运算符重载函数，用于将一个字符串对象赋值给另一个字符串对象。这也是一个深拷贝操作，因为它创建了新的内存空间来存储复制的字符串，而不是简单地复制指针。

string& operator=(const string& s)
{
	if (this != &s)
	{
		char* tmp = new char[s._capaicity + 1];
		strcpy(tmp, s._str);
		delete[] _str;
		_str = tmp;

		_size = s._size;
		_capaicity = s._capacity;
	}

	return *this;
}

1. string& operator=(const string& s): 这是赋值运算符重载函数的声明。它接受一个对已存在的字符串对象的引用作为参数，并返回对当前对象的引用，以便支持链式赋值（例如 a = b = c）。

2. if (this != &s): 这是一个保护性检查，用于防止自我赋值。如果尝试将一个对象赋值给它自己，那么这个检查将阻止后续的代码执行。

3. char* tmp = new char[s._capaicity + 1];: 这行代码创建一个新的字符数组，大小为传入的字符串对象的 _capaicity 加 1。这里加 1 是为了留出空间存储字符串的结束字符 ‘\0’。

4. strcpy(tmp, s._str);: 这行代码将传入的字符串对象的 _str 成员变量的内容复制到新创建的字符数组中。

5. delete[] _str;: 这行代码释放当前对象的 _str 成员变量所占用的内存。这是为了避免内存泄漏，因为 _str 将被重新赋值。

6. _str = tmp;: 这行代码将 _str 成员变量设置为新创建的字符数组的地址。

7. _size = s._size;: 这行代码将当前对象的 _size 成员变量设置为传入的字符串对象的 _size。

8. _capaicity = s._capaicity;: 这行代码将当前对象的 _capaicity 成员变量设置为传入的字符串对象的 _capaicity。

9. return *this;: 这行代码返回对当前对象的引用，以支持连续赋值。

四、成员访问

我们为这个类重载了一些运算符，以便可以像使用内置类型一样使用我们自己定义的string类。

 operator[ ]

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

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

1. const char& operator[](size_t pos) const: 这是一个重载的下标运算符，它接受一个位置参数，并返回该位置的字符的引用。这个版本的函数是常量版本，它不能用于修改字符串的内容，只能用于读取。如果位置超出字符串的大小，它会触发一个断言错误。

2. char& operator[](size_t pos): 这也是一个重载的下标运算符，它接受一个位置参数，并返回该位置的字符的引用。这个版本的函数可以用于修改字符串的内容。如果位置超出字符串的大小，它也会触发一个断言错误。

使用[ ]时会自动选取合适的函数重载，这两种重载版本的存在，使得我们可以在保证类型安全的同时，对常量和非常量字符串对象进行适当的操作。

五、比较大小&判断相等

这些函数都是常量的，这意味着它们不能修改字符串对象的状态。这些函数都接受一个对 string 对象的常量引用作为参数，这可以避免不必要的复制操作。

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

1. bool operator>(const string& s) const: 这个函数重载了大于运算符 >。它使用 strcmp 函数比较两个字符串，如果当前字符串大于参数字符串，strcmp 会返回一个大于0的值，所以函数返回 true。

2. bool operator==(const string& s) const: 这个函数重载了等于运算符 ==。它使用 strcmp 函数比较两个字符串，如果两个字符串相等，strcmp 会返回0，所以函数返回 true。

3. bool operator>=(const string& s) const: 这个函数重载了大于等于运算符 >=。它使用已经重载的 > 和 == 运算符来判断当前字符串是否大于或等于参数字符串。注释掉的代码有误，应该是 return *this > s || *this == s;。

4. bool operator<(const string& s) const: 这个函数重载了小于运算符 <。它使用已经重载的 >= 运算符来判断当前字符串是否不大于等于参数字符串，即小于参数字符串。

5. bool operator<=(const string& s) const: 这个函数重载了小于等于运算符 <=。它使用已经重载的 > 运算符来判断当前字符串是否不大于参数字符串，即小于或等于参数字符串。

6. bool operator!=(const string& s) const: 这个函数重载了不等于运算符 !=。它使用已经重载的 == 运算符来判断当前字符串是否不等于参数字符串。

六、容量操作 

1、size()

size_t size() const
{
    return _size;
}

size_t size() const: 这个函数返回字符串的大小，即字符串中的字符数量。这个函数是常量函数，这意味着它不能修改字符串的状态。

2、reserve

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

		_capacity = n;
	}
}

1. if (n > _capacity): 检查新的容量 n 是否大于当前的容量 _capacity。如果不是，那么函数立即返回，不做任何操作。

2. char* tmp = new char[n + 1];: 如果新的容量大于当前的容量，那么首先创建一个新的字符数组，大小为新的容量加 1。这里加 1 是为了留出空间存储字符串的结束字符 ‘\0’。

3. strcpy(tmp, _str);: 然后将当前字符串的内容复制到新的字符数组中。

4. delete[] _str;: 然后释放当前字符串的内存。这是为了避免内存泄漏，因为 _str 将被重新赋值。

5. _str = tmp;: 然后将 _str 指向新的字符数组。这样，_str 就指向了一个更大的内存区域，可以存储更多的字符。

6. _capacity = n;: 最后更新字符串的容量为新的容量。

3、push_back

void push_back(char ch)
{
	if (_size + 1 > _capacity)
	{
		reserve(_capacity * 2);
	}

	_str[_size] = ch;
	++_size;

	_str[_size] = '\0';
}

void push_back(char ch): 这个函数在字符串的末尾添加一个字符。如果添加新字符后字符串的大小超过了当前的容量，那么它会首先调用 reserve 函数来增加字符串的容量。然后它将新字符添加到字符串的末尾，并更新字符串的大小，最后不要忘记补充‘ \0 ’在新的字符串末尾。 

4、append

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

	strcpy(_str + _size, str);
	_size += len;
}

void append(const char* str): 这个函数在字符串的末尾添加一个C风格字符串。它首先计算要添加的字符串的长度，如果添加新字符串后字符串的大小超过了当前的容量，那么它会首先调用 reserve 函数来增加字符串的容量。然后它将新字符串添加到当前字符串的末尾，并更新字符串的大小。

5、加等运算符 

这两个函数提供了一种简洁的方式来修改字符串的内容，它们可以用来代 push_back 和 append 函数。

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

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

1. string& operator+=(char ch): 这个函数接受一个字符作为参数，并在字符串的末尾添加这个字符。它调用了 push_back 函数来完成这个操作。然后它返回对当前对象的引用，以支持链式操作，例如 str += 'a' += 'b'。

2. string& operator+=(const char* str): 这个函数接受一个C风格字符串作为参数，并在字符串的末尾添加这个字符串。它调用了 append 函数来完成这个操作。然后它也返回对当前对象的引用，以支持链式操作，例如 str += "hello" += " world"。

6、C风格

const char* c_str()
{
    return _str;
}

const char* c_str(): 这个函数返回一个指向字符串内部字符数组的指针。这个函数通常用于与需要C风格字符串的函数进行交互。返回类型为 const char*，意味着你不能通过这个指针修改字符串的内容。 

7、insert

这两个 insert 函数用于在 string 对象的指定位置插入字符或字符串。

插入字符 

 下面的代码有什么问题呢？

void insert(size_t pos, char ch)
{
	assert(pos <= _size);
	if (_size + 1 > _capacity)
	{
		reserve(2 * _capacity);
	}

	size_t end = _size;
	while (end >= pos)
	{
		_str[end + 1] = _str[end];
		--end;
	}

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

• 这段代码的主要问题在于 while 循环中的条件判断。在 C++ 中，size_t 是无符号整数类型，当 end 为 0 时，--end 会导致 end 变为最大的无符号整数，而不是 -1。因此，当 pos 为 0 时，end >= pos 的判断条件始终为 true，这会导致无限循环。
• 在这个无限循环中，程序会尝试访问 _str[end]，其中 end 是一个非常大的数。这将导致数组越界，可能会引发运行时错误，或者导致未定义的行为。

对上述代码进行改进： 

string& insert(size_t pos, char ch)
{
	assert(pos <= _size);
	if (_size + 1 > _capacity)
	{
		reserve(2 * _capacity);
	}

	size_t end = _size + 1;
	while (end > pos)
	{
		_str[end] = _str[end-1];
		--end;
	}

	_str[pos] = ch;
	++_size;

	return *this;
}

1. string& insert(size_t pos, char ch): 这个函数在指定位置 pos 插入一个字符 ch。

2. 首先，它检查位置是否有效，然后检查是否需要增加字符串的容量。

3. 接下来，它将从位置 pos 开始的所有字符向后移动一位，为新字符腾出空间。

4. 然后，它在位置 pos 插入新字符，并更新字符串的大小。

5. 最后，它返回对当前对象的引用，以支持链式操作。

插入字符串

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

	strncpy(_str + pos, str, len);
	_size += len;

	return *this;

}

1. string& insert(size_t pos, const char* str): 这个函数在指定位置 pos 插入一个C风格字符串 str。

2. 首先，它检查位置是否有效，然后计算要插入的字符串的长度，然后检查是否需要增加字符串的容量。

3. 然后，它将从位置 pos 开始的所有字符向后移动 len 位，为新字符串腾出空间。然后，它在位置 pos 插入新字符串，并更新字符串的大小。

4. 最后，它也返回对当前对象的引用，以支持链式操作。

insert实现push_back&append

void push_back(char ch)
{
	//if (_size + 1 > _capacity)
	//{
	//	reserve(_capacity * 2);
	//}

	//_str[_size] = ch;
	//++_size;

	//_str[_size] = '\0';
	insert(_size, ch);
}

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

	//strcpy(_str + _size, str);
	strcat(_str, str);
	//_size += len;
	insert(_size, str);
}

8、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);
		}

		size_t i = _size;
		while (i < n)
		{
			_str[i] = ch;
			++i;
		}

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

这个 resize 函数用于改变 string 对象的大小。它接受两个参数：新的大小 n 和用于填充的字符 ch，默认为 ‘\0’。

1. if (n < _size): 如果新的大小 n 小于当前的大小 _size，那么将删除多余的字符。这通过将 _size 设置为 n，并在新的末尾位置添加结束字符 ‘\0’ 来实现。

2. else if (n > _size): 如果新的大小 n 大于当前的大小 _size，那么将添加额外的字符。

3. if (n > _capacity): 如果新的大小 n 大于当前的容量 _capacity，那么将调用 reserve 函数来增加字符串的容量。
4. while (i < n): 然后使用一个循环来添加额外的字符。每个额外的字符都被设置为 ch。
5. _size = n;: 最后更新字符串的大小为新的大小 n，并在新的末尾位置添加结束字符 ‘\0’。

9、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);
		_size -= len;
	}

	return *this;
}

1. 函数定义: string& erase(size_t pos, size_t len = npos) 定义了一个名为 erase 的成员函数，它属于某个 string 类型。它接受两个参数：pos 和 len。pos 是要开始删除的位置索引（从零开始），而 len 是要删除的字符数。如果 len 没有指定，默认值是 npos，这通常表示字符串的最大长度，意味着从 pos 开始删除到字符串末尾。

2. assert(pos < _size); 这一行是一个调试时使用的断言，确保 pos 小于当前字符串的大小 _size。如果 pos 大于等于 _size，程序会在调试模式下终止。

3. 检查 len 和删除操作:

   • 如果 len 等于 npos 或 pos + len 大于等于 _size（意味着要删除的范围超出了字符串的末尾），那么只需将位置 pos 处的字符设置为 \0（空字符），表示字符串在这里结束。然后更新 _size 为 pos，相当于删除了从 pos 到字符串末尾的所有字符。
   • 如果不是上述情况，则执行 else 里的代码。这里使用 strcpy(_str + pos, _str + pos + len); 来删除指定的字符。这个操作实际上是将 pos + len 之后的字符串复制到 pos 处，从而覆盖掉要删除的部分。然后更新 _size 来反映新的字符串长度，即减去删除的字符数。

4. 返回值: 函数返回 *this，即返回经过修改后的字符串对象的引用。这允许链式调用，例如 str.erase(1, 3).append("abc");。

10、swap

通过使用std::swap函数，它交换了两个对象的成员变量，包括字符串内容、容量和大小。

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

11、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);

	// kmp
	char* p = strstr(_str + pos, str);
	if (p == nullptr)
	{
		return npos;
	}
	else
	{
		return p - _str;
	}
}

这两个函数都是 string 类的 find 方法的实现，用于在字符串中查找特定的字符或子字符串。我将逐步解释它们的作用和逻辑：

1. 函数定义：size_t find(char ch, size_t pos = 0) 和 size_t find(const char* str, size_t pos = 0) 定义了两个重载的 find 函数。第一个函数用于查找单个字符 ch，第二个函数用于查找子字符串 str。两个函数都接受一个可选的起始位置 pos，默认值为 0，表示从字符串的开始位置进行查找。

2. 断言：assert(pos < _size); 这一行是一个调试时使用的断言，确保 pos 小于当前字符串的大小 _size。如果 pos 大于等于 _size，程序会在调试模式下终止。

3. 查找字符：在第一个 find 函数中，从位置 pos 开始，遍历字符串中的每个字符，如果找到与 ch 相等的字符，就返回其位置。如果遍历完整个字符串都没有找到，就返回 npos，通常表示字符串的最大长度，这里用作查找失败的标志。

4. 查找子字符串：在第二个 find 函数中，使用 strstr 函数从位置 pos 开始查找子字符串 str。strstr 是 C/C++ 标准库中的一个函数，用于在一个字符串中查找另一个字符串的首次出现位置。如果找到，strstr 返回第一次出现的位置的指针，否则返回 nullptr。如果 strstr 返回 nullptr，表示没有找到子字符串，函数返回 npos。否则，返回找到的位置，即 p - _str。

七、迭代器

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

1. typedef char* iterator;: 这行代码定义了一个类型别名 iterator，它是 char* 类型的别名。这意味着你可以使用 iterator 来代替 char*。

2. typedef const char* const_iterator;: 这行代码定义了一个类型别名 const_iterator，它是 const char* 类型的别名。这意味着你可以使用 const_iterator 来代替 const char*。

3. iterator begin(): 这个函数返回一个指向字符串开始的迭代器。在这个 string 类中，字符串的开始就是 _str 成员变量的地址。

4. iterator end(): 这个函数返回一个指向字符串结束的迭代器。在这个 string 类中，字符串的结束就是 _str 成员变量的地址加上字符串的大小 _size。

5. const_iterator begin() const: 这是 begin() 函数的常量版本，它返回一个指向常量字符串开始的常量迭代器。这个函数是常量的，这意味着它不能修改字符串对象的状态。

6. const_iterator end() const: 这是 end() 函数的常量版本，它返回一个指向常量字符串结束的常量迭代器。这个函数也是常量的。

八、流输出流输入

ostream& operator<<(ostream& out, const string& s)：这是输出流操作符<<的重载函数，用于将string对象s输出到输出流out。

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

1. for (auto ch : s)：这是一个范围for循环，用于遍历字符串s中的每一个字符ch。
2. out << ch：这行代码将字符ch输出到输出流out。
3. return out：最后，函数返回输出流out，以便进行链式操作。

在类中定义clear()成员函数用于清空 string 对象中的字符串。

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

 istream& operator>>(istream& in, string& s)：这是输入流操作符>>的重载函数，用于从输入流in读取数据到string对象s。 

std::istream& operator>>(std::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;
}

1. 首先，函数接收两个参数，一个是输入流对象in，另一个是字符串s。这个函数的目的是从输入流in中读取字符，然后将这些字符存储到字符串s中。

2. 在函数开始时，首先清空字符串s，以确保它是空的。

3. 然后，使用in.get()函数从输入流中获取一个字符，并将其存储在变量ch中。

4. 定义一个字符数组buff，用于临时存储从输入流中读取的字符。同时定义一个变量i，用于跟踪buff中的当前位置。

5. 接下来是一个循环，该循环会一直执行，直到从输入流中读取的字符是空格或换行符。在循环中，首先将从输入流中读取的字符存储到buff中，然后增加i的值。

6. 如果i的值达到127（即buff的最大容量），则将buff的最后一个字符设置为\0（表示字符串的结束），然后将buff中的内容添加到字符串s中，并将i重置为0。

7. 在每次循环的结束，都会从输入流中获取一个新的字符。

8. 循环结束后，如果buff中还有未添加到s的字符（即i不等于0），则将buff的最后一个字符设置为\0，然后将buff中的内容添加到s中。

9. 最后，函数返回输入流对象in，以便可以链式地进行更多的输入操作。

完整版代码

#pragma once
#include <assert.h>
#include<string.h>
#include <algorithm>
#include <iostream>
namespace test
{
	class string
	{
	private:
		char* _str;
		size_t _size;
		size_t _capacity;
		static const size_t npos;
	 
	public:
		string(const char* str = "")
			:_size(strlen(str))
		{
			_capacity = _size == 0 ? 3 : _size;
			_str = new char[_capacity + 1];
			strcpy(_str, str);
		}

		~string()
		{
			delete[] _str;
			_str = nullptr;
			_size = _capacity = 0;
		}

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

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

		char& operator[](size_t pos)
		{
			assert(pos < _size);
			return _str[pos];
		}
		const char& operator[](size_t pos) const
		{
			assert(pos < _size);
			return _str[pos];
		}
		
		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);
		}
		
		size_t size()const
		{
			return _size;
		}

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

		void push_back(char ch)
		{
			if (_size + 1 > _capacity)
			{
				reserve(_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;
		}
		const char* c_str()
		{
			return _str;
		}
		string& insert(size_t pos, char ch)
		{
			assert(pos <= _size);
			if (_size + 1 > _capacity)
			{
				reserve(2 * _capacity);
			}
			size_t end = _size + 1;
			while (end > pos)
			{
				_str[end] = _str[end - 1];
				--end;
			}
			_size++;
			_str[pos] = ch;
			return *this;
		}
		string& insert(size_t pos, char* str)
		{
			assert(pos <= _size);
			size_t len = strlen(str);
			if (_size + len > _capacity)
			{
				reserve(2 * _capacity);
			}
			size_t end = _size + len;
			while (end > pos - 1 + len)
			{
				_str[end] = _str[end - len];
				--end;
			}
			strncpy(_str + pos, str, len);
			_size + len;
			return *this;
		}
		void resize(size_t n, char ch = '\0')
		{
			if (n < _size)
			{
				_size = n;
				_str[_size] = '\0';
			}
			else if (n > _size)
			{
				if (n > _capacity)
					reserve(n);
				size_t i = _size;
				while (i < n)
				{
					_str[i] = ch;
					++i;
				}
				_size = n;
				_str[_size] = '\0';
			}
		}
		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);
				_size = pos;
			}
			return *this;
		}
		void swap(string& s)
		{
			std::swap(_str, s._str);
			std::swap(_capacity, s._capacity);
			std::swap(_size, s._size);
		}
		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);

			// kmp
			char* p = strstr(_str + pos, str);
			if (p == nullptr)
			{
				return npos;
			}
			else
			{
				return p - _str;
			}
		}
		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;
		}

		

		void clear()
		{
			_str[0] = '\0';
			_size = 0;
		}
		
	};
	const size_t string::npos = -1;

	std::ostream& operator<<(std::ostream& out, const string& s)
	{
		for (auto ch : s)
		{
			out << ch;
		}
		return out;
	}
	std::istream& operator>>(std::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;
	}
}