1. 容器

在C++的stl中，容器分為序列式容器和關聯式容器。

對于序列式容器而言，容器的邏輯結構是線性的，相鄰兩個位置的數據之間，沒有較為緊密的聯系，因此通常是可以交換的。對于這類容器的數據訪問，一般都是通過數據存儲的位置進行訪問，最典型的例子，如vector

對于關聯式容器，容器的邏輯結構是非線性的，相鄰兩個位置的數據之間，是有緊密的聯系，通常是不可以交換的，一旦交換，便會破壞整個容器的結構。像map和set,就是關聯式容器的代表，這類容器中數據的訪問，一般都是借助于key，即鍵值來進行訪問的。

2. set和multiset

2.1 set

set的底層是不支持鍵值冗余的二叉搜索樹，存儲的是key，而非key-value。
以下，我們介紹使用set容器時，幾個非常重要的接口。

2.1.1 構造函數

set的構造函數，有三個是比較重要的。

一個是默認構造。

默認構造中，關于內存池的形參一般不用在意，除非有別的內存池可以供你調用。
set中的仿函數需要注意，默認的仿函數進行的是小于的比較，因此，默認對整個set容器的遍歷，是依據鍵值得到的升序。如果想要得到降序，可以傳入一個進行大于比較的仿函數。

一個是使用迭代器進行構造。

還有一個是在C++11中引入的，使用初始化列表這種容器進行構造。

2.1.2 insert和erase

2.1.2.1 insert

在set中，我們使用insert來進行鍵值的插入。

較為常用的主要是三個：直接插入鍵值的，插入迭代器區間的，插入初始化列表的。

直接插入鍵值的：

我們主要看第一個左值引用，第二個右值引用暫不做討論。
這個函數重載就是直接插入鍵值，比較特殊的是它的返回值，返回的是一個pair類型。

在這個pair類型中，有兩個成員，第一個成員是set的迭代器，第二個成員是bool型的變量。

由于set是不允許鍵值冗余的二叉搜索樹，因此set是存在插入失敗的情況。在插入成功時，pair中包含插入位置對應的迭代器，以及一個true;插入失敗時，返回二叉搜索樹中某個已存在key值的迭代器(此key值與所要插入的key值相同)，以及一個false。

其余的兩種形式：

2.1.2.2 erase

erase有三種刪除形式，其中前兩種使用得最多。

iterator erase(const_iterator position):這是利用迭代器進行刪除，刪除的是迭代器所對應的key，返回值也是一個迭代器——一般是返回刪除元素的后一個迭代器，但如果刪除的元素后面沒有元素，那就返回set.end()

size_type erase (const value_type& val): 這是利用鍵值去刪除。在刪除前，先要找到鍵值對應的具體位置，然后再刪除。這個返回值很特殊，是刪除的數據個數。這讓人有點疑惑，set既然是不支持冗余的，那么刪除的數據個數最多只是1，設計這樣的返回值感覺沒什么用——實際上，這是在設計上與multiset進行一個統一，對于multiset，這個返回值是有意義的。

iterator erase(const_iterator first,const_iterator last):刪除一段迭代器區間。

2.1.3 查找和訪問

2.1.3.1 set迭代器相關

set的迭代器使用和其它容器一樣，這里不做贅述。

需要注意的是，雖然set中也區分了const迭代器和非const迭代器，但是無論是哪種迭代器，都是不能對set中的鍵值進行修改，因為一旦修改，就很可能破壞整棵二叉搜索樹的結構。

2.1.3.2 find && count

利用鍵值進行查找，返回相應位置的迭代器，對應的有const迭代器和非const迭代器兩個版本。

count是去查找set中相應鍵值的元素個數，這個在set中不是0，就是1，最主要還是在multiset中的使用，不過在設計時，考慮到set和multiset的協同，因此set中也有這個函數。

2.1.3.3 范圍查找

范圍查找lower_bound和upper_bound配套使用。

對于lower_bound,返回的是整棵二叉搜索樹中大于或等于傳入val的第一個數據的迭代器；對于upper_bound,返回的是整棵二叉搜索樹中大于傳入val的第一個數據的迭代器（這里之所以是大于val，緣于迭代器的使用規則，因為迭代器遍歷的循環條件總是！= 某個迭代器）。如果這樣的數據不存在，那么這兩個函數都是返回set.end()。

除了上述的用于查找某個范圍的兩個函數，還有一個用于查找相同鍵值范圍的函數，這個函數在set中沒有啥意義，在multiset中才比較有用。

這個equal_range函數返回的是一個pair類型，存儲對應某個范圍的左右兩個邊界的迭代器，注意，右迭代器對應這個范圍之后的第一個元素（或是set.end()）。如果key值不存在，則pair中的兩個成員變量均為set.end()。

2.2 multiset

