string的底层实现

String底层实现

 
string在C++也是一个重要的知识，但是想要用好它，就要知道它的底层是如何写的，才能更好的用好这个string，那么这次就来实现string的底层，但是string的接口功能是非常多的，我们无法一一来实现它，这次实现的主要是它常用的接口，和重要的接口这次实现的功能有：string的构造函数，拷贝构造函数，析构函数，迭代器（分为const与非const两个版本），reserve，push_back,append,+=（分为+=字符与字符串），clear，swap，流插入，流输出，c_str，size，capacity，empty，resize，[]的重载（非为const与非const两个版本），=,==,!=的重载，find（分为查找字符与字符串两个版本）insert（分为插入字符与插入字符串的两个版本），erase。（至于实现了多少个，这里就不数了，挺多的了...
首先做好准备工作: 因为要单独实现string的底层，所以为了避免与库内的string冲突，所以我们把它封装在一个单独命名空间中，其次它的四个私有成员：_str(存储字符串），_capacity(记录容量大小),_size（记录有效字符),npos（在某些函数需要用到它)

 
一：构造函数

1它的有效个数与大小就是它的长度，用strlen计算即可。
2开一个空间（这里+1为了给\0预留位置 开空间时都必须给\0多开一个)
3在把字符串拷贝到开好的空间内

1. 1         string(const char* str = "")
2. 2             :_size(strlen(str))
3. 3             , _capacity(_size)
4. 4         {
5. 5             _str = new char[_capacity + 1];//+1是为了给 '\0' 留位置 string开空间都必须多一个位置
6. 6             strcpy(_str, str);
7. 7         }

复制代码

 
二：拷贝构造

拷贝构造分为：传统写法与现代写法
传统写法：该构造就构造，该拷贝就拷贝
1它的有效个数与大小就是它的长度，用strlen计算即可。
2开一个空间 （给\0多开一个空间）
3讲字符串拷贝到该空间内
4把该空间赋值给_str 
5把它的size与capacity与s同步

1. 1         string(const string& s)
2. 2             :_size(strlen(s._str))
3. 3             ,_capacity(_size)
4. 4         {
5. 5             char* tmp = new char[_capacity + 1];
6. 6             strcpy(tmp, s._str);
7. 7             _str = tmp;
8. 8             _size = s._size;
9. 9             _capacity = s._capacity;
10. 10         }

复制代码

现代写法：利用tmp拷贝，再让他们交换
1因为拷贝构造是拷贝给一个不存在的，所以要先把他们初始化，才能让他们交换
2利用tmp构造一个需要拷贝的字符串
3再让_str与tmp交换

1.         string(const string& s)
2.             :_str(nullptr)
3.             ,_size(0)
4.             ,_capacity(0)
5.         {
6.             string tmp(s._str);
7.             swap(tmp);
8.         }

复制代码

（这里更推荐现代写法）
 
三：析构函数

 1当str不为空
2释放，并且置空，再把它的有效字符与大小置0

1. 1         ~string()
2. 2         {
3. 3             if (_str)
4. 4             {
5. 5                 delete[] _str;
6. 6                 _str = nullptr;
7. 7                 _size = _capacity = 0;
8. 8             }
9. 9         }

复制代码

 
四：赋值重载

分为传统写法与现代写法①和②
传统写法
1当不是自己给自己赋值时
2开一个空间
3把字符串拷贝进该空间
4释放掉_str的空间
5把tmp空间赋值给_str
6再把_str与赋值的字符串的有效字符与大小相同
7返回

1. 1         string& operator=(const string &s)
2. 2         {
3. 3             if (this != &s)
4. 4             {
5. 5                 char* tmp = new char[s._capacity + 1];
6. 6                                strcpy(tmp, s._str);
7. 7                 delete[] _str;
8. 8                 _str = tmp;
9. 9                 _size = s._size;
10. 10                 _capacity = s._capacity;
11. 11             }
12. 12             return *this;
13. 13         }   

复制代码

现代写法①

1利用tmp构造一个字符串
2让_str与tmp交换
3返回

1. 1         string& operator=(const string &s)
2. 2         {
3. 3             string tmp(s._str);
4. 4             swap(tmp);
5. 5             return *this;
6. 6         }

复制代码

现代写法②

1这里有些特殊，因为需要直接交换而不改变s的数据，就不用引用，而是用传值返回
2把_str与字符串交换
3返回

1. 1         string& operator=(string s)
2. 2         {
3. 3             swap(s);
4. 4             return *this;
5. 5         }

复制代码

 
五：swap

