string的底层实现

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在把字符串拷贝到开好的空间内

1         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同步

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

7返回

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

3返回

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

现代写法②

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

2把_str与字符串交换

3返回

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创建一个空间(为多开一个空间)

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

 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] = "";
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在第一个位置添加 那么打印时遇到 就会停止,后面的数据就无法打印

2有效个数修改为0

1         void clear()
2         {
3             _str[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在有效字符的大小添加

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

5扩容n的大小

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

7全部修改为c (若不传参时,默认为)

8实际有效字符改为n

9在有效字符修改为

 1         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对应下标的值

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

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返回

 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是因为有一个
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返回

 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] = "";
 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返回尾

返回头加上有效字符即可

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

3返回

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

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 != "
")
        {
            buff[i++] = ch;
            if (i == 127)
            {
                s += buff;
                memset(buff, "", 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);

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

 

原文地址:https://www.cnblogs.com/LonelyMoNan/archive/2022/07/06/string.html