相較于set，multiset是支持鍵值冗余的搜素二叉樹。
multiset整體的成員函數于set相類似，不過由于其支持鍵值冗余的特性，在部分函數上會有所差別。

2.2.1 insert和erase

對于insert,由于multiset允許鍵值冗余，所以不存在插入失敗的情況，因此直接返回插入位置對應的迭代器即可。

對于erase,如果使用的是迭代器版本，那么就是將相應位置的元素清除；如果使用傳val值的版本，則會將multiset中，所有等于該鍵值的數據全部刪除，并返回刪除的數據個數。

2.2.2 find和count

multiset中，存在鍵值冗余的情況，那么這個find，究竟是查找哪一個數據呢？
find函數默認查找的是整棵二叉搜索樹的中序遍歷中的鍵值與val相等的第一個數。

count函數即返回整棵二叉搜索樹中，與val相等的鍵值的個數。

2.3 set和multiset的在算法題中的應用

set是非鍵值冗余的二叉搜索樹，而二叉搜索數的中序遍歷又是有序的，所以，我們如果要對一系列數據進行去重+排序處理，那么就可以將這些數據放至set容器中，否則就需要使用算法庫中的sort+unique。

multiset是鍵值冗余的二叉搜索樹，如果僅需要實現排序功能，而不需去重，可將數據放至multiset中。

3. map和multimap

map和multimap，底層都是key-value的二叉搜索樹，map允許鍵值冗余，multimap不允許鍵值冗余。由于key-value需要存儲兩個數，所以map和multimap底層存放的數據類型是pair,默認pair類型中的第一個成員是key,第二個成員是value。

3.1 pair介紹

pair是用于存儲成對的，并且往往有關聯的兩個數據，分別存儲到pair的first成員和second成員中，這兩個成員是允許類外直接訪問的。

pair中，最重要的便是如何去構造出一個pair對象，以下介紹幾種常用的方法。

pair類型的對象也可以進行大小的比較，重載了相關的運算符。

pair類型對象的比較，先比較成員first,再比較成員second。

• 相等比較：兩個成員都相等，則相等。
• 大于比較：誰first大，誰就大;first一樣大，再比較second,誰second大，誰就大。
• 小于比較：與大于比較邏輯相同，比大轉為比小即可。
• 不等于比較：兩個成員有一個不相等，便不相等。

3.2 map

3.2.1 構造函數

map的常用構造與set類似，默認構造、拷貝構造和使用一段迭代器區間進行構造。

需要注意的是，由于map的底層數據是pair類型的，因此使用一段迭代器區間進行構造時，迭代器指向的一定要是pair類的對象。

3.2.2 insert和erase

map的insert需要插入一個pair對象。

最常見的插入還是單元素的插入，這種插入通常習慣以下兩種寫法：

map的erase:

size_type erase(const key_type& k) : map中的erase是按照key值來刪除，而非value。

3.2.3 find和count

均是按照鍵值key來進行查找和統計

3.2.4 operator[] 和 at

方括號在map中的重載，是map中非常重要的一個成員函數，功能也較為復雜。

operator[ ]的重載，需要傳一個key值（key_type）進去，返回的是key值相應的value值的引用（mapped_type）。

但實際上，這個重載函數遠沒有看上去那么簡單。這個函數的使用，要分為兩種情況：

• 相應的key值存在。此時返回key值相應的val值的引用。
• 相應的key值不存在。此時并不會查找失敗，這個函數會調用insert向map中再插入一個pair對象，這個pair對象的key值是傳入的key值，value值是利用map中的value類型構造出的匿名對象，然后函數再返回這個value值。

實質上，在相應的key值存在時，函數也會調用insert,只不過會插入失敗，不過由于即便插入失敗，insert也會返回相應key值對應的迭代器(返回是pair類型，迭代器為其第一個成員)，因此可以正常返回相應value值的引用。

以下是stl庫中，map容器中operator[ ]函數的實現：

mapped_type& operator[] (const key_type& k)
{pair<iterator, bool> ret = insert({ k, mapped_type() });iterator it = ret.first;return it->second;
}

at與operator[ ]類似，傳key值，返回value值，只不過at只能用于已存在的key值查找，不能用于插入不存在的key值，當輸入一個不存在的key值時，at函數會拋異常。

以下舉一個使用operator[ ]進行次數統計的典型例子：

在main函數中調用，相應的輸出為：

3.3 multimap

與map相比較,multimap 是支持鍵值冗余的key-value二叉搜索樹。

multimap與map的差別，同multiset與set的差異相類似，此處不再贅述。

有一點需要注意，map是不支持鍵值冗余，但是value值是可以相同的，只要相應的key值不同即可；而multimap對于key和value則都是沒有限制的。

另外，在multimap中沒有了operator[ ]和at這兩個成員函數，最主要的原因還是在于鍵值冗余，因此會無法解決到底返回哪個value值的問題。