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为了给预留位置 开空间时都必须给多开一个)

3在把字符串拷贝到开好的空间内

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

 

二：拷贝构造

拷贝构造分为：传统写法与现代写法

传统写法：该构造就构造，该拷贝就拷贝

1它的有效个数与大小就是它的长度，用strlen计算即可。

2开一个空间 （给多开一个空间）

3讲字符串拷贝到该空间内

4把该空间赋值给_str 

5把它的size与capacity与s同步

        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

        ~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与赋值的字符串的有效字符与大小相同

7返回

        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交换

3返回

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

现代写法②

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

2把_str与字符串交换

3返回

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

 

五：swap

因为要完成三个私有成员的交换操作，所以swap里直接交换三个私有成员

这里要借助库里的，但编译器在命名空间内会默认使用该命名空间下的swap，所以我们需要加上std，使用库里的swap

        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，防止意外改变

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

 

七:reserve

这个函数是专门用来扩容的。

1当需要的值大于空间时，就需要扩容

2创建一个空间（为多开一个空间）

3把_str拷贝到新空间

4再把_str的空间释放

5把新空间赋值给_str

6把新大小capacity改成扩容的大小

        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再添加 不然打印时没有 无法停止

        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] = ''; 10                  }

 

九:+=重载

在实际使用中，+=的功能与push_back相同，并且+=更加方便，那么需要提供+=的功能

1因为实际功能是相同的，这里可以直接复用push_back即可 

2因为需要支持连续的+=所以需要返回

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

 

十：append

此函数用来添加字符串

1计算有效字符与要添加字符串的长度

2若有效字符与要添加字符串的长度大于实际空间

3那么就需要扩容，扩容字符串长度+有效字符长度即可

4把字符串拷贝到有效字符的后面开始

6有效字符也修改为有效字符与要添加字符串的长度

        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因为要支持连续的+=，所以需要返回

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

 

十二：clear

用来清除数据

清除数据，但没有缩容空间，只是把空间内的数据清除，这点需要注意

1在第一个位置添加 那么打印时遇到 就会停止，后面的数据就无法打印

2有效个数修改为0

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

 

十三:提供查询size

此函数提供了私有成员size的大小

因为不需要修改，所以要加const

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

 

十四：提供查询capacity

此函数提供了私有成员capacity的大小

因为不需要修改，所以要加const

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

 

十五：empty

提供了判空的功能

1当_str为空串时 返回true

2当_str不为空串时 返回false

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

 

十六:resize

功能：扩容，并且初始化

当要扩容的大小，小于实际的大小，那么是需要把实际大小-要扩容大小不用的空间清除数据即可

1当当要扩容的大小，小于实际的大小

2size改为要扩容的大小

3在有效字符的大小添加

4当要扩容的大小大于实际大小

5扩容n的大小

6从实际有效字符开始，直到实际空间大小结束

7全部修改为c （若不传参时，默认为)

8实际有效字符改为n

9在有效字符修改为

        void resize(size_t n, char c = '')  2         {  3             //当n小于size时  4             if (n < _size)  5             {  6                 _size = n;  7                 _str[_size] = '';  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] = '';//添加字符 都要手动在后面加上 22             } 23         }

 

十七:[]重载

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

非const版本

1需要访问的大小不能超过有效字符 需要断言下

2返回_str对应下标的值

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

const版本

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

        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的值

并且其他函数是可以直接复用

        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)

        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（*）

 

        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从有效字符后开始（后开始 有效字符时记录到）

4把一个数往后移动后， end前进，继续移动下一个数

5当到了需要插入的位置时，停止

6在需要插入的位置 插入字符c

7有效字符+1

8返回

        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有效字符加上字符串的长度

11返回

        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是因为有一个 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位置加上 直接删除pos后的数据

4有效字符修改为pos

5如果不是大于有效字符，要删除部分字符串时

6让begin从pos+len（要删除的字符串的后面位置开始）

7往前面覆盖 从begin-len的位置开始覆盖）

8begin++ 继续将begin的数往前面覆盖

9直到begin到了有效字符

10有效字符减去要删除字符串的长度

11在有效字符的位置加上  凡是删除，添加字符这些无法自动添加的 都必须手动添加

12返回

        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] = '';  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] = ''; 20  21             return *this; 22         }

 

二十四:迭代器

分为非const版本与const版本

非const版本

将char* 重命名为 iterator

迭代器为 begin end

begin返回头

直接返回_str即可

end返回尾

返回头加上有效字符即可

                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即可

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 以此打印即可

3返回

    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数组 初始化为

4定义索引 i

5当不以空格 换行为条件时

6讲字符分别放进数组内

7当数组满时 

8讲数组以字符串形式添加进s

9再讲buff全部重载为

10索引重载为0

11结束循环后，继续插入到ch

12当还有剩下没满的字符时，添加到s内

13返回

    istream& operator>>(istream& in, string& s)     {         char ch;         ch = in.get();         char buff[128] = { '' };         size_t i = 0;         while (ch != '  ' && ch != 'n')         {             buff[i++] = ch;             if (i == 127)             {                 s += buff;                 memset(buff, '', 128);                 i = 0;             }             ch = in.get();         }         s += buff;         return in;     }

 

这里添加两个比较好用的函数

to_string 讲整形转换为字符串

    int i = 123456; 2     string s1 = to_string(i);

stoi 讲字符串转换为整形

    int n = stoi(s1);

---

这就是本篇的全部内容，如过对您有帮助，希望能获得您的赞！