C++string底層框架模擬實(shí)現(xiàn)代碼
一、 前言
本節(jié)文章主要說(shuō)明淺拷貝和深拷貝的優(yōu)缺點(diǎn)，以及仿寫(xiě)string類(lèi)的邏輯并分析實(shí)現(xiàn)過(guò)程
如果人對(duì)一個(gè)事物感興趣，總是那么好奇，就會(huì)刨根問(wèn)底
二、 淺拷貝與深拷貝優(yōu)缺點(diǎn)
1. 淺拷貝
話不多說(shuō)，先來(lái)上一組代碼
class string{
public:
string(char* str="")
:_size(strlen(str))
,_capacity(_size)
{
_str = new char[_capacity+1];
strcpy(_str, str);
}
char& operator[](const char& pos) const {
return _str[pos];
}
~string(){
delete[] _str;
_str = nullptr;
_size = _capacity = 0;
}
private:
char* _str;
size_t _size;
size_t _capacity;
};
void Test1(){
string s1("never gonna give you up");
string s2 = s1;
s2[0] = 'Y';
}
當(dāng)我們把s1拷貝給s2，這里是深拷貝還是淺拷貝呢？先不說(shuō)答案我們debug看一下
一目了然，這里的s1和s2為同一個(gè)地址
那么當(dāng)我們改變s2[0]的值時(shí)，s1[0]也隨之改變，那么還是給人一種藕斷絲連的感覺(jué)沒(méi)有完全獨(dú)立拷貝，這就是淺拷貝，相信我們也看到了淺拷貝帶來(lái)的弊端
其次，當(dāng)我們調(diào)用析構(gòu)函數(shù)也會(huì)出現(xiàn)問(wèn)題，由于他們指向的是同一塊空間，s2會(huì)先析構(gòu)將里面的數(shù)組delete并置空
接著s1調(diào)用析構(gòu)函數(shù)時(shí)就會(huì)報(bào)錯(cuò)，所以不能指向同一塊空間
總結(jié)一下淺拷貝問(wèn)題：
這塊空間會(huì)在兩個(gè)對(duì)象析構(gòu)函數(shù)被delete兩次一個(gè)對(duì)象修改會(huì)影響另外一個(gè)對(duì)象
2. 深拷貝
深拷貝怎么實(shí)現(xiàn)？
string(const string& s) //函數(shù)重載
:_str(new char[strlen(s._str)+1])
{
strcpy(this->_str, s._str);
}
我們重新new一個(gè)空間給s2，下面下圖可以看到s1和s2在堆上不再是同一個(gè)空間
這里第一個(gè)參數(shù)是this被匿名了，為了方面看，我把this加了進(jìn)去
和淺拷貝區(qū)別就在于指明了當(dāng)前字符串需重新分配空間和重新賦值到新開(kāi)的這組新空間，這里的深拷貝就不會(huì)出現(xiàn)上面的問(wèn)題，當(dāng)我們改變s2[0]的值，s1[0]不會(huì)跟著改變
賦值重載的方式解決淺拷貝問(wèn)題
string& operator=(string& s){
if(this != &s){
char* tmp = new char[strlen(s._str)+1];
delete[] _str; //刪除this原來(lái)的內(nèi)容
_str = tmp; //將新空間賦給_str
strcpy(_str, s._str);
_size = _capacity = strlen(s._str);
_str[_size] = '\0';
}
return *this;
}
3. 深拷貝現(xiàn)代版
上面都為傳統(tǒng)寫(xiě)法，通過(guò)new開(kāi)辟一組新的堆空間，和現(xiàn)代寫(xiě)法的思路是有區(qū)別的
這里是重新構(gòu)造一個(gè)臨時(shí)string tmp變量新開(kāi)了一組空間，然后再swap把兩者進(jìn)行交換，等于this->_str獲得了這個(gè)新空間，最后把不需要的空間自動(dòng)析構(gòu)
string (const string& str)
:_str(nullptr)
{
string tmp(str);
swap(_str, tmp._str);
}
//這組沒(méi)有用到引用，因?yàn)樾螀⒆詣?dòng)調(diào)用拷貝構(gòu)造
string& operator=(string t)
{
swap(_s,t._s);
return *this;
}
4. 寫(xiě)時(shí)拷貝
那么是不是深拷貝一定就是最好的呢？
答案是不一定，寫(xiě)時(shí)拷貝在淺拷貝基礎(chǔ)上增加了引用計(jì)數(shù)方式，換句話說(shuō)有多少個(gè)對(duì)象指向這塊空間，計(jì)數(shù)就會(huì)++，那么只有當(dāng)某個(gè)對(duì)象去寫(xiě)數(shù)據(jù)時(shí)，那個(gè)對(duì)象才會(huì)進(jìn)行深拷貝，然后計(jì)數(shù)–
這本質(zhì)上是寫(xiě)的時(shí)候一種延遲深拷貝，但如果拷貝對(duì)象后沒(méi)有人進(jìn)行修改，沒(méi)有進(jìn)行深拷貝重開(kāi)一塊空間，也就順理成章的提高效率。但是實(shí)際應(yīng)用場(chǎng)景中不是很理想
三、 string框架搭建
1. 框架定義
這里私有成員結(jié)構(gòu)就類(lèi)似順序表，當(dāng)我們?cè)黾踊騽h除數(shù)據(jù)時(shí)需要記錄當(dāng)前的信息，以及是否需要擴(kuò)容等，npos用于查找是否有此字符，默認(rèn)返回-1
class string{
public:
private:
char* _str;
size_t _size;
size_t _capacity;
static const size_t npos;
};
const size_t string::npos = -1;
2. 構(gòu)造函數(shù)
void Test2(){
string s1("helloworld");
string s2(5, 'g');
string();
}
上面的函數(shù)名都構(gòu)成函數(shù)重載，目前實(shí)現(xiàn)了三種常見(jiàn)的
string(const char* str="")
:_size(strlen(str))
,_capacity(_size)
{
_str = new char[_capacity+1];
strcpy(_str, str);
}
第一種最普遍，直接將字符串賦給s1即可
string(size_t n, char c)
:_size(n)
,_capacity(_size)
{
_str = new char[ _size + 1];
for(size_t i=0; i<n; ++i) _str[i] = c;
}
第二種可以創(chuàng)建一組n個(gè)相同的字符
string()
:_str(new char[1])
,_size(0)
,_capacity(0)
{
*_str = '\0';
}
最后一種創(chuàng)建一個(gè)空函數(shù)，里面并不為空，默認(rèn)放一個(gè)斜杠零
3. 析構(gòu)函數(shù)
~string(){
delete[] _str;
_str = nullptr;
_size = _capacity = 0;
}
用于釋放空間，當(dāng)我們new完一組空間后需要手動(dòng)創(chuàng)建析構(gòu)函數(shù)
4. 賦值重載
下列賦值重載中，第一個(gè)支持讀和寫(xiě)
char& operator[](size_t pos){
return _str[pos];
}
第二個(gè)不支持寫(xiě)
const char& operator[](size_t pos) const{
return _str[pos];
}
這里我把賦值重載都給列出來(lái)，push_back函數(shù)在下面會(huì)提到
//可讀可寫(xiě)
String& operator+=(char ch){
push_back(ch);
return *this;
}
下列的賦值重載，實(shí)現(xiàn)依次比較數(shù)組中值的大小
//按照ASCII碼進(jìn)行比較
//s1 > s2 ?
//"abc" "abc" false
//"abc" "ab" true
//"ab" "abc" false
bool operator>(const string& s1, const string& s2){
size_t i1 = 0, i2 =0;
while(i1 < s1.size() && i2 < s2.size()){
if(s1[i1] > s2[i2]){
return true;
}else if(s1[i1] < s2[i2]){
return false;
}else{
++i1;
++i2;
}
}
if(i1 == s1.size()){
return false;
}else{
return true;
}
return true;
}
bool operator==(const string& s1, const string& s2){
size_t i1 = 0, i2 =0;
while(i1 < s1.size() && i2 < s2.size()){
if(s1[i1] > s2[i2]){
return true;
}else if(s1[i1] < s2[i2]){
return false;
}else{
++i1;
++i2;
}
}
if(i1 == s1.size() && i2 == s2.size()){
return true;
}else{
return false;
}
}
bool operator!=(const string& s1, const string& s2){
return !(s1==s2);
}
bool operator>=(const string& s1, const string& s2){
return (s1>s2 || s1==s2);
}
bool operator<(const string& s1, const string& s2){
return !(s1 >= s2);
}
bool operator<=(const string& s1, const string& s2){
return !(s1>s2);
}
String operator+(const string& s1, const string& str){
String ret = s1;
ret += str;
return ret;
}
5. 實(shí)現(xiàn)擴(kuò)容
resize分為三種情況
- 當(dāng)n小于等于size，則size等于n
- 當(dāng)n大于size但小于capacity，無(wú)法添加數(shù)據(jù)
- 當(dāng)n大于capacity時(shí)，先增容，然后從size開(kāi)始填數(shù)據(jù)，填到n
void reserve(size_t n){
if(n > _capacity){
char* tmp = new char[n+1]; //開(kāi)一個(gè)更大的空間
strcpy(tmp, _str); //進(jìn)行拷貝，然后釋放此空間
delete[] _str;
_str = tmp; //然后指向新開(kāi)的空間
}
_capacity = n;
}
void resize(size_t n, char ch='\0'){
//大于，小于，等于的情況
if(n <= _size){
_size = n;
_str[_size] = '\0';
}else{
if(n > _capacity){ //空間不夠，先增容
reserve(n);
for(size_t i = _size; i<n; i++){ //從size開(kāi)始填數(shù)據(jù)，填到n
_str[i] = ch;
}
_size = n;
_str[_size] = '\0';
}
}
}
6. 增添數(shù)據(jù)
在字符串的最后增加一個(gè)字符
void push_back(char c){
if(_size >= _capacity){
//這種如果size和capacity都為0，那么計(jì)算出的2倍w也為0，最后調(diào)用析構(gòu)的時(shí)候報(bào)錯(cuò)
//reserve(_capacity * 2);
size_t newCapacity = _capacity == 0 ? 4 : _capacity*2;
reserve(newCapacity);
}
_str[_size] = c;
++_size;
_str[_size] = '\0';
}
在字符串的最后增加一串字符，這里需要注意判斷原本容量的大小是否比新增的字符串容量要小，如果是就需要新reserve一組更大的空間
void append(const char* s){
size_t len = strlen(s);
if(_size + len >= _capacity){
reserve(_size + len);
}
strcpy(_str + _size, s); //把這個(gè)字符串給拷貝過(guò)去
_size += len;
}
在pos位置，插入字符或者字符串，這里我們實(shí)際應(yīng)用中，不推薦使用，因?yàn)閿?shù)組數(shù)據(jù)過(guò)于龐大時(shí)，在中間插入后，pos后面的數(shù)據(jù)都需要依次向后挪動(dòng)
string& insert(size_t pos, char ch){
assert(pos<=_size); //pos不能超出此范圍
if(_size == _capacity){
size_t newcapacity = _capacity == 0 ? 4 : _capacity*2;
reserve(newcapacity);
}
size_t end = _size+1;
while( end > _size){
_str[end-1] = _str[end];
--end;
}
_str[_size] = ch;
++_size;
return *this;
}
string& insert(size_t pos, const char* str){
assert(pos <= _size);
size_t len = strlen(str);
if(len == 0){
return *this;
}
if(len + _size > _capacity){
reserve(len + _size);
}
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;
return *this;
}
7. 刪除數(shù)據(jù)
String& erase(size_t pos, size_t len=npos){
assert(pos < _size);
//1. pos后面刪完
//2. pos后面刪一部分
if(len == npos || len+pos >= _size){
_str[pos] = '\0';
_size = pos;
}else{
//刪一部分
strcpy(_str + pos, _str + pos + len);
_size -= len;
}
return *this;
}
8. 數(shù)據(jù)查找
查找匹配的第一個(gè)字符，返回其下標(biāo)
//查找，直接返回字符的下標(biāo)位置
size_t find(char ch, size_t pos=0){
for(size_t i = pos; i<_size; ++i){
if(_str[i] == ch ){
return i;
}
}
return npos;
}
查找字符串，這里就直接調(diào)用C語(yǔ)言中的strstr函數(shù)進(jìn)行暴力匹配查找
size_t find(const char* sub, size_t pos=0){
const char* p = strstr(_str+pos, sub);
if(p == nullptr){
return npos;
}else{
return p-_str;
}
}
9. iterator迭代器
前面不加const的支持?jǐn)?shù)據(jù)修改
初次用迭代器玩不明白，其實(shí)刨開(kāi)看也沒(méi)有特別神奇，只不過(guò)是封裝起來(lái)了
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;
}
10. 插入/提取流與getline函數(shù)
//流插入
ostream& operator<<(ostream& out, const String& s){
for(size_t i = 0; i<s.size(); ++i){
out << s[i];
}
return out;
}
//流提取
istream& operator>>(istream& in, String& s){
s.clear();
char ch;
// in >> ch; 遇到換行會(huì)自動(dòng)停止
ch = in.get();
while(ch != ' ' && ch != '\n'){
s += ch; //提取字符串到這個(gè)String s字符串中去
ch = in.get();
}
return in;
}
//上面的是遇到空格就停止了然后傳給cout，而下面我們要實(shí)現(xiàn)一行哪怕中間有空格
istream& getline(istream& in, String& s){
s.clear();
char ch;
ch = in.get();
// while(ch != ' ' && ch != '\n'){
while(ch != '\n'){ //遇到空格不結(jié)束
s += ch;
ch = in.get();
}
return in;
}
我們可以看到流提取和getline的最大區(qū)別在于，流提取遇到空格后，就直接結(jié)束了
而getline不一樣，函數(shù)里面忽略判斷空格條件，而只保留判斷換行符
void test1(){
// cin >> s1;
// cout << s1 << endl; //注意如果有空格的hello world，hello打印出來(lái)了但是 world check the rythm還在緩沖區(qū)
getline(cin, s1); //打印帶有空格的一個(gè)字符串
cout << s1 <<endl;
}
四. 完整代碼
Gitee鏈接🔗 🔗 🔗
到此這篇關(guān)于C++string底層框架模擬實(shí)現(xiàn)代碼的文章就介紹到這了,更多相關(guān)C++string底層框架內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了c++ 智能指針基礎(chǔ)的相關(guān)資料，幫助大家更好的理解和學(xué)習(xí)使用c++，感興趣的朋友可以了解下，希望能給你帶來(lái)幫助2021-10-10
通過(guò)C++獲取CPU占用率的代碼示例(windows、linux、macOS)
C語(yǔ)言實(shí)現(xiàn)統(tǒng)計(jì)100以內(nèi)所有素?cái)?shù)的個(gè)數(shù)
C++實(shí)現(xiàn)LeetCode(768.可排序的最大塊數(shù)之二)
詳解在C++中顯式默認(rèn)設(shè)置的函數(shù)和已刪除的函數(shù)的方法
C++基于OpenCV實(shí)現(xiàn)手勢(shì)識(shí)別的源碼
解讀C語(yǔ)言非void函數(shù)卻沒(méi)有return會(huì)怎么樣