[C++] string类常用接口的模拟实现

1、前言

string上篇我们实现了 各类构造与赋值重载 接口，点这里看string类的介绍与构造的模拟实现
本篇我们对string常用的接口 增删查改+遍历 模拟实现一下。

以下就是要实现的接口：

namespace s
{class string{friend ostream& operator<<(ostream& _cout, const bit::string& s);friend istream& operator>>(istream& _cin, bit::string& s);public:typedef char* iterator;public://// iteratoriterator begin()；iterator end()；/// modifyvoid push_back(char c);string& operator+=(char c);void append(const char* str);string& operator+=(const char* str);void clear();void swap(string& s);const char* c_str()const;/// capacitysize_t size()constsize_t capacity()constbool empty()constvoid resize(size_t n, char c = '\0');void reserve(size_t n);/// accesschar& operator[](size_t index);const char& operator[](size_t index)const;///relational operatorsbool operator<(const string& s);bool operator<=(const string& s);bool operator>(const string& s);bool operator>=(const string& s);bool operator==(const string& s);bool operator!=(const string& s);// 返回c在string中第一次出现的位置size_t find (char c, size_t pos = 0) const;// 返回子串s在string中第一次出现的位置size_t find (const char* s, size_t pos = 0) const;// 在pos位置上插入字符c/字符串str，并返回该字符的位置string& insert(size_t pos, char c);string& insert(size_t pos, const char* str);    // 删除pos位置上的元素，并返回该元素的下一个位置string& erase(size_t pos, size_t len);private:char* _str;size_t _capacity;size_t _size;}
}；

2、遍历

2.1 operator[ ]+下标方式

这种方式是我们最喜欢使用的一种，使用下标将字符逐个打印出来。

char& operator[](size_t pos)
{assert(pos < _size);return _str[pos];
}//只读
const char& operator[](size_t pos) const
{assert(pos < _size);return _str[pos];
}int main()
{string s1("hello world");for (int i = 0; i < s1.size(); ++i){cout << s1[i] << " ";}cout << endl;return 0;
}

2.2 迭代器

string类的迭代器的底层是一个 char 原生指针*，string的迭代器使用方法就像是使用指针一样来用就可以了，但是不是所有的迭代器都是指针。（list，对于顺序表来说，并不是连续的空间，因此底层就不是指针）。

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

我们来试一下迭代器的遍历：

int main()
{string s1("hello world");string::iterator it = s1.begin();while (it != s1.end()){cout << *it << " ";++it;}cout << endl;return 0;
}

2.3 范围for

我们在之前就接触过范围for，使用起来很简单，这次我们来深究一下范围for。

int main()
{string s1("hello world");for (auto ch : s1)//范围for的底层就是迭代器，这里很严格，begin大小写变了都会出问题{cout << ch << " ";}cout << endl;return 0;
}

我们来看看汇编代码中迭代器与范围for。

我们可以看到在汇编代码中，迭代器与范围for都是调用了begin与end函数**，这里我们就能看到范围for的底层就是范围for。**

注意：范围for是傻瓜式调用，我们将迭代器的名称字符改为大写范围for都使用不了。

2.4 c_str

由此我们知道，c_str返回的就是字符串以及末尾的 ‘\0’ ，因此我们就可以使用c_str来打印字符串。

const char* c_str() const
{return _str;
}
int main()
{cout << c_str << endl;return 0;
}

3、容量相关

3.1 size（大小）

直接返回字符串的大小，没什么讲的秒杀。

size_t size() const//对this不修改，加const保证安全
{return _size;
}

3.2 capacity（容量）

size_t capacity() const//对this不修改，加const保证安全
{return _capacity;
}

3.3 empty（判空）

bool empty() const//对this不修改，加const保证安全
{return _size == 0;
}

3.4 clear（清理）

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

这里我们不需要删掉字符串内容，直接将字符串首元素改为 ‘\0’，大小置为0即可。

3.5 reserve

由此我们可以得到，reserve函数特点是只扩不缩的。扩大到容量为n。

因此我们在实现的时候，先判断 n是否大于capacity，如果小于就不处理，大于进行扩容。

void reserve(size_t n)//reserve只扩不缩
{if (n > _capacity){char* tmp = new char[n + 1];//多一个是\0的位置strcpy(tmp, _str);//strcpy会将\0一同拷贝过去delete[] _str;_str = tmp;_capacity = n;}
}

3.6 resize

由此我们可以看出resize是对字符串的size进行扩充的。
当n小于当前字符串的大小时，将字符串缩短到n，保留字符串前n个字符。
当n大于当前字符串的大小时，字符串长度就增加，如果有指定字符，就用指定字符对大于n的空间初始化，如果没有指定，就初始化为 ‘\0’。
我们对比一下resize与reserve：
resize是对size的更改，可扩可缩，并支持初始化，会间接影响容量的大小；
reserve是对capacity的更改，只能扩容，不支持初始化。

思路：
先判断 n是否大于size
如果小于，就是缩小，直接将n位置改为 ‘\0’，size改为n即可；
如果大于，还需要判断n是否超过capacity，不超过原地修改，超过直接复用reserve，对超出当前字符串长度的空间初始化为c，并将最后一个位置置为 ‘\0’（reserve只负责扩容，不做初始化）。

void resize(size_t n, char c = '\0')//c给为缺省最合适
{if (n <= _size){_str[n] = '\0';_size = n;}else{if(n > _capacity)reserve(n);while (_size < n){_str[_size] = c;++_size;}_str[_size] = '\0';}
}

测试：

int main()
{string s1("hello world");s1.resize(5);cout << s1 << endl;s1.resize(8, 'x');cout << s1 << endl;return 0;
}

4、增

4.1 push_back（尾插）

思路：
先判满，如果满了（_size == _capacity），就扩容（二倍方式扩容），再进行尾插字符；
没有满，直接尾插字符。

void push_back(char ch)
{if (_size == _capacity){//reserve(2 * _capacity);//直接给二倍的话，对于空字符串来说，//二倍还是0，扩容里面有释放空间，会出问题reserve(_capacity == 0 ? 4 : 2 * _capacity);//三目才正确}_str[_size] = ch;_size++;_str[_size] = '\0';//别忘了还有\0，size指的是最后一个字符的下一个位置
}

注意：对于扩容的传参我们使用三目操作符，防止直接对空字符串进行尾插时给二倍，相当于没有扩容。

4.2 operator+=（char ch）

+=字符比尾插更常用，很有必要实现。逻辑与尾插是一致的，复用push_back就可以。

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

4.3 append

由此我们知道，append函数是在原有的字符串基础上追加字符串。

此函数不常用，我们仅实现第三个接口就可以了。
思路：
先判断容量是否足够，不够先扩容，但是append的扩容与尾插的扩容的大小不一样，尾插在原容量基础上扩二倍一定足够，这里是插入字符串，扩二倍不一定足够，我们来分析一下：
判断容量是否足够其实不难，我们对追加的字符串计算长度(strlen(str))，看看被追加的字符串+追加的字符串长度（_size+len）是否大于_capacity，大于就扩容，复用reserve，传值 size+len；
再使用strcpy函数，从字符串的_size位置开始，将追加的字符串拷贝到_str后面。
代码实现：

void append(const char* str)
{size_t len = strlen(str);if (_size + len > _capacity){reserve(_size + len);//这里扩容不能是二倍，因为插入的字符串长度可能大于二倍}strcpy(_str + _size, str);//strcpy会将\0一起拷贝过去_size += len;
}

4.4 operator+=（char* str）

+=很常用，尾插字符串，直接复用刚写的append即可。

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

4.5 insert（任意位置插入）

虽然insert的函数很多，但是常用的就两个，在任意位置插入字符或字符串，我们就来实现这两个。

4.5.1 任意位置插入字符

思路：
1、判断pos位置是否合法。
2、先判断是否需要扩容，与尾插一样；
3、挪动数据，从_size位置开始，依次往后挪，直到到pos位置停下来；
4、在pos位置插入数据，再++_size。

代码实现：

string& insert(size_t pos, char ch)
{assert(pos <= _size);if (_size == _capacity){reserve(_capacity == 0 ? 4 : 2 * _capacity);}size_t end = _size + 1;while (end > pos)//size_t是无符号整型，头插时end走到-1还是会进去，形成死循环{_str[end] = _str[end - 1];--end;}_str[end] = ch;_size++;return *this;
}

4.5.2 任意位置插入字符串

思路与任意位置插入字符是类似的，只需要注意一下边界就好了。

代码实现：

string& insert(size_t pos, const char* str)
{assert(pos <= _size);size_t len = strlen(str);if (_size + len > _capacity){reserve(_size + len);}//挪动数据int end = _size;while (end >= (int)pos)//这里也存在提升，end变为-1仍然进去循环，因此需要强转{_str[end + len] = _str[end];--end;}strncpy(_str + pos, str, len);_size += len;return *this;
}

5、删

这里的npos我们再来看看

我们可以看到文档中nops是size_t类型（无符号整型），值为-1，无符号整型的-1就是int类型的max。
对于erase函数，我们仅实现常用的第一个接口就可以。
文档中可以看到，erase是从pos位置开始往后删长度为len个字符。
这里erase我们要分情况来讨论：
情况一：len == npos 或者 pos+len >= _size，那么就是从pos位置到末尾全部删除，我们直接将pos位置改为 ‘\0’，_size改为pos即可。

情况二：删除其中的一段，我们定义 begin=pos+len，_str[begin-len] = _str[begin]，begin++不断挪动数据，当 begin==_size 的时候挪动完数据。因此循环结束的条件是 begin<=_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{size_t begin = pos + len;while (begin <= _size){_str[begin - len] = _str[begin];++begin;}_size -= len;}return *this;
}

6、查

6.1 查找一个字符

由文档中我们可以知道，找到后返回的是字符的位置，即就是下标。如果没有找到返回npos。

size_t find(char c, size_t pos = 0) const
{for (size_t i = pos; i < _size; ++i){if (_str[i] == c)return i;}return npos;
}

6.2 查找一个字符串

我们使用strstr来找。

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

7、字符串比较

比较的本质是ASCII码值，因此我们套用strcmp就可以。

bool operator<(const string& s)
{return strcmp(_str, s._str) < 0;
}bool operator==(const string& s) const
{return strcmp(_str, s._str) == 0;
}bool operator<=(const string& s)
{return (*this < s) || (*this == s);//复用
}bool operator>(const string& s)
{return !(*this <= s);
}bool operator>=(const string& s)
{return !(*this < s);
}bool operator!=(const string& s)
{return !(*this == s);
}

写好<与==，其他的直接复用就可以。

8、流插入、流提取重载

8.1 流提取重载

流提取使用在赋值或初始化上，因此，在赋值前我们先对空间清理一下，在对变量赋值。

istream& operator>>(istream& _cin, string& s)
{s.clear();char buff[129];//这样可以避免扩容问题size_t i = 0;char ch;//_cin >> ch//本身是拿不到' '或'\n'的，因此循环条件就判断不了ch = _cin.get();while (ch != ' ' && ch != '\n'){buff[i++] = ch;if (i == 128){buff[i] = '\0';s += buff;i = 0;//下一轮}//_cin >> ch;ch = _cin.get();}if (i != 0){buff[i] = '\0';s += buff;}return _cin;
}

8.2 流插入重载

ostream& operator<<(ostream& _cout, const string& s)//for (int i = 0; i < s.size(); ++i)//{//	_cout << s[i];//}for (auto ch : s){_cout << ch;}return _cout;
}

*** 本篇结束 ***