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

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创建一个空间（为\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

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

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] = '\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 以此打印即可

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

4定义索引 i

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

6讲字符分别放进数组内

7当数组满时

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

9再讲buff全部重载为\0

10索引重载为0

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

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

13返回

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

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

string的底层实现的更多相关文章

汇编窥探Swift String的底层
String(字符串),是所有编程语言中非常重要的成员,因此非常值得去深入研究.众所周知,字符串的本质是字符序列,由若干个字符组成.比如字符串 "iOS" 由 'i'.'O'.'S ...
C++之string的底层真的是用char数组来实现的么？
一.引言遇到一个问题:使用加密库对数据进行加密,得到密文,使用string进行保存并传输,然后可以正确解密出来,但是使用string.c_str()进行参数传递则无法正确解密出明文. 原因是:密文中 ...
【1】String,StringBuffer,StringBuillder的底层结构研究
一:StringBuffer的底层 (1)线程安全的字符串操作类 (2)通过synchronized关键字声明同步方法,保证多线程环境下数据安全 @Override public synchroniz ...
String,StringBuffer,StringBuillder的底层结构
一:StringBuffer的底层 (1)线程安全的字符串操作类 (2)通过synchronized关键字声明同步方法,保证多线程环境下数据安全 public synchronized StringB ...
Redis 底层数据结构之String
文章参考:<Redis设计与实现>黄建宏 Redis 的 string 类型底层使用的是 SDS(动态字符串) 实现的, 具体数据结构如下: struct sdshdr { int len ...
String、StringBuffer、StringBuilder源码分析
利用反编译具体看看"+"的过程 1 public class Test 2 { 3 public static void main(String[] args) 4 { 5 int ...
Java 基础知识总结 (四、String)
四.String public final class String extends Object implements Serializable, Comparable<String>, ...
JDK6与JDK7中String类subString()方法的区别
1.subString()方法的作用 subString(int beginIndex, int endIndex)方法的返回的是以beginIndex开始到 endIndex-1结束的某个调用字符串 ...
golang string和[]byte的对比
golang string和[]byte的对比为啥string和[]byte类型转换需要一定的代价?为啥内置函数copy会有一种特殊情况copy(dst []byte, src string) in ...
java基础(六)-----String性质深入解析
本文将讲解String的几个性质. 一.String的不可变性对于初学者来说,很容易误认为String对象是可以改变的,特别是+链接时,对象似乎真的改变了.然而,String对象一经创建就不可以修改 ...

随机推荐

几年前做家教写的C教程（之四专讲了指针与汉诺塔问题）
C语言学习宝典(4) 指针:可以有效的表示复杂的数据结构,能动态的分配动态空间,方便的使用字符串,有效的使用数组,能直接处理内存单元不掌握指针就没有掌握C语言的精华地址:系统为每一个变量分配一个内 ...
WP8.1 侧边滑动Item
效果图我看ios 和安卓上有好多类似的Item的效果,UWP上有微软官方的库,其中也有类似得效果,看样子WP8.1没有啊,顺便我的程序也是需要,我也就仿了一个. 具体思路是: 触摸控制GRId在CA ...
GPS经纬度换算成XY坐标
; }
【BZOJ 2321】 [BeiJing2011集训]星器
Description Magic Land上的时间又过了若干世纪…… 现在,人们谈论着一个传说:从前,他们的祖先来到了一个位于东方的岛屿,那里简直就是另外一个世界.善于分析与构造的Magic Lan ...
css3等待框
第1种效果: <div class="loading"> <span></span> <span></span> < ...
PHP关联查询
article文章表: aid title content uid 1 文章1 文章1正文内容... 1 2 文章2 文章2正文内容... 1 3 文章3 文章3正文内容... 2 4 文章4 文章4 ...
BZOJ4076 : [Wf2014]Maze Reduction
设$f[i][j][k]$表示从房间$j$的第$k$扇门进去探索不超过$i$步的情况. 对于$0$步的情况,可以用每个房间的度数来表示. 否则可以绕着那个房间走一圈,将所有情况依次hash来表示. 最 ...
luogu4932 浏览器 (拆)
分析1的个数的奇偶性: 奇xor奇=偶xor偶=偶奇xor偶=奇所以只要统计1的个数是奇数的数的个数和是偶数的个数乘一起就行了直接用bitset来做,虽然常数很小/数据随机可以过,但复杂度 ...
How to Pronounce the 50 States
How to Pronounce the 50 States (1/4) Share Tweet Share Tagged With: Places The US state names can be ...
React Native 填坑一
React Native 填坑一关于RN的布局分为主轴和交叉轴, 主轴可以是横向也可以是竖向,交叉轴也是对应的. 主轴默认是竖向.如果要更改用flexdirection 主轴对齐方式:justif ...