C++ vector的介紹及常見功能實(shí)現(xiàn)
1. 前言
上一篇文章我們學(xué)習(xí)了C++中string類的使用和模擬實(shí)現(xiàn)，string是一種表示字符串的字符串類今天我們來繼續(xù)學(xué)習(xí)C++中的另一種容器：vector。
2. vector的介紹
1.vector是表示可變大小數(shù)組的序列容器。
2.就像數(shù)組一樣，vector也采用的連續(xù)存儲(chǔ)空間來存儲(chǔ)元素。也就是意味著可以采用下標(biāo)對vector的元素進(jìn)行訪問，和數(shù)組一樣高效。但是又不像數(shù)組，它的大小是可以動(dòng)態(tài)改變的，而且它的大小會(huì)被容器自動(dòng)處理。
3.本質(zhì)講，vector使用動(dòng)態(tài)分配數(shù)組來存儲(chǔ)它的元素。當(dāng)新元素插入時(shí)候，這個(gè)數(shù)組需要被重新分配大小為了增加存儲(chǔ)空間。其做法是，分配一個(gè)新的數(shù)組，然后將全部元素移到這個(gè)數(shù)組。就時(shí)間而言，這是一個(gè)相對代價(jià)高的任務(wù)，因?yàn)槊慨?dāng)一個(gè)新的元素加入到容器的時(shí)候，vector并不會(huì)每次都重新分配大小。
4.vector分配空間策略：vector會(huì)分配一些額外的空間以適應(yīng)可能的增長，因?yàn)榇鎯?chǔ)空間比實(shí)際需要的存儲(chǔ)空間更大。不同的庫采用不同的策略權(quán)衡空間的使用和重新分配。但是無論如何，重新分配都應(yīng)該是對數(shù)增長的間隔大小，以至于在末尾插入一個(gè)元素的時(shí)候是在常數(shù)時(shí)間的復(fù)雜度完成的。
5.因此，vector占用了更多的存儲(chǔ)空間，為了獲得管理存儲(chǔ)空間的能力，并且以一種有效的方式動(dòng)態(tài)增長。
6.與其它動(dòng)態(tài)序列容器相比（deque, list and forward_list）， vector在訪問元素的時(shí)候更加高效，在末尾添加和刪除元素相對高效。對于其它不在末尾的刪除和插入操作，效率更低。比起list和forward_list統(tǒng)一的迭代器和引用更好。
3. vector的常用接口
3.1 vector對象的常見構(gòu)造函數(shù)
| 函數(shù)名稱 | 功能說明 |
|---|---|
| vector() | 無參構(gòu)造 |
| vector（size_type n, const value_type& val = value_type()） | 構(gòu)造并初始化n個(gè)val |
| vector (const vector& x) | 拷貝構(gòu)造 |
| vector (InputIterator first, InputIterator last) | 使用迭代器進(jìn)行初始化構(gòu)造 |
void Test1()
{
vector<int> v1;
vector<int> v2(10, 1);
vector<int> v3(v2);
}
3.2 iterator的使用
| 函數(shù)名稱 | 功能說明 |
|---|---|
| begin+end | 獲取第一個(gè)數(shù)據(jù)位置的iterator/const_iterator， 獲取最后一個(gè)數(shù)據(jù)的下一個(gè)位置的iterator/const_iterator |
| rbegin+rend | 獲取最后一個(gè)數(shù)據(jù)位置的reverse_iterator，獲取第一個(gè)數(shù)據(jù)前一個(gè)位置的reverse_iterator |
void Test1()
{
vector<int> v1;
vector<int> v2(10, 1);
vector<int> v3(v2);
//迭代器
vector<int>::iterator it = v2.begin();
while (it != v2.end())
{
(*it)++;
cout << *it << ' ';
it++;
}
cout << endl;
}
3.3 vector的空間管理
| 函數(shù)名稱 | 功能說明 |
|---|---|
| size | 獲取數(shù)據(jù)個(gè)數(shù) |
| capacity | 獲取容量大小 |
| empty | 判斷是否為空 |
| resize | 改變vector的size |
| reserve | 改變vector的capacity |
注意：
1.capacity的代碼在vs和g++下分別運(yùn)行會(huì)發(fā)現(xiàn)，vs下capacity是按1.5倍增長的，g++是按2倍增長的。不要固化的認(rèn)為，vector增容都是2倍，具體增長多少是根據(jù)具體的需求定義的。vs是PJ版本STL，g++是SGI版本STL。
2.reserve只負(fù)責(zé)開辟空間，如果確定知道需要用多少空間，reserve可以緩解vector增容的代價(jià)缺陷問
題。
3.resize在開空間的同時(shí)還會(huì)進(jìn)行初始化，影響size。
void TestVectorExpand()
{
size_t sz;
vector<int> v;
//v.resize(100);
//v.reserve(100);
sz = v.capacity();
cout << "making v grow:\n";
for (int i = 0; i < 100; ++i)
{
v.push_back(i);
if (sz != v.capacity())
{
sz = v.capacity();
cout << "capacity changed: " << sz << '\n';
}
}
}
void Test3()
{
vector<int> v1;
cout << v1.max_size() << endl;
TestVectorExpand();
}
void TestVectorExpand()
{
size_t sz;
vector<int> v;
//v.resize(100);
v.reserve(100);
sz = v.capacity();
cout << "making v grow:\n";
for (int i = 0; i < 100; ++i)
{
v.push_back(i);
if (sz != v.capacity())
{
sz = v.capacity();
cout << "capacity changed: " << sz << '\n';
}
}
}
void Test3()
{
vector<int> v1;
cout << v1.max_size() << endl;
TestVectorExpand();
}
3.4 vector的增刪查改
| 函數(shù)名稱 | 功能說明 |
|---|---|
| push_back | 尾插 |
| pop_back | 尾刪 |
| find | 查找 |
| insert | 在position之前插入val |
| erase | 刪除position位置的數(shù)據(jù) |
| swap | 交換兩個(gè)vector的數(shù)據(jù)空間 |
| operator[] | 像數(shù)組一樣訪問 |
void Test4()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
vector<int>::iterator pos = find(v1.begin(), v1.end(), 3);
if (pos != v1.end())
{
v1.insert(pos, 30);
}
for (size_t i = 0; i < v1.size(); i++)
{
cout << v1[i] << ' ';
}
cout << endl;
pos = find(v1.begin(), v1.end(), 300);
if (pos != v1.end())
{
v1.erase(pos);
}
for (auto e : v1)
{
cout << e << ' ';
}
cout << endl;
}
void Test5()
{
vector<int> v1;
v1.push_back(10);
v1.push_back(1);
v1.push_back(44);
v1.push_back(223);
v1.push_back(32);
v1.push_back(56);
v1.push_back(15);
v1.push_back(90);
for (auto e : v1)
{
cout << e << ' ';
}
cout << endl;
sort(v1.begin(), v1.end());
for (auto e : v1)
{
cout << e << ' ';
}
cout << endl;
//less<int> ls;
//greater<int> gt;
//sort(v1.begin(), v1.end(), gt);
sort(v1.begin(), v1.end(), greater<int>());
for (auto e : v1)
{
cout << e << ' ';
}
cout << endl;
}
4. vector迭代器失效的問題
迭代器的主要作用就是讓算法能夠不用關(guān)心底層數(shù)據(jù)結(jié)構(gòu)，其底層實(shí)際就是一個(gè)指針，或者是對指針進(jìn)行了封裝，比如：vector的迭代器就是原生態(tài)指針T* 。因此迭代器失效，實(shí)際就是迭代器底層對應(yīng)指針?biāo)赶虻目臻g被銷毀了，而使用一塊已經(jīng)被釋放的空間，造成的后果是程序崩潰(即如果繼續(xù)使用已經(jīng)失效的迭代器，程序可能會(huì)崩潰)。
可能導(dǎo)致迭代器失效的操作有很多，下面我們來一一介紹。
4.1 底層空間改變的操作
會(huì)引起其底層空間改變的操作，都有可能導(dǎo)致迭代器失效，比如：resize、reserve、insert、assign、push_back等。
void Test6()
{
vector<int> v{ 1,2,3,4,5,6 };
auto it = v.begin();
// 將有效元素個(gè)數(shù)增加到100個(gè)，多出的位置使用8填充，操作期間底層會(huì)擴(kuò)容
// v.resize(100, 8);
// reserve的作用就是改變擴(kuò)容大小但不改變有效元素個(gè)數(shù)，操作期間可能會(huì)引起底層容量改變
// v.reserve(100);
// 插入元素期間，可能會(huì)引起擴(kuò)容，而導(dǎo)致原空間被釋放
// v.insert(v.begin(), 0);
// v.push_back(8);
// 給vector重新賦值，可能會(huì)引起底層容量改變
v.assign(100, 8);
while (it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
出錯(cuò)原因：以上操作，都有可能會(huì)導(dǎo)致vector擴(kuò)容，也就是說vector底層原理舊空間被釋放掉，而在打印時(shí)，it還使用的是釋放之間的舊空間，在對it迭代器操作時(shí)，實(shí)際操作的是一塊已經(jīng)被釋放的空間，而引起代碼運(yùn)行時(shí)崩潰。
解決方式：在以上操作完成之后，如果想要繼續(xù)通過迭代器操作vector中的元素，只需給it重新賦值即可。
4.2 指定位置元素的刪除操作
void Test7()
{
int a[] = { 1, 2, 3, 4 };
vector<int> v(a, a + sizeof(a) / sizeof(int));
// 使用find查找3所在位置的iterator
vector<int>::iterator pos = find(v.begin(), v.end(), 3);
// 刪除pos位置的數(shù)據(jù)，導(dǎo)致pos迭代器失效。
v.erase(pos);
cout << *pos << endl; // 此處會(huì)導(dǎo)致非法訪問
}erase刪除pos位置元素后，pos位置之后的元素會(huì)往前搬移，沒有導(dǎo)致底層空間的改變，理論上講迭代器不應(yīng)該會(huì)失效，但是：如果pos剛好是最后一個(gè)元素，刪完之后pos剛好是end的位置，而end位置是沒有元素的，那么pos就失效了。因此刪除vector中任意位置上元素時(shí)，vs就認(rèn)為該位置迭代器失效了。
總結(jié)：
迭代器失效解決辦法：在使用前，對迭代器重新賦值即可。
5. vector模擬實(shí)現(xiàn)
namespace fiora
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin()const
{
return _start;
}
const_iterator end()const
{
return _finish;
}
size_t size()const
{
return _finish - _start;
}
size_t capacity()const
{
return _end_of_storage - _start;
}
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;
}
}
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;
}
}
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start);
assert(pos <= _finish);
if (_finish == _end_of_storage)
{
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = len + _start;
}
//向后挪動(dòng)數(shù)據(jù)
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
end--;
}
*pos = x;
_finish++;
return pos;
}
//erase返回刪除位置的下一個(gè)位置的迭代器
iterator erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator begin = pos + 1;
while (begin < _finish)
{
*(begin - 1) = *begin;
begin++;
}
_finish--;
return pos;
}
T& front()
{
assert(size() > 0);
return *_start;
}
T& back()
{
assert(size() > 0);
return *(_finish - 1);
}
void push_back(const T& x)
{
if (_finish == _end_of_storage)
{
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
*_finish = x;
_finish++;
}
void pop_back()
{
assert(_finish > _start);
_finish--;
}
const T& operator[](size_t pos)const
{
assert(pos < size());
return _start[pos];
}
T& operator[](size_t pos)
{
assert(pos < size());
return _start[pos];
}
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
vector()
:_start(nullptr)
,_finish(nullptr)
,_end_of_storage(nullptr)
{
}
/*vector(const vector<T>& v)
:_start(nullptr)
,_finish(nullptr)
,_end_of_storage(nullptr)
{
reserve(v.size());
for (const auto& e : v)
{
push_back(e);
}
}*/
vector(const vector<T>& v)
:_start(nullptr)
,_finish(nullptr)
,_end_of_storage(nullptr)
{
vector<T> tmp(v.begin(), v.end());
swap(tmp);
}
vector(size_t n, const T& val = T())
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
reserve(n);
for (size_t i = 0; i < n; ++i)
{
push_back(val);
}
}
template<class Iterator>
vector(Iterator first, Iterator last)
:_start(nullptr)
,_finish(nullptr)
,_end_of_storage(nullptr)
{
while (first != last)
{
push_back(*first);
first++;
}
}
~vector()
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
private:
iterator _start;
iterator _finish;
iterator _end_of_storage;
};
}6. 結(jié)尾
到這里，關(guān)于vector的介紹和常見功能我們就學(xué)習(xí)結(jié)束了，vector在實(shí)際中非常的重要，但在實(shí)際中我們只要熟悉常見的接口就可以了，最重要的是理解他的底層原理，要能夠自己模擬實(shí)現(xiàn)出一個(gè)簡單的vector。
最后，感謝各位大佬的耐心閱讀和支持，覺得本篇文章寫的不錯(cuò)的朋友可以三連關(guān)注支持一波，如果有什么問題或者本文有錯(cuò)誤的地方大家可以私信我，也可以在評論區(qū)留言討論，再次感謝各位。
到此這篇關(guān)于C++ vector的介紹及常見功能實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)C++ vector內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了C++ 虛函數(shù) virtual的相關(guān)資料,本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-03-03
以下文章是對C/C++中判斷某一文件或目錄是否存在的實(shí)現(xiàn)代碼進(jìn)行了詳細(xì)的分析介紹，需要的朋友可以參考下2013-07-07
C語言實(shí)現(xiàn)輸入ascii碼,輸出對應(yīng)的字符方式
這篇文章主要介紹了C語言實(shí)現(xiàn)輸入ascii碼，輸出對應(yīng)的字符方式，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-01-01
這篇文章主要為大家詳細(xì)介紹了QT實(shí)現(xiàn)簡單的音樂播放器，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-06-06
C++ map 根據(jù)value找key的實(shí)現(xiàn)
今天小編就為大家分享一篇C++ map 根據(jù)value找key的實(shí)現(xiàn)，具有很好的參考價(jià)值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-12-12
鏈接描述了名稱在整個(gè)程序或一個(gè)翻譯單元中如何引用或不引用同一實(shí)體,下面這篇文章主要給大家介紹了關(guān)于C++內(nèi)鏈接與外鏈接意義的理解,需要的朋友可以參考下2021-11-11
這篇文章主要為大家詳細(xì)介紹了C語言控制臺打磚塊小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-05-05
這篇文章主要介紹了C語言解決螺旋矩陣算法問題的代碼示例,螺旋矩陣中的數(shù)字由第一行開始到右邊不斷變大,向下變大,向左變大,向上變大,如此循環(huán)...需要的朋友可以參考下2016-04-04
這篇文章主要介紹了C++中sting類的簡單實(shí)現(xiàn)方法的相關(guān)資料,需要的朋友可以參考下2016-08-08