C++ vector的介紹及常見功能實現
更新時間：2023年05月29日 09:17:31 作者：_Fiora
這篇文章主要介紹了C++ vector的介紹及模擬實現,vector在實際中非常的重要，但在實際中我們只要熟悉常見的接口就可以了，最重要的是理解他的底層原理，要能夠自己模擬實現出一個簡單的vector，本文結合示例代碼給大家詳細介紹，需要的朋友可以參考下
1. 前言
上一篇文章我們學習了C++中string類的使用和模擬實現，string是一種表示字符串的字符串類今天我們來繼續(xù)學習C++中的另一種容器：vector。
2. vector的介紹
1.vector是表示可變大小數組的序列容器。
2.就像數組一樣，vector也采用的連續(xù)存儲空間來存儲元素。也就是意味著可以采用下標對vector的元素進行訪問，和數組一樣高效。但是又不像數組，它的大小是可以動態(tài)改變的，而且它的大小會被容器自動處理。
3.本質講，vector使用動態(tài)分配數組來存儲它的元素。當新元素插入時候，這個數組需要被重新分配大小為了增加存儲空間。其做法是，分配一個新的數組，然后將全部元素移到這個數組。就時間而言，這是一個相對代價高的任務，因為每當一個新的元素加入到容器的時候，vector并不會每次都重新分配大小。
4.vector分配空間策略：vector會分配一些額外的空間以適應可能的增長，因為存儲空間比實際需要的存儲空間更大。不同的庫采用不同的策略權衡空間的使用和重新分配。但是無論如何，重新分配都應該是對數增長的間隔大小，以至于在末尾插入一個元素的時候是在常數時間的復雜度完成的。
5.因此，vector占用了更多的存儲空間，為了獲得管理存儲空間的能力，并且以一種有效的方式動態(tài)增長。
6.與其它動態(tài)序列容器相比（deque, list and forward_list）， vector在訪問元素的時候更加高效，在末尾添加和刪除元素相對高效。對于其它不在末尾的刪除和插入操作，效率更低。比起list和forward_list統一的迭代器和引用更好。
3. vector的常用接口
3.1 vector對象的常見構造函數
| 函數名稱 | 功能說明 |
|---|---|
| vector() | 無參構造 |
| vector（size_type n, const value_type& val = value_type()） | 構造并初始化n個val |
| vector (const vector& x) | 拷貝構造 |
| vector (InputIterator first, InputIterator last) | 使用迭代器進行初始化構造 |
void Test1()
{
vector<int> v1;
vector<int> v2(10, 1);
vector<int> v3(v2);
}
3.2 iterator的使用
| 函數名稱 | 功能說明 |
|---|---|
| begin+end | 獲取第一個數據位置的iterator/const_iterator， 獲取最后一個數據的下一個位置的iterator/const_iterator |
| rbegin+rend | 獲取最后一個數據位置的reverse_iterator，獲取第一個數據前一個位置的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的空間管理
| 函數名稱 | 功能說明 |
|---|---|
| size | 獲取數據個數 |
| capacity | 獲取容量大小 |
| empty | 判斷是否為空 |
| resize | 改變vector的size |
| reserve | 改變vector的capacity |
注意：
1.capacity的代碼在vs和g++下分別運行會發(fā)現，vs下capacity是按1.5倍增長的，g++是按2倍增長的。不要固化的認為，vector增容都是2倍，具體增長多少是根據具體的需求定義的。vs是PJ版本STL，g++是SGI版本STL。
2.reserve只負責開辟空間，如果確定知道需要用多少空間，reserve可以緩解vector增容的代價缺陷問
題。
3.resize在開空間的同時還會進行初始化，影響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的增刪查改
| 函數名稱 | 功能說明 |
|---|---|
| push_back | 尾插 |
| pop_back | 尾刪 |
| find | 查找 |
| insert | 在position之前插入val |
| erase | 刪除position位置的數據 |
| swap | 交換兩個vector的數據空間 |
| operator[] | 像數組一樣訪問 |
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迭代器失效的問題
迭代器的主要作用就是讓算法能夠不用關心底層數據結構，其底層實際就是一個指針，或者是對指針進行了封裝，比如：vector的迭代器就是原生態(tài)指針T* 。因此迭代器失效，實際就是迭代器底層對應指針所指向的空間被銷毀了，而使用一塊已經被釋放的空間，造成的后果是程序崩潰(即如果繼續(xù)使用已經失效的迭代器，程序可能會崩潰)。
可能導致迭代器失效的操作有很多，下面我們來一一介紹。
4.1 底層空間改變的操作
會引起其底層空間改變的操作，都有可能導致迭代器失效，比如：resize、reserve、insert、assign、push_back等。
void Test6()
{
vector<int> v{ 1,2,3,4,5,6 };
auto it = v.begin();
// 將有效元素個數增加到100個，多出的位置使用8填充，操作期間底層會擴容
// v.resize(100, 8);
// reserve的作用就是改變擴容大小但不改變有效元素個數，操作期間可能會引起底層容量改變
// v.reserve(100);
// 插入元素期間，可能會引起擴容，而導致原空間被釋放
// v.insert(v.begin(), 0);
// v.push_back(8);
// 給vector重新賦值，可能會引起底層容量改變
v.assign(100, 8);
while (it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
出錯原因：以上操作，都有可能會導致vector擴容，也就是說vector底層原理舊空間被釋放掉，而在打印時，it還使用的是釋放之間的舊空間，在對it迭代器操作時，實際操作的是一塊已經被釋放的空間，而引起代碼運行時崩潰。
解決方式：在以上操作完成之后，如果想要繼續(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位置的數據，導致pos迭代器失效。
v.erase(pos);
cout << *pos << endl; // 此處會導致非法訪問
}erase刪除pos位置元素后，pos位置之后的元素會往前搬移，沒有導致底層空間的改變，理論上講迭代器不應該會失效，但是：如果pos剛好是最后一個元素，刪完之后pos剛好是end的位置，而end位置是沒有元素的，那么pos就失效了。因此刪除vector中任意位置上元素時，vs就認為該位置迭代器失效了。
總結：
迭代器失效解決辦法：在使用前，對迭代器重新賦值即可。
5. vector模擬實現
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;
}
//向后挪動數據
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
end--;
}
*pos = x;
_finish++;
return pos;
}
//erase返回刪除位置的下一個位置的迭代器
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. 結尾
到這里，關于vector的介紹和常見功能我們就學習結束了，vector在實際中非常的重要，但在實際中我們只要熟悉常見的接口就可以了，最重要的是理解他的底層原理，要能夠自己模擬實現出一個簡單的vector。
最后，感謝各位大佬的耐心閱讀和支持，覺得本篇文章寫的不錯的朋友可以三連關注支持一波，如果有什么問題或者本文有錯誤的地方大家可以私信我，也可以在評論區(qū)留言討論，再次感謝各位。
到此這篇關于C++ vector的介紹及常見功能實現的文章就介紹到這了,更多相關C++ vector內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要介紹了C++ TinyXML解析案例詳解,本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下2021-08-08
這篇文章主要介紹了C語言中編寫可變參數函數的相關資料,需要的朋友可以參考下2017-07-07
在處理跨平臺的數據交換或網絡通信時,字節(jié)流的重要性更加突出,不同的系統可能有不同的字節(jié)序（大端序或小端序）,因此在發(fā)送和接收字節(jié)流時,可能需要考慮字節(jié)序的轉換,這篇文章主要介紹了C++實用庫之字節(jié)流合成器,需要的朋友可以參考下2024-04-04
文章介紹了C++中命名空間的定義和使用,包括定義和沖突解決、使用方式和標準庫中的應用,還詳細介紹了C++輸入輸出流、缺省參數、函數重載、引用、內聯函數和nullptr等概念及其用法和注意事項2026-03-03
這篇文章主要為大家介紹了C/C++開發(fā)中extern一些使用注意事項的事例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-01-01
此游戲是《2D 賽車》的”魔改版“——2.5D 雙人賽車！原作實現了 2D 視角的賽車游戲，但是我覺得不夠真實、操縱感不強，故擠出數個周末完成了這個”魔改版“，實現了第一人稱的視角，希望大家喜歡2022-12-12
現實生活中我們經常需要根據不同的條件做出不同的選擇。程序設計中也需要根據條件來選擇不同的程序進行處理，這稱之為分支結構，當條件表達式不存在時,它被假設為真。您也可以設置一個初始值和增量表達式,一般情況下,C?程序員偏向于使用?for(;;)?結構來表示一個無限循環(huán)2022-03-03
桶排序或所謂的箱排序，是一個排序算法，工作的原理是將數組分到有限數量的桶子，本文詳細的介紹了如何實現，感興趣的可以了解一下2021-07-07
本文檔介紹如何在 C++ 項目中使用 SQLite3 數據庫,假設通過 vcpkg 安裝了 SQLite3,因本機為Windows環(huán)境,為方便,用了本機的Visual Studio 2022 創(chuàng)建cmake項目,需要的朋友可以參考下2025-11-11
這篇文章主要介紹了c++ 前自增/后自增操作符效率分析，幫助大家更好的理解和學習c++,感興趣的朋友可以了解下2021-01-01