C++ STL 容器選擇指南：vector vs set/map 深度性能分析

前言：STL 容器選型的藝術

C++ 標準模板庫（STL）提供了豐富的容器，但「沒有最好的容器，只有最適合場景的容器」。本文針對遊戲開發、高性能計算等對效率敏感的領域，深度剖析 std::vector、std::set、std::map 的內存模型、操作複雜度、緩存友好性與隱藏開銷，幫助你做出基於數據而非直覺的選擇。

核心對比：vector vs set (以「唯一對象列表」為例)

場景：維護一組唯一對象，需支持插入、刪除、查找、遍歷。

關鍵洞見：為什麼 vector 常勝出？

1. 小 N 效應：實際場景 N 往往不大（幾十到幾百），O(N) 掃描因緩存優勢遠快於 O(log N) 樹操作。
2. 指針存儲消除拷貝：容器存指針而非對象，避免對象拷貝/構造/析構開銷，memmove 移動指針極其廉價。
3. 內存碎片與分配器壓力：set/map 大量小塊分配易造成堆碎片，分配器鎖在多線程下成瓶頸。vector 幾乎無此問題。
4. 遍歷頻次：遊戲主循環每幀遍歷實體列表，vector 線性遍歷效率碾壓樹遍歷。

set/map 的適用場景

• 數據量極大 (N > 10,000+) 且查找/插入/刪除極其頻繁、遍歷較少。
• 需要有序遍歷（map 按鍵序，set 按值序）且不想手動排序。
• 需要穩定迭代器（插入/刪除不失效非目標迭代器）。

vector 內存管理進階技巧

1. reserve() 預分配 — 避免擴容拷貝

std::vector entities;
entities.reserve(MAX_ENTITIES); // 一次性分配足夠空間，零擴容

2. swap() 技巧 — 徹底釋放內存

clear() 不保證釋放內存（capacity 不變），導致重啟遊戲時內存碎片。

// 釋放內存的標準惯用法
std::vector().swap(entities); 
// 原理：創建臨時空 vector，與 entities 交換內部指針，臨時對象析構時釋放原大塊內存

3. shrink_to_fit() (C++11)

entities.clear();
entities.shrink_to_fit(); // 請求釋放多餘容量 (非強制)

總結：決策清單

1. 默認選 vector（存指針）。
2. 需唯一性 → 插入前 std::find 檢查 (O(N))，N 小時極快。
3. 需頻繁查找/刪除且 N 大 → 考慮 set/unordered_set。
4. 需鍵值映射 → unordered_map (哈希表，O(1) 平均) 優於 map (紅黑樹)，除非需有序遍歷。
5. 關鍵路徑必實測：用 ChronoTimer (見前文) 對比真實數據下的吞吐量。

名言：「過早優化是萬惡之源，但選錯容器是性能災難的開端。」—— 理解容器底層機制，才能在設計階段做出正確抉擇。