c++容器詳解

C++為我們提供了許多容器可以使用

C++中的容器定義為：

在資料存儲上，有一種對象類型，它可以持有其它對象或指向其它對像的指針，這種對象類型就叫做容器。

這些容器大體可以分為順序容器、關聯容器和容器擴充卡

也就是我們常用的

這裡隻說一下這些容器之間的關系和特點

具體的用法在别的部落格中會有詳細講解

關聯容器

關聯容器	特點
set	快速查找，元素有序，不允許有重複元素
multiset	快速查找，元素有序允許有重複元素
unordered_set	快速查找，元素無序，不允許有重複元素
unordered_multiset	快速查找，元素無序，允許有重複元素
map	映射，key-value型容器，元素有序，不允許有重複元素
multimap	映射，key-value型容器，元素有序，允許有重複元素
unordered_map	映射，key-value型容器，快速查找，元素無序，不允許有重複元素
unordered_multimap	映射，key-value型容器，快速查找，元素無序，允許有重複元素

上面給出的這些關聯容器都是非線性的樹結構，内部都是用紅黑樹這種二叉樹結構實作的。

set

字面意思集合，其作用也就是一個集合，裡面不允許有相同的元素，其内部是通過連結清單的方式來組織的，每個元素隻包含一個關鍵字。set是保證有序的，每次插入元素之後都會自動按升序排列。

multiset

顧名思義，可重集合，内部實作方式和相同，它允許内部的元素重複，同一個元素可以出現多次

unordered_set

無序集合，是一個存儲唯一進制素的關聯容器，容器中的元素無特别的秩序關系，該容器允許基于值的快速元素檢索，同時也支援正向疊代。其内部實作與不同，是用哈希表實作的。

unordered_multiset

和上面一樣的，隻是元素可以重複

順序容器

順序容器	特點
deque	可以在容器的開頭或結尾分别插入或删除元素
vector	在容器後方插入或删除元素，可通過下标直接通路
list	可以在任何地方插入或删除

deque

雙端隊列，可以在隊列的首尾進行操作，其内部實作更加複雜，支援對所有元素的随機通路，它的随機通路和周遊性能比差。它不像一樣有連續的存儲空間，而是多個連續的記憶體塊。應用舉例就是的優化。

vector

是一種線性順序結構，它的大小和所用記憶體是不定的，會在使用中自動配置設定。是一個類模闆，像才叫一種資料類型。它的存儲空間是連續的。

list

這個基本是用的最少的了，它是一個線性雙向連結清單結構。它的随機通路是要按順序查找，并不像一樣直接找到位址。記憶體空間和一樣不是連續的。

容器擴充卡	特點
stack	不允許随機通路棧元素，先進後出
queue	不允許随機通路隊列元素，先進先出
priority_queue	不允許随機通路隊列元素，優先級高的先出

stack

支援先進後出，是一個線性表，插入和删除隻在表的一端進行，它不提供元素的任何疊代器操作。由于它的的内部使用的是其他容器，是以它可看做是一種擴充卡，作用就是将一種容器轉換為另一種容器。它的模版需要定義兩個模版參數，一個是元素類型，一個是容器類型，元素類型是必要的，容器類型是可選的，預設為類型。

queue

priority_queue