??🧑?🎓個人主頁:簡 料
??🏆所屬專欄:C++
??🏆個人社區:越努力越幸運社區
??🏆簡? ? ?? 介:簡料簡料,簡單有料~在校大學生一枚,專注C/C++/GO的干貨分享,立志成為您的好幫手 ~
C/C++學習路線 (點擊解鎖) |
---|
??C語言 |
??初階數據結構與算法 |
??C++ |
??高階數據結構 |
??Linux系統編程與網絡編程 |
文章目錄
- 🏆前言
- 🧑?🎓vector的介紹
- 🧑?🎓vector的使用
- ??vector的定義
- ??vector iterator 的使用
- ??vector 空間增長問題
- ??vector 增刪查改
- ??vector 迭代器失效問題(重點)
- ??小試牛刀
- 🏆寫在最后
🏆前言
🌀 前面對
STL
進行了介紹 【 戳此了解STL】,本章就給大家帶來STL
當中的vector
~
🌀vector
在C++
里也是非常常用的,它相當于C語言當中的數組,但是比數組多了更多實用的操作,數組有的它有,數組沒有的它也有,所以說,學習vector
可以使我們能夠更好的對以一個序列(連續)存儲的數據進行操作~
🌀能夠熟練的使用vector
,可以很大程度上提高寫算法題的效率,有許多的困難算法題,都需要對一串連續儲存的數據進行操作,這時候vector
以及它里面的方法就是個殺手锏了~
使用
STL
的三個境界:能用,明理,能擴展 ,那么下面學習vector
,我們也是按照這個方法去學習👀
🧑?🎓vector的介紹
?
vector的文檔介紹
?
在C++中,vector是一種動態數組,它提供了對數組的抽象管理,包括動態調整大小、隨機訪問等。vector是C++標準庫中的一部分,它提供了一個高效的、可預測的、可擴展的方式來存儲和訪問一組連續的數據。
?
- vector是表示可變大小數組的序列容器。
- 就像數組一樣,vector也采用的連續存儲空間來存儲元素。也就是意味著可以采用下標對vector的元素進行訪問,和數組一樣高效。但是又不像數組,它的大小是可以動態改變的,而且它的大小會被容器自動處理。
- 本質講,vector使用動態分配數組來存儲它的元素。當新元素插入時候,這個數組需要被重新分配大小為了增加存儲空間。其做法是,分配一個新的數組,然后將全部元素移到這個數組。就時間而言,這是一個相對代價高的任務,因為每當一個新的元素加入到容器的時候,vector并不會每次都重新分配大小。
- vector分配空間策略:vector會分配一些額外的空間以適應可能的增長,因為存儲空間比實際需要的存儲空間更大。不同的庫采用不同的策略權衡空間的使用和重新分配。但是無論如何,重新分配都應該是對數增長的間隔大小,以至于在末尾插入一個元素的時候是在常數時間的復雜度完成的。
- 因此,vector占用了更多的存儲空間,為了獲得管理存儲空間的能力,并且以一種有效的方式動態增長。
- 與其它動態序列容器相比(deque, list and forward_list), vector在訪問元素的時候更加高效,在末尾添加和刪除元素相對高效。對于其它不在末尾的刪除和插入操作,效率更低。比起list和forward_list統一的迭代器和引用更好。
vector的主要特點包括:
- 動態大小:vector的大小是動態的,可以根據需要增加或減少元素。你可以使用push_back()函數添加元素,使用erase()函數刪除元素,或者直接使用resize()函數調整其大小。
- 隨機訪問:vector支持隨機訪問,你可以使用索引操作符[]直接訪問任意位置的元素。
- 內存管理:vector自動管理其內存。當你向vector添加元素時,它會自動分配足夠的內存以容納新元素。當刪除元素時,它會自動回收相應的內存。
- 插入和刪除:vector提供了插入和刪除元素的方法,如push_back()、pop_back()、insert()和erase()等。這些方法可以在指定的位置插入或刪除元素,保持vector的連續性。
- 迭代器:vector提供了迭代器,可以遍歷其所有元素。迭代器提供了訪問每個元素的有效方式,并支持向前和向后遍歷。
- 高效的隨機訪問:由于vector內部使用連續的內存空間來存儲元素,因此隨機訪問非常高效。在大多數情況下,使用索引訪問vector中的元素比使用迭代器遍歷整個vector更快。
- 可修改的容量:你可以使用resize()函數來更改vector的容量。這允許你在運行時根據需要增加或減少存儲空間的大小。
- 支持常量引用語義:對于包含常量元素的vector,可以使用常量引用語義來訪問和修改元素。這有助于提高代碼的可讀性和安全性。
- 支持異常安全:C++的vector類型在某些操作中提供了異常安全的保證。例如,在執行push_back()或insert()操作時,如果發生異常,vector將保留其原始狀態。這有助于防止在異常情況下破壞數據完整性。
此外,C++的vector是一個模板類【戳此了解模板】,這意味著它可以根據需要為不同的數據類型提供不同的實現。模板是一種C++的編程技術,允許程序員編寫可以處理不同數據類型的通用代碼。通過使用模板,可以創建可重用的組件,從而提高代碼的可重用性和靈活性。
在C++中,vector的模板聲明如下:
template <class T>
class vector { // vector implementation details
};
這里,T是一個模板參數,表示vector可以容納的任意數據類型。當創建vector對象時,需要指定模板參數,即要存儲在vector中的數據類型。例如,要創建一個整數類型的vector,可以這樣聲明:
std::vector<int> myVector;
在這個例子中,int是模板參數,表示vector將容納整數類型的數據。類似的,你也可以使用其他數據類型,如浮點數、字符串等。
?
由于vector是一個模板類,它提供了針對不同數據類型的成員函數和操作。例如,push_back()函數可以添加元素到vector的末尾,對于整數、浮點數、字符串等不同類型的vector都適用。類似地,vector也可以提供用于訪問、修改和刪除元素的成員函數,如at(), front(), back(), erase()等。
?
通過使用模板,vector提供了一種通用的、可擴展的方式來存儲和操作一組連續的元素。這種靈活性使得vector成為C++標準庫中非常有用的容器之一,適用于各種不同的編程場景。
🧑?🎓vector的使用
?
vector學習時一定要學會查看文檔:[vector的文檔介紹],vector在實際中非常的重要,在實際中我們熟悉常見的接口就可以,下面列出了哪些接口是要重點掌握的。
?
??vector的定義
int TestVector1()
{// constructors used in the same order as described above:vector<int> first; // empty vector of intsvector<int> second(4, 100); // four ints with value 100vector<int> third(second.begin(), second.end()); // iterating through secondvector<int> fourth(third); // a copy of third// 下面涉及迭代器初始化的部分,我們學習完迭代器再來看這部分// the iterator constructor can also be used to construct from arrays:int myints[] = { 16,2,77,29 };vector<int> fifth(myints, myints + sizeof(myints) / sizeof(int));cout << "The contents of fifth are:";for (vector<int>::iterator it = fifth.begin(); it != fifth.end(); ++it)cout << ' ' << *it;cout << '\n';return 0;
}
??vector iterator 的使用
void PrintVector(const vector<int>& v)
{// const對象使用const迭代器進行遍歷打印vector<int>::const_iterator it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;
}
??vector 空間增長問題
- capacity的代碼在vs和g++下分別運行會發現,vs下capacity是按1.5倍增長的,g++是按2倍增長的。這個問題經常會考察,不要固化的認為,vector增容都是2倍,具體增長多少是根據具體的需求定義的。vs是PJ版本STL,g++是SGI版本STL。
- reserve只負責開辟空間,如果確定知道需要用多少空間,reserve可以緩解vector增容的代價缺陷問題。
- resize在開空間的同時還會進行初始化,影響size。
// 測試vector的默認擴容機制
void TestVectorExpand()
{size_t sz;vector<int> v;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';}}
}
vs:運行結果:vs下使用的STL基本是按照1.5倍方式擴容
making foo grow:
capacity changed: 1
capacity changed: 2
capacity changed: 3
capacity changed: 4
capacity changed: 6
capacity changed: 9
capacity changed: 13
capacity changed: 19
capacity changed: 28
capacity changed: 42
capacity changed: 63
capacity changed: 94
capacity changed: 141g++運行結果:linux下使用的STL基本是按照2倍方式擴容
making foo grow:
capacity changed: 1
capacity changed: 2
capacity changed: 4
capacity changed: 8
capacity changed: 16
capacity changed: 32
capacity changed: 64
capacity changed: 128----------------------------------------------------------------------------------// 如果已經確定vector中要存儲元素大概個數,可以提前將空間設置足夠
// 就可以避免邊插入邊擴容導致效率低下的問題了
void TestVectorExpandOP()
{vector<int> v;size_t sz = v.capacity();v.reserve(100); // 提前將容量設置好,可以避免一遍插入一遍擴容cout << "making bar 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';}}
}
// vector的resize 和 reserve
// reisze(size_t n, const T& data = T())
// 將有效元素個數設置為n個,如果時增多時,增多的元素使用data進行填充
// 注意:resize在增多元素個數時可能會擴容
void TestVector3()
{vector<int> v;// set some initial content:for (int i = 1; i < 10; i++)v.push_back(i);v.resize(5);v.resize(8, 100);v.resize(12);cout << "v contains:";for (size_t i = 0; i < v.size(); i++)cout << ' ' << v[i];cout << endl;
}
??vector 增刪查改
// 尾插和尾刪:push_back/pop_back
void TestVector4()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);auto it = v.begin();while (it != v.end()) {cout << *it << " ";++it;}cout << endl;v.pop_back();v.pop_back();it = v.begin();while (it != v.end()) {cout << *it << " ";++it;}cout << endl;
}// 任意位置插入:insert和erase,以及查找find
// 注意find不是vector自身提供的方法,是STL提供的算法
void TestVector5()
{// 使用列表方式初始化,C++11新語法vector<int> v{ 1, 2, 3, 4 };// 在指定位置前插入值為val的元素,比如:3之前插入30,如果沒有則不插入// 1. 先使用find查找3所在位置// 注意:vector沒有提供find方法,如果要查找只能使用STL提供的全局findauto pos = find(v.begin(), v.end(), 3);if (pos != v.end()){// 2. 在pos位置之前插入30v.insert(pos, 30);}vector<int>::iterator it = v.begin();while (it != v.end()) {cout << *it << " ";++it;}cout << endl;pos = find(v.begin(), v.end(), 3);// 刪除pos位置的數據v.erase(pos);it = v.begin();while (it != v.end()) {cout << *it << " ";++it;}cout << endl;
}/ 遍歷方式// operator[]+index 和 C++11中vector的新式for+auto的遍歷
// vector使用這兩種遍歷方式是比較便捷的。
void TestVector6()
{vector<int> v{ 1, 2, 3, 4 };// 通過[]讀寫第0個位置。v[0] = 10;cout << v[0] << endl;// 1. 使用for+[]小標方式遍歷for (size_t i = 0; i < v.size(); ++i)cout << v[i] << " ";cout << endl;vector<int> swapv;swapv.swap(v);cout << "v data:";for (size_t i = 0; i < v.size(); ++i)cout << v[i] << " ";cout << endl;// 2. 使用迭代器遍歷cout << "swapv data:";auto it = swapv.begin();while (it != swapv.end()){cout << *it << " ";++it;}// 3. 使用范圍for遍歷for (auto x : v)cout << x << " ";cout << endl;
}
??vector 迭代器失效問題(重點)
?
迭代器的主要作用就是讓算法能夠不用關心底層數據結構,其底層實際就是一個指針,或者是對指針進行了封裝,比如:vector的迭代器就是原生態指針T * 。因此迭代器失效,實際就是迭代器底層對應指針所指向的空間被銷毀了,而使用一塊已經被釋放的空間,造成的后果是程序崩潰(即如果繼續使用已經失效的迭代器,程序可能會崩潰)。
?
對于vector可能會導致其迭代器失效的操作有:
- 會引起其底層空間改變的操作,都有可能是迭代器失效,比如:resize、reserve、insert、assign、push_back等。
#include <iostream>
using namespace std;
#include <vector>
int main()
{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);/*出錯原因:以上操作,都有可能會導致vector擴容,也就是說vector底層原理舊空間被釋放掉,而在打印時,it還使用的是釋放之間的舊空間,在對it迭代器操作時,實際操作的是一塊已經被釋放的空間,而引起代碼運行時崩潰。解決方式:在以上操作完成之后,如果想要繼續通過迭代器操作vector中的元素,只需給it重新賦值即可。*/while(it != v.end()){cout<< *it << " " ;++it;}cout<<endl;return 0;
}
- 指定位置元素的刪除操作–erase
#include <iostream>
using namespace std;
#include <vector>int main()
{int a[] = { 1, 2, 3, 4 };vector<int> v(a, a + sizeof(a) / sizeof(int));// 使用find查找3所在位置的iteratorvector<int>::iterator pos = find(v.begin(), v.end(), 3);// 刪除pos位置的數據,導致pos迭代器失效。v.erase(pos);cout << *pos << endl; // 此處會導致非法訪問return 0;
}
erase刪除pos位置元素后,pos位置之后的元素會往前搬移,沒有導致底層空間的改變,理論上講迭代器不應該會失效,但是:如果pos剛好是最后一個元素,刪完之后pos剛好是end的位置,而end位置是沒有元素的,那么pos就失效了。因此刪除vector中任意位置上元素時,vs就認為該位置迭代器失效了。
思考:以下代碼的功能是刪除vector中所有的偶數,請問那個代碼是正確的,為什么?
#include <iostream>
using namespace std;
#include <vector>int main()
{vector<int> v{ 1, 2, 3, 4 };auto it = v.begin();while (it != v.end()){if (*it % 2 == 0)v.erase(it);++it;}return 0;
}==========================================================================================================int main()
{vector<int> v{ 1, 2, 3, 4 };auto it = v.begin();while (it != v.end()){if (*it % 2 == 0)it = v.erase(it);else++it;}return 0;
}
- 注意:Linux下,g++編譯器對迭代器失效的檢測并不是非常嚴格,處理也沒有vs下極端。
// 1. 擴容之后,迭代器已經失效了,程序雖然可以運行,但是運行結果已經不對了
int main()
{vector<int> v{1,2,3,4,5};for(size_t i = 0; i < v.size(); ++i)cout << v[i] << " ";cout << endl;auto it = v.begin();cout << "擴容之前,vector的容量為: " << v.capacity() << endl;// 通過reserve將底層空間設置為100,目的是為了讓vector的迭代器失效 v.reserve(100);cout << "擴容之后,vector的容量為: " << v.capacity() << endl;// 經過上述reserve之后,it迭代器肯定會失效,在vs下程序就直接崩潰了,但是linux下不會// 雖然可能運行,但是輸出的結果是不對的while(it != v.end()){cout << *it << " ";++it;}cout << endl;return 0;
}程序輸出:
1 2 3 4 5
擴容之前,vector的容量為: 5
擴容之后,vector的容量為: 100
0 2 3 4 5 409 1 2 3 4 5// 2. erase刪除任意位置代碼后,linux下迭代器并沒有失效
// 因為空間還是原來的空間,后序元素往前搬移了,it的位置還是有效的
#include <vector>
#include <algorithm>int main()
{vector<int> v{1,2,3,4,5};vector<int>::iterator it = find(v.begin(), v.end(), 3);v.erase(it);cout << *it << endl;while(it != v.end()){cout << *it << " ";++it;}cout << endl;return 0;
}
程序可以正常運行,并打印:
4
4 5// 3: erase刪除的迭代器如果是最后一個元素,刪除之后it已經超過end
// 此時迭代器是無效的,++it導致程序崩潰
int main()
{vector<int> v{1,2,3,4,5};// vector<int> v{1,2,3,4,5,6};auto it = v.begin();while(it != v.end()){if(*it % 2 == 0)v.erase(it);++it;}for(auto e : v)cout << e << " ";cout << endl;return 0;
}========================================================
// 使用第一組數據時,程序可以運行
[sly@VM-0-3-centos 20220114]$ g++ testVector.cpp -std=c++11
[sly@VM-0-3-centos 20220114]$ ./a.out
1 3 5
=========================================================
// 使用第二組數據時,程序最終會崩潰
[=============linux=========]$ vim testVector.cpp
[=============linux=========]$ g++ testVector.cpp -std=c++11
[=============linux=========]$ ./a.out
Segmentation fault
從上述三個例子中可以看到:SGI STL中,迭代器失效后,代碼并不一定會崩潰,但是運行結果肯定不對,如果it不在begin和end范圍內,肯定會崩潰的。
4. 與vector類似,string在插入+擴容操作+erase之后,迭代器也會失效
#include <string>
void TestString()
{string s("hello");auto it = s.begin();// 放開之后代碼會崩潰,因為resize到20會string會進行擴容// 擴容之后,it指向之前舊空間已經被釋放了,該迭代器就失效了// 后序打印時,再訪問it指向的空間程序就會崩潰//s.resize(20, '!');while (it != s.end()){cout << *it;++it;}cout << endl;it = s.begin();while (it != s.end()){it = s.erase(it);// 按照下面方式寫,運行時程序會崩潰,因為erase(it)之后// it位置的迭代器就失效了// s.erase(it); ++it;}
}
迭代器失效解決辦法:在使用前,對迭代器重新賦值即可。
??小試牛刀
😊楊輝三角
😊只出現一次的數字
😊刪除有序數組中的重復項
😊只出現一次的數字 II
😊只出現一次的數字 III
😊數組中出現次數超過一半的數字
😊電話號碼的字母組合
🏆寫在最后
💝本章主要是給大家介紹vector~ 在
C++
中,vector
是一個非常重要的數據結構。它具有動態大小、隨機訪問、內存管理、插入和刪除、迭代器等優點。它是一種通用的、可擴展的容器,適用于各種不同的編程場景。學習和掌握vector
的使用對于編寫高效的C++
程序非常重要。因此,大家可要好好敲噢~😊
???🔥后續將會繼續輸出有關
C++
的文章,你們的支持就是我寫作的最大動力!
感謝閱讀本小白的博客,錯誤的地方請嚴厲指出噢~