C++ STL及Python中等效實現


一. 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 列表支持更多動態類型(如混合存儲 intstr),但性能比 C++ vector 低。
      • Python 無需手動管理內存擴容,但底層仍類似 vector 的動態數組。

(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 更常用。
      • 元組不可變,適合常量數據。

(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

(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)
      
    • 競賽中較少用,因 vectordeque 更靈活。
  • Python 等效:無直接內置鏈表

    • Python 沒有內置雙向鏈表,list 是動態數組。
    • 可用 collections.deque 模擬鏈表操作,但性能不同。
    • 自定義鏈表:
      class ListNode:def __init__(self, val=0):self.val = valself.next = Noneself.prev = None
      
    • 差異:
      • Python 競賽中很少用鏈表,因 dequelist 足以應對大多數場景。

(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))。

(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 更高效。

(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 更簡潔,支持自定義比較器。

(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)。

(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 適合需要鍵有序的場景。

(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 的 setdict 就是哈希表實現。
    • 無需額外模塊,性能接近 C++ 的 unordered_ 容器。

三. STL 算法及 Python 對應

STL 提供了豐富的算法,頭文件為 #include <algorithm>。Python 的內置函數和模塊(如 itertoolsfunctools)提供了類似功能。

(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,性能優秀。

(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 模塊專為二分查找設計。

(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 快于 listunordered_set 快于 set)。
  • 邊界檢查:訪問 vector 前檢查 empty(),避免越界。
  • 自定義比較:優先隊列和 sort 的比較器要嚴格弱序(避免 a == b 時不一致)。
  • 內存管理:大數據量時用 reserveswap 清空容器。
  • 調試:用 cerr 輸出容器內容,便于調試。

Python

  • 性能:避免頻繁用 in 檢查列表( O ( n ) O(n) O(n)),改用 set O ( 1 ) O(1) O(1))。
  • 模塊:熟悉 collectionsdequeCounter)、heapqbisect
  • 簡潔性: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

    • 優點:高效(編譯期優化)、容器豐富(vectorsetmap 等)、算法強大(sortbinary_search)。
    • 缺點:語法復雜,需手動管理內存,調試稍麻煩。
    • 競賽推薦:vectorpriority_queuesetmapunordered_map
  • Python 等效

    • 優點:代碼簡潔,內置功能強大(listsetdict),模塊豐富(collectionsheapq)。
    • 缺點:運行時常數大,易超時,需優化輸入輸出。
    • 競賽推薦:listdequeheapqsetdict

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/pingmian/76584.shtml
繁體地址,請注明出處:http://hk.pswp.cn/pingmian/76584.shtml
英文地址,請注明出處:http://en.pswp.cn/pingmian/76584.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

python-63-前后端分離之圖書管理系統的Flask后端

文章目錄 1 flask后端1.1 數據庫實例extension.py1.2 數據模型models.py1.3 .flaskenv1.4 app.py1.5 運行1.6 測試鏈接2 關鍵函數和文件2.1 請求視圖類MethodView2.2 .flaskenv文件3 參考附錄基于flask形成了圖書管理系統的后端,同時對其中使用到的關鍵文件.flaskenv和函數類M…

藍橋杯真題——好數、R格式

目錄 藍橋杯2024年第十五屆省賽真題-好數 【模擬題】 題目描述 輸入格式 輸出格式 樣例輸入 樣例輸出 提示 代碼1&#xff1a;有兩個案例過不了&#xff0c;超時 藍橋杯2024年第十五屆省賽真題-R 格式 【vector容器的使用】 題目描述 輸入格式 輸出格式 樣例輸入…

Python中NumPy的索引和切片

在數據科學和科學計算領域&#xff0c;NumPy是一個功能強大且廣泛使用的Python庫。它提供了高效的多維數組對象以及豐富的數組操作函數&#xff0c;其中索引和切片是NumPy的核心功能之一。通過靈活運用索引和切片操作&#xff0c;我們可以輕松訪問和操作數組中的元素&#xff0…

設計模式:策略模式 - 消除復雜條件判斷的利器

一、什么是策略模式&#xff1f; 策略模式&#xff08;Strategy Pattern&#xff09;是一種行為型設計模式&#xff0c;它將一組算法或業務邏輯封裝為獨立的策略類&#xff0c;使這些策略可以互換使用&#xff0c;并通過上下文類動態選擇合適的策略。 核心思想 ? 將不同的行…

LeetCode hot 100—不同路徑

題目 一個機器人位于一個 m x n 網格的左上角 &#xff08;起始點在下圖中標記為 “Start” &#xff09;。 機器人每次只能向下或者向右移動一步。機器人試圖達到網格的右下角&#xff08;在下圖中標記為 “Finish” &#xff09;。 問總共有多少條不同的路徑&#xff1f; …

pytorch查詢字典、列表維度

輸出tensor變量維度 print(a.shape)輸出字典維度 for key, value in output_dict.items():if isinstance(value, torch.Tensor):print(f"{key} shape:", value.shape)輸出列表維度 def get_list_dimensions(lst):# 基線條件&#xff1a;如果lst不是列表&#xff0…

多坐標系變換全解析:從相機到WGS-84的空間坐標系詳解

多坐標系變換全解析:從相機到WGS-84的空間坐標系詳解 一、常見坐標系簡介二、各坐標系的功能和使用場景1. WGS-84 大地坐標系(經緯高)2. 地心直角坐標系(ECEF)3. 本地 ENU / NED 坐標系4. 平臺坐標系(Body)5. 相機坐標系三、坐標變換流程圖四、如何選用合適的坐標系?五…

【NumPy科學計算:高性能數組操作核心指南】

目錄 前言&#xff1a;技術背景與價值當前技術痛點解決方案概述目標讀者說明 一、技術原理剖析核心概念圖解關鍵技術模塊技術選型對比 二、實戰演示環境配置要求核心代碼實現運行結果驗證 三、性能對比測試方法論量化數據對比結果分析 四、最佳實踐推薦方案 ?常見錯誤 ?調試技…

【特權FPGA】之PS/2鍵盤解碼

0 故事背景 見過這種接口的朋友們&#xff0c;大概都已經成家立業了吧。不過今天我們不討論這種接口的歷史&#xff0c;只講講這種接口的設計。&#xff08;如果還沒有成家的朋友也別生氣&#xff0c;做自己想做的事情就對了&#xff01;&#xff09; 1 時序分析 數據幀格式如圖…

DAPP實戰篇:使用web3.js實現前端輸入錢包地址查詢該地址的USDT余額—操作篇

專欄:區塊鏈入門到放棄查看目錄-CSDN博客文章瀏覽閱讀396次。為了方便查看將本專欄的所有內容列出目錄,按照順序查看即可。后續也會在此規劃一下后續內容,因此如果遇到不能點擊的,代表還沒有更新。聲明:文中所出觀點大多數源于筆者多年開發經驗所總結,如果你想要知道區塊…

高中生學習數據隱私保護的“技術-制度-文化”協同機制研究

一、引言 1.1 研究背景與意義 在數字化時代的浪潮下&#xff0c;教育領域正經歷著深刻的變革&#xff0c;智能教育平臺如雨后春筍般涌現&#xff0c;為高中教育帶來了新的活力與機遇。這些平臺借助先進的信息技術&#xff0c;能夠實時收集、分析大量的高中生學習數據&#xf…

【Java多線程】告別線程混亂!深度解析Java多線程4大實現方式(附實戰案例)

一、繼承Thread類 實現步驟&#xff1a; 1.繼承Thread類 2.重寫run()方法 3.創建線程對象并調用start()方法 示例&#xff1a; class MyThread extends Thread {Overridepublic void run() {for (int i 0; i < 5; i) {System.out.println(Thread.currentThread().getNam…

全國產V7-690T核心板/算法驗證板/FPGA開發板

UD SOM-404全國產化信號處理模塊既可以作為核心板使用&#xff0c;也可以單獨使用。FPGA對外有80組GTY通過兩個FMC連接器全部引出&#xff0c;多個模塊可以級聯使用&#xff0c;擴展信號處理能力。FMC連接器也滿足標準規范&#xff0c;可以插入標準的FMC或FMC子板。模塊為100%國…

STM32_HAL庫提高中斷執行效率

目錄 中斷流程分析我的解決辦法優缺點 大家都在說STM32 HAL 庫中斷效率低下。具體哪里不行&#xff1f;如何優化&#xff1f; 我手里的項目要用到多個定時器TIM6、TIM7、TIM9、TIM10、TIM11、TIM12、TIM13&#xff0c;在處理這些定時器中斷的時候&#xff0c;也發現了這個問題。…

RabbitMQ惰性隊列的工作原理、消息持久化機制、同步刷盤的概念、延遲插件的使用方法

惰性隊列工作原理 惰性隊列通過盡可能多地將消息存儲到磁盤上來減少內存的使用。與傳統隊列相比&#xff0c;惰性隊列不會主動將消息加載到內存中&#xff0c;而是盡量讓消息停留在磁盤上&#xff0c;從而降低內存占用。盡管如此&#xff0c;它并不保證所有操作都是同步寫入磁…

Spark Core(二)

Spark-Core編程&#xff08;二&#xff09; RDD轉換算子 RDD 根據數據處理方式的不同將算子整體上分為 Value 類型、雙 Value 類型和 Key-Value 類型 Value類型 1&#xff09;map 將處理的數據逐條進行映射轉換&#xff0c;這里的轉換可以是類型的轉換&#xff0c;也可以是…

C#打開文件及目錄腳本

如果每天開始工作前都要做一些準備工作&#xff0c;比如打開文件或文件夾&#xff0c;我們可以使用代碼一鍵完成。 using System.Diagnostics; using System.IO;namespace OpenFile {internal class Program{static void Main(string[] args){Console.WriteLine("Hello, …

Python生成exe

其中的 -w 參數是 PyInstaller 用于窗口模式&#xff08;Windowed mode&#xff09;&#xff0c;它會關閉命令行窗口的輸出&#xff0c;這通常用于 圖形界面程序&#xff08;GUI&#xff09;&#xff0c;比如使用 PyQt6, Tkinter, PySide6 等。 所以&#xff1a; 如果你在沒有…

【大模型微調】如何解決llamaFactory微調效果與vllm部署效果不一致如何解決

以下個人沒整理太全 一、生成式語言模型的對話模板介紹 使用Qwen/Qwen1.5-0.5B-Chat訓練 對話模板不一樣。回答的內容就會不一樣。 我們可以看到例如qwen模型的tokenizer_config.json文件&#xff0c;就可以看到對話模板&#xff0c;一般同系列的模型&#xff0c;模板基本都…

Linux網絡編程——詳解網絡層IP協議、網段劃分、路由

目錄 一、前言 二、IP協議的認識 1、什么是IP協議&#xff1f; 2、IP協議報頭 三、網段劃分 1、初步認識IP與路由 2、IP地址 I、DHCP動態主機配置協議 3、IP地址的劃分 I、CIDR設計 II、子網數目的計算 III、子網掩碼的確定 四、特殊的IP地址 五、IP地址的數量限…