（1）vector具有自動擴展操作，每次擴展都伴隨著“配置新空間/移動舊數據/釋放舊空間”的操作，因此具有壹定的時間成本。？
（2）vector提供預留接口。如果妳能對元素的數量有壹個大致的了解，妳就可以從壹開始就分配適當的空間。？
（3）向量的存儲空間是連續的。對於插入元素的操作，在向量的末尾插入是合適的選擇。保持連續的線性空間，因此vector支持隨機訪問。？
（4）當4）向量動態增加其大小時，它不會在原始空間後保留壹個新空間（不能保證原始空間後仍有配置空間），而是分配壹個兩倍於原始大小的更大空間，然後復制原始內容，然後在原始內容後開始構造新元素，並釋放原始空間。因此，壹旦對向量的任何操作導致空間重新配置，所有指向原始向量的叠代器都將失敗。
2、向量和數組的區別
向量與數組非常相似。兩者之間的唯壹區別是空間使用的靈活性。數組是壹個靜態空間，壹旦配置就無法更改。向量是壹個動態空間。隨著元素的增加，其內部機制將擴展空間以容納新元素。因此，向量的使用對記憶的合理使用和靈活性有很大幫助。
采用的數據結構很簡單:線性連續空間。為了降低空間配置的速度成本，vector的實際配置大小可能會大於客戶端對未來可能擴展的需求，這就是容量的概念。添加新元素時，如果容量不足，則將其擴展到2倍（如果原始大小為0，則將其配置為1），如果2倍的容量仍然不足，則將其擴展到足夠大的容量。
2 .列表功能
（1）與向量的連續線性空間相比，列表要復雜得多。？
（2）它的優點是每次插入或刪除元素時，都會配置或釋放壹個元素空間。因此，list在空間使用方面絕對準確，而且壹點也不浪費。？
（3）對於任何位置的元素插入或元素移除，list始終是壹個常數時間。？
（4）list不僅是雙向鏈表，而且是循環雙向鏈表。它只需要壹個指針就可以完整地表示整個鏈表。？
（5）插入操作和連接操作都不會導致原始列表叠代器失敗，這在vector中不成立。因為vector的插入可能會導致內存重新配置，從而導致所有原始叠代器失敗。即使是列表的元素刪除操作（erase），也只有“指向被刪除元素”的叠代器無效，其他叠代器不受影響。？
（6）list不能再像vector那樣使用普通指針作為叠代器，因為它的節點在存儲空間中不能保證連續。List提供雙向叠代器。
slist
slist和list的區別:
（1）STL列表是雙向鏈表，而slist是單向鏈表。？
（2）STL list的叠代器是雙向的雙向叠代器，而slist的叠代器是單向的正向叠代器。？
（3）單向鏈表占用空間少，某些操作速度更快。？
（4）它們有壹個共同的特點:insert、erase和splice等操作不會導致原油叠代器失敗。在移除操作之後，指向被移除元素的叠代器肯定會失敗。？
（5）由於單鏈表只能向前叠代，因此沒有提供許多操作，即使提供了操作，也是非常低效的操作，需要從開始節點開始遍歷。
在除了slist開頭附近的區域之外的其他位置使用insert或erase操作函數是不明智的，這是slist與list相比的壹大缺點。？
（6）slist叠代器是單向正向叠代器，所以除了叠代器的基本操作外，只實現了operator++操作。
雙端隊列
1、deque和vector之間的差異
（1）vector是壹個單向打開的連續線性空間，用戶只能在vector的末尾插入和刪除（也允許在pos處插入，但由於vector的底層實現是數組，因此過多的非隊列末尾位置會有性能消耗）。Deque是壹個具有雙向開口的連續線性空間，它允許在頭尾兩端插入和刪除。
（2）deque允許在恒定的時間內插入或刪除頭部中的元素。
（3）德克沒有容量的概念。它由分段連續的空間動態組成，並且可以隨時添加和連接新的空間。不需要提供所謂的空間預留功能。
（4）deque最大的任務是在這些片段的定量連續空間中保持整體連續的假象，並提供隨機訪問接口。它以復雜的叠代器架構為代價，避免了“重新配置、復制和發布”的循環。
（5）作為壹個分段連續的線性空間，必須有中心控制，並且為了保持整體連續的假象，數據結構的設計和叠代器向前向後的操作都相當復雜。Deque的實現代碼組件比vector或list的要多得多。因此，我們應該盡可能選擇vector而不是deque。
2.德克的中央控制器
Deque使用壹個所謂的map（註意它不是STL的map容器）作為主控。這裏所謂的地圖是壹個小的連續空間，其中每個元素（這裏稱為節點）都是壹個指針，指向另壹個（更大的）連續線性空間，稱為緩沖區。緩沖區是deque的主要存儲空間。SGI STL允許我們指定緩沖區的大小。默認值0表示將使用512字節的緩沖區。
總結:
（1）map是塊連續空間，其中每個元素都是指向緩沖區的指針。？
（2）進壹步發現map實際上是壹個T**，也就是說它是壹個指針，它所指的東西也是壹個指針，指向壹個T類型的空間。
3.德克的叠代器
德克是壹個分段連續的空間。保持“整體連續性”假象的任務落在了叠代器的兩個運算符上:operator++和operator-。
deque的叠代器應該有什麽結構:？
（1）它必須能夠指示分段連續空間（即緩沖區）的位置。
（2）它必須能夠判斷它是否處於其緩沖區的邊緣，如果是，那麽壹旦它向前或向後移動，它必須跳到下壹個或前壹個緩沖區。為了正確跳躍，德克必須隨時掌握控制中心（地圖）。
因此需要在叠代器中定義:當前元素的指針、當前元素所在緩沖區的起始指針、當前元素所在緩沖區的尾指針以及指向map中緩沖區地址的指針。
Deque的效率不如vector高，因此有時在對deque進行排序時，需要先將元素移動到vector中，然後對其進行排序，最後再移回。
4.deque的構造和內存管理
由於deque的設計思想是通過緩存塊來連接的，因此其內存管理將更加復雜。插入時，我們要考慮是否跳轉到緩存中，是否創建新的地圖節點（與vector壹樣，實際上是將壹個空間重新分配給地圖並刪除原始空間），以及插入的元素是向前移動還是向後移動（誰移動的小）。刪除元素時，考慮是向後移動前壹個元素以覆蓋需要刪除元素的位置，還是向前移動後壹個元素以覆蓋它（無論誰移動得小）。移動後，應該析構冗余元素並釋放冗余緩沖區。
4 .堆棧
棧是壹種先進後出的數據結構，只有壹個出口。允許添加元素，刪除元素和獲取最上面的元素。不允許遍歷行為。
SGI STL的源代碼
堆棧不提供訪問函數或叠代器。
5 .排隊
隊列是壹種先進先出的數據結構。有兩個出口允許您添加、刪除、從底部添加和獲取頂部元素。不允許遍歷行為。
Deque是雙向隊列，而queue是單向隊列。
Deque是壹種雙向開放的數據結構。如果使用deque作為底部結構，並且其底部出口和前部入口關閉，則可以很容易地形成隊列。因此，SGI STL默認將deque作為隊列的底層結構。
隊列不提供遍歷函數或叠代器。
地圖和多地圖
地圖的特點:？
（1）所有元素都根據鍵值自動排序。？
（2）2）映射的所有元素都是成對的，第壹個值是鍵值，第二個是實值。？
（3）map不允許兩個元素具有相同的鍵值。？
（4）可以通過map的叠代器改變元素的實值，但不能改變鍵值，這樣會違反元素的排列規則。？
（5）客戶端插入或刪除映射後，之前的叠代器仍然有效。當然，刪除元素的叠代器是個例外。？
它的底層機制是r B-樹。幾乎所有的操作都只是調用RB-tree的操作行為。
Multimap和map幾乎相同，唯壹的區別是multimap允許重復的鍵值。因此，映射使用底層RB樹的insert_unique（）來實現插入，而多映射插入使用RB樹的insert_equal（）而不是insert_unique（）。
散列表
1和哈希表概述
哈希表可以訪問和刪除任何著名的項目。這種結構的目的是提供時間恒定的基本操作，它不依賴於插入元素的隨機性，而是基於統計數據。
哈希函數:負責將元素映射到“具有可接受大小的索引”。簡而言之，就是把大數映射成小數。
使用哈希函數導致的問題:可能有不同的元素映射到同壹位置（同壹索引）。這就是碰撞或沖突的問題。解決沖突問題的方法:線性探測、二次探測、分離鏈接等。stl哈希表采用的哈希方法是開鏈方法。
（1）線性檢測:當哈希函數計算元素的插入位置時，位置空間不再可用，該怎麽辦？最簡單的方法是按順序壹個壹個往下看，直到找到壹個可用的空間。
需要兩個假設:a .表足夠大。b .每個元素都可以是獨立的。
線性檢測會造成初級聚類的問題:平均插入成本的增長率遠高於負載因子的增長率。
（2）二次檢測:主要用於解決主群問題。求解碰撞的方程是f（I）= I ^ 2。如果哈希函數計算出新元素的位置是H，並且該位置實際上已被使用，則嘗試H+1 2，H+2 2，H+3 2，H+4 2，...，H+I ^ 2依次進行，不像H+1的線性檢測嘗試。
二次檢測可以消除主聚類，但可能會導致二次聚類:如果哈希函數計算的兩個元素的位置相同，則插入時檢測到的位置也相同，從而導致壹些浪費。消除子組的方法，如雙重哈希。
（3）開放鏈:這種做法是在每個表元素中維護壹個列表。散列函數給我們分配壹個列表，然後我們在該列表上執行插入、搜索和刪除元素等操作。如果列表足夠短，速度仍然足夠快。
使用開鏈方法，表的加載因子將大於1。SGI STL哈希表采用了開放鏈方法。
關於c++的更多信息，歡迎訪問我的博客:網絡鏈接。