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