【C++】Vector完全指南：動態數組高效使用

0. 官方文檔

vector

1. vector介紹

Vector 簡單來說就是順序表，是一個可以動態增長的數組。

vector是表示可變大小數組的序列容器。
就像數組一樣，vector也采用的連續存儲空間來存儲元素。也就是意味著可以采用下標對vector的元素進行訪問，和數組一樣高效。但是又不像數組，它的大小是可以動態改變的，而且它的大小會被容器自動處理。
本質講，vector使用動態分配數組來存儲它的元素。當新元素插入時候，這個數組需要被重新分配大小為了增加存儲空間。其做法是，分配一個新的數組，然后將全部元素移到這個數組。就時間而言，這是一個相對代價高的任務，因為每當一個新的元素加入到容器的時候，vector并不會每次都重新分配大小。
vector分配空間策略：vector會分配一些額外的空間以適應可能的增長，因為存儲空間比實際需要的存儲空間更大。不同的庫采用不同的策略權衡空間的使用和重新分配。但是無論如何，重新分配都應該是對數增長的間隔大小，以至于在末尾插入一個元素的時候是在常數時間的復雜度完成的。
因此，vector占用了更多的存儲空間，為了獲得管理存儲空間的能力，并且以一種有效的方式動態增長。
與其它動態序列容器相比（deque, list and forward_list）， vector在訪問元素的時候更加高效，在末尾添加和刪除元素相對高效。對于其它不在末尾的刪除和插入操作，效率更低。比起list和forward_list統一的迭代器和引用更好。

優點：

支持下標隨機訪問，間接的就很好的支持了排序、二分查找、堆算法等等

缺點：

頭部和中部的插入刪除效率低。O(N)，因為需要挪動數據。
插入數據空間不夠需要增容，增容需要開新空間，拷貝數據，釋放舊空間，會付出很大代價。

2. vector庫函數的使用

2.1 vector 的基本構造、拷貝與賦值操作

vector 的默認構造與元素添加

vector<int> v1;  // 創建一個空的整型vector
v1.push_back(1); // 在vector末尾添加元素1
v1.push_back(2); // 在vector末尾添加元素2
v1.push_back(3); // 在vector末尾添加元素3
v1.push_back(4); // 在vector末尾添加元素4

vector<int> v1 使用默認構造函數創建一個空的vector容器
push_back() 成員函數用于在vector的末尾添加新元素

vector 的拷貝構造

vector<int> v2(v1); // 使用v1作為源創建v2（拷貝構造）

拷貝構造函數 vector<int> v2(v1) 創建一個新vector，其元素是v1元素的完整拷貝
兩個vector對象完全獨立，修改一個不會影響另一個

vector 的遍歷與下標訪問

for (size_t i = 0; i < v1.size(); ++i)
{cout << v1[i] << " "; // 使用下標運算符[]訪問元素
}

size() 成員函數返回vector中元素的數量
可以使用下標運算符 [] 像數組一樣訪問vector中的元素

vector 的賦值操作

vector<int> v3;
v3.push_back(60);
v3.push_back(61);
v3.push_back(62);
v3.push_back(63);v1 = v3; // 將v3的內容賦值給v1

賦值操作 v1 = v3 會將v3的所有元素復制到v1中
賦值后v1的原始內容會被替換，大小會調整為與v3相同

2.2 vector 的遍歷與元素修改

使用下標遍歷和修改元素

for (size_t i = 0; i < v.size(); ++i)
{v[i] *= 2;        // 修改元素值cout << v[i] << " "; // 訪問元素值
}

使用下標遍歷是最直觀的方式，類似于操作普通數組
可以通過下標直接修改vector中的元素

使用迭代器遍歷和修改元素

vector<int>::iterator it = v.begin(); // 獲取指向第一個元素的迭代器
while (it != v.end())                 // 循環直到迭代器指向末尾
{*it *= 2;          // 解引用迭代器并修改元素值cout << *it << " "; // 訪問元素值++it;              // 移動迭代器到下一個元素
}

begin() 返回指向第一個元素的迭代器
end() 返回指向最后一個元素之后位置的迭代器
迭代器提供了類似指針的語法來訪問和修改元素

使用范圍for循環遍歷元素

for (auto e : v)
{cout << e << " "; // 訪問每個元素
}

范圍for循環是C++11引入的語法糖，代碼更簡潔
編譯器會自動將其轉換為迭代器操作
注意：這種方式默認是值拷貝，如果需要修改元素，應使用引用 for (auto& e : v)

