前言

在 C++ 標(biāo)準(zhǔn)庫（STL）中，std::vector 和 std::list 都是最常用的序列容器，它們都支持 push_back、insert、erase、begin()/end() 等相似接口，看起來“用法差不多”。但如果只停留在接口層面，就很容易在性能瓶頸出現(xiàn)時(shí)踩坑。本篇文章將一步步幫你徹底搞清楚二者的本質(zhì)區(qū)別~~

一、底層數(shù)據(jù)結(jié)構(gòu)（這是理解一切差異的根源）

std::vector< T >：動態(tài)數(shù)組。
它在連續(xù)的一塊內(nèi)存上存儲元素，就像一個(gè)可以自動擴(kuò)容的普通數(shù)組。當(dāng)元素?cái)?shù)量超過當(dāng)前容量時(shí)，會向操作系統(tǒng)申請一塊更大的連續(xù)內(nèi)存，把舊元素搬過去（復(fù)制或移動），再釋放舊內(nèi)存。

std::list< T >：雙向鏈表。
每個(gè)元素都是一個(gè)獨(dú)立的節(jié)點(diǎn)，節(jié)點(diǎn)結(jié)構(gòu)大致為：

struct Node{
    T data；
    Node* prev；
    Node* next；
}；

節(jié)點(diǎn)之間通過指針鏈接，內(nèi)存完全不連續(xù)。list 內(nèi)部只維護(hù)頭尾指針（head 和 tail），無需連續(xù)內(nèi)存塊。

二、內(nèi)存布局與分配策略

1. vector：

• 元素連續(xù)存放，相鄰元素地址差正好是 sizeof(T)。
• 維護(hù)兩個(gè)關(guān)鍵值：size()（當(dāng)前元素個(gè)數(shù)）和 capacity()（已分配空間能容納的最大元素個(gè)數(shù)），始終滿足 size() ≤ capacity()。
• 擴(kuò)容策略（實(shí)現(xiàn)相關(guān)，通常是 1.5~2 倍增長）：當(dāng) size() == capacity() 時(shí)，重新分配更大內(nèi)存（典型 2 倍），并把所有元素移動過去。
• 緩存友好：CPU 讀取連續(xù)內(nèi)存時(shí)會自動預(yù)取，命中率極高。

2. list：

• 每個(gè)節(jié)點(diǎn)單獨(dú)向堆申請內(nèi)存（new Node），節(jié)點(diǎn)之間可能散布在堆的任意位置。
• 每個(gè)節(jié)點(diǎn)至少額外占用 2 個(gè)指針（64 位系統(tǒng) 16 字節(jié)），加上可能的內(nèi)存對齊開銷，內(nèi)存占用遠(yuǎn)大于 vector。
• 插入/刪除無需搬動其他節(jié)點(diǎn)，只需改 2~4 個(gè)指針即可。

vector 更“省內(nèi)存 + 快訪問”，list 更“靈活但浪費(fèi)空間”。

三、操作時(shí)間復(fù)雜度對比

記憶總結(jié)：
vector：隨機(jī)訪問快，中間修改慢。
list：任意位置修改快，隨機(jī)訪問慢。

四、迭代器有效性與類別

迭代器是 STL 容器的“指針”，修改容器后迭代器可能失效，這是很多Bug的源頭。

1.迭代器類別：

vector：隨機(jī)訪問迭代器，支持 it + n、it[n]、it < other 等。
list：雙向迭代器，僅支持 ++、–。

2.插入/刪除后的迭代器有效性

vector：
insert/erase：可能導(dǎo)致所有迭代器、指針、引用全部失效（因?yàn)榭赡苡|發(fā) reallocation）。
即使不 reallocation，后面的元素也會前移，指向后面元素的迭代器會“錯(cuò)位”。
#：reallocation 指的是動態(tài)數(shù)組的內(nèi)存重新分配。

list：
insert/erase：只有指向被刪除元素的迭代器失效，其他所有迭代器、指針、引用全部保持有效（這是鏈表的最大優(yōu)勢）。

