map和set

序列式容器和關聯式容器

之前我們接觸的vector,list,deque等，這些容器統稱為序列式容器，其底層為線性序列的的數據結構，里面存儲的是元素本身。
關聯式容器也是用來存儲數據的，只不過存儲的是<key, value>結構的鍵值對，在查找時比序列式容器效率更高。

鍵值對

用來表示具有對應關系的一種結構，該結構中一般只包含兩個成員變量key和value，key代表鍵值，value表示與key對應的信息。
SGI-STL中關于鍵值對的定義：

template <class T1, class T2>
struct pair
{
typedef T1 first_type;
typedef T2 second_type;
T1 first;
T2 second;
pair(): first(T1()),second(T2())
{}
pair(const T1& a, const T2& b): first(a), second(b)
{}
};

pair所在頭文件：#include < utility >
C++標準庫中提供了四種主要的樹形結構關聯式容器:map,set,multiset,multimap

set

set是按照一定次序存儲元素的容器
在set中，元素的value也標識它(value就是key，類型為T)，并且每個value必須是唯一的。
set中的元素不可以重復(因此可以使用set進行去重)。
使用set的迭代器遍歷set中的元素，可以得到有序序列
set中的元素默認按照小于來比較
set中查找某個元素，時間復雜度為：$lo{g}_{2}n$

set的主要操作

在set中插入元素x，實際插入的是<x, x>構成的鍵值對，如果插入成功，返回<該元素在set中的位置，true>,如果插入失敗，說明x在set中已經存在，返回<x在set中的位置，false>

刪除set中position位置上的元素

返回set中值等于val的節點個數

lower_bound返回set中第一個大于等于val的迭代器
upper_bound返回set中第一個大于val的迭代器

map

key: 鍵值對中key的類型
T： 鍵值對中value的類型

map主要操作

和set一樣，insert返回一個pair<iterator, bool>, iterator 指向成功創建的節點或者已經存在的節點，bool代表插入是否成功
同時map的其他操作如erase,count等和set類似，這里就不一一列舉了
map和set操作最大的不同就是map重載了operator[]

首先，在調用operator[]時，map會去調用insert(),得到返回值pair<iterator, bool>,如果bool 為true，代表新節點插入成功，為false,表示以及存在一個節點的key相同的節點，iterator指向這個節點，返回iterator->second

multiset和multimap

multiset/multimap與set/set的區別是，multiset/multimap中的元素可以重復，set/map是中value是唯一的。
multimap沒有重載operator[]。其他接口和set/map功能相同。