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