C++ STL(2)

from my csdn blog

順序性容器

• 向量 vector

  • 動態(tài)數(shù)組幕垦，創(chuàng)建后會在內存中分配一段連續(xù)的內存空間甥桂。
  • 初始空間大小可以預先指定，當數(shù)據(jù)超過空間時會重新分配一塊內存，將原數(shù)據(jù)拷貝到新的內存塊中桶现，然后銷毀原內存塊中的對象（調用析構函數(shù)）彤敛，最后釋放原內存与帆。
  • 所以盡量不要導致重復申請內存，只有預先知道大小的情況下vector性能最優(yōu)墨榄，大多數(shù)情況下vector不是滿存的玄糟。
  • 注意：內部插入刪除效率非常低，頭部也不能插入刪除袄秩，最好創(chuàng)建時指定空間大小阵翎，只能在末尾進行push,pop。

• 雙向鏈表 list

  • 線性鏈表之剧，若干節(jié)點構成（信息塊+前驅后繼指針）郭卫，無需分配內存大小且可任意伸縮，存儲在非連續(xù)的內存空間中背稼。
  • 隨即檢索性能差贰军，目標元素越靠后，時間越長蟹肘。 < vector
  • 可迅速在任何節(jié)點進行插入刪除词疼，也可以在兩端進行push,pop。 >vector
  • 相對vector帘腹，內存占用更多贰盗。

• 雙端隊列 deque

  • 優(yōu)化的，對序列兩端元素進行添加刪除的序列容器阳欲，采用多個連續(xù)的存儲塊舵盈，并且在一個映射結構中保存對這些塊和順序的跟蹤陋率。
  • 較為快速的隨機訪問 < vector > list
  • 兩端添加元素開銷小，無需重新分配內存 > vector
  • 可以在內部進行插入和刪除秽晚，性能不如 list
  • 感覺這玩意挺不錯的瓦糟，在需求多情況下，如果不追求效率可以用

關聯(lián)容器

• set, multiset, map, multimap

  • 非線性結構赴蝇，使用一種高效特殊的平衡檢索二叉樹——紅黑樹（我學過AVL和splay）

• 集合 set

  • 一組元素的組合狸页，包含的元素值唯一，按一定順序排列
  • 內部通過鏈表的方式組織扯再，插入時比vector塊芍耘，查找和末尾添加比vector慢

• 多重集合 multiset

  • 與set不同是元素可以不唯一

• 字典 map

  • 提供 鍵-值 關系一對一的數(shù)據(jù)存儲，鍵不可重復熄阻，且按照一定順序排列斋竞，默認升序排列
  • multimap允許鍵不唯一

區(qū)別

• 關聯(lián)容器鏈式存儲，vector順序存儲秃殉，插入刪除操作更快坝初。但是比list要慢，list為線性結構钾军，而關聯(lián)容器每次插入刪選需要重新排序鳄袍。

• 關聯(lián)容器元素檢索比vector慢，比list快很多吏恭，當容器越大時拗小，相對于list的優(yōu)越性更加明顯。

• 在使用上set 區(qū)別于vector,deque,list 的最大特點就是set 是內部排序的樱哼，這在查詢上雖然遜色于vector 哀九，但是卻大大的強于list 。（有點不大懂）

• map的功能不可取代搅幅，其他容器無法做到阅束。

容器適配器

• 容器適配器

  • 棧stack
  • 隊列queue
  • 優(yōu)先隊列priority_queue

• 不懂的地方，粘過來的

  • 適配器是容器的接口茄唐，它本身不能直接保存元素息裸，它保存元素的機制是調用另一種順序容器去實現(xiàn)，即可以把適配器看作“它保存一個容器沪编，這個容器再保存所有元素”呼盆。
  • STL 中提供的三種適配器可以由某一種順序容器去實現(xiàn)。默認下stack 和queue 基于deque 容器實現(xiàn)漾抬，priority_queue 則基于vector 容器實現(xiàn)宿亡。
  • 當然在創(chuàng)建一個適配器時也可以指定具體的實現(xiàn)容器常遂，創(chuàng)建適配器時在第二個參數(shù)上指定具體的順序容器可以覆蓋適配器的默認實現(xiàn)纳令。
  • 由于適配器的特點，一個適配器不是可以由任一個順序容器都可以實現(xiàn)的。

• 注意事項

  • 棧stack 的特點是后進先出平绩，所以它關聯(lián)的基本容器可以是任意一種順序容器圈匆，因為這些容器類型結構都可以提供棧的操作有求，它們都提供了push_back,pop_back和back操作
  • 隊列queue 的特點是先進先出捏雌，適配器要求其關聯(lián)的基礎容器必須提供pop_front操作跃赚，因此其不能建立在vector容器上
  • 優(yōu)先級隊列priority_queue 適配器要求提供隨機訪問功能，因此不能建立在list容器上性湿。