??博主CSDN主頁(yè):杭電碼農(nóng)-NEO??
?
?專欄分類:C++從入門到精通?
?
??代碼倉(cāng)庫(kù):NEO的學(xué)習(xí)日記??
?
??關(guān)注我??帶你學(xué)習(xí)C++
? ????
1. 前言
和string的學(xué)習(xí)不同
vector即要掌握它的用法
更要會(huì)自己去實(shí)現(xiàn)一個(gè)vector
本章重點(diǎn):
熟悉STL庫(kù)中vector的接口函數(shù)
自己實(shí)現(xiàn)一個(gè)簡(jiǎn)易vector類
本章只實(shí)現(xiàn)容量相關(guān)函數(shù)
和構(gòu)造,析構(gòu),拷貝構(gòu)造函數(shù)
注:vector其實(shí)就是順序容器
string類只用考慮存儲(chǔ)字符
然而vector中可以存儲(chǔ)任一類型所以vector的自我實(shí)現(xiàn)需要用模板
2. 熟悉vector的接口函數(shù)
還是借助老朋友:cplusplus來(lái)查閱文檔
庫(kù)中的vector的模板參數(shù)有兩個(gè)
后一個(gè)是內(nèi)存池,用來(lái)提升空間利用效率對(duì)于現(xiàn)階段的學(xué)習(xí)而言可有可無(wú)
2.1 vector的構(gòu)造與拷貝構(gòu)造
常見的構(gòu)造有:
vector<int> v1;
vector<int> v2(10,1);
vector<int> v3(v2);
v2:構(gòu)造并初始化10個(gè)值為1的順序表
vector可以用迭代器區(qū)間初始化:
string str("abcdefg");
vector<string> vv(str.begin(),str.end());
2.2 vector迭代器的使用
和string一樣,vector有正向和反向
兩種迭代器,且使用方法和string相同
vector<int> vv{1,2,3,4,5,6};
vector<int>::iterator it = vv.begin();
while(it!=vv.end())
{
cout<<*it;
it++;
}
2.3 vector空間相關(guān)函數(shù)
vector的空間相關(guān)的函數(shù)
和string的機(jī)會(huì)一模一樣
如果你看了文檔還不懂的話
可以先閱讀此篇文章:string接口函數(shù)
2.4 vector的增刪查改
push_back和pop_back
都是老朋友了,這里就不多說(shuō)了
在介紹insert和erase之前先來(lái)了解幾個(gè)算法庫(kù)的函數(shù)
2.41 find,swap和sort
這三個(gè)函數(shù)都在頭文件:algorithm中
find函數(shù):參數(shù)是一段迭代器區(qū)間
以及在此區(qū)間你需要查找的值
找到后返回這個(gè)值對(duì)應(yīng)的迭代器位置
若找不到,則返回迭代器last
find的使用:
vector<int> vv{1,2,3,4,5,6,7,8,9};
auto pos = find(vv.begin(),vv.end(),5);
cout<<*pos;
注:使用auto是為了簡(jiǎn)寫迭代器也可以用vector< int >::iterator替代
swap想必是大家的?？土?br> 這里給它個(gè)面子,就不介紹它了
sort非常方便,它內(nèi)部實(shí)現(xiàn)是快排
我們只需要傳一個(gè)迭代器區(qū)間
就可以將整個(gè)區(qū)間排好序
sort的使用:
vector<int> vv{5,7,3,9,6,4,1,2,8};
sort(vv.begin().vv.end());
2.42 insert和erase
和string不同,vector的insert
的參數(shù)pos不是整型,而是迭代器
默認(rèn)是在pos位置前插入一個(gè)數(shù)據(jù)
insert和find常常配合在一起使用
在整型5前面插入一個(gè)100:
vector<int> vv{1,2,3,4,5,6,7,8,9};
auto pos = find(vv.begin(),vv.end(),5);
vv.insert(pos,100);
和string的erase不同,vector
的erase一次只刪除一個(gè)數(shù)據(jù)
然而string如果使用缺省值就是
將全部數(shù)據(jù)刪完
vector的erase甚至可以刪除一段區(qū)間
刪除順序表中值為100的元素
vector<int> vv{1,2,3,4,5,6,7,8,9,100};
auto pos = find(vv.begin(),vv.end(),100);
vv.erase(pos);
//刪除一個(gè)區(qū)間
vv.erase(vv.begin()+2,vv.end()-2);
2.43 隨機(jī)訪問operator[ ]
vector中最喜歡用的是[ ]
它支持隨機(jī)訪問,是否方便
operator[]的使用:
vector<int> vv{1,2,3,4,5,6,7,8,9};
for(int i=0;i<vv.size();i++)
{
cout<<vv[i]<<" ";
}
3. vector的模擬實(shí)現(xiàn)
首先要關(guān)注的是成員變量
vector是順序表,所以和實(shí)現(xiàn)C語(yǔ)言
時(shí)的順序表一樣,至少有三個(gè)參數(shù)
- 指向一段空間的指針
- 空間的有效大小
- 空間的實(shí)際大小
由于vector的迭代器就是普通指針
所以成員變量的類型其實(shí)是迭代器
template<class T>
class vector
{
public:
typedef T* iterator;
private:
iterator _start;
iterator _finish;
iterator _endof_storage;
這里使用迭代器作為三個(gè)參數(shù)的類型
是因?yàn)?求vector的size和capacity時(shí)
可以直接使用finish-start
也就是指針相減求出長(zhǎng)度
成員變量和空間的關(guān)系:
3.1 vector容量相關(guān)函數(shù)
上來(lái)首先要考慮的容量相關(guān)的函數(shù):
- size
- capacity
- empty
- resize
- reverse
前三個(gè)十分簡(jiǎn)單:
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _endof_storage - _finish;
}
bool empty() const
{
return (size()==0);
}
3.11 reverse函數(shù)
reverse只會(huì)改變capacity的大小
并不會(huì)改變size的大小
void reserve(size_t n)
{
if (n > capacity())
{
size_t sz = size();
T* tmp = new T[n];
if (_start)
{
//memcpy(tmp, _start, sizeof(T)*sz);
for (size_t i = 0; i < sz; ++i)
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = _start + sz;
_end_of_storage = _start + n;
}
}
注:當(dāng)n小于capacity時(shí),不進(jìn)行擴(kuò)容
由于C++內(nèi)存管理的new
無(wú)法像C語(yǔ)言的realloc一樣原地?cái)U(kuò)容
所以必須先開辟n個(gè)空間,再將數(shù)據(jù)
拷貝到新空間,且釋放舊空間
3.12 resize函數(shù)
resize即會(huì)改變size大小
也會(huì)改變capacity大小
resize要分三種情況:
- n大于capacity時(shí)
- n大于size小于capacity時(shí)
- n小于size時(shí)
它們的解決方案分別是:
-
直接套用reversezhu -
初始有效值不變,在此之后初始化新的內(nèi)容 -
直接將size縮小到n
void resize(size_t n, const T& val = T())
{
if (n > capacity())
{
reserve(n);
}
if (n > size())
{
// 初始化填值
while (_finish < _start + n)
{
*_finish = val;
++_finish;
}
}
else
{
_finish = _start + n;
}
}
注:參數(shù)val=T()使用了匿名對(duì)象
C++將內(nèi)置類型特殊處理過
int/char等等都被升級(jí)為了類
所以可以使用int()表示匿名對(duì)象
int tmp1 = int();
int tmp2 = int(10);
int的缺省值為0
3.2 vector的構(gòu)造函數(shù)
- 首先最簡(jiǎn)單的無(wú)參構(gòu)造:
vector()
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{}
- 緊接著是帶參的構(gòu)造函數(shù)
我們跟著STL庫(kù)的風(fēng)格走:
vector(size_t n, const T& val = T())
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
reserve(n);//開辟n個(gè)空間
for (size_t i = 0; i < n; ++i)
{
push_back(val);//給初始值賦值
}
}
- 最后是使用迭代器區(qū)間來(lái)構(gòu)造
比如我想在順序表中存放string類型:
string str("abcdefg");
vector<string> vv(str.begin(),str.end());
此時(shí)在模板類中還應(yīng)該有一個(gè)模板
template <class InputIterator>
vector(InputIterator first, InputIterator last)
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
while (first != last)
{
push_back(*first);
++first;
}
}
注:inputiterator取名是模仿STL的
你也可以取任一除了T的名字
3.3 vector的析構(gòu)函數(shù)
vector的析構(gòu)函數(shù)非常簡(jiǎn)單
只需要將空間釋放
并且將各個(gè)指針置為空就行了
~vector()
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
3.4 vector的拷貝構(gòu)造函數(shù)
拷貝構(gòu)造的實(shí)現(xiàn)有很多種寫法
大家可以先自己嘗試一下
vector(const vector<T>& v)
:_start(nullptr)
, _finish(nullptr)
, _endof_storage(nullptr)
{
reserve(v.size());
for (const auto& e : v)
{
push_back(e);
}
}
4. 總結(jié)以及拓展
vector模擬實(shí)現(xiàn)的全部代碼我將在
下一篇文章中分享給大家
可以發(fā)現(xiàn):STL的神奇之處在于
它把所有接口函數(shù)都做了統(tǒng)一化處理
每一個(gè)容器的接口函數(shù)的使用都相似
但是內(nèi)部實(shí)現(xiàn)被這種封裝隱藏起來(lái)了
進(jìn)一步又體現(xiàn)了C++的三大特性:封裝
并且C++實(shí)現(xiàn)了所有容器通用的算法庫(kù)
比如sort和find都只需要傳迭代器
然而所有容器都會(huì)被迭代器封裝
所以一份代碼就能實(shí)現(xiàn)對(duì)不同容器的操作
拓展題目:
熟悉了vector的基本使用
可以嘗試解決一下下面幾個(gè)問題:文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-679111.html
- 只出現(xiàn)一次的數(shù)字
- 刪除有序數(shù)組中的重復(fù)項(xiàng)
- 數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字
- 楊輝三角
留給大家當(dāng)作小試牛刀了~文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-679111.html
到了這里，關(guān)于【C++進(jìn)階(二)】STL大法--vector的深度剖析以及模擬實(shí)現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
