string的底层实现 - Lonely丶MoNan
source link: https://www.cnblogs.com/LonelyMoNan/p/string.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
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 string(const char* str = "")
2 :_size(strlen(str))
3 , _capacity(_size)
4 {
5 _str = new char[_capacity + 1];//+1是为了给 '\0' 留位置 string开空间都必须多一个位置
6 strcpy(_str, str);
7 }
二：拷贝构造
拷贝构造分为：传统写法与现代写法
传统写法：该构造就构造，该拷贝就拷贝
1它的有效个数与大小就是它的长度，用strlen计算即可。
2开一个空间 （给\0多开一个空间）
3讲字符串拷贝到该空间内
4把该空间赋值给_str
5把它的size与capacity与s同步
1 string(const string& s)
2 :_size(strlen(s._str))
3 ,_capacity(_size)
4 {
5 char* tmp = new char[_capacity + 1];
6 strcpy(tmp, s._str);
7 _str = tmp;
8 _size = s._size;
9 _capacity = s._capacity;
10 }
现代写法：利用tmp拷贝，再让他们交换
1因为拷贝构造是拷贝给一个不存在的，所以要先把他们初始化，才能让他们交换
2利用tmp构造一个需要拷贝的字符串
3再让_str与tmp交换
string(const string& s)
:_str(nullptr)
,_size(0)
,_capacity(0)
{
string tmp(s._str);
swap(tmp);
}
（这里更推荐现代写法）
三：析构函数
1当str不为空
2释放，并且置空，再把它的有效字符与大小置0
1 ~string()
2 {
3 if (_str)
4 {
5 delete[] _str;
6 _str = nullptr;
7 _size = _capacity = 0;
8 }
9 }
四：赋值重载
分为传统写法与现代写法①和②
1当不是自己给自己赋值时
2开一个空间
3把字符串拷贝进该空间
4释放掉_str的空间
5把tmp空间赋值给_str
6再把_str与赋值的字符串的有效字符与大小相同
1 string& operator=(const string &s)
2 {
3 if (this != &s)
4 {
5 char* tmp = new char[s._capacity + 1];
6 strcpy(tmp, s._str);
7 delete[] _str;
8 _str = tmp;
9 _size = s._size;
10 _capacity = s._capacity;
11 }
12 return *this;
13 }
现代写法①
1利用tmp构造一个字符串
2让_str与tmp交换
1 string& operator=(const string &s)
2 {
3 string tmp(s._str);
4 swap(tmp);
5 return *this;
6 }
现代写法②
1这里有些特殊，因为需要直接交换而不改变s的数据，就不用引用，而是用传值返回
2把_str与字符串交换
1 string& operator=(string s)
2 {
3 swap(s);
4 return *this;
5 }
五：swap
因为要完成三个私有成员的交换操作，所以swap里直接交换三个私有成员
这里要借助库里的，但编译器在命名空间内会默认使用该命名空间下的swap，所以我们需要加上std，使用库里的swap
1 void swap(string& s)
2 {
3 std::swap(_str, s._str);
4 std::swap(_size, s._size);
5 std::swap(_capacity, s._capacity);
6 }
六：c_str
因为还没实现流插入，所以展示可以用这个函数打印
因为此函数只是打印，而不需要改变字符串，所以要加上const，防止意外改变
1 const char* c_str()const
2 {
3 return _str;
4 }
七:reserve
这个函数是专门用来扩容的。
1当需要的值大于空间时，就需要扩容
2创建一个空间（为\0多开一个空间）
3把_str拷贝到新空间
4再把_str的空间释放
5把新空间赋值给_str
6把新大小capacity改成扩容的大小
1 void reserve(size_t n)
2 {
3 if (n > _capacity)
4 {
5 char* tmp = new char[n + 1];
6 strcpy(tmp, _str);
7 delete[] _str;
8 _str = tmp;
9 _capacity = n;
10 }
11 }
八：push_back
此函数是用来尾插一个字符的
1先判断空间是否满了
2利用reserve开空间 (这里有特殊情况：有时候我们开的空间是0 那么再继续以2倍扩，是无法扩容的（0*n=0) 所以当capacity为0时 扩容4 如果不为0 二倍扩容
3扩容完后或者不需要扩容时 在有效字符的地方添加要添加的字符
4再让有效字符往后移
5再添加\0 不然打印时没有\0 无法停止
1 void push_back(char c)
2 {
3 if (_size == _capacity)
4 {
5 reserve(_capacity == 0 ? 4 : _capacity * 2);
6 }
7 _str[_size] = c;
8 ++_size;
9 _str[_size] = '\0';
10 }
九:+=重载
在实际使用中，+=的功能与push_back相同，并且+=更加方便，那么需要提供+=的功能
1因为实际功能是相同的，这里可以直接复用push_back即可
2因为需要支持连续的+=所以需要返回
1 string& operator+=(char c)
2 {
3 push_back(c);
4 return *this;
5 }
十：append
此函数用来添加字符串
1计算有效字符与要添加字符串的长度
2若有效字符与要添加字符串的长度大于实际空间
3那么就需要扩容，扩容字符串长度+有效字符长度即可
4把字符串拷贝到有效字符的后面开始
6有效字符也修改为有效字符与要添加字符串的长度
1 void append(const char* str)
2 {
3 int len = _size+strlen(str);
4 if (len > _capacity)
5 {
6 reserve(len);
7 }
8 strcpy(_str+_size, str);
9 _size = len;
10 }
十一:+=的重载
+=的添加字符串也比append用的次数多，所以也需要提供
这里实际功能都相同，所以直接复用即可
1因为要支持连续的+=，所以需要返回
1 string& operator+=(const char* str)
2 {
3 append(str);
4 return *this;
5 }
十二：clear
用来清除数据
清除数据，但没有缩容空间，只是把空间内的数据清除，这点需要注意
1在第一个位置添加\0 那么打印时遇到\0 就会停止，后面的数据就无法打印
2有效个数修改为0
1 void clear()
2 {
3 _str[0] = '\0';
4 _size = 0;
5 }
十三:提供查询size
此函数提供了私有成员size的大小
因为不需要修改，所以要加const
1 size_t size()const
2 {
3 return _size;
4 }
十四：提供查询capacity
此函数提供了私有成员capacity的大小
因为不需要修改，所以要加const
1 size_t capacity()const
2 {
3 return _capacity;
4 }
十五：empty
提供了判空的功能
1当_str为空串时 返回true
2当_str不为空串时 返回false
1 bool empty()const
2 {
3 if (_str == "")
4 {
5 return true;
6 }
7 else
8 {
9 return false;
10 }
11 }
十六:resize
功能：扩容，并且初始化
当要扩容的大小，小于实际的大小，那么是需要把实际大小-要扩容大小不用的空间清除数据即可
1当当要扩容的大小，小于实际的大小
2size改为要扩容的大小
3在有效字符的大小添加\0
4当要扩容的大小大于实际大小
5扩容n的大小
6从实际有效字符开始，直到实际空间大小结束
7全部修改为c （若不传参时，默认为\0)
8实际有效字符改为n
9在有效字符修改为\0
1 void resize(size_t n, char c = '\0')
2 {
3 //当n小于size时
4 if (n < _size)
5 {
6 _size = n;
7 _str[_size] = '\0';
8 }
9 else//当n大于size时
10 {
11 if (n > _capacity)
12 {
13 reserve(n);
14 }
15
16 for (size_t i = _size; i < n; i++)
17 {
18 _str[i] = c;
19 }
20 _size = n;
21 _str[_size] = '\0';//添加字符 都要手动在后面加上\0
22 }
23 }
十七:[]重载
此函数分为非const版本与const版本
非const版本
1需要访问的大小不能超过有效字符 需要断言下
2返回_str对应下标的值
1 char& operator[](size_t index)
2 {
3 assert(index < _size);
4
5 return _str[index];
6 }
const版本
有些地方访问下标不需要修改，所以需要提供const版本
1 const char& operator[](size_t index) const
2 {
3 assert(index < _size);
4
5 return _str[index];
6 }
十八：<,<=,>,>=,==,!=的重载
这里使用strcmp（）函数 若_str<s._str 返回<0的值 相等返回0 大于返回>0的值
并且其他函数是可以直接复用
1 bool operator<(const string& s)
2 {
3 return strcmp(_str, s._str) < 0;
4 }
5
6 bool operator<=(const string& s)
7 {
8 return _str < s._str || strcmp(_str, s._str) == 0;
9 }
10
11 bool operator>(const string& s)
12 {
13 return strcmp(_str, s._str) > 0;
14 }
15
16 bool operator>=(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 }
十九:find
功能:返回c在string中第一次出现的位置
1从pos位置开始查看，若查找到字符c 返回，若循环结束，则代表没找到，返回npos（代表-1)
1 size_t find(char c, size_t pos = 0) const
2 {
3 assert(pos <= _size);
4 for (; pos <= _size; pos++)
5 {
6 if (_str[pos] == c)
7 {
8 return pos;
9 }
10 }
11 return npos;
12 }
二十:find
功能返回子串s在string中第一次出现的位置
这里使用strstr函数，查找字符串s
若未查找到 返回空 需要判断
若为空,返回npos
若不为空 返回第一次出现的位置
第一次出现的位置-_str（*）
1 size_t find(const char* s, size_t pos = 0)
2 {
3 const char* p = strstr(_str + pos, s);
4 if (p == nullptr)
5 {
6 return npos;
7 }
8 else
9 {
10 return p - _str;
11 }
12 }
二十一：insert
功能:在pos位置上插入字符c，并返回该字符的位置
1先判断空间是否满
2当满时需要扩容， 特殊情况 当capacity为0时 扩容4 当不为0时，2倍扩容
3定义索引end从有效字符后开始（\0后开始 有效字符时记录到\0）
4把一个数往后移动后， end前进，继续移动下一个数
5当到了需要插入的位置时，停止
6在需要插入的位置 插入字符c
7有效字符+1
string& insert(size_t pos, char c)
{
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] = c;
++_size;
return *this;
}
二十二 insert
功能:在pos位置上插入字符串str，并返回该字符的位置
1当需要插入的位置大于有效字符时 需要断言
2计算添加字符串的长度
3若有效字符加上添加字符串的长度大于实际大小
4扩容有效字符加上添加字符串的长度大于实际大小
5定义索引end从有效字符+len （这是为了有足够的空间插入字符串）
6当end到了pos+len-1的位置停下
7将每个字符移动len个位置
8end-- 继续移动下一个位置
9用strncpy函数，将字符串拷贝进去
10有效字符加上字符串的长度
1 string& insert(size_t pos, const char* str)
2 {
3 assert(pos <= _size);
4 size_t len = strlen(str);
5 if (len+_size > _capacity)
6 {
7 reserve(len+_size);
8 }
9
10 size_t end = _size + len;
11 while (end>pos+len-1)//-1是因为有一个\0
12 {
13 _str[end] = _str[end-len];
14 end--;
15 }
16 strncpy(_str + pos, str, len);
17 _size += len;
18
19 return *this;
20 }
二十三:erase
1当要删除的位置大于有效字符时 要断言
2当没给位置时或者要删除的长度大于有效字符时
3直接在pos位置加上\0 直接删除pos后的数据
4有效字符修改为pos
5如果不是大于有效字符，要删除部分字符串时
6让begin从pos+len（要删除的字符串的后面位置开始）
7往前面覆盖 从begin-len的位置开始覆盖）
8begin++ 继续将begin的数往前面覆盖
9直到begin到了有效字符
10有效字符减去要删除字符串的长度
11在有效字符的位置加上\0 凡是删除，添加字符这些无法自动添加\0的 都必须手动添加\0
1 string& erase(size_t pos, size_t len=npos)
2 {
3 assert(pos < _size);
4 if (pos == npos || pos + len > _size)
5 {
6 _str[pos] = '\0';
7 _size = pos;
8 }
9 else
10 {
11 int begin = pos + len;
12 while (begin < _size)
13 {
14 _str[begin - len] = _str[begin];
15 ++begin;
16 }
17 }
18 _size -= len;
19 _str[_size] = '\0';
20
21 return *this;
22 }
二十四:迭代器
分为非const版本与const版本
非const版本
将char* 重命名为 iterator
迭代器为 begin end
begin返回头
直接返回_str即可
end返回尾
返回头加上有效字符即可
1 typedef char* iterator;
2
3 iterator begin()
4 {
5 return _str;
6 }
7
8 iterator end()
9 {
10 return _str + _size;
11 }
const版本
讲char* 重命名为 const_iterator
只需要加上const即可
1 typedef const char* const_iterator;
2 const_iterator begin() const//要提供const与非const两版本
3 {
4 return _str;
5 }
6
7 const_iterator end() const
8 {
9 return _str + _size;
10 }
二十五：流插入、流提取
因为需要匹配，所以需要在类外实现
1因为要支持连续提取 所以要用ostream&作为返回类型
2使用返回for 以此打印即可
1 ostream& operator<<(ostream& out, const string& s)
2 {
3 for (auto k : s)
4 {
5 out << k;
6 }
7 return out;
8 }
因为需要匹配，所以需要在类外实现
1创建一个字符
2字符用来提取 因为要字符不能以空格为分割 防止冲突 所以要用到get 以换行为分割
3创建buff数组 初始化为\0
4定义索引 i
5当不以空格 换行为条件时
6讲字符分别放进数组内
7当数组满时
8讲数组以字符串形式添加进s
9再讲buff全部重载为\0
10索引重载为0
11结束循环后，继续插入到ch
12当还有剩下没满的字符时，添加到s内
istream& operator>>(istream& in, string& s)
{
char ch;
ch = in.get();
char buff[128] = { '\0' };
size_t i = 0;
while (ch != ' ' && ch != '\n')
{
buff[i++] = ch;
if (i == 127)
{
s += buff;
memset(buff, '\0', 128);
i = 0;
}
ch = in.get();
}
s += buff;
return in;
}
这里添加两个比较好用的函数
to_string 讲整形转换为字符串
1 int i = 123456; 2 string s1 = to_string(i);
stoi 讲字符串转换为整形
1 int n = stoi(s1);
这就是本篇的全部内容，如过对您有帮助，希望能获得您的赞！
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK