由于以后我們寫OJ題時會經常使用到vector，所以我們必不可缺的是熟悉它的各個接口。來為我們未來作鋪墊。

首先，我們了解一下：

https://cplusplus.com/reference/vector/

vector的概念：?

1. vector是表示可變大小數組的序列容器。

2. 就像數組一樣，vector也采用的連續存儲空間來存儲元素。也就是意味著可以采用下標對vector的元素進行訪問，和數組一樣高效。但是 又不像數組，它的大小是可以動態改變的，而且它的大小會被容器自動處理。

3. 本質講，vector使用動態分配數組來存儲它的元素。當新元素插入時候，這個數組需要被重新分配大小，為了增加存儲空間。其做法是，分配一個新的數組，然后將全部元素移到這個數組。就時間而言，這是一個相對代價高的任務，因為每當一個新的元素加入到容器的時候，vector并不會每次都重新分配大小。

4. vector分配空間策略：vector會分配一些額外的空間以適應可能的增長，因為存儲空間比實際需要的存儲空間更大。不同的庫采用不同的策略權衡空間的使用和重新分配。但是無論如何，重新分配都應該是對數增長的間隔大小，以至于在末尾插入一個元素的時候是在常數時間的復雜度完成的。

5. 因此，vector占用了更多的存儲空間，為了獲得管理存儲空間的能力，并且以一種有效的方式動態增長。

6. 與其它動態序列容器相比（deque, list and forward_list）， vector在訪問元素的時候更加高效(因為它在內存中是連續的)，在末尾添加和刪除元素相對高效。對于其它不在末尾的刪除和插入操作，效率更低。比起list和forward_list統一的迭代器和引用更好

vector的使用：

包含頭文件#include<vector>?

構造函數聲明

?1.定義（構造函數聲明）

構造函數聲明	接口
vector()（重點）	無參構造
vector（size_type n, const value_type& val = value_type()）	構造并初始化n個val
vector (const vector& x); （重點）	拷貝構造
vector (InputIterator first, InputIterator last);	使用迭代器進行初始化構造

allocator簡單理解

簡單了解上面出現的allocator概念：

ps：allocator在C++ 中，?alloc?通常和 內存分配有關。
??std::allocator?是C++標準庫中的一個 類模板，它用于將 內存分配和對象構造分離開來。例如，當你要創建一個包含自定義類型（如?class MyClass?）的容器（像?std::vector?）時，?std::allocator?就會發揮作用。它可以 高效地獲取內存塊，并且能夠在合適的時候釋放這些內存。這有助于優化內存使用，特別是在頻繁分配和釋放內存的場景下。
?
此外，有些非標準的庫或者自定義的代碼中也可能會有名為?alloc?的函數或者類，用于實現自定義的內存分配策略，比如實現一個簡單的 內存池 來避免頻繁的系統內存分配調用所帶來的開銷。

池化技術簡單認識?

?什么是池化技術（包括：內存池，線程池，連接池）呢：這里簡單了解了解

現在，以一個具體等等例子來講解：

1.現有一座廟，廟的地點在山頂，住在廟里的和尚。由于山上沒有水，只有山下有一湖水。每天起來刷牙，煮飯，和尚每天需要下山來一點一點的取水，這就顯得非常麻煩的了而且耽誤時間。而有一天，和尚在廟里弄了一個水池，來儲存水。這時候，和尚就不需要每天上下山來用水了，減少了上下山所消耗的時間。

2.而C++中的池化技術也是類似的道理：

?優勢：減少內存碎片，提高內存分配效率，尤其是在頻繁進行小內存分配的場景，如網絡編程中服務器頻繁創建和銷毀小數據包。

?構造函數初始化：