因为要完成三个私有成员的交换操作，所以swap里直接交换三个私有成员
这里要借助库里的，但编译器在命名空间内会默认使用该命名空间下的swap，所以我们需要加上std，使用库里的swap

1. 1         void swap(string& s)
2. 2         {
3. 3             std::swap(_str, s._str);
4. 4             std::swap(_size, s._size);
5. 5             std::swap(_capacity, s._capacity);
6. 6     }

复制代码

 
六：c_str

因为还没实现流插入，所以展示可以用这个函数打印
因为此函数只是打印，而不需要改变字符串，所以要加上const，防止意外改变

1. 1         const char* c_str()const
2. 2         {
3. 3             return _str;
4. 4          }

复制代码

 
七:reserve

这个函数是专门用来扩容的。
1当需要的值大于空间时，就需要扩容
2创建一个空间（为\0多开一个空间）
3把_str拷贝到新空间
4再把_str的空间释放
5把新空间赋值给_str
6把新大小capacity改成扩容的大小

1. 1         void reserve(size_t n)
2. 2         {
3. 3             if (n > _capacity)
4. 4             {
5. 5                 char* tmp = new char[n + 1];
6. 6                 strcpy(tmp, _str);
7. 7                 delete[] _str;
8. 8                 _str = tmp;
9. 9                 _capacity = n;
10. 10             }
11. 11         }

复制代码

 
八：push_back

此函数是用来尾插一个字符的
1先判断空间是否满了
2利用reserve开空间 (这里有特殊情况：有时候我们开的空间是0 那么再继续以2倍扩，是无法扩容的（0*n=0) 所以当capacity为0时 扩容4 如果不为0 二倍扩容
3扩容完后或者不需要扩容时  在有效字符的地方添加要添加的字符
4再让有效字符往后移
5再添加\0 不然打印时没有\0 无法停止

1. 1         void push_back(char c)
2. 2         {
3. 3             if (_size == _capacity)
4. 4             {
5. 5                 reserve(_capacity == 0 ? 4 : _capacity * 2);
6. 6             }
7. 7             _str[_size] = c;
8. 8             ++_size;
9. 9             _str[_size] = '\0';
10. 10                  }

复制代码

 
九:+=重载

在实际使用中，+=的功能与push_back相同，并且+=更加方便，那么需要提供+=的功能
1因为实际功能是相同的，这里可以直接复用push_back即可 
2因为需要支持连续的+=所以需要返回

1. 1         string& operator+=(char c)
2. 2         {
3. 3             push_back(c);
4. 4             return *this;
5. 5         }

复制代码

 
十：append

此函数用来添加字符串
1计算有效字符与要添加字符串的长度
2若有效字符与要添加字符串的长度大于实际空间
3那么就需要扩容，扩容字符串长度+有效字符长度即可
4把字符串拷贝到有效字符的后面开始
6有效字符也修改为有效字符与要添加字符串的长度

1. 1         void append(const char* str)
2. 2         {
3. 3             int len = _size+strlen(str);
4. 4             if (len > _capacity)
5. 5             {
6. 6                 reserve(len);
7. 7             }
8. 8             strcpy(_str+_size, str);
9. 9             _size = len;   
10. 10                 }            

复制代码

 
十一:+=的重载

+=的添加字符串也比append用的次数多，所以也需要提供
这里实际功能都相同，所以直接复用即可
1因为要支持连续的+=，所以需要返回

1. 1         string& operator+=(const char* str)
2. 2         {
3. 3             append(str);
4. 4             return *this;
5. 5         }

复制代码

 
十二：clear

用来清除数据
清除数据，但没有缩容空间，只是把空间内的数据清除，这点需要注意
1在第一个位置添加\0 那么打印时遇到\0 就会停止，后面的数据就无法打印
2有效个数修改为0

1. 1         void clear()
2. 2         {
3. 3             _str[0] = '\0';
4. 4             _size = 0;
5. 5     }

复制代码

 
十三:提供查询size

此函数提供了私有成员size的大小
因为不需要修改，所以要加const

1. 1         size_t size()const
2. 2         {
3. 3             return _size;
4. 4         }

复制代码

 
十四：提供查询capacity

此函数提供了私有成员capacity的大小
因为不需要修改，所以要加const

1. 1         size_t capacity()const
2. 2         {
3. 3             return _capacity;
4. 4         }

复制代码

 
十五：empty

提供了判空的功能
1当_str为空串时 返回true
2当_str不为空串时 返回false

1. 1         bool empty()const
2. 2         {
3. 3             if (_str == "")
4. 4             {
5. 5                 return true;
6. 6             }
7. 7             else
8. 8             {
9. 9                 return false;
10. 10             }
11. 11         }

