一. STL 概述
STL 包含以下核心組件:
- 容器(Containers):存儲數據的結構,如數組、鏈表、集合等。
- 迭代器(Iterators):用于遍歷容器的接口,類似指針。
- 算法(Algorithms):通用的算法,如排序、查找、遍歷等。
- 函數對象(Functors):可調用的對象,用于自定義算法行為。
- 適配器(Adapters):修改容器或算法行為的工具。
- 分配器(Allocators):管理內存(競賽中很少自定義)。
競賽中最常用的是容器、迭代器和算法。
二. C++ STL 主要容器及 Python 對應
(1) vector(動態數組)
-
C++ vector:
- 動態大小的數組,支持隨機訪問,尾部增刪效率高。
- 頭文件:
#include <vector>
- 常用操作:
#include <vector> using namespace std; vector<int> v; // 聲明空向量 v.push_back(1); // 尾部添加元素 O(1) 均攤 v.pop_back(); // 尾部刪除 O(1) v.size(); // 返回大小 v[0]; // 隨機訪問 O(1) v.clear(); // 清空 v.insert(v.begin()+i, x); // 在第i位插入x O(n) v.erase(v.begin()+i); // 刪除第i位 O(n)
- 迭代器:
for (auto it = v.begin(); it != v.end(); ++it) {cout << *it << " "; } // 或用范圍for循環(C++11) for (int x : v) {cout << x << " "; }
- 競賽技巧:
- 初始化:
vector<int> v(n, 0);
創建大小為n,元素全為0的向量。 - 避免頻繁插入/刪除中間元素,復雜度為O(n)。
- 用
reserve(n)
預分配空間,減少擴容開銷。
- 初始化:
-
Python 等效:列表(
list
)- Python 的
list
是動態數組,功能與vector
類似。 - 常用操作:
v = [] # 空列表 v.append(1) # 尾部添加 O(1) 均攤 v.pop() # 尾部刪除 O(1) len(v) # 返回大小 v[0] # 隨機訪問 O(1) v.clear() # 清空 v.insert(i, x) # 在第i位插入x O(n) v.pop(i) # 刪除第i位 O(n)
- 遍歷:
for x in v:print(x) # 或用索引 for i in range(len(v)):print(v[i])
- 差異:
- Python 列表是內置類型,無需導入。
- Python 列表支持更多動態類型(如混合存儲
int
和str
),但性能比 C++vector
低。 - Python 無需手動管理內存擴容,但底層仍類似
vector
的動態數組。
- Python 的
(2) array(固定大小數組,C++11)
-
C++ array:
- 固定大小的數組,替代原生數組,接口更安全。
- 頭文件:
#include <array>
- 常用操作:
#include <array> array<int, 5> arr = {1, 2, 3, 4, 5}; // 固定大小5 arr[0]; // 隨機訪問 O(1) arr.size(); // 返回大小 arr.fill(0); // 填充為0
- 競賽中較少用,因
vector
更靈活。
-
Python 等效:
array.array
或元組(tuple
)array.array
:固定類型的數組,效率高于list
。from array import array arr = array('i', [1, 2, 3]) # 'i'表示整數 arr[0] # 訪問 len(arr) # 大小
- 元組:不可變,類似固定數組。
t = (1, 2, 3) t[0] # 訪問 O(1)
- 差異:
- Python 的
array.array
使用場景較窄,list
更常用。 - 元組不可變,適合常量數據。
- Python 的
(3) deque(雙端隊列)
-
C++ deque:
- 支持兩端高效增刪,隨機訪問。
- 頭文件:
#include <deque>
- 常用操作:
#include <deque> deque<int> dq; dq.push_back(1); // 尾部添加 O(1) dq.push_front(0); // 頭部添加 O(1) dq.pop_back(); // 尾部刪除 O(1) dq.pop_front(); // 頭部刪除 O(1) dq[0]; // 隨機訪問 O(1)
- 競賽場景:需要雙端操作(如滑動窗口)。
-
Python 等效:
collections.deque
- 專為雙端操作設計,性能優于
list
。 - 常用操作:
from collections import deque dq = deque() dq.append(1) # 尾部添加 O(1) dq.appendleft(0) # 頭部添加 O(1) dq.pop() # 尾部刪除 O(1) dq.popleft() # 頭部刪除 O(1) dq[0] # 隨機訪問 O(1)
- 差異:
- Python 的
deque
是算法競賽神器,尤其在需要高效雙端操作時。 - C++
deque
內存不連續,隨機訪問略慢于vector
。
- Python 的
- 專為雙端操作設計,性能優于
(4) list(雙向鏈表)
-
C++ list:
- 雙向鏈表,支持高效插入/刪除,但無隨機訪問。
- 頭文件:
#include <list>
- 常用操作:
#include <list> list<int> lst; lst.push_back(1); // 尾部添加 O(1) lst.push_front(0); // 頭部添加 O(1) lst.insert(++lst.begin(), 2); // 插入 O(1) lst.erase(lst.begin()); // 刪除 O(1)
- 競賽中較少用,因
vector
或deque
更靈活。
-
Python 等效:無直接內置鏈表
- Python 沒有內置雙向鏈表,
list
是動態數組。 - 可用
collections.deque
模擬鏈表操作,但性能不同。 - 自定義鏈表:
class ListNode:def __init__(self, val=0):self.val = valself.next = Noneself.prev = None
- 差異:
- Python 競賽中很少用鏈表,因
deque
和list
足以應對大多數場景。
- Python 競賽中很少用鏈表,因
- Python 沒有內置雙向鏈表,
(5) stack(棧)
-
C++ stack:
- 后進先出(LIFO)。
- 頭文件:
#include <stack>
- 常用操作:
#include <stack> stack<int> s; s.push(1); // 入棧 O(1) s.top(); // 訪問棧頂 O(1) s.pop(); // 出棧 O(1) s.empty(); // 是否為空
- 競賽場景:括號匹配、單調棧。
-
Python 等效:列表(
list
)模擬棧- 無內置棧,用
list
實現:s = [] s.append(1) # 入棧 O(1) s[-1] # 訪問棧頂 O(1) s.pop() # 出棧 O(1) not s # 是否為空
- 差異:
- Python 無專用棧類型,
list
足夠高效。 - 注意不要用
list
頭部操作模擬棧(insert(0)
是 O ( n ) O(n) O(n))。
- Python 無專用棧類型,
- 無內置棧,用
(6) queue(隊列)
-
C++ queue:
- 先進先出(FIFO)。
- 頭文件:
#include <queue>
- 常用操作:
#include <queue> queue<int> q; q.push(1); // 入隊 O(1) q.front(); // 訪問隊首 O(1) q.pop(); // 出隊 O(1) q.empty(); // 是否為空
- 競賽場景:BFS。
-
Python 等效:
collections.deque
- 用
deque
實現隊列:from collections import deque q = deque() q.append(1) # 入隊 O(1) q[0] # 訪問隊首 O(1) q.popleft() # 出隊 O(1) not q # 是否為空
- 差異:
- Python 的
queue.Queue
適用于多線程,競賽中用deque
更高效。
- Python 的
- 用
(7) priority_queue(優先隊列/堆)
-
C++ priority_queue:
- 默認大頂堆(最大值優先)。
- 頭文件:
#include <queue>
- 常用操作:
#include <queue> priority_queue<int> pq; // 大頂堆 priority_queue<int, vector<int>, greater<int>> pq_min; // 小頂堆 pq.push(1); // 插入 O(log n) pq.top(); // 訪問堆頂 O(1) pq.pop(); // 刪除堆頂 O(log n)
- 競賽場景:貪心、Dijkstra、最小/最大k個數。
-
Python 等效:
heapq
- 默認小頂堆。
- 常用操作:
import heapq pq = [] heapq.heappush(pq, 1) # 插入 O(log n) pq[0] # 訪問堆頂 O(1) heapq.heappop(pq) # 刪除堆頂 O(log n) # 大頂堆:存負值 pq_max = [] heapq.heappush(pq_max, -1) -pq_max[0] # 最大值
- 差異:
- Python 的
heapq
是函數接口,需用列表存儲堆。 - C++ 的
priority_queue
更簡潔,支持自定義比較器。
- Python 的
(8) set(集合)
-
C++ set:
- 有序集合(默認升序),元素唯一,基于紅黑樹。
- 頭文件:
#include <set>
- 常用操作:
#include <set> set<int> s; s.insert(1); // 插入 O(log n) s.erase(1); // 刪除 O(log n) s.count(1); // 查找是否存在 O(log n) s.lower_bound(x); // 第一個>=x的迭代器
multiset
:允許重復元素。- 競賽場景:去重、查找、區間查詢。
-
Python 等效:
set
- 無序集合,基于哈希表。
- 常用操作:
s = set() s.add(1) # 插入 O(1) 平均 s.remove(1) # 刪除 O(1) 平均 1 in s # 查找 O(1) 平均
- 有序集合:
sortedcontainers.SortedSet
(需安裝)。 - 差異:
- Python
set
是哈希表,查找更快,但無序。 - C++
set
是紅黑樹,支持有序操作(如lower_bound
)。
- Python
(9) map(映射/字典)
-
C++ map:
- 有序鍵值對,鍵唯一,基于紅黑樹。
- 頭文件:
#include <map>
- 常用操作:
#include <map> map<string, int> m; m["key"] = 1; // 插入/更新 O(log n) m.erase("key"); // 刪除 O(log n) m["key"]; // 訪問 O(log n) m.count("key"); // 查找鍵是否存在
multimap
:允許重復鍵。
-
Python 等效:字典(
dict
)- 基于哈希表。
- 常用操作:
m = {} m["key"] = 1 # 插入/更新 O(1) 平均 m.pop("key") # 刪除 O(1) 平均 m["key"] # 訪問 O(1) 平均 "key" in m # 查找 O(1) 平均
- 有序字典:
collections.OrderedDict
(Python 3.7+dict
默認有序)。 - 差異:
- Python
dict
更快,但無紅黑樹支持的有序操作。 - C++
map
適合需要鍵有序的場景。
- Python
(10) unordered_set/unordered_map(哈希集合/哈希表)
-
C++ unordered_set/unordered_map:
- 無序,基于哈希表,查找/插入平均 O ( 1 ) O(1) O(1)。
- 頭文件:
#include <unordered_set>
、#include <unordered_map>
- 操作類似
set
/map
,但更快且無序。 - 競賽場景:需要極快查找/去重。
-
Python 等效:
set
/dict
- Python 的
set
和dict
就是哈希表實現。 - 無需額外模塊,性能接近 C++ 的
unordered_
容器。
- Python 的
三. STL 算法及 Python 對應
STL 提供了豐富的算法,頭文件為 #include <algorithm>
。Python 的內置函數和模塊(如 itertools
、functools
)提供了類似功能。
(1) 排序
-
C++:
#include <algorithm> vector<int> v = {3, 1, 4}; sort(v.begin(), v.end()); // 升序 sort(v.begin(), v.end(), greater<int>()); // 降序 // 自定義比較 sort(v.begin(), v.end(), [](int a, int b) { return a > b; });
- 復雜度: O ( n l o g n ) O(n log n) O(nlogn)。
-
Python:
v = [3, 1, 4] v.sort() # 升序 v.sort(reverse=True) # 降序 # 自定義比較 v.sort(key=lambda x: -x) # 或用 sorted() 返回新列表 sorted_v = sorted(v)
- Python 的
sort
是 Timsort,性能優秀。
- Python 的
(2) 二分查找
-
C++:
vector<int> v = {1, 2, 3, 4}; // 要求 v 已排序 binary_search(v.begin(), v.end(), 3); // 是否存在 lower_bound(v.begin(), v.end(), 3); // 第一個>=3 upper_bound(v.begin(), v.end(), 3); // 第一個>3
- 復雜度: O ( l o g n ) O(log n) O(logn)。
-
Python:
from bisect import bisect_left, bisect_right v = [1, 2, 3, 4] 3 in v # 是否存在 O(n),競賽慎用 bisect_left(v, 3) # 第一個>=3 bisect_right(v, 3) # 第一個>3
- Python 的
bisect
模塊專為二分查找設計。
- Python 的
(3) 最大/最小值
-
C++:
vector<int> v = {3, 1, 4}; *max_element(v.begin(), v.end()); // 最大值 *min_element(v.begin(), v.end()); // 最小值
-
Python:
v = [3, 1, 4] max(v) # 最大值 min(v) # 最小值
(4) 其他算法
- C++:
reverse(v.begin(), v.end())
:反轉。unique(v.begin(), v.end())
:去重(需先排序)。next_permutation(v.begin(), v.end())
:下一個排列。
- Python:
v.reverse()
或v[::-1]
:反轉。list(set(v))
:去重(無序)。itertools.permutations
:生成排列。
四. 競賽中的注意事項
C++ STL
- 性能:選擇合適的容器(如
vector
快于list
,unordered_set
快于set
)。 - 邊界檢查:訪問
vector
前檢查empty()
,避免越界。 - 自定義比較:優先隊列和
sort
的比較器要嚴格弱序(避免a == b
時不一致)。 - 內存管理:大數據量時用
reserve
或swap
清空容器。 - 調試:用
cerr
輸出容器內容,便于調試。
Python
- 性能:避免頻繁用
in
檢查列表( O ( n ) O(n) O(n)),改用set
( O ( 1 ) O(1) O(1))。 - 模塊:熟悉
collections
(deque
、Counter
)、heapq
、bisect
。 - 簡潔性:Python 代碼短,但運行時常數大,注意 TLE(超時)。
- 輸入輸出:用
sys.stdin.readline
加速大輸入。
五. 示例:解決一個競賽問題
問題:給定一個數組,找出所有和為目標值的子數組(不要求連續)。
-
C++ 解法(用
map
記錄前綴和):#include <iostream> #include <vector> #include <map> using namespace std; long long countSubarrays(vector<int>& nums, int target) {map<long long, int> prefixSum;prefixSum[0] = 1;long long sum = 0, count = 0;for (int num : nums) {sum += num;count += prefixSum[sum - target];prefixSum[sum]++;}return count; } int main() {vector<int> nums = {1, 2, 3, -3, 3};cout << countSubarrays(nums, 3) << endl; // 輸出 4return 0; }
-
Python 解法(用
dict
):from collections import defaultdict def count_subarrays(nums, target):prefix_sum = defaultdict(int)prefix_sum[0] = 1sum_ = 0count = 0for num in nums:sum_ += numcount += prefix_sum[sum_ - target]prefix_sum[sum_] += 1return count nums = [1, 2, 3, -3, 3] print(count_subarrays(nums, 3)) # 輸出 4
分析:
- C++ 用
map
記錄前綴和,鍵有序但稍慢。 - Python 用
defaultdict
(哈希表),更快且代碼更簡潔。 - 兩者邏輯相同,Python 寫法更直觀,C++ 運行效率更高。
六. 總結
-
C++ STL:
- 優點:高效(編譯期優化)、容器豐富(
vector
、set
、map
等)、算法強大(sort
、binary_search
)。 - 缺點:語法復雜,需手動管理內存,調試稍麻煩。
- 競賽推薦:
vector
、priority_queue
、set
、map
、unordered_map
。
- 優點:高效(編譯期優化)、容器豐富(
-
Python 等效:
- 優點:代碼簡潔,內置功能強大(
list
、set
、dict
),模塊豐富(collections
、heapq
)。 - 缺點:運行時常數大,易超時,需優化輸入輸出。
- 競賽推薦:
list
、deque
、heapq
、set
、dict
。
- 優點:代碼簡潔,內置功能強大(