C++中的vector使用詳解及重要部分底層實現(xiàn)
一、vector 簡單概述
1、1 C語言中數(shù)組的不便
在C語言中，我們所要存放一組類型相同的數(shù)據(jù)，我們可以選擇數(shù)組。C語言中的數(shù)組是靜態(tài)的，一旦聲明后，其大小就是固定的，無法動態(tài)調(diào)整。這就導(dǎo)致使用起來并不方便。當(dāng)然，我們也用malloc、calloc來動態(tài)申請空間。當(dāng)我們不再使用此數(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ù)存儲空間來存儲元素。也就是意味著可以采用下標(biāo)對vector的元素進(jìn)行訪問，和數(shù)組一樣高效。但是又不像數(shù)組，它的大小是可以動態(tài)改變的，而且它的大小會被容器自動處理。
- C++中的vector自動處理內(nèi)存管理，無需手動指定大小或釋放內(nèi)存。
- C++中的vector提供了邊界檢查功能，能夠確保在訪問元素時不會發(fā)生越界錯誤。
- C++中的vector提供了豐富的函數(shù)和操作，如添加元素、刪除元素、排序、查找等。這些功能能夠更方便地操作和處理數(shù)組元素。
本質(zhì)講，vector使用動態(tài)分配數(shù)組來存儲它的元素。當(dāng)新元素插入時候，這個數(shù)組需要被重新分配大小為了增加存儲空間。其做法是，分配一個新的數(shù)組，然后將全部元素移到這個數(shù)組。就時間而言，這是 一個相對代價高的任務(wù)，因為每當(dāng)一個新的元素加入到容器的時候，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的用法進(jìn)行詳解。
2、1 vector的聲明和定義
當(dāng)我們想用vector時，我們首先要引入頭文件:#include<vector>。當(dāng)我們可展開命名空間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個元素默認(rèn)為0。v2是開辟了一個大小為10個int的數(shù)組，這10個元素初始化為1。v3是用v2中的元素來進(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;
}運行結(jié)果如下：
我們發(fā)現(xiàn)，v數(shù)組不是空間大小為0嗎，怎么還能插入元素呢？這個是因為vector是一個動態(tài)數(shù)組，底層就是一個動態(tài)的順序表。當(dāng)空間容量不夠時，會自動進(jìn)行擴(kuò)容。
2、3 尾刪 pop_back
pop_back可對尾部元素進(jìn)行刪除。當(dāng)然，尾刪的前提是數(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進(jìn)行刪除的結(jié)果：
我們再看看實際的尾刪效果:
2、4 設(shè)置容量大小 reserve
當(dāng)我們知道要存儲的元素個數(shù)是多少時，我們可直接通過reserve來設(shè)置vector的容量大小。有人就說了，vector空間不夠了可以自己進(jìn)行擴(kuò)容，為啥還要用reserve來設(shè)定容量大小呢？注意，擴(kuò)容是有損耗的。頻繁的擴(kuò)容會大大的降低程序的運行效率。我們來看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，當(dāng)我們reserve（）后，容量大小變?yōu)榱?0。size為當(dāng)前vector中的實際有多少個元素。capacity為當(dāng)前vector實際能夠存儲多少個元素。兩者是不同的。
2、5 賦值 =
當(dāng)然，我們也可直接對不同的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;
}運行結(jié)果如下：
賦值完后，v與v1完全相同。
2、6 在pos位置插入
我們發(fā)現(xiàn)尾插并不能很好的滿足我們對插入的實現(xiàn)。insert就可以選擇位置進(jìn)行插入。當(dāng)然，我們插入的位置必須是合法的位置。否則程序就會終止。我們看如下例子：
#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é)果如下:
我們是在開始位置往后偏移兩個元素的位置進(jìn)行插入結(jié)果也正是如此。細(xì)心的同學(xué)也會發(fā)現(xiàn)，在插入的同時實現(xiàn)的擴(kuò)容。 具體的擴(kuò)容大小
2、7 任意位置刪除
尾刪也并不能滿足我們所需的刪除功能。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;
}運行結(jié)果如下：
我們就是在之前所插入的位置進(jìn)行了刪除。
2、8 訪問vector中的元素
訪問vector中的元素有兩種：通過 [] + 下標(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中的元素個數(shù)。運行結(jié)果如下：
都能夠很好的打印出vector中的元素。
2、9 數(shù)組中的頭和尾元素front（）、back（）
front（）、back（）函數(shù)可返回數(shù)組中的第一個元素和最后一個元素。當(dāng)然，我們也可通過下標(biāo)直接訪問。所以這兩個函數(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時，我們需要注意的是擴(kuò)容后，釋放掉原來的空間，原來的pos就變成了野指針！需要記錄相對位置，更新pos。具體代碼如下：
iterator insert(iterator pos,const T& x)
{
assert(pos >= start);
assert(pos <= finish);
if (start == end_of_storage)
{
//注意，擴(kuò)容后原來的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ù)嗎？答案是不能?。?！為什么呢？因為當(dāng)我們擴(kuò)容后，原指針 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并沒有擴(kuò)容，為啥會出現(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;
}上述準(zhǔn)確來說，第一個運行結(jié)果正確的為僥幸。為什么呢？注意，erase刪除后，后面的元素就會向前移動。并且會返回當(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;
}總的來說，我們進(jìn)行插入和刪除后，就盡可能的不要再次去訪問原指針了。很有可能已經(jīng)失效了，會出現(xiàn)意想不到的效果。
3、4 vector中深拷貝的問題
vector中，不管是賦值重載還是拷貝構(gòu)造，都是需要進(jìn)行深拷貝的。但是vector中元素也必須進(jìn)行深拷貝。為什么呢？當(dāng)vector中的元素為int、char等內(nèi)置類型無所謂，如果是自定義類型，那問題就出來了。
當(dāng)vector中的元素為自定義類型，對元素進(jìn)行先拷貝，元素還是指向的同一塊空間。
vector中存儲的為string：
_str中存儲的是string的地址，如果使用淺拷貝，在插入擴(kuò)容時，就把原來的地址拷貝過來。
再釋放掉原來的地址，就會導(dǎo)致新拷貝的地址變成野指針。具體如下：
以上就是C++中的vector使用詳解及重要部分底層實現(xiàn)的詳細(xì)內(nèi)容，更多關(guān)于C++ vector使用的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
這篇文章主要介紹了C語言的Struct Hack例子,個人的一篇筆記,需要的朋友可以參考下吧2014-04-04
這篇文章主要介紹了解決C語言輸入單個字符屏蔽回車符的問題，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-12-12
為什么要進(jìn)程替換？因為父進(jìn)程創(chuàng)建出來的子進(jìn)程和父進(jìn)程擁有相同的代碼段，所以，子進(jìn)程看到的代碼和父進(jìn)程是一樣的。當(dāng)我們想要讓子進(jìn)程執(zhí)行不同的程序時候，就需要讓子進(jìn)程調(diào)用進(jìn)程程序替換的接口，從而讓子進(jìn)程執(zhí)行不一樣的代碼2022-08-08
這篇文章主要為大家詳細(xì)介紹了C++的const關(guān)鍵字,常量與常變量，使用數(shù)據(jù)庫，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03
基于Sizeof與Strlen的區(qū)別以及聯(lián)系的使用詳解
本篇文章是對Sizeof與Strlen的區(qū)別以及聯(lián)系的使用進(jìn)行了詳細(xì)的介紹。需要的朋友參考下2013-05-05
C++ Primer Plus 第四章之C++ Primer Plus復(fù)合類型學(xué)習(xí)筆記
數(shù)組（array）是一種數(shù)據(jù)格式，能夠存儲多個同類型的值。每個值都存儲在一個獨立的數(shù)組元素中，計算機(jī)在內(nèi)存中依次存儲數(shù)組的各個元素，今天給大家重點介紹C++ Primer Plus復(fù)合類型的實例詳解，感興趣的朋友一起看看吧2021-07-07
大家好，本篇文章主要講的是C++如何用數(shù)組模擬鏈表，感興趣的同學(xué)趕快來看一看吧，對你有幫助的話記得收藏一下2022-01-01
用while判斷輸入的數(shù)字是否回文數(shù)的簡單實現(xiàn)
這篇文章主要介紹了用while判斷輸入的數(shù)字是否回文數(shù)的簡單實現(xiàn),需要的朋友可以參考下2014-02-02
大家好，本篇文章主要講的是C語言輸出任意邊長的菱形，感興趣的同學(xué)趕快來看一看吧，對你有幫助的話記得收藏一下，方便下次瀏覽2021-12-12
這篇文章主要介紹了C/C++?控制臺等待指令解析，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-07-07