C++map

1. 關聯式容器

vector、list、deque、forward_list(C++11)等STL容器，其底層為線性序列的數據結構，里面存儲的是元素本身，這樣的容器被統稱為序列式容器。而map、set是一種關聯式容器，關聯式容器也是用來存儲數據的，與序列式容器不同的是，關聯式容器里面存儲的是<key, value>結構的鍵值對，在數據檢索時比序列式容器效率更高。map和set的鍵是唯一的，但是mutimap和multiset支持多個同名且有不同映射的鍵共存。

2. 鍵值對

用來表示具有一一對應關系的一種結構，該結構中一般只包含兩個成員變量key和value, key代表鍵值，value表示與key對應的信息。比如：學生的姓名和他的學號是一一對應的，那么就可以通過查找學生的姓名來查找到對應的學號。map容器是Key Value結構，允許修改value，且允許多個相同的value存在。但map不允許存在相同的key（multimap除外），且key不可修改（因為會破壞內部的紅黑樹結構）。

3. map容器

形參含義：

key:鍵值對應key的類型
T：鍵值對應value的類型
Compare:比較器的類型，map中的元素是按照key來比較的，缺省情況下按照小于來比較，一般情況下（內置類型元索）該參數不需要傳遞，如果無法比較時（自定義類型），需要用戶自己顯式傳遞比較規則（一般情況下按照函數指針或者仿函數來傳遞）
Alloc：通過空間配置器來申請底層空間，不需要用戶傳遞，除非用戶不想使用標準庫提供的空間配置器

4. map的成員變量

map中鍵是不允許被修改的（因為修改鍵會破壞搜索二叉樹的結構），但是映射可以被修改。map在value_type中使用了pair來保護鍵。map實例化的格式，實際上是調用了pair模板的顯式實例化。

pair：

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){}
};

5. map的成員函數

5.1 map的成員函數介紹

map的構造：

函數聲明	功能介紹
map<K,V>m()	構造一個空的map

map的迭代器：

函數聲明	功能介紹
begin()和end()	begin:首元素的位置；end：下一個元素的位置
cbegin()和cend()	c指const，cbegin和cend指向的內容不能修改
rbegin()和rend()	反向迭代器，rbegin從end開始，rend從begin開始，其++和–的方向相反
crbegin()和crend()	與前一個功能相同，但指向的內容不能修改

map的容量與元素訪問：

函數名	函數聲明	功能介紹
empty	bool empty() const	檢測map中的元素是否為空，為空返回ture，不為空返回false
size	size_type size() const	返回map中有效元素的個數
operator[]	mapped type& operator[] (const key_type& k	返回key對應的value
at	mapped_type& at (const key_type& k);const mapped_type& at (const key_type& k) const;	返回key對應的value

注意：

在元素訪問時，at()（該函數不常用）函數，于operator[]功能相同但有一點區別：當key不存在時，operator[]用默認value與key構造鍵值對然后插入，返回該默認value, at()函數直接拋異常。

map的修改：

函數名	函數聲明	功能介紹
insert	pair<iterator,bool> insert (const value_type& val)	在map中插入鍵值對x，注意x是一個鍵值對，返回值也是鍵值對；iterator代表新插入元素的位置，bool代表插入成功
erase	void erase (iterator position)	刪除position位置上的元素
	size_type erase (const key_type& k)	刪除鍵值為x的元素
	void erase (iterator first, iterator last)	刪除**[first,last)**區間中的元素
swap	void swap (map& x)	交換兩個map中的元素
clear	void clear()	刪除map里所有的元素

map的比較:

函數名	函數聲明	功能介紹
key_comp
value_comp

map的操作：

函數名	函數聲明	功能介紹
find	iterator find (const key_type& k)	搜索map里鍵等于k的元素，如果找到返回一個映射的迭代器，找不到返回end的迭代器
count	size_type count (const key_type& k) const	搜索map里鍵等于k的元素，找到返回1，找不到返回0
lower_bound	iterator lower_bound (const key_type& k)	在map里找>=k的元素，返回符合情況的最小鍵的迭代器
upper_bound	iterator upper_bound (const key_type& k)	在map里找>k的元素，返回符合情況的最小鍵的迭代器
equal_range	pair<iterator,iterator>equal_range (const key_type& k)

5.2 insert

insert的返回值是一個pair類模板，而它的參數val也有一個pair類模板。**insert使用pair類模板使得它同時具有插入和搜索的功能。**bool值用來判斷map中需要插入的值是否已經存在，iterator是指向val值的迭代器。

insert的返回值:

如果insert搜索的val值存在，bool值就為false（判斷插入失敗），iterator會指向map中已經存在的val值；如果insert搜索的val值不存在，bool值就為true（判斷插入成功），iterator會指向新插入的val值。

使用insert進行搜索：

由于insert使用pair類模板，所以它也有搜索的功能：

#include<iostream>
#include<map>
#include<string.h>
using namespace std;int main()
{string arr[] = { "張三","李四","王五","張三","張三","李四","張三","李四","王五","張三" };map<string, int> countmap;for (auto& e : arr)//傳引用是為了拷貝臨時變量浪費資源{pair<map<string, int>::iterator, bool>ret = countmap.insert(make_pair(e, 1));if (ret.second == false){ret.first->second++;}}for (auto& i : countmap){cout << i.first << ":" << i.second << endl;}return 0;
}

5.3 operator[]

map的operator[]是借助inert來實現的：

因此map的operator[]同時具有插入、查找和修改的功能：

#include<iostream>
#include<map>
#include<string.h>
using namespace std;int main()
{map<string, string> m;m.insert(make_pair("first", "first"));m.insert(make_pair("second", "second"));cout << "before:" << endl;for (auto& i : m){cout << i.first << " : " << i.second << endl;}m["third"];//插入printf("\n");cout << m["first"] << endl;//查找m["first"] = "x";//修改m["fourth"] = "xxxx";//插入+修改printf("\n");cout << "after:" << endl;for (auto& i : m){cout << i.first << " : " << i.second << endl;}return 0;
}

6. map的特點

stl里的map和set用的是同一顆紅黑樹來實現的。

set：

注意：Rb_tree里有一個key_type和一個value_type，但set應該是key和key的映射關系，所以在成員變量里，stl把key_type和value_type都定義了為_key

map：

而在stl的map里，value_type則定義了一個pair,這樣做的目的就是為了復用同一顆紅黑樹

所以從set和map的底層來看，它們的實現方法分別是：

set<K.>->rb_tree<K, K>

map<K, V>->rb_tree<K ,pair<const K, V>>

這種寫法實際上是由stl_tree.h文件中的val模板決定你是key的set，還是key/value的map：