1.介紹:C++ 標準模板庫(Standard Template Library,簡稱 STL)是一組泛型編程的模板類和函數,旨在提供常用的數據結構、算法和函數對象。STL 是 C++ 標準庫的一部分,極大地提高了編程效率和代碼的可重用性。STL 主要分為6個部分。
STL 的設計基于泛型編程的思想,通過使用模板,STL 提供了與類型無關的代碼,從而實現了代碼的高復用性和靈活性
---------------------------------------------------順序容器-----------------------------------------------------------
1.順序容器(Sequence Containers)是一類用于存儲和管理具有順序關系的元素的容器。這些容器允許在容器中的任意位置插入和刪除元素,并且可以通過迭代器訪問元素。C++ STL中的順序容器主要包括以下幾種
2.1. std::vector
2. std::deque (雙端隊列)
3. std::list (雙向鏈表)
4. std::forward_list (單向鏈表):
特性 :單向鏈表,支持在任何位置快速插入和刪除元素。優點 :在任何位置插入和刪除元素效率高(O(1)時間復雜度),內存占用較少。 |
缺點 :不支持隨機訪問,訪問元素需要從頭節點開始遍歷(O(n)時間復雜度)。不支持反向遍歷。
5. std::array (C++11引入):
特性 :固定大小的數組,大小在編譯時確定,不支持動態調整大小。
優點 :支持隨機訪問,訪問速度快(O(1)時間復雜度)。性能通常優于 std::vector ,因為不需要動態內存分配。
缺點 :大小固定,不能動態調整。
------------------------------------------------------順序容器--------------------------------------------------
一.順序容器:順序容器(Sequence Containers)是一類用于存儲和管理具有順序關系的元素的容器。這些容器允許在容器中的任意位置插入和刪除元素,并且可以通過迭代器訪問元素。C++ STL中的順序容器主要包括以下幾種:
1.std::vector(動態數組)
2.std::deque(雙端隊列)
3.std::list(雙向鏈表):
特性 :單向鏈表,支持在任何位置快速插入和刪除元素。優點 :在任何位置插入和刪除元素效率高(O(1)時間復雜度),內存占用較少。 |
缺點 :不支持隨機訪問,訪問元素需要從頭節點開始遍歷(O(n)時間復雜度)。不支持反向遍歷
學習網站:vector 類 | Microsoft Learn
二。VECTOR
補充:
雙端隊列:
3.list雙向鏈表
------------------------------------------------------容器適配器------------------------------------------------------------
1.introduce:
適配器(Adaptors)是標準庫中的一個通用概念, 容器、迭代器和函數都有適配器 。
C++中的 適配器是一種設計模式 , 用于將一個類或對象的接口轉換為另一個接口,以便不同的類或對象可以相互協作 。適配器模式可以分為類適配器和對象適配器兩種形式。
類適配器通過繼承源類并實現目標接口來實現適配。在類適配器中,適配器類同時繼承自源類和目標接口,并重
新實現目標接口的方法,以將源類的方法轉換為目標接口的方法。
對象適配器則通過在適配器類中包裝一個源對象來實現適配。在對象適配器中,適配器類持有一個源對象的引用,并實現目標接口的方法,在方法內部調用源對象的相應方法來完成適配。
標準庫定義了三個序列容器適配器: stack,queue,priority_queue
1.queue:是一個隊列 先進先出
queue不是標準的STL容器,卻以標準的STL容器為基礎。queue是在deque的基礎上封裝的
之所以選擇deque而不選擇vector是因為deque在刪除元素的時候釋放空間,同時在重新申請空間的時候無需拷貝所有元素
2.stack
stack是一個棧 , 實現先進后出功能 ,
stack不是標準的STL容器,卻以標準的STL容器為基礎。stack是在deque的基礎上封裝的。
3.priority_queue
優先級隊列:優先級大的先出隊,底層數據結構默認是大根堆(完全二叉樹)。
優先級隊列底層默認把數據組成一個大根堆結構 ,而大根堆的構建就需要在一個內存連續的數組上(堆中結點和它左右孩子的關系是通過下標計算的), vector動態數組底層是絕對連續的,而deque是分段連續的,所以用vector