int TestVector1()
{// constructors used in the same order as described above:1.vector<int> first;                                // empty vector of ints2.vector<int> second(4, 100);                       // four ints with value 1003.vector<int> third(second.begin(), second.end());  // iterating through second4.vector<int> fourth(third);                       // a copy of third// 下面涉及迭代器初始化的部分，迭代器// the iterator constructor can also be used to construct from arrays:4.用數組的值進行初始化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的使用	接口說明
begin + end（重點）	獲取第一個數據位置的iterator/const_iterator， 獲取最后一個數據的下一個位置的iterator/const_iterator
rbegin + rend	獲取最后一個數據位置的reverse_iterator，獲取第一個數據前一個位置的reverse_iterator? ? （與上面的begin和end相反）

void PrintVector(const vector<int>& v)
{// const對象使用const迭代器進行遍歷打印vector<int>::const_iterator it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;
}

ps：范圍for同樣適用：用法跟之前的string時也是一樣的。

int main()
{vector<int> v={1,2,3,4,5,6};for(auto e:v){cout<<e<<" ";}return 0;
}

vector的增刪查改

vector增刪查改	接口說明
push_back（重點）	尾插
pop_back （重點）	尾刪
find	查找。（注意這個是算法模塊實現，不是vector的成員接口）
insert	在position之前插入val
erase	刪除position位置的數據
swap	交換兩個vector的數據空間
operator[] （重點）	像數組一樣訪問

// 尾插和尾刪：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[]與at()

operator[]:返回對向量容器中位置n處的元素的引用。

但是，vector：：at()是邊界檢查的，并在請求的位置超出范圍后通過異常拋出（out_of_range）的信號。operator[]在vs2022中是通過斷言的

operator[]遍歷vector對象：

operator[]改變vector對象：

?vector的容量空間：

容量空間	接口說明
size	獲取數據個數
capacity	獲取容量大小
empty	判斷是否為空
resize（重點）	改變vector的size
reserve （重點）	改變vector的capacity

// 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 << '\n';
}

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';}}
}

不同平臺下capacity的增長方式會不同

vs：

linux：

從上面我們可以得出：

vs下capacity是按1.5倍增長的，g++是按2倍增長的。因此，不要固化的認為，vector增容都是2倍，具體增長多少是根據具體的需求定義的。

// 往vecotr中插入元素時，如果大概已經知道要存放多少個元素
// 可以通過reserve方法提前將容量設置好，避免邊插入邊擴容效率低
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';}}
}

易錯：reserve誤區：

使用reserve（）開辟好看到的空間后直接使用operator[]來給vector賦值，這是錯誤的！！！

在 ?C++??中，?std::vector??的 ?reserve()??函數和 ?operator[]??的使用存在一些規則和限制，直接在 ?reserve()??開辟空間后就使用 ?operator[]??賦值是錯誤的，

主要原因如下：
?
?reserve()??函數的作用是確保 ?vector??至少有足夠的容量來容納指定數量的元素，但它不會改變 ?vector??的 ?size?（元素個數）。?size??表示 ?vector??中實際已有的元素數量，而 ?capacity??表示在不重新分配內存的情況下 ?vector??可以存儲的最大元素數量。
?
?operator[]??用于訪問 ?vector??中已存在的元素，它不會自動添加新元素。當你在 ?reserve()??之后直接使用 ?operator[]??時，由于 ?size??沒有改變，?vector??中實際上還沒有那么多元素，此時使用 ?operator[]??訪問超出 ?size??的位置會導致未定義行為（因為該位置可能是無效的內存區域）。

#include <iostream>
#include <vector>
using namespace std;int main() {vector<int> v;v.reserve(5);  // 預留 5 個元素的空間，但 size 還是 0v[0] = 10;     // 錯誤，因為 v 的 size 是 0，不存在索引為 0 的元素，這是未定義行為return 0;
}

如果確實想通過來賦值，可以先使用 resize() ?函數來調整 vector ?的 size ， resize() ?函數不僅會改變 vector ?的 size ，如果新的 size ?大于原來的 size ，還會在末尾添加默認值初始化的元素，這樣就可以安全地使用 operator[] ?進行賦值了。

或者說使用push_back,每次插入一個

#include <iostream>
#include <vector>
using namespace std;int main() {vector<int> v;v.reserve(5);  // 預留 5 個元素的空間v.resize(5);   // 調整 size 為 5，元素初始化為 0v[0] = 10;     // 現在可以安全地使用 operator[] 賦值for (int i : v) {cout << i << " ";}return 0;
}

綜上：不能在 reserve() ?開辟空間后直接使用 operator[] ?賦值，因為 reserve() ?沒有改變 size ， operator[] ?訪問超出 size ?的位置會導致未定義行為。

sort排序

1.sort（）函數是STL中算法部分的一個接口。這個函數是在OJ題中是頻繁使用到的。

2.調用sort時需要另外包含頭文件#include<algorithm>

3.簡單了解：

小于：

大于：?

4.sort默認情況下是升序，若想要降序，則需要用greater輔助。

5.從上面我們可以看到，參數是一個類模板，所以sort可以是int，string，數組等等都可以排序的。

find（）函數?

**重點**：

迭代器失效問題（分析）

概念：

迭代器失效是指在使用迭代器遍歷容器（如 vector 、 list 等）的過程中，由于容器的結構發生改變，導致原來的迭代器不再有效。

迭代器的主要作用就是讓算法能夠不用關心底層數據結構，其底層實際就是一個指針，或者是對指針進行了封裝，比如：vector的迭代器就是原生態指針T* 。因此迭代器失效，實際就是迭代器底層對應指針所指向的空間被銷毀了，而使用一塊已經被釋放的空間，造成的后果是程序崩潰(即如果繼續使用已經失效的迭代器，程序可能會崩潰)。

造成迭代器失效的原因：

引起其底層空間改變的操作

1.會引起其底層空間改變的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、push_back等。

我們知道預留空間時，一旦發生擴容，那么它實質上就是開一個新的空間，然后賦值過去，給原來的，這時候就會產生指向的空間被銷毀的問題。

對應上面的函數，我們不妨去看看string的模擬實現那里看看它對應是如何實現函數的內容的，一旦有開一個新空間，如何在賦值拷貝給它，指向的空間發生變化，因此，就出現了迭代器失效的問題了。

string的模擬實現_string& s0 = strs[0];-CSDN博客

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底層原理舊空間被釋放掉，而在打印時，it還使用的是釋放之間的舊空間，在對it迭代器操作時，實際操作的是一塊已經被釋放的空間，而引起代碼運行時崩潰，這就是迭代器失效！！

指定位置元素的刪除操作--erase
?

int main()
{
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; // 此處會導致非法訪問
return 0;
}

erase刪除pos位置元素后，pos位置之后的元素會往前搬移，沒有導致底層空間的改變，理論上講迭代器不應該會失效，

但是：如果pos剛好是最后一個元素，刪完之后pos剛好是end的位置，而end位置是沒有元素的，那么pos就失效了。因此刪除vector中任意位置上元素時，vs就認為該位置迭代器失效了（這里挺好理解的，就不畫圖了）。

?刪除所有的偶數：

我們發現，它出現了迭代器失效的問題：其理由就是上面所說迭代情況。

那么我們該怎么改正它呢？

?*******在使用前，對迭代器重新賦值即可******

區別差異：不同平臺下，處理迭代器失效的問題的方式會不同：

vs平臺下，它會出現直接強制檢查，因此只要有迭代器失效，統統報錯。

Linux的centos的g++編譯器下：它有時盡管出現了迭代器失效的問題，但是仍然可以跑的。只是輸出的結果不對而已！

??刪除所有的偶數：（Linux中）也是錯誤。

關于vector的基礎知識分享就到處結束了。

最后，到了我們本次雞湯環節：

下面文字與大家共勉！

?