2.3 vector 的迭代器類型

????????一般來說分為三大種：正向、反向、const

普通正向迭代器

vector<int>::iterator it = v.begin();
while (it != v.end())
{*it *= 2;        // 可讀寫操作cout << *it << " ";++it;
}

普通迭代器允許讀取和修改指向的元素
使用 iterator 類型定義，適用于需要修改vector內容的場景

const 正向迭代器

vector<int>::const_iterator it = vt.begin();
while (it != vt.end())
{// *it *= 2;     // 錯誤：不能修改const迭代器指向的值cout << *it << " "; // 只能讀取++it;
}

const迭代器指向的元素不能被修改
使用 const_iterator 類型定義，適用于只讀訪問場景

反向迭代器

vector<int>::reverse_iterator rit = v.rbegin();
while (rit != v.rend())
{cout << *rit << " "; // 從后向前遍歷++rit;               // 注意：++操作是向前移動
}

反向迭代器從容器的末尾向開頭遍歷
rbegin() 返回指向最后一個元素的迭代器
rend() 返回指向第一個元素之前位置的迭代器
++ 操作使迭代器向前移動（向容器開頭方向）

const 反向迭代器

vector<int>::const_reverse_iterator crit = v.rbegin();

結合了反向迭代和const特性的迭代器
可以反向遍歷容器，但不能修改元素值

函數參數中的const引用

void print_vector(const vector<int>& vt)
{vector<int>::const_iterator it = vt.begin();while (it != vt.end()){cout << *it << " ";++it;}cout << endl;
}

使用const引用傳參 const vector<int>& vt 避免不必要的拷貝
函數內部使用const迭代器確保不會意外修改原始數據
這是C++中常見的編程實踐，既能提高效率又能保證數據安全

const對象與const迭代器

const對象只能使用const迭代器進行遍歷
在實際工程中，const對象常用于函數參數，防止函數內部修改調用者的數據
使用const是正確的編程習慣，可以提高代碼的可讀性和安全性

2.4 容量相關

下面是一段擴容測試代碼，插入1000個數據，觀測容量空間變化：

void test_vector4()
{vector<int> v;cout << "making v grow:\n";size_t sz = v.size();for (int i = 0; i < 1000; ++i){v.push_back(i);if (sz != v.capacity()){sz = v.capacity();cout << "capacity changed: " << sz << '\n';}}
}

同樣的代碼，如下圖，左邊是linux環境下編譯運行出的結果，右邊是window的vs編譯的結果：

增容次數越少，效率越高，但可能導致的空間浪費越多。
增容次數越多，效率越低，但可能導致的空間浪費越少。

v.reserve(1000);        // 擴容
v.resize(1000);         // 擴大size，額外擴出來的部分會自動補'\0'或自定義字符

reserve只負責開辟空間，如果確定知道需要用多少空間，reserve可以緩解vector增容的代價缺陷問題。

resize在開空間的同時還會進行初始化，影響size。

2.5 修改與查找

尾部插入元素

vector<int> v;
// 尾插 - 使用 push_back() 在容器末尾添加元素
v.push_back(5);
v.push_back(4);
v.push_back(3);
v.push_back(2);
v.push_back(1);

push_back() 是 vector 最常用的添加元素方法
每次調用會在 vector 的末尾添加一個新元素
如果當前容量不足，vector 會自動重新分配更大的內存空間

指定位置插入元素

// 頭插 - 使用 insert() 在指定位置插入元素
v.insert(v.begin(), 0);     // 在開頭插入元素0
v.insert(v.end(), -1);    // 在結尾插入元素-1

insert() 方法可以在任意位置插入元素
第一個參數是迭代器，指定插入位置
第二個參數是要插入的值
在開頭插入元素會導致后續所有元素向后移動，效率較低

刪除指定位置元素

// 頭刪 - 使用 erase() 刪除指定位置的元素
v.erase(v.begin());  // 刪除第一個元素

erase() 方法刪除指定位置的元素
參數是一個迭代器，指向要刪除的元素
刪除元素后，后面的所有元素會向前移動
刪除開頭元素效率較低，因為需要移動所有后續元素

查找操作：使用標準庫的 find 算法

// vector 沒有提供內置的查找方法// 使用標準庫中的 find 算法
vector<int>::iterator pos = find(v.begin(), v.end(), 5);

vector 本身不提供查找方法，需要使用標準庫的 find 算法
find 需要包含 <algorithm> 頭文件
find 接受三個參數：起始迭代器、結束迭代器和要查找的值
查找范圍是左閉右開區間 [first, last)，即包含 first 但不包含 last