复制代码

 
十六:resize

功能：扩容，并且初始化
当要扩容的大小，小于实际的大小，那么是需要把实际大小-要扩容大小不用的空间清除数据即可
1当当要扩容的大小，小于实际的大小
2size改为要扩容的大小
3在有效字符的大小添加\0
4当要扩容的大小大于实际大小
5扩容n的大小
6从实际有效字符开始，直到实际空间大小结束
7全部修改为c （若不传参时，默认为\0)
8实际有效字符改为n
9在有效字符修改为\0

1. 1         void resize(size_t n, char c = '\0')
2. 2         {
3. 3             //当n小于size时
4. 4             if (n < _size)
5. 5             {
6. 6                 _size = n;
7. 7                 _str[_size] = '\0';
8. 8             }
9. 9             else//当n大于size时
10. 10             {
11. 11                 if (n > _capacity)
12. 12                 {
13. 13                     reserve(n);
14. 14                 }
15. 15                 
16. 16                 for (size_t i = _size; i < n; i++)
17. 17                 {
18. 18                     _str[i] = c;
19. 19                 }
20. 20                 _size = n;
21. 21                 _str[_size] = '\0';//添加字符 都要手动在后面加上\0
22. 22             }
23. 23         }

复制代码

 
十七:[]重载

此函数分为非const版本与const版本
非const版本

1需要访问的大小不能超过有效字符 需要断言下
2返回_str对应下标的值

1. 1         char& operator[](size_t index)
2. 2         {
3. 3             assert(index < _size);
4. 4
5. 5             return _str[index];
6. 6         }

复制代码

const版本

有些地方访问下标不需要修改，所以需要提供const版本

1. 1         const char& operator[](size_t index) const
2. 2         {
3. 3             assert(index < _size);
4. 4
5. 5             return _str[index];
6. 6         }

复制代码

 
十八：=,==,!=的重载


这里使用strcmp（）函数 若_str=(const string& s)17         {18             return _str>s._str|| strcmp(_str, s._str) == 0;19         }20 21         bool operator==(const string& s)22         {23             return strcmp(_str, s._str) == 0;24         }25 26         bool operator!=(const string& s)27         {28             return !(_str == s._str);29         }[/code] 
十九:find

功能:返回c在string中第一次出现的位置
1从pos位置开始查看，若查找到字符c 返回，若循环结束，则代表没找到，返回npos（代表-1)

1. 1         bool operator<(const string& s)
2. 2         {
3. 3             return strcmp(_str, s._str) < 0;
4. 4         }
5. 5
6. 6         bool operator<=(const string& s)
7. 7         {
8. 8             return _str < s._str || strcmp(_str, s._str) == 0;
9. 9         }
10. 10
11. 11         bool operator>(const string& s)
12. 12         {
13. 13             return strcmp(_str, s._str) > 0;
14. 14         }
15. 15
16. 16         bool operator>=(const string& s)
17. 17         {
18. 18             return _str>s._str|| strcmp(_str, s._str) == 0;
19. 19         }
20. 20
21. 21         bool operator==(const string& s)
22. 22         {
23. 23             return strcmp(_str, s._str) == 0;
24. 24         }
25. 25
26. 26         bool operator!=(const string& s)
27. 27         {
28. 28             return !(_str == s._str);
29. 29         }

复制代码

 
二十四:迭代器

分为非const版本与const版本
非const版本

将char* 重命名为 iterator
迭代器为 begin end
begin返回头
直接返回_str即可
end返回尾
返回头加上有效字符即可

1. 1         size_t find(char c, size_t pos = 0) const
2. 2         {
3. 3             assert(pos <= _size);
4. 4             for (; pos <= _size; pos++)
5. 5             {
6. 6                 if (_str[pos] == c)
7. 7                 {
8. 8                     return pos;
9. 9                 }
10. 10             }
11. 11             return npos;
12. 12         }

复制代码

 
const版本

讲char* 重命名为 const_iterator
只需要加上const即可

1. 1         size_t find(const char* s, size_t pos = 0)
2. 2         {
3. 3             const char* p = strstr(_str + pos, s);
4. 4             if (p == nullptr)
5. 5             {
6. 6                 return npos;
7. 7             }
8. 8             else
9. 9             {
10. 10                 return p - _str;
11. 11             }
12. 12         }

复制代码

 
二十五：流插入、流提取

流提取
因为需要匹配，所以需要在类外实现
1因为要支持连续提取 所以要用ostream&作为返回类型
2使用返回for 以此打印即可
3返回
[code]1     ostream& operator