所以在循環(huán)中邊遍歷邊刪除時(shí)，list 可以安全地 it = lst.erase(it);，vector 必須小心處理索引或使用 erase 返回的迭代器。

五、其他特性與成員函數(shù)差異

1. vector 獨(dú)有（動態(tài)數(shù)組特權(quán)）：

• reserve(n)：提前分配容量，避免反復(fù) reallocation。
• capacity()、shrink_to_fit()（C++11）。
• data()：返回底層數(shù)組指針，可直接傳給 C API。
• 支持 operator[]（不檢查越界）和 at()（拋異常）。

2. list 獨(dú)有（鏈表特權(quán)）：

• splice：O(1) 把另一個(gè) list 的子鏈“剪切”過來（無需復(fù)制元素）。
• merge、remove、remove_if、reverse、unique 等鏈表專用算法。
• sort()：使用穩(wěn)定的歸并排序（std::sort 無法用于 list）。

共同點(diǎn)：兩者都支持 emplace_back、emplace（C++11 原地構(gòu)造）、移動語義（高效轉(zhuǎn)移）。

六、內(nèi)存占用與緩存性能

假設(shè) sizeof(T) = 8 字節(jié)，存儲 10000 個(gè)元素：

vector：約 80KB + 少量元數(shù)據(jù)。
list：約 80KB（數(shù)據(jù)）+ 10000×16 字節(jié)（指針）≈ 240KB，3 倍內(nèi)存。

緩存命中率：

vector 在順序遍歷時(shí)幾乎 100% 命中 L1/L2 緩存。
list 每個(gè)節(jié)點(diǎn)跳轉(zhuǎn)可能導(dǎo)致緩存失效，性能差距可達(dá) 5~10 倍。

七、適用場景

1. 選擇 std::vector 的情況：

• 需要頻繁隨機(jī)訪問（下標(biāo)、排序、二分查找）。
• 主要在尾部 push/pop。
• 元素?cái)?shù)量較多，對內(nèi)存和緩存敏感。
• 需要與 C 語言 API 交互（data()）。
• 典型場景：游戲中的實(shí)體列表、日志緩沖、JSON 解析結(jié)果、科學(xué)計(jì)算數(shù)組等。

2.選擇 std::list 的情況：

• 極其頻繁地在任意位置插入/刪除（尤其鏈表中間）。
• 需要穩(wěn)定迭代器（刪除一個(gè)元素后，其他迭代器不能失效）。
• 元素本身很大，移動代價(jià)高（list 只改指針）。
• 典型場景：LRU 緩存的鏈表實(shí)現(xiàn)、音樂播放器的播放隊(duì)列（頻繁切歌）、多線程任務(wù)調(diào)度隊(duì)列（頻繁插入/移除任務(wù)）。

八、代碼示例

#include <vector>
#include <list>
#include <iostream>
using namespace std;
int main() 
{
    vector<int> v = {1,2,3,4,5};
    list<int> l = {1,2,3,4,5};
    // vector 中間插入（慢）
    v.insert(v.begin()+2,999);   // 1 2 999 3 4 5
    // list 中間插入（快 + 迭代器不失效）
    auto it = l.begin();
    advance(it,2);            // 指向第 3 個(gè)元素
    l.insert(it,999);              // 1 2 999 3 4 5
    // 此時(shí)原 it 仍指向原來的 3，不會失效
    cout<<"vector[2] ="<<v[2]<<endl;  // 999（O(1)）
    // list 不能寫 l[2]，必須遍歷
    return 0;
}

總結(jié)：
vector = 動態(tài)數(shù)組：連續(xù)內(nèi)存 -》 隨機(jī)訪問快、緩存友好、內(nèi)存省，但中間操作慢。
list = 雙向鏈表：指針鏈接 -》 任意位置修改快、迭代器穩(wěn)定，但隨機(jī)訪問慢、內(nèi)存占用高。

到此這篇關(guān)于C++ 中 std::vector 和 std::list 的區(qū)別的文章就介紹到這了,更多相關(guān)C++ std::vector 和 std::list 區(qū)別內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論