C++中String增刪查改模擬實現(xiàn)方法舉例
更新時間：2023年11月24日 11:41:17 作者：小宇成長錄
這篇文章主要給大家介紹了關(guān)于C++中String增刪查改模擬實現(xiàn)方法的相關(guān)資料,String是C++中的重要類型,程序員在C++面試中經(jīng)常會遇到關(guān)于String的細節(jié)問題,甚至要求當場實現(xiàn)這個類,需要的朋友可以參考下
前言
本篇博客僅僅實現(xiàn)存儲字符的string。同時由于C++string庫設(shè)計的不合理，博主僅實現(xiàn)一些最常見的增刪查改接口！
接下來給出的接口都是基于以下框架：
namespace achieveString
{
class string
{
private:
char* _str;
size_t _capacity;
size_t _size;
};
}
一、string默認構(gòu)造、析構(gòu)函數(shù)、拷貝構(gòu)造、賦值重載
1.1 默認構(gòu)造
博主在這僅僅提供如無參和帶參默認構(gòu)造接口：
//無參默認構(gòu)造
string()
:_str(new char[1]{'\0'})
,_capacity(0)
,_size(0)
{ }
//帶參默認構(gòu)造
string(const char* str = "")
:_capacity(strlen(str))
,_size(_capacity)
{
_str = new char[_capacity + 1];
strcpy(_str, str);
}
小tips：
- C++string標準庫中，無參構(gòu)造并不是空間為0，直接置為空指針。而是開一個字節(jié)，并存放‘\0’。（C++中支持無參構(gòu)造一個對象后，直接在后面插入數(shù)據(jù)，也從側(cè)面說明了這點）
- 由于C++構(gòu)造函數(shù)不管寫不寫都會走初始化列表的特性，所以這里博主也走初始化列表。
- string中，_capacity和_size都不包含空指針，所以帶參構(gòu)造要多開一個空間，用來存儲’\0’。
1.2 析構(gòu)函數(shù)
~string()
{
delete[] _str;
_str = nullptr;
_size = _capacity = 0;
}
1.3 拷貝構(gòu)造
傳統(tǒng)寫法：
string(const string& s)
{
_str = new char[s._capacity + 1];
strcpy(_str, s._str);
_size = s._size;
_capacity = s._capacity;
}
現(xiàn)代寫法：現(xiàn)代寫法的核心在于：將拷貝數(shù)據(jù)的工作交給別人來做，最后將成果交換一樣即可。
//交換
void swap(string& s)
{
std::swap(_str, s._str);
std::swap(_size, s._size);
std::swap(_capacity, s._capacity);
}
//現(xiàn)代寫法
string(const string& s)
:_str(nullptr)
,_size(0)
,_capacity(0)
{
string tmp(s._str);
swap(tmp);
}
tips：現(xiàn)代寫法中，拷貝構(gòu)造是數(shù)據(jù)需初始化為空。原因在于C++中，編譯器對內(nèi)置類型不會做處理（個別如vs2019等編譯器會做處理的），這也就意味這_str是一個隨機值，指向任意一塊空間。調(diào)用析構(gòu)函數(shù)時會報錯。
1.4 賦值重載
賦值重載同樣分為傳統(tǒng)寫法和現(xiàn)代寫法。
傳統(tǒng)寫法：
string& operator=(const string& s)
{
if (this != &s)
{
char* tmp = new char[s._capacity + 1];
strcpy(tmp, s._str);
delete[] _str;
_str = tmp;
_size = s._size;
_capacity = s._capacity;
}
return *this;
}
現(xiàn)代寫法：
//現(xiàn)代寫法
//法一
/*string& operator=(const string& s)
{
if (this != &s)
{
string tmp(s._str);
swap(tmp);
}
return *this;
}*/
//法二
string& operator=(string tmp)
{
swap(tmp);
return *this;
}
二、迭代器和范圍for
在C++中，范圍for在底層是通過迭代器來實現(xiàn)的。所以只要實現(xiàn)了迭代器，就支持范圍for。
而迭代器類似于指針，迭代器可以被看作是指針的一種泛化，它提供了類似指針的功能，可以進行解引用操作、指針運算等。
以下提供了const迭代器和非const迭代器：
typedef char* iterator;
const typedef 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;
}
三、元素相關(guān)：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];
}
四、容量相關(guān)：size、resize、capacity、reserve
4.1 size、capacity
size_t size()const
{
return _size;
}
size_t capacity()const
{
return _capacity;
}
4.2 reserve
在C++中，我們一般不縮容。
所以實現(xiàn)reserve時（容量調(diào)整到n），首先判斷目標容量n是否大于當前容量。如果小于就不做處理，否則先開辟n+1個內(nèi)存空間（多出來的一個用于存儲‘\0’），然后將原有數(shù)據(jù)拷貝到新空間（strcpy會將’\0’一并拷貝過去）。然后釋放就空間，并讓_str指向新空間，同時更新_capacity。
void reserve(size_t n)
{
if (n > _capacity)
{
char* tmp = new char[n + 1];
strcpy(tmp, _str);
delete[] _str;
_str = tmp;
_capacity = n;
}
}
4.3 resize
resize到目標大小分為以下3中情況：
- 當n<_size時，只需將下標為n的地址處的數(shù)據(jù)改為’\0’。
- 其他情況，我們直接統(tǒng)一處理。直接復用reserve()函數(shù)將_capacity擴到n。然后用將[_size, n)中的數(shù)據(jù)全部初始化為ch。（這里博主給ch一個初始值’\0’，但ch不一定為’\0’，所以要將下標為n處的地址初始化為’\0’）
void resize(size_t n, char ch='\0')
{
if (n <= _size)
{
_str[n] = '\0';
_size = n;
}
else
{
reserve(n);
while (_size < n)
{
_str[_size] = ch;
_size++;
}
_str[_size] = '\0';
}
}
五、數(shù)據(jù)相關(guān)：push_bach、append、operator+=、insert、erase
5.1 尾插：push_back
尾插首先檢查擴容，在插入數(shù)據(jù)
void push_back(char ch)
{
//擴容
if (_size == _capacity)
{
reserve(_capacity == 0 ? 4 : _capacity * 2);
}
//插入數(shù)據(jù)
_str[_size] = ch;
_size++;
_str[_size] = '\0';
}
5.2 append尾部插入字符串
void append(const char* str)
{
size_t len = strlen(str);
if (_size + len > _capacity)//擴容
{
reserve(_size + len);
}
strcpy(_str + _size, str);
_size += len;
}
5.3 operator+=()字符、字符串
operator+=()字符、字符串可以直接復用push_back和append。
string& operator+=(char ch)
{
push_back(ch);
return *this;
}
string& operator+=(const char* str)
{
append(str);
return *this;
}
5.4 insert插入字符、字符串
5.4.1 insert插入字符
（在這提醒下，博主是所有的拷貝數(shù)據(jù)都是從’\0’開始，這樣就不需要單獨對’\0’做處理）
insert插入字符邏輯上還是很簡單的。
首先判斷插入字符時是否需要擴容。然后從下標為pos開始，所有數(shù)據(jù)依次往后挪動。最后將待插入字符給到pos處即可。
初學者最容易范的一個錯誤
但對于初學者來說，貌似也不太輕松。。。。。。
下面給出各位初學者容易犯的錯誤：
void insert(size_t pos, char ch)
{
assert(pos <= _size);
//擴容
if (_size == _capacity)
{
reserve(_capacity == 0 ? 4 : _capacity * 2);
}
//挪動數(shù)據(jù)
size_t end = _size;
while (end >= pos)
{
_str[end+1] = _str[end];
end--;
}
_str[pos] = ch;
_size++
}
這樣對嗎？答案是錯誤的。
假設(shè)是在頭插字符，end理論上和pos(即0)比較完后就減到-1，在下一次循環(huán)條件比較時失敗，退出循環(huán)。
遺憾的是end是size_t類型，始終>=0, 會導致死循環(huán)。
博主在這給出兩種解決方法：
- 將pos強轉(zhuǎn)為整型。
void insert(size_t pos, char ch)
{
assert(pos <= _size);
//擴容
if (_size == _capacity)
{
reserve(_capacity == 0 ? 4 : _capacity * 2);
}
//挪動數(shù)據(jù)
int end = _size;
while (end >= (int)pos)
{
_str[end+1] = _str[end];
end--;
}
_str[pos] = ch;
_size++
}
2.從end從最后數(shù)據(jù)的后一位開始，每次將前一個數(shù)據(jù)移到當前位置。最后條件判斷就轉(zhuǎn)化為end>pos，不會出現(xiàn)死循環(huán)這種情況。
void insert(size_t pos, char ch)
{
assert(pos <= _size);
//擴容
if (_size == _capacity)
{
reserve(_capacity == 0 ? 4 : _capacity * 2);
}
//挪動數(shù)據(jù)
size_t end = _size+1;
while (end > pos)
{
_str[end] = _str[end-1];
end--;
}
//插入數(shù)據(jù)，更新_size
_str[pos] = ch;
_size++;
}
5.4.2 insert插入字符串
insert同樣存在相同問題，并且思路一樣。博主就直接給出代碼了。
法一：
void insert(size_t pos, const char* str)
{
int len = strlen(str);
if (_size + len > _capacity)
{
reserve(_size + len);
}
int end = _size;
while (end >= (int)pos)
{
_str[end + len] = _str[end];
end--;
}
strncpy(_str + pos, str, len);
_size += len;
}
法二：
void insert(size_t pos, const char* str)
{
int len = strlen(str);
if (_size + len > _capacity)
{
reserve(_size + len);
}
size_t end = _size+1;
while (end > pos)
{
_str[end + len-1] = _str[end-1];
end--;
}
strncpy(_str + pos, str, len);
_size += len;
}
5.5 erase
erase分兩種情況：
- 從pos開始，要刪的數(shù)據(jù)個數(shù)超過的字符串，即將pos后序所有數(shù)據(jù)全部情況。（直接將pos處數(shù)據(jù)置為’\0’即可）
- 從pos開始，要刪的數(shù)據(jù)個數(shù)沒有超出的字符串。所以只需要從pos+len位置后的所有數(shù)據(jù)向前移動從pos位置覆蓋原數(shù)據(jù)即可。
void erase(size_t pos, size_t len = npos)
{
if (len==npos || pos + len >= _size)
{
//有多少，刪多少
_str[pos] = '\0';
_size = pos;
}
else
{
size_t begin = pos + len;
while (begin <= _size)
{
_str[begin - len] = _str[begin];
begin++;
}
_size -= len;
}
}
六、 關(guān)系操作符重載：< 、 ==、 <=、 >、>=、!=
bool operator<(const string& s) const
{
return strcmp(_str, s._str) < 0;
}
bool operator==(const string& s) const
{
return strcmp(_str, s._str) == 0;
}
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);
}
七、find查找字符、字符串、substr
7.1 find查找字符
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;
}
7.2 find查找字符串
size_t find(const char* sub, size_t pos = 0)
{
const char* p = strstr(_str + pos, sub);
if (p)
{
return p - _str;
}
else
{
return npos;
}
}
7.3 strsub( ) 模擬實現(xiàn)
strsub目標長度可能越界string，也可能還有沒有。但不管是那種情況，最后都需要拷貝數(shù)據(jù)。所以這里我們可以先將len真實長度計算出來，在拷貝數(shù)據(jù)。
string substr(size_t pos, size_t len = npos)const
{
string s;
size_t end = pos + len;
//目標字符越界string,更新len
if (len == npos || end >= _size)
{
len = _size - pos;
end = _size;
}
//拷貝數(shù)據(jù)
s.reserve(len);
for (size_t i = pos; i < end; i++)
{
s += _str[i];
}
return s;
}
八、流插入和流提取（<<、>>）(實現(xiàn)在string類外)
8.1 流插入<<
由于前面我們實現(xiàn)了迭代器，所以最簡單的方式就是范圍for
ostream& operator<<(ostream& out, const string& s)
{
/*for (size_t i = 0; i < s.size(); i++)
{
out << s[i];
}*/
for (auto ch : s)
out << ch;
return out;
}
8.1 流提取>>
流提取比較特殊。在流提取前需要將原有數(shù)據(jù)全部清空。同時由于>>無法獲取空字符和換行符()(都是作為多個值之間的間隔)，直接流提取到ostream對象中，沒法結(jié)束。（類似于C語言中scanf, 換行符和空字符僅僅只是起到判斷結(jié)束的作用，但scanf無法獲取到它們）
所以這里博主直接調(diào)用istream對象中的get()函數(shù)。（類似于C語言中的getchar()函數(shù)）
get詳細文檔
class string
{
void clear()
{
_str[0] = '\0';
_size = 0;
}
private:
char* _str;
size_t _capacity;
size_t _size;
};
istream& operator>>(istream& in, string& s)
{
s.clear();
char ch;
//in >> ch;
ch = in.get();
while (ch != ' ' && ch != '\n')
{
s += ch;
//in >> ch;
ch = in.get();
}
return in;
}
上面這種方法雖然可以達到目的。但還有一個問題，每次插入數(shù)據(jù)都面臨可擴容問題。那如何優(yōu)化呢？
優(yōu)化
其中一種辦法就是調(diào)用reserve()提前開好空間，但這樣面臨這另一個問題：開大了浪費空間；開小了，同樣面臨這擴容的問題。
所以在這博主采用和vs底層實現(xiàn)的思路：首先開好一段數(shù)組（包含’\0’，以16為例）。當數(shù)據(jù)個數(shù)小于16時，字符串存在數(shù)組中；當數(shù)據(jù)個數(shù)大于等于16時，將數(shù)據(jù)存在_str指向的空間。
這是一種以空間換時間的思路，同時也能很好的減少內(nèi)存碎片的問題。
class string
{
void clear()
{
_str[0] = '\0';
_size = 0;
}
private:
char* _str;
size_t _capacity;
size_t _size;
};
istream& operator>>(istream& in, string& s)
{
s.clear();
char buff[16];
size_t i = 0;
char ch;
ch = in.get();
while (ch != ' ' && ch != '\n')
{
buff[i++] = ch;
if (i == 16)
{
buff[i] = '\0';
s += buff;
i = 0;
}
ch = in.get();
}
if (i != 0)
{
buff[i] = '\0';
s += buff;
}
return in;
}
九、所有代碼
namespace achieveString
{
class string
{
public:
typedef char* iterator;
const typedef 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;
}
//構(gòu)造函數(shù)
/*string()
:_str(new char[1]{'\0'})
,_capacity(0)
,_size(0)
{ }*/
string(const char* str = "")
:_capacity(strlen(str))
, _size(_capacity)
{
_str = new char[_capacity + 1];
strcpy(_str, str);
}
const char* c_str() const
{
return _str;
}
//析構(gòu)函數(shù)
~string()
{
delete[] _str;
_str = nullptr;
_size = _capacity = 0;
}
//拷貝構(gòu)造
/*string(const string& s)
{
_str = new char[s._capacity + 1];
strcpy(_str, s._str);
_size = s._size;
_capacity = s._capacity;
}*/
//交換
void swap(string& s)
{
std::swap(_str, s._str);
std::swap(_size, s._size);
std::swap(_capacity, s._capacity);
}
//現(xiàn)代寫法
string(const string& s)
:_str(nullptr)
,_size(0)
,_capacity(0)
{
string tmp(s._str);
swap(tmp);
}
// 賦值重載
/*string& operator=(const string& s)
{
if (this != &s)
{
char* tmp = new char[s._capacity + 1];
strcpy(tmp, s._str);
delete[] _str;
_str = tmp;
_size = s._size;
_capacity = s._capacity;
}
return *this;
}*/
//現(xiàn)代寫法
//法一
/*string& operator=(const string& s)
{
if (this != &s)
{
string tmp(s._str);
swap(tmp);
}
return *this;
}*/
//法二
string& operator=(string tmp)
{
swap(tmp);
return *this;
}
//可讀可寫
char operator[](size_t pos)
{
assert(pos < _size);
return _str[pos];
}
//只讀
const char operator[](size_t pos)const
{
assert(pos < _size);
return _str[pos];
}
size_t size()const
{
return _size;
}
size_t capacity()const
{
return _capacity;
}
bool empty()const
{
return _size == 0;
}
void reserve(size_t n)
{
if (n > _capacity)
{
char* tmp = new char[n + 1];
strcpy(tmp, _str);
delete[] _str;
_str = tmp;
_capacity = n;
}
}
void resize(size_t n, char ch='\0')
{
if (n <= _size)
{
_str[n] = '\0';
_size = n;
}
else
{
reserve(n);
while (_size < n)
{
_str[_size] = ch;
_size++;
}
_str[_size] = '\0';
}
}
void push_back(char ch)
{
//擴容
if (_size == _capacity)
{
reserve(_capacity == 0 ? 4 : _capacity * 2);
}
//插入數(shù)據(jù)
_str[_size] = ch;
_size++;
_str[_size] = '\0';
}
void append(const char* str)
{
size_t len = strlen(str);
if (_size + len > _capacity)
{
reserve(_size + len);
}
strcpy(_str + _size, str);
_size += len;
}
string& operator+=(char ch)
{
push_back(ch);
return *this;
}
string& operator+=(const char* str)
{
append(str);
return *this;
}
void insert(size_t pos, char ch)
{
assert(pos <= _size);
//擴容
if (_size == _capacity)
{
reserve(_capacity == 0 ? 4 : _capacity * 2);
}
//挪動數(shù)據(jù)
size_t end = _size+1;
while (end > pos)
{
_str[end] = _str[end-1];
end--;
}
//插入數(shù)據(jù)，更新_size
_str[pos] = ch;
_size++;
}
void insert(size_t pos, const char* str)
{
int len = strlen(str);
if (_size + len > _capacity)
{
reserve(_size + len);
}
//法一
/*int end = _size;
while (end >= (int)pos)
{
_str[end + len] = _str[end];
end--;
}
strncpy(_str + pos, str, len);
_size += len;*/
//法二
size_t end = _size+1;
while (end > pos)
{
_str[end + len-1] = _str[end-1];
end--;
}
strncpy(_str + pos, str, len);
_size += len;
}
void erase(size_t pos, size_t len = npos)
{
if (len==npos || pos + len >= _size)
{
//有多少，刪多少
_str[pos] = '\0';
_size = pos;
}
else
{
size_t begin = pos + len;
while (begin <= _size)
{
_str[begin - len] = _str[begin];
begin++;
}
_size -= len;
}
}
bool operator<(const string& s)const
{
return strcmp(_str, s._str) < 0;
}
bool operator==(const string& s)const
{
return strcmp(_str, s._str) == 0;
}
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);
}
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;
}
size_t find(const char* sub, size_t pos = 0)
{
const char* p = strstr(_str + pos, sub);
if (p)
{
return p - _str;
}
else
{
return npos;
}
}
string substr(size_t pos, size_t len = npos)
{
string s;
size_t end = pos + len;
if (len == npos || end >= _size)
{
len = _size - pos;
end = _size;
}
s.reserve(len);
for (size_t i = pos; i < end; i++)
{
s += _str[i];
}
return s;
}
void clear()
{
_str[0] = '\0';
_size = 0;
}
private:
char* _str;
size_t _capacity;
size_t _size;
//const static size_t npos = -1; // C++支持const整型靜態(tài)變量在聲明時給值初始化，但不建議
//const static double npos = 1.1; // 不支持
const static size_t npos;
};
const size_t string::npos = -1;
ostream& operator<<(ostream& out, const string& s)
{
/*for (size_t i = 0; i < s.size(); i++)
{
out << s[i];
}*/
for (auto ch : s)
out << ch;
return out;
}
//istream& operator>>(istream& in, string& s)
//{
// s.clear();
// char ch;
// //in >> ch;
// ch = in.get();
// while (ch != ' ' && ch != '\n')
// {
// s += ch;
// //in >> ch;
// ch = in.get();
// }
// return in;
//}
istream& operator>>(istream& in, string& s)
{
s.clear();
char buff[16];
size_t i = 0;
char ch;
ch = in.get();
while (ch != ' ' && ch != '\n')
{
buff[i++] = ch;
if (i == 16)
{
buff[i] = '\0';
s += buff;
i = 0;
}
ch = in.get();
}
if (i != 0)
{
buff[i] = '\0';
s += buff;
}
return in;
}
}總結(jié)
到此這篇關(guān)于C++中String增刪查改模擬實現(xiàn)方法的文章就介紹到這了,更多相關(guān)C++ String增刪查改內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
今天小編就為大家分享一篇關(guān)于關(guān)于單片機按鍵問題性能提升總結(jié)，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2018-12-12
VC++實現(xiàn)輸出GIF到窗體并顯示GIF動畫的方法
這篇文章主要介紹了VC++實現(xiàn)輸出GIF到窗體并顯示GIF動畫的方法,需要的朋友可以參考下2014-07-07
c++ 動態(tài)內(nèi)存分配相關(guān)總結(jié)
這篇文章主要介紹了c++ 動態(tài)內(nèi)存分配相關(guān)的相關(guān)資料，幫助大家更好的理解和學習和使用c++，感興趣的朋友可以了解下2021-02-02
這篇文章主要為大家詳細介紹了基于VS+Opencv2.4.10微信跳一跳輔助工具，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-01-01
這篇文章主要介紹了C++ 動態(tài)庫導出函數(shù)名亂碼及解決，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2019-03-03
pair是C++STL(標準模板庫)中的一個現(xiàn)有容器,它將2個數(shù)據(jù)整合成一組數(shù)據(jù)，當我們類似需求的時候就可以使用到pair，pair的本質(zhì)其實就是個結(jié)構(gòu)體，本文將詳細的給大家介紹pair用法，感興趣的同學可以參考閱讀2023-05-05
類和對象是兩種以計算機為載體的計算機語言的合稱。對象是對客觀事物的抽象，類是對對象的抽象。類是一種抽象的數(shù)據(jù)類型；變量就是可以變化的量，存儲在內(nèi)存中—個可以擁有在某個范圍內(nèi)的可變存儲區(qū)域2022-05-05
本文介紹了使用C++實現(xiàn)并行計算的兩種方式,包括OpenMP和MPI,文中通過示例代碼介紹的非常詳細,需要的朋友們下面隨著小編來一起學習學習吧2024-03-03
下面小編就為大家?guī)硪黄狢++ string 字符串查找匹配實例代碼。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-10-10
數(shù)據(jù)結(jié)構(gòu)之Treap詳解
這篇文章主要介紹了數(shù)據(jù)結(jié)構(gòu)之Treap詳解,本文講解了Treap的基本知識、Treap的基本操作、Treap的高級操作技巧等,需要的朋友可以參考下2014-08-08