深入探索C++ string的底層實現(xiàn)
一、成員變量
private: char* _str;//用來存儲字符串 size_t _size;//用來表示有效字符數(shù) size_t _capacity;//用來表示可以存儲有效字符的容量 public: static size_t npos;//要在類外面定義
string本質(zhì)上是一個動態(tài)順序表，它可以根據(jù)需要動態(tài)的擴容，所以字符串一定是通過在堆上動態(tài)申請空間進行存儲的，因此_str指向存儲字符串的空間，_size用來表示有效字符數(shù)，_capacity用來表示可以存儲有效字符的容量數(shù)。
二、成員函數(shù)
2.1 默認構(gòu)造函數(shù)
string(const char* str = "")
:_str(new char[strlen(str) + 1])//strlen計算的是有效字符的個數(shù)，而我們存儲的時候要在字符串的最后存一個'\0'
,_size(strlen(str))
,_capacity(_size)
{
//memcpy(_str, str, _size);
//strcpy(_str, str);//常量字符串就是遇到'\0'終止，所以直接用strcpy也可以
memcpy(_str, str, strlen(str) + 1);
}注意：默認構(gòu)造函數(shù)需要注意的地方是：首先形參必須加上 const 修飾，這樣才能用 C 語言中的常量字符串來初始化 string 類對象，形參的的缺省值直接給一個空字符串即可，注意空字符串是用""表示，該字符串只有結(jié)尾默認的一個 '\0'，"\0"并不表示空字符串，它表示該字符串有一個字符 '\0' ，它的結(jié)尾還有一個默認的 '\0'，因此有兩個 '\0'，nullptr也不能表示空字符串，他表示的是空指針。其次需要注意初始化列表的順序，應該嚴格按照成員變量的出現(xiàn)順序。strlen 計算的是字符串中有效字符的個數(shù)，不算 '\0'，而常量字符串的結(jié)尾默認有一個 '\0'，因此在用 new開辟空間的時候需要多開一個用來存儲結(jié)尾的 \0。_capacity表示的是可以存儲有效字符的容量，而字符串結(jié)尾默認的 '\0' 并不算作有效字符，因此最初的 _capacity 就是形參 str 的長度。最后記得在構(gòu)造函數(shù)體內(nèi)將形參 str 的字符拷貝到動態(tài)申請的空間中。
小Tips：涉及到字符串拷貝的地方，建議使用 memcpy，strcpy 默認遇到 \0 就終止，但是不排除 \0 就是 string 對象中的有效字符。但是 strcpy 會默認在結(jié)尾加 \0，而 memcpy 不會，因此使用 memcpy 的時候需要注意拷貝得到的字符串結(jié)尾是否有 \0。
2.2 拷貝構(gòu)造函數(shù)
//傳統(tǒng)寫法
string(const string& str)
:_str(new char[str._size + 1])
,_size(str._size)
,_capacity(_size)
{
memcpy(_str, str._str, str._size + 1);
}
//現(xiàn)代寫法
string(const string& str)
:_str(nullptr)
, _size(0)
,_capacity(0)
{
string tmp(str._str);
swap(tmp);
}注意：現(xiàn)代寫法不需要我們親自去申請空間初始化，而是調(diào)用構(gòu)造函數(shù)去幫我們完成。最后再將初始化好的 tmp 交換過來，這里一定要通過初始化列表對 *this 進行初始化，不然交換給 tmp 后，里面都是隨機值，最終出了作用域 tmp 去銷毀的時候就會出問題?，F(xiàn)代寫法的坑點在于，如果 string 對象中有 '\0'，只會把 '\0' 前面的字符拷貝過去。
2.3 operator=
//傳統(tǒng)寫法
string& operator=(const string& s)
{
if (this != &s)
{
char* tmp = new char[s._capacity + 1];
memcpy(tmp, s._str, s._size + 1);
delete[] _str;
_str = tmp;
_size = s._size;
_capacity = s._capacity;
}
return *this;
}注意：這種寫法需要我們自己去開辟空間新空間 tmp，自己去釋放舊空間 _str，下面將對這種寫法加以改進，通過已有的接口來幫我們完成這些工作。
//現(xiàn)代寫法
string& operator=(const string& s)
{
if (this != &s)
{
string tmp(s);//通過調(diào)用拷貝構(gòu)造來創(chuàng)建空間
//tmp是局部變量，出了作用于會自動銷毀，把待銷毀的資源通過交換，給tmp
std::swap(_str, tmp._str);
std::swap(_size, tmp._size);
std::swap(_capacity, tmp._capacity);
//std::swap(*this, tmp);//錯誤的寫法
}
return *this;
}
//現(xiàn)代寫法優(yōu)化
void swap(string& s)
{
std::swap(_str, s._str);
std::swap(_size, s._size);
std::swap(_capacity, s._capacity);
}
string& operator=(string s)
{
swap(s);
return *this;
}
//優(yōu)化版本，連拷貝構(gòu)造函數(shù)也不需要我們自己去調(diào)用啦，直接通過形參去調(diào)用注意：這種寫法通過調(diào)用拷貝構(gòu)造來幫我們申請空間，在利用局部對象出了作用就會被銷毀的特點，將需要釋放的資源通過 swap 交換給這個局部變量，讓這個局部變量幫我們銷毀。這里不能直接用 swap 交換兩個 string 類對象，會導致棧溢出，因為 swap 函數(shù)中會調(diào)用賦值運算符重載，而賦值運算符重載又要調(diào)用 swap 成了互相套娃。我們可以不用庫里面的 swap，自己實現(xiàn)一個 Swap 用來交換兩個 string 對象。
2.4 c_str()
char* c_str() const
{
return _str;
}注意：記得加上 const，這樣普通的 string 類對象可以調(diào)用，const 類型的 string 類對象也可以調(diào)用，普通對象來調(diào)用就是權(quán)限的縮小。
2.5 size()
size_t size() const
{
return _size;
}2.6 operator[ ]
//讀寫版本
char& operator[](size_t pos)
{
assert(pos < _size);
return _str[pos];
}//只讀版本
const char& operator[](size_t pos) const
{
assert(pos < _size);
return _str[pos];
}注意：這兩個運算符重載函數(shù)構(gòu)成函數(shù)重載，對象在調(diào)用的時候會走最匹配的，普通對象會調(diào)用讀寫版本，const 對象會調(diào)用只讀版本。
2.7 iterator
iterator 是 string 類的內(nèi)嵌類型，也可以說是在 string 類里面定義的類型，在一個類里面定義類型有兩種方法，typedef 和 內(nèi)部類。string 類的 iterator 是通過前者來實現(xiàn)的，即對字符指針 char* 通過 typedef 得到的。
typedef char* iterator;
typedef const char* const_iterator;
//可讀可寫版本
iterator begin()
{
return _str;
}
iterator end()
{
return _str + _size;
}
//只讀版本
const_iterator begin() const
{
return _str;
}
const_iterator end() const
{
return _str + _size;
}2.8 reserve
void reserve(size_t n = 0)
{
if (n > _capacity)
{
char* tmp = new char[n + 1];
//strcpy(tmp, _str);
memcpy(tmp, _str, _size + 1);
_capacity = n;
delete[] _str;
_str = tmp;
}
}2.9 resize
void resize(size_t n, char ch = '\0')
{
if (n < _size)
{
erase(n);
}
else
{
reserve(n);
for (size_t i = _size; i < n; i++)
{
_str[i] = ch;
}
_size = n;
_str[_size] = '\0';
}
}注意：reserve 函數(shù)不會進行縮容，因此在擴容前要先進程判斷，只有當形參 n 大于當前容量的時候才擴容。
2.10 push_back
void push_back(char ch)
{
//先檢查容量，進行擴容
if (_size == _capacity)
{
reserve(_capacity == 0 ? 4 : _capacity * 2);
}
_str[_size++] = ch;
_str[_size] = '\0';
}注意：需要注意對空串的追加，空串的 _capacity = 0 ，因此在調(diào)用 reserve 函數(shù)進行擴容的時候，不能簡單傳遞 _capacity*2，要先進行判斷，當 capacity == 0 的時候，給它一個初始大小。
2.11 append
void append(const char* str)
{
if (_size + strlen(str) > _capacity)
{
reserve(_size + strlen(str));
}
//strcpy(_str + _size, str);//常量字符串就是遇到'\0'終止，所以直接用strcpy也可以
memcpy(_str + _size, str, strlen(str) + 1);
_size += strlen(str);
}2.12 operator+=
//追加一個字符串
string& operator+=(const char* str)
{
append(str);
return *this;
}
//追加一個字符
string& operator+=(char ch)
{
push_back(ch);
return *this;
}注意：+= 需要有返回值。
2.13 insert
//插入n個字符
void insert(size_t pos, size_t n, char ch)
{
assert(pos <= _size);
//檢查容量，擴容
if (_size + n > _capacity)
{
reserve(_size + n);
}
//挪動數(shù)據(jù)
size_t end = _size;
while (end != npos && end >= pos)
{
_str[end + n] = _str[end--];
}
//插入數(shù)據(jù)
size_t i = pos;
while (i < pos + n)
{
_str[i++] = ch;
}
_size += n;
}注意：這里需要注意挪動數(shù)據(jù)時的判斷條件，因為 end 和 pos 都是 sizt_t 類型，所以當 pos = 0 的時候 end >= pos 永遠成立，此時就會有問題，只把 end 改成 int 也解決不了問題，在比較的時候會發(fā)生整形提升，最終還是永遠成立。一種解決方法就是想上面一樣，加一個 size_t 類型的成員變量 npos，把它初始化成 -1，即整形最大值，判斷 end 是否等于 npos，等于說明 end 已經(jīng)減到 -1 了，就應該停止挪動。解決上面的問題還有一種方法，上面的問題出現(xiàn)在 pos = 0 時，end 會減到 -1，最終變成正的無窮大，導致判斷條件永遠成立，那我們可以將 end 初始化成 _size + n，把 end - n 上的字符挪到 end 位置上，此時計算 pos = 0，也不會出現(xiàn) end 減到 -1 的情況，代碼如下：
//插入n個字符
void insert(size_t pos, size_t n, char ch)
{
assert(pos <= _size);
//檢查容量，擴容
if (_size + n > _capacity)
{
reserve(_size + n);
}
//挪動數(shù)據(jù)
size_t end = _size + n;
while (end >= pos + n)
{
_str[end] = _str[end - n];
--end;
}
//插入數(shù)據(jù)
size_t i = pos;
while (i < pos + n)
{
_str[i++] = ch;
}
_size += n;
}小Tips：npos作為一個靜態(tài)成員變量，必須在類外面進行初始化（定義），并且不能在聲明時給默認值，默認值是給初始化列表用的，而靜態(tài)成員變量屬于該類所有對象共有，并不會走初始化列表。但是！但是?。?，整形的靜態(tài)成員變量變量在加上 const 修飾后就可以在聲明的地方給默認值，注意！僅限整形。其他類型的靜態(tài)成員變量在加 const 修飾后仍需要在類外面定義。
const static size_t npos = -1;//可以 //const static double db = 1.1//不可以
//插入一個字符串
void insert(size_t pos, const char* str)
{
assert(pos <= _size);
size_t len = strlen(str);
if (_size + len > _capacity)
{
reserve(_size + len);
}
//挪動
size_t end = _size + len;
while (end >= pos + len)
{
_str[end] = _str[end - len];
--end;
}
//插入
for (size_t i = 0; i < len; i++)
{
_str[pos + i] = str[i];
}
_size += len;
}2.14 erase
void erase(size_t pos, size_t len = npos)
{
assert(pos < _size);
if (len == npos || pos + len >= _size)//
{
_str[pos] = '\0';
_size = pos;
}
else
{
//挪動覆蓋
size_t end = pos + len;
while (end <= _size)
{
_str[end - len] = _str[end++];
}
_size -= len;
}
}注意：pos 將整個數(shù)組劃分成兩部分，[0,pos-1]是一定不需要刪除的區(qū)域，[pos,_size-1]是待刪除區(qū)域，一定不需要刪除的區(qū)域有 pos 個元素，我們希望刪除 len 個字符，當一定不會刪除的字符數(shù)加我們希望刪除的字符數(shù)如果大于或等于全部的有效字符數(shù)，那就說明待刪除區(qū)域的所有字符都要刪除，即當 pos + len >= _size 的時候就是要從 pos 位置開始刪除后面的所有字符，刪完后加的把 pos 位置的字符置為 \0。
2.15 find
//查找一個字符
size_t find(char ch, size_t pos = 0)
{
assert(pos < _size);
for (size_t i = 0; i < _size; i++)
{
if (_str[i] == ch)
{
return i;
}
}
return npos;
}
//查找一個字符串
size_t find(const char* str, size_t pos = 0)
{
assert(pos < _size);
const char* ptr = strstr(_str, str);
if (ptr == NULL)
{
return npos;
}
else
{
return ptr - _str;
}
}2.16 substr
string substr(size_t pos = 0, size_t len = npos)
{
assert(pos < _size);
size_t n = len;
if (len == npos || pos + len >= _size)
{
n = _size - pos;
}
string tmp;
tmp.reserve(n);
for (size_t i = 0; i < n; i++)
{
tmp += _str[i + pos];
}
return tmp;
}2.17 operator<<
ostream& operator<<(ostream& out, const wcy::string& str)
{
for (auto e : str)
{
out << e;
}
return out;
}注意：因為涉及到競爭左操作數(shù)的原因，流插入和流提取運算符重載要寫在類外面。其次，不能直接打印 str._str 或者通過 str.c_str() 來打印，因為 string 對象中可能會有 \0 作為有效字符存在，前面兩種打印方法，遇到 \0 就停止了，無法完整將一個 string 對象打印出來，正確的做法是逐個打印。
小Tips：無論是形參還是返回值，只要涉及到 ostream 或 istream 都必須要用引用，因為這倆類不允許拷貝或者賦值的。
2.18 operator>>
istream& operator>>(istream& in, wcy::string& str)
{
if (str._size != 0)
{
str.erase(0);
}
//in >> str._str;//這樣寫是錯的，空間都沒有
char ch;
ch = in.get();
while (ch == ' ' || ch == '\n')//清除緩沖區(qū)
{
ch = in.get();
}
while (ch != ' ' && ch != '\n')
{
str += ch;
ch = in.get();
}
return in;
}注意：空格符 ' ' 和換行符 \n 作為輸入時分割多個 string 對象的標志，是不能直接用 istream 對象來讀取的，即 cin >> ch 是讀不到空格符和換行符。需要借助 get() 成員函數(shù)才能讀取到空格符和換行符。其次庫中對 string 進行二次流提取的時候會進行覆蓋，所以我們在插入前也要先進行判斷。上面這種寫法，在輸入的字符串很長的情況下會多次調(diào)用 reserve 進行擴容，為了解決這個問題，我們可以對其進行優(yōu)化。
//優(yōu)化版本
istream& operator>>(istream& in, wcy::string& str)
{
/*if (str._size != 0)
{
str.erase(0);
}*/
//in >> str._str;//這樣寫是錯的，空間都沒有
str.clear();
char buff[128] = { '\0' };
char ch;
ch = in.get();
while (ch == ' ' || ch == '\n')
{
ch = in.get();
}
size_t i = 0;
while (ch != ' ' && ch != '\n')
{
buff[i++] = ch;
if (i == 127)
{
str += buff;
i = 0;
}
ch = in.get();
}
if (i != 0)
{
buff[i] = '\0';
str += buff;
}
return in;
}注意：這里的做法是，先開辟一個數(shù)組，將輸入的字符存儲到數(shù)組中，然后從數(shù)組中拷貝到 string 對象當中。
2.19 operator<
bool operator<(const string& s) const
{
size_t i1 = 0;
size_t i2 = 0;
while (i1 < _size && i2 < s._size)
{
if (_str[i1] < s[i2])
{
return true;
}
else if (_str[i1] > s[i2])
{
return false;
}
else
{
i1++;
i2++;
}
}
if (i1 == _size && i2 == s._size)
{
return false;
}
else if (i1 < _size)
{
return false;
}
else
{
return true;
}
}注意：string 類對象是按照 ASCII 進行比較的。其次，這里不能直接復用 strcmp 或者 memcmp，前者遇到 '\0' 就會終止，后者只能比較長度相等的部分。所以我們可以自己來寫比較邏輯，也可以復用 memcmp 然后進行補充。
//復用memcpy
bool operator<(const string& s) const
{
int ret = memcmp(_str, s._str, _size < s._size ? _size : s._size);
return ret == 0 ? _size < s._size : ret < 0;
}2.20 operator==
bool operator==(const string& s) const
{
return _size == s._size
&& memcmp(_str, s._str, _size < s._size ? _size : s._size) == 0;
}有了 < 和 ==，剩下的直接復用即可。
2.21 <=、>、>=、!=
bool operator<=(const string& s) const
{
return *this < s || *this == s;
}
bool operator>(const string& s) const
{
return !(*this <= s);
}
bool operator>=(const string& s) const
{
return !(*this < s);
}
bool operator!=(const string& s) const
{
return !(*this == s);
}三、結(jié)語
今天的分享到這里就結(jié)束啦！
以上就是深入探索C++ string的底層實現(xiàn)的詳細內(nèi)容，更多關于C++ string底層實現(xiàn)的資料請關注腳本之家其它相關文章！
相關文章
這篇文章主要介紹了C++實現(xiàn)矩陣原地轉(zhuǎn)置算法,非常經(jīng)典的算法,需要的朋友可以參考下2014-08-08
這篇文章主要介紹了C語言中的參數(shù)傳遞機制,C語言中函數(shù)參數(shù)的傳遞有：值傳遞、地址傳遞、引用傳遞這三種形式。下面我們詳細探討下2017-04-04
這篇文章主要介紹了LZ77壓縮算法原理的理解的相關資料,數(shù)據(jù)壓縮是一個減小數(shù)據(jù)存儲空間的過程，目前被應用在軟件工程的各個地方，了解其一些原理，方便我們更好的甄選壓縮方案,需要的朋友可以參考下2017-08-08
本篇文章主要介紹了C++11返回類型后置語法的使用示例，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-10-10
這篇文章主要為大家詳細介紹了C語言實現(xiàn)學生學籍管理系統(tǒng)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-01-01
C/C++判斷傳入的UTC時間是否當天的實現(xiàn)方法
在項目中經(jīng)常會顯示一個時間，如果這個時間在今日內(nèi)就顯示為時分秒，否則顯示為年月日，有需要的朋友可以參考一下2014-01-01
這篇文章主要為大家詳細介紹了C++代碼實現(xiàn)五子棋小游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-05-05
這篇文章主要介紹的是利用C語言實現(xiàn)單鏈表，實現(xiàn)的是鏈表中最簡單的一種單鏈表且每個結(jié)點中只含有一個指針域，下面將詳細舉例說明,需要的朋友可以參考一下2021-10-10
當我們在寫一段代碼時，如果要頻繁的在一塊區(qū)域進行插入或者刪除操作時，會發(fā)現(xiàn)用數(shù)組實現(xiàn)會比較復雜，這時候我們就要用另一種數(shù)據(jù)結(jié)構(gòu)，鏈表來實現(xiàn)2022-05-05
本文主要聊一聊如何使用互斥鎖以及都有哪幾種方式實現(xiàn)互斥鎖。實現(xiàn)互斥，可以有以下幾種方式：互斥量（Mutex）、遞歸互斥量（Recursive Mutex）、讀寫鎖（Read-Write Lock）、條件變量（Condition Variable）。感興趣的同學可以參考一下2023-04-04