常用數據結構

• 數組
• 棧
• 隊列
• 鏈表
• 樹
• 圖，最短路徑的查詢，
• 哈希表,把數據的存儲和查找消耗的時間大大降低，幾乎可以看成是常數時間；而代價僅僅是消耗比較多的內存。

C++中數據組織方式

• 數組，內置的數據類型，存放類型相同的對象的容器，數組的大小確定不變，不能隨意向數組中增加元素
  • 存放在棧中，其內存的分配和釋放完全由系統(tǒng)自動完成
• vector 封裝數組，連續(xù)內存，vector的大小可以變化，可以向數組中增加元素
  • 支持隨機訪問即[]或vector.at()
  • 存放在堆中，由STL庫中程序負責內存的分配和釋放，使用方便。
  • 執(zhí)行效率，數組>vector向量。主要原因是vector的擴容過程要消耗大量的時間
• list 封裝了雙向鏈表
  • 內部插入、刪除方便;不支持隨機訪問([]),單個元素內存相對占用內存大
• deque 雙向隊列，多個連續(xù)內存，功能上合并了vector和list。
  • 支持隨機訪問，內部插入刪除方便；占用內存大
  • 注：vector，高效的隨即存取，而不在乎插入和刪除的效率
    list，大量的插入和刪除，而不關心隨即存取
    deque，隨即存取，而且關心兩端數據的插入和刪除
• stack 基于deque實現，封裝棧
• queue 基于deque實現，封裝了隊列
• map 紅黑樹實現，提供key-value的存儲和查找功能
• set 平衡二叉樹實現，時間復雜度O(lgN);類似于集合，里面的元素不會重復，而且呈現為有序性
• multiset 平衡二叉樹實現，允許有重復元素
• hash_set 底層用hash table實現，時間復雜度取決于哈希函數和哈希負載情況;里面的元素不會重復。
• hash_map,基于hash table實現，提供key-value的存儲和查找功能