處理查找結果

if (pos != v.end())  // 檢查是否找到元素
{v.erase(pos);    // 如果找到，刪除該元素
}

find 返回一個迭代器，指向找到的元素
如果沒找到，返回結束迭代器 v.end()
在刪除前必須檢查是否找到元素，否則可能引發未定義行為

vector 的排序操作：使用標準庫的 sort 算法

// 使用標準庫的 sort 算法對 vector 排序
sort(v.begin(), v.end());  // 默認升序排序

sort 需要包含 <algorithm> 頭文件
默認情況下，sort 按升序排列元素
sort 使用快速排序算法實現，平均時間復雜度為 O(N log N)
排序范圍也是左閉右開區間 [first, last)

2.6 標準庫算法的說明

find 算法

// std::find 函數模板聲明（簡化）
template <class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T& value);

find 是一個函數模板，可用于任何支持迭代器的容器
它在 [first, last) 范圍內查找第一個等于 value 的元素
如果找到，返回指向該元素的迭代器；否則返回 last
使用 == 運算符進行比較，因此元素類型必須支持此操作

sort 算法

// std::sort 函數模板聲明（簡化）
template <class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);

sort 要求迭代器是隨機訪問迭代器，vector 的迭代器滿足此要求
默認使用 < 運算符進行比較，因此元素類型必須支持此操作
可以自定義比較函數來實現不同的排序規則

2.7 迭代器失效問題

1.增容導致的迭代器失效

看下面這段代碼：

void test_vector8()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);vector<int>::iterator it = v.begin();v.push_back(6);v.push_back(7);while (it != v.end()){cout << *it << " ";++it;}cout << endl;
}

如果我們把上面的代碼修改一下，把push_back(7)注釋掉，就可以運行：

????????這是為什么呢？這個問題和動態增容有關。

????????假設我們插入 7 之前的 v 有6個空間，即 v.capacity() 為6，當我們插入 7 后發生了增容，開辟了一塊新的空間，v 的內容全都被拷貝去了新的空間，然而此時 it 迭代器還指向舊空間的 v.begin() ，it 迭代器就失效了。

????????因此迭代器失效，實際就是迭代器底層對應指針所指向的空間被銷毀了，而使用一塊已經被釋放的空間，造成的后果是程序崩潰(即如果繼續使用已經失效的迭代器，程序可能會崩潰)。

????????所以 push_back 、insert 、resize 、reserve 等可能擴容的接口都會導致迭代器失效。

解決辦法（正確寫法）：

????????很簡單，不要在初始化迭代器后在調用可能導致擴容的接口就行了。

2.刪除導致的迭代器失效

void test_vector9()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);// 要求刪除容器中的所有偶數vector<int>::iterator it = v.begin();while (it != v.end()){if (*it % 2 == 0){v.erase(it);}++it;}for (auto e : v){cout << e << " ";}cout << endl;}

程序又崩潰了：

????????當 it 到 2 的位置時，會刪掉 2 ，然后后面的數據會往前挪，it++，此時 it 會直接略過 3 ，到 4 的位置。

????????也就是說，刪除 it 位置的元素后，it 就失效了，這里的失效是 it 迭代器已經失效了，再 ++it 就不行。這個問題在 vs 下會報錯，是編譯器強制檢查的，但是在 gcc 下就不報錯，但是結果不對，無法刪除掉連續的偶數（比如把3改成30就無法刪除30）。

????????編譯器檢查迭代器失效原因：erase刪除 it 位置元素后，it 位置之后的元素會往前搬移，沒有導致底層空間的改變，理論上講迭代器不應該會失效，但是：如果 it 剛好是最后一個元素，刪完之后 it 剛好是end的位置，而end位置是沒有元素的，那么 it 就失效了。因此刪除vector中任意位置上元素時，vs就認為該位置迭代器失效了。

????????總結：不管哪個平臺下，erase(it) 后，it 就失效了，只是導致的結果不一樣，總之都有各種各樣的問題。

????????作為編譯器檢查迭代器失效的印證，哪怕把代碼改成下面這樣也會報錯（vs 會報錯，linux 下正常運行）

解決辦法（正確寫法）：

????????通過官網對 erase 的返回值的介紹，我們可以知道，erase 的返回值是被刪除元素的下一個元素的位置。我們只需要改一下代碼就可以正常運行了：

void test_vector9()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);// 要求刪除容器中的所有偶數vector<int>::iterator 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;}