C++中l(wèi)ist的使用場景詳解
更新時間：2025年05月06日 08:32:00 作者：北辰alk
這篇文章主要介紹了C++標(biāo)準(zhǔn)庫中的`std::list`容器,包括其內(nèi)部結(jié)構(gòu)、與其它容器的對比、核心使用場景、性能分析、特殊應(yīng)用場景、使用陷阱與最佳實踐,需要的朋友可以參考下
一、list的基本特性與實現(xiàn)原理
1.1 list的內(nèi)部結(jié)構(gòu)
C++中的std::list是一個雙向鏈表實現(xiàn)的序列容器，其核心特點是非連續(xù)內(nèi)存存儲。每個元素（節(jié)點）包含三部分：
- 數(shù)據(jù)部分（存儲實際值）
- 前驅(qū)指針（指向前一個節(jié)點）
- 后繼指針（指向后一個節(jié)點）
template <class T>
struct __list_node {
__list_node* prev;
__list_node* next;
T data;
};
1.2 與其它序列容器的對比
| 特性 | list | vector | deque |
|---|---|---|---|
| 內(nèi)存布局 | 非連續(xù) | 連續(xù) | 分段連續(xù) |
| 隨機訪問 | O(n) | O(1) | O(1) |
| 頭部插入/刪除 | O(1) | O(n) | O(1) |
| 尾部插入/刪除 | O(1) | O(1) | O(1) |
| 中間插入/刪除 | O(1) | O(n) | O(n) |
| 迭代器失效 | 僅刪除元素失效 | 多數(shù)操作失效 | 部分操作失效 |
| 內(nèi)存開銷 | 較高(每個元素額外2指針) | 低 | 中等 |
二、list的核心使用場景
2.1 頻繁的任意位置插入/刪除操作
典型場景：
- 實時數(shù)據(jù)流處理（如交易訂單修改）
- 游戲?qū)ο蠊芾恚l繁增刪游戲?qū)嶓w）
- 文本編輯器中的緩沖區(qū)操作
// 高頻插入刪除示例 std::list<Order> order_book; // 插入新訂單（O(1)） auto it = order_book.begin(); std::advance(it, 100); // 定位到第100個位置 order_book.insert(it, new_order); // 刪除特定訂單（O(1)） order_book.erase(found_order);
2.2 需要穩(wěn)定迭代器的場景
典型場景：
- 長時間存在的元素引用
- 多數(shù)據(jù)結(jié)構(gòu)協(xié)同處理（如多個list間元素交換）
std::list<Player> game_players; auto player_it = game_players.begin(); // 即使在其他位置插入/刪除元素，原有迭代器仍然有效 game_players.push_back(Player()); // 不影響player_it game_players.pop_front(); // 不影響player_it // 除非刪除該迭代器指向的元素 player_it = game_players.erase(player_it); // 返回下一個有效迭代器
2.3 大對象存儲避免移動開銷
典型場景：
- 大型數(shù)據(jù)結(jié)構(gòu)（如矩陣、圖像塊）
- 復(fù)雜對象（多態(tài)對象、大型類實例）
class LargeObject {
char data[1024*1024]; // 1MB數(shù)據(jù)
// ...其他成員
};
std::list<LargeObject> big_data_store;
// 插入不會導(dǎo)致元素移動（vector會導(dǎo)致重新分配和拷貝）
big_data_store.push_back(LargeObject());
2.4 需要特殊操作的場景
list獨有的高效操作：
splice()：O(1)時間轉(zhuǎn)移元素到另一個listmerge()：O(n)時間合并兩個有序listsort()：鏈表專用排序算法
std::list<int> list1 = {1, 3, 5};
std::list<int> list2 = {2, 4, 6};
// 合并兩個有序list
list1.merge(list2); // list1變?yōu)閧1,2,3,4,5,6}, list2為空
// 轉(zhuǎn)移元素
std::list<int> list3 = {10, 20};
auto it = list1.begin();
std::advance(it, 2);
list1.splice(it, list3); // list1: {1,2,10,20,3,4,5,6}
三、性能分析與優(yōu)化
3.1 內(nèi)存訪問模式
緩存不友好問題：
// 連續(xù)訪問list元素（性能較差）
std::list<int> nums(1000000);
int sum = 0;
for (int n : nums) { // 每次訪問都可能cache miss
sum += n;
}
優(yōu)化方案：
- 對需要頻繁遍歷的數(shù)據(jù)考慮vector/deque
- 將相關(guān)數(shù)據(jù)打包存儲（提高局部性）
3.2 內(nèi)存使用效率
內(nèi)存開銷計算：
// 64位系統(tǒng)下
sizeof(std::list<int>::node) ==
sizeof(int) + 2*sizeof(void*) = 4 + 16 = 20字節(jié)（通常對齊到24字節(jié)）
// 存儲100萬個int：
vector內(nèi)存：~4MB
list內(nèi)存：~24MB
3.3 迭代器性能測試
#include <iostream>
#include <list>
#include <vector>
#include <chrono>
const int SIZE = 1000000;
void test_list_traversal() {
std::list<int> lst(SIZE, 1);
auto start = std::chrono::high_resolution_clock::now();
long sum = 0;
for (auto n : lst) sum += n;
auto end = std::chrono::high_resolution_clock::now();
std::cout << "list traversal: "
<< std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count()
<< "ms\n";
}
void test_vector_traversal() {
std::vector<int> vec(SIZE, 1);
auto start = std::chrono::high_resolution_clock::now();
long sum = 0;
for (auto n : vec) sum += n;
auto end = std::chrono::high_resolution_clock::now();
std::cout << "vector traversal: "
<< std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count()
<< "ms\n";
}
int main() {
test_list_traversal();
test_vector_traversal();
return 0;
}
典型輸出：
list traversal: 12ms vector traversal: 2ms
四、特殊應(yīng)用場景
4.1 LRU緩存實現(xiàn)
template <typename K, typename V>
class LRUCache {
std::list<std::pair<K, V>> items;
std::unordered_map<K, typename std::list<std::pair<K, V>>::iterator> key_map;
size_t capacity;
public:
LRUCache(size_t cap) : capacity(cap) {}
void put(const K& key, const V& value) {
auto it = key_map.find(key);
if (it != key_map.end()) {
items.erase(it->second);
key_map.erase(it);
}
items.push_front({key, value});
key_map[key] = items.begin();
if (items.size() > capacity) {
key_map.erase(items.back().first);
items.pop_back();
}
}
bool get(const K& key, V& value) {
auto it = key_map.find(key);
if (it == key_map.end()) return false;
items.splice(items.begin(), items, it->second);
value = it->second->second;
return true;
}
};
4.2 多級反饋隊列調(diào)度
class Process {
int pid;
int remaining_time;
// ...其他屬性
};
class Scheduler {
std::array<std::list<Process>, 5> queues; // 5個優(yōu)先級隊列
public:
void add_process(Process&& p, int priority) {
queues[priority].push_back(std::move(p));
}
void schedule() {
for (auto& queue : queues) {
if (!queue.empty()) {
auto& process = queue.front();
// 執(zhí)行一個時間片
process.remaining_time--;
if (process.remaining_time <= 0) {
queue.pop_front(); // 完成
} else if (&queue != &queues.back()) {
// 降級到下一優(yōu)先級
queues[&queue - &queues[0] + 1].splice(
queues[&queue - &queues[0] + 1].end(),
queue, queue.begin());
}
break;
}
}
}
};
五、使用陷阱與最佳實踐
5.1 常見陷阱
錯誤使用隨機訪問：
std::list<int> lst = {1, 2, 3};
// 錯誤：list不支持operator[]
// int x = lst[1];
// 正確做法
auto it = lst.begin();
std::advance(it, 1); // O(n)操作
int x = *it;
忽略內(nèi)存開銷：
// 存儲小型元素極不劃算 std::list<char> char_list; // 每個char消耗24+字節(jié)(64位系統(tǒng))
低效查找：
std::list<std::string> names; // O(n)查找 - 性能差 auto it = std::find(names.begin(), names.end(), "Alice");
5.2 最佳實踐
結(jié)合使用策略：
// 大型對象+頻繁插入刪除 std::list<Matrix> matrix_pool; // 小型對象+頻繁遍歷 std::vector<int> counters;
預(yù)分配節(jié)點（C++17起）：
std::list<ExpensiveObject> obj_list; obj_list.emplace_back(args...); // 直接構(gòu)造，避免拷貝/移動
使用自定義分配器：
template <typename T>
class PoolAllocator { /*...*/ };
std::list<int, PoolAllocator<int>> pooled_list;
替代方案考慮：
- 需要隨機訪問時考慮
std::deque - C++17的
std::pmr::list（多態(tài)內(nèi)存資源） - 侵入式鏈表（如Boost.Intrusive)
- 需要隨機訪問時考慮
六、總結(jié)與決策指南
6.1 何時選擇list
優(yōu)先使用list的情況：
- 需要頻繁在序列中間插入/刪除元素
- 需要長期穩(wěn)定的迭代器/指針/引用
- 存儲大型或不可拷貝/移動的對象
- 需要執(zhí)行
splice、merge等鏈表特有操作 - 內(nèi)存分配需要精細(xì)控制（結(jié)合自定義分配器）
避免使用list的情況：
- 需要頻繁隨機訪問元素
- 存儲小型基本類型（int、char等）
- 內(nèi)存資源極度受限
- 需要最佳緩存利用率
- 需要與C API交互（需要連續(xù)內(nèi)存）
6.2 現(xiàn)代C++的替代方案
forward_list（C++11）：
- 單向鏈表
- 更小內(nèi)存開銷（每個節(jié)點少一個指針）
- 缺少反向遍歷能力
pmr::list（C++17）：
#include <memory_resource>
std::pmr::list<int> pmr_list{std::pmr::monotonic_buffer_resource()};
Boost.Container：
- 提供更豐富的鏈表實現(xiàn)
- 如
boost::container::stable_vector
通過深入理解list的特性與適用場景，開發(fā)者可以更好地在適當(dāng)?shù)膱龊鲜褂眠@一經(jīng)典數(shù)據(jù)結(jié)構(gòu)，平衡性能需求與功能需求，編寫出更高效的C++代碼。
以上就是C++中l(wèi)ist的使用場景詳解的詳細(xì)內(nèi)容，更多關(guān)于C++ list使用場景的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
本篇文章是對使用OpenGL實現(xiàn)3D立體顯示的方法進行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
Qt動態(tài)庫調(diào)用宿主進程中的對象方法純虛函數(shù)使用
這篇文章主要為大家介紹了Qt動態(tài)庫調(diào)用宿主進程中的對象方法純虛函數(shù)使用，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-08-08
本文主要介紹了C++?雙冒號::符號詳解，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-03-03
C語言對組文件處理的相關(guān)函數(shù)小結(jié)
這篇文章主要介紹了C語言對組文件處理的相關(guān)函數(shù)小結(jié),包括setgrent()函數(shù)和getgrent()函數(shù)以及endgrent()函數(shù),需要的朋友可以參考下2015-08-08
這篇文章主要介紹了C++中const用于函數(shù)重載的相關(guān)資料,需要的朋友可以參考下2017-09-09
基于C++語言實現(xiàn)機動車違章處罰管理系統(tǒng)
這篇文章主要介紹了基于C++語言實現(xiàn)機動車違章處罰管理系統(tǒng)的相關(guān)資料,需要的朋友可以參考下2016-07-07
chrono是C++11中新加入的時間日期操作庫，可以方便地進行時間日期操作，本文詳細(xì)的介紹了一下如何使用，感興趣的可以了解一下2022-01-01
C語言內(nèi)存函數(shù) memcpy,memmove ,memcmp
這篇文章主要介紹了C語言內(nèi)存函數(shù) memcpy,memmove ,memcmp，文章圍繞主題展開詳細(xì)的內(nèi)容介紹，具有一定的參考價值，需要的小伙伴可以參考一下2022-09-09
在某些情況下我們希望函數(shù)的參數(shù)個數(shù)可以根據(jù)需要確定，因此c語言引入可變參數(shù)函數(shù)。典型的可變參數(shù)函數(shù)的例子有printf()、scanf()等,下面我就開始講解2021-08-08
這篇文章主要為大家詳細(xì)介紹了C++實現(xiàn)動態(tài)數(shù)組的方法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-06-06