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

這就是本篇的全部內容，如過對您有幫助，希望能獲得您的贊！

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/498524.html

標籤：C++

上一篇：01章-記憶體磁區模型--C++核心知識學習筆記

下一篇：02章-參考--C++核心知識學習筆記

string的底層實作

String底層實作

一：建構式

二：拷貝構造

三：解構式

四：賦值多載

現代寫法①

現代寫法②

五：swap

六：c_str

七:reserve

八：push_back

九:+=多載

十：append

十一:+=的多載

十二：clear

十三:提供查詢size

十四：提供查詢capacity

十五：empty

十六:resize

十七:[]多載

非const版本

const版本

十八：<,<=,>,>=,==,!=的多載

十九:find

二十:find

二十一：insert

二十二 insert

二十三:erase

二十四:迭代器

非const版本

const版本

二十五：流插入、流提取

流插入

這就是本篇的全部內容，如過對您有幫助，希望能獲得您的贊！