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的底層實現

String底層實現

一：建構函式

二：拷貝構造

三：解構函式

四：賦值過載

現代寫法①

現代寫法②

五：swap

六：c_str

七:reserve

八：push_back

九:+=過載

十：append

十一:+=的過載

十二：clear

十三:提供查詢size

十四：提供查詢capacity

十五：empty

十六:resize

十七:[]過載

非const版本

const版本

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

十九:find

二十:find

二十一：insert

二十二 insert

二十三:erase

二十四:迭代器

非const版本

const版本

二十五：流插入、流提取

流插入

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