C++中的vector使用詳解及重要部分底層實現(xiàn)
一、vector 簡單概述
1、1 C語言中數(shù)組的不便
在C語言中，我們所要存放一組類型相同的數(shù)據(jù)，我們可以選擇數(shù)組。C語言中的數(shù)組是靜態(tài)的，一旦聲明后，其大小就是固定的，無法動態(tài)調(diào)整。這就導致使用起來并不方便。當然，我們也用malloc、calloc來動態(tài)申請空間。當我們不再使用此數(shù)組時，我們也要時刻注意是否已經(jīng)釋放我們所動態(tài)開辟的空間。
1、2 C++中的動態(tài)數(shù)組容器vector
針對C語言中靜態(tài)數(shù)組的不便，C++中引出了動態(tài)數(shù)組容器vector，vector有以下幾個不同和優(yōu)點：
可以根據(jù)需要自動調(diào)整大小，可以動態(tài)地添加或刪除元素。
- 就像數(shù)組一樣，vector也采用的連續(xù)存儲空間來存儲元素。也就是意味著可以采用下標對vector的元素進行訪問，和數(shù)組一樣高效。但是又不像數(shù)組，它的大小是可以動態(tài)改變的，而且它的大小會被容器自動處理。
- C++中的vector自動處理內(nèi)存管理，無需手動指定大小或釋放內(nèi)存。
- C++中的vector提供了邊界檢查功能，能夠確保在訪問元素時不會發(fā)生越界錯誤。
- C++中的vector提供了豐富的函數(shù)和操作，如添加元素、刪除元素、排序、查找等。這些功能能夠更方便地操作和處理數(shù)組元素。
本質(zhì)講，vector使用動態(tài)分配數(shù)組來存儲它的元素。當新元素插入時候，這個數(shù)組需要被重新分配大小為了增加存儲空間。其做法是，分配一個新的數(shù)組，然后將全部元素移到這個數(shù)組。就時間而言，這是 一個相對代價高的任務，因為每當一個新的元素加入到容器的時候，vector并不會每次都重新分配大小。
只有概念并不能很好的使用vector，我們接下來看一下vector語法的講解。
二、vector的常用語法舉例
#include <vector>
#include <iostream>
using namespace std;
int main()
{
vector<int> v;
vector<int> v1(10);
vector<int> v2(10, 1);
vector<int> v3(v2);
v.push_back(10);
v.push_back(20);
v.pop_back();
v.reserve(10);
v = v1;
v.insert(v.begin() + 2, 3);
v.erase(v.begin() + 2);
int sz = v.size();
for (int i = 0; i < sz; i++)
{
cout << v[i] << " ";
}
cout << endl;
vector<int>::iterator it = v.begin();
while (it != v.end())
{
cout << *it << " ";
it++;
}
cout << endl;
for (auto it : v)
{
cout << it << " ";
}
cout << endl;
v.clear();
v.front();
v.back();
return 0;
}我們就上面的例子展開對vector的用法進行詳解。
2、1 vector的聲明和定義
當我們想用vector時，我們首先要引入頭文件:#include<vector>。當我們可展開命名空間std，也可選擇不展開命名空間std。具體例子如下：
#include <vector>
#include <iostream>
using namespace std;
int main()
{
//std::vector<int> v;
vector<int> v;
vector<int> v1(10);
vector<int> v2(10, 1);
vector<int> v3(v2);
return 0;
} 注意，上述中的變量v為空數(shù)組，空間大小為0。v1是開辟了一個大小為10個int的數(shù)組，這10個元素默認為0。v2是開辟了一個大小為10個int的數(shù)組，這10個元素初始化為1。v3是用v2中的元素來進行初始化的，也就是v3中的元素與v2中的元素相同。我們可看如下結(jié)果：
2、2 尾插 push_back
有了vector，我們想要往里添加元素，我們可使用push_back進行尾部插入元素。具體例子如下：
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<int> v;
vector<int> v1(10);
vector<int> v2(10, 1);
v.push_back(10);
v.push_back(20);
v.push_back(30);
return 0;
}運行結(jié)果如下：
我們發(fā)現(xiàn)，v數(shù)組不是空間大小為0嗎，怎么還能插入元素呢？這個是因為vector是一個動態(tài)數(shù)組，底層就是一個動態(tài)的順序表。當空間容量不夠時，會自動進行擴容。
2、3 尾刪 pop_back
pop_back可對尾部元素進行刪除。當然，尾刪的前提是數(shù)組不為空。否則會程序會被終止。具體例子如下：‘
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<int> v;
//v.pop_back();
vector<int> v1(10);
vector<int> v2(10, 1);
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.pop_back();
return 0;
}我們先看看在空vector進行刪除的結(jié)果：
我們再看看實際的尾刪效果:
2、4 設置容量大小 reserve
當我們知道要存儲的元素個數(shù)是多少時，我們可直接通過reserve來設置vector的容量大小。有人就說了，vector空間不夠了可以自己進行擴容，為啥還要用reserve來設定容量大小呢？注意，擴容是有損耗的。頻繁的擴容會大大的降低程序的運行效率。我們來看reserve的實際效果。
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.pop_back();
v.reserve(10);
return 0;
}運行結(jié)果如下：
我們之前看到尾刪后的容量（capacity）大小為3，當我們reserve（）后，容量大小變?yōu)榱?0。size為當前vector中的實際有多少個元素。capacity為當前vector實際能夠存儲多少個元素。兩者是不同的。
2、5 賦值 =
當然，我們也可直接對不同的vector進行賦值操作。具體例子如下：
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<int> v;
vector<int> v1(10);
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.pop_back();
v.reserve(10);
v = v1;
return 0;
}運行結(jié)果如下：
賦值完后，v與v1完全相同。
2、6 在pos位置插入
我們發(fā)現(xiàn)尾插并不能很好的滿足我們對插入的實現(xiàn)。insert就可以選擇位置進行插入。當然，我們插入的位置必須是合法的位置。否則程序就會終止。我們看如下例子：
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<int> v;
vector<int> v1(10);
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.pop_back();
v.reserve(10);
v = v1;
v.insert(v.begin() + 2, 3);
return 0;
}運行結(jié)果如下:
我們是在開始位置往后偏移兩個元素的位置進行插入結(jié)果也正是如此。細心的同學也會發(fā)現(xiàn)，在插入的同時實現(xiàn)的擴容。 具體的擴容大小
2、7 任意位置刪除
尾刪也并不能滿足我們所需的刪除功能。erase可進行任意位置刪除。具體例子如下：
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<int> v;
vector<int> v1(10);
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.pop_back();
v.reserve(10);
v = v1;
v.insert(v.begin() + 2, 3);
v.erase(v.begin() + 2);
return 0;
}運行結(jié)果如下：
我們就是在之前所插入的位置進行了刪除。
2、8 訪問vector中的元素
訪問vector中的元素有兩種：通過 [] + 下標索引 、迭代器。具體例子如下：
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<int> v(10,2);
int sz = v.size();
for (int i = 0; i < sz; i++)
{
cout << v[i] << " ";
}
cout << endl;
vector<int>::iterator it = v.begin();
while (it != v.end())
{
cout << *it << " ";
it++;
}
cout << endl;
for (auto it : v)
{
cout << it << " ";
}
cout << endl;
return 0;
}size（）可返回vector中的元素個數(shù)。運行結(jié)果如下：
都能夠很好的打印出vector中的元素。
2、9 數(shù)組中的頭和尾元素front（）、back（）
front（）、back（）函數(shù)可返回數(shù)組中的第一個元素和最后一個元素。當然，我們也可通過下標直接訪問。所以這兩個函數(shù)也并不常用。
三、部分重要底層實現(xiàn)及常見問題
vector的底層是由三個指針是私有成員變量。來記錄數(shù)組的不同位置、大小、容量。實際如下：
template<class T>
class vector
{
public:
typedef T* iterator;private:
private:
iterator start;
iterator finish;
iterator end_of_storage;
};注意，底層使用類模板來試實現(xiàn)的。很好的解決了vector可以存儲不同類型的數(shù)據(jù)問題。
3、1 拷貝構(gòu)造的底層實現(xiàn)
拷貝構(gòu)造底層實現(xiàn)的方式有很多，但思路是大同小異的，具體如下：
vector(const vector<T>& v)
:start(nullptr)
,finish(nullptr)
,end_of_storage(nullptr)
{
iterator tmp = new T[v.size()];
//memcpy(tmp, v.start, sizeof(T) * v.size());
//T為自定義類型時，自定義類型自動調(diào)用賦值重載，完成深拷貝
for (size_t i = 0; i < v.size(); i++)
{
tmp[i] = v.start[i];
}
start = tmp;
finish = start + v.size();
end_of_storage = start + v.size();
}
//vector(const vector<T>& v)
// :start(nullptr)
// , finish(nullptr)
// , end_of_storage(nullptr)
//{
// reserve(v.size());
// for (auto it : v)
// {
// push_back(it);
// }
//}
template <class InputIterator>
vector(InputIterator first, InputIterator last)
:start(nullptr)
, finish(nullptr)
, end_of_storage(nullptr)
{
while (first != last)
{
push_back(*first);
first++;
}
}
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(const vector<T>& v)
:start(nullptr)
, finish(nullptr)
, end_of_storage(nullptr)
{
vector<T> tmp(v.begin(), v.end());
swap(tmp);
}3、2 insert的底層實現(xiàn)及迭代器失效
在實現(xiàn)insert時，我們需要注意的是擴容后，釋放掉原來的空間，原來的pos就變成了野指針！需要記錄相對位置，更新pos。具體代碼如下：
iterator insert(iterator pos,const T& x)
{
assert(pos >= start);
assert(pos <= finish);
if (start == end_of_storage)
{
//注意，擴容后原來的pos就變?yōu)橐爸羔?，需要記錄相對位置更新pos
size_t len = pos - start;
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = start + len;
}
iterator end = finish - 1;
while (end >= pos)
{
*(end+1) = *end;
end--;
}
*pos = x;
finish++;
return pos;
}void test()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
//v.push_back(5);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
vector<int>::iterator p = find(v.begin(), v.end(), 3);
if (p != v.end())
{
// 在p位置插入數(shù)據(jù)以后，不要訪問p，因為p可能失效了。
v.insert(p, 30);
//cout << *p << endl;
//v.insert(p, 40);
}
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
v.insert(v.begin(), 1);
}我們在用迭代器時，可能會出現(xiàn)很多意想不到的錯誤。上述代碼中的變量 p 為例子，我們能一直在變量 p 位置插入數(shù)據(jù)嗎？答案是不能！??！為什么呢？因為當我們擴容后，原指針 p 所指向的空間就會被釋放，p 就變成了野指針！所以，在p位置插入數(shù)據(jù)以后，不要訪問p，因為p可能失效了。這就是所謂的迭代器失效。
3、3 erase的底層實現(xiàn)及迭代器失效
erase的底層實現(xiàn)較為簡單，直接更改finish指針即可。我們直接看代碼：
iterator erase(iterator pos)
{
assert(pos >= start);
assert(pos < finish);
iterator cur = pos + 1;
while (cur < finish)
{
*(cur - 1) = *cur;
cur++;
}
finish--;
return pos;
}erase并沒有擴容，為啥會出現(xiàn)迭代器失效呢？我們先看個例子：
void test_vector4()
{
// 正常運行
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
// 要求刪除所有的偶數(shù)
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
{
v.erase(it);
}
++it;
}
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
void test_vector4()
{
// 崩潰
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
// 要求刪除所有的偶數(shù)
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
{
v.erase(it);
}
++it;
}
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
void test_vector4()
{
// 結(jié)果不對
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(4);
v.push_back(3);
v.push_back(4);
v.push_back(5);
// 要求刪除所有的偶數(shù)
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
{
v.erase(it);
}
++it;
}
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}上述準確來說，第一個運行結(jié)果正確的為僥幸。為什么呢？注意，erase刪除后，后面的元素就會向前移動。并且會返回當前所指向的位置，所以不用再 it++ 了。正確的代碼如下：
//正確的方式
void test_vector4()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(4);
v.push_back(3);
v.push_back(4);
v.push_back(5);
// 要求刪除所有的偶數(shù)
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
{
it = v.erase(it);
}
else
{
++it;
}
}
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}總的來說，我們進行插入和刪除后，就盡可能的不要再次去訪問原指針了。很有可能已經(jīng)失效了，會出現(xiàn)意想不到的效果。
3、4 vector中深拷貝的問題
vector中，不管是賦值重載還是拷貝構(gòu)造，都是需要進行深拷貝的。但是vector中元素也必須進行深拷貝。為什么呢？當vector中的元素為int、char等內(nèi)置類型無所謂，如果是自定義類型，那問題就出來了。
當vector中的元素為自定義類型，對元素進行先拷貝，元素還是指向的同一塊空間。
vector中存儲的為string：
_str中存儲的是string的地址，如果使用淺拷貝，在插入擴容時，就把原來的地址拷貝過來。
再釋放掉原來的地址，就會導致新拷貝的地址變成野指針。具體如下：
以上就是C++中的vector使用詳解及重要部分底層實現(xiàn)的詳細內(nèi)容，更多關(guān)于C++ vector使用的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
c語言中字符串函數(shù)(庫函數(shù)使用)和模擬實現(xiàn)圖文教程
C語言中對字符和字符串的處理很是頻繁,但是C語言本身并沒有字符串類型,這篇文章主要給大家介紹了關(guān)于c語言中字符串函數(shù)(庫函數(shù)使用)和模擬實現(xiàn)的相關(guān)資料,需要的朋友可以參考下2024-01-01
大家好，本篇文章主要講的是C語言實現(xiàn)單鏈表的快速排序算法，感興趣的同學趕快來看一看吧，對你有幫助的話記得收藏一下2022-01-01
從下面表中的數(shù)據(jù)來看寫入用時vector和deque很快，因為他們內(nèi)存分配次數(shù)少，關(guān)聯(lián)容器和list都是一個一個分配的，一個一個分配也會造成內(nèi)存碎片，內(nèi)存利用率低2013-09-09
這篇文章主要為大家詳細介紹了C語言實現(xiàn)字符串拼接和拷貝，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-08-08
這篇文章主要介紹了C++中的引用與高級函數(shù)詳解,概念：引用是為已存在的變量取了一個別名，引用和引用的變量共用同一塊內(nèi)存空間,需要的朋友可以參考下2023-07-07
類型轉(zhuǎn)換（type?cast），是高級語言的一個基本語法。它被實現(xiàn)為一個特殊的運算符，以小括號內(nèi)加上類型名來表示，接下來讓我們一起來詳細了解2022-04-04
C++ getline()是一種標準庫函數(shù),用于從輸入流中讀取字符串或行,它是<string>標頭的一部分,本文介紹C++ string類getline()用法詳解,感興趣的朋友一起看看吧2024-03-03
這篇文章主要為大家詳細介紹了C語言實現(xiàn)鏈隊列基本操作，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-09-09
這篇文章主要為大家詳細介紹了C語言實現(xiàn)隨機抽取紙牌，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-10-10
Cocos2d-x UI開發(fā)之CCControlSlider控件類使用實例
這篇文章主要介紹了Cocos2d-x UI開發(fā)之CCControlSlider控件類使用實例,本文代碼中包含大量注釋講解了CCControlSlider控件類的使用,需要的朋友可以參考下2014-09-09