map容器

1. 基本概念

• map是關聯式容器，按照key的大小來存盤由<key,value>組合而成的元素
• 鍵值key通常用來唯一的標識元素，即key不可重復，value可重復
• map底層實作為紅黑樹，紅黑樹是平衡二叉樹

map模板引數說明

• key： 鍵值對中key的型別
• T： 鍵值對中value的型別
• Compare:：比較器的型別，map中的元素是按照key來比較的，預設情況下按照小于來比較，一般情況下(內置型別元素)該引數不需要傳遞，如果無法比較時(自定義型別)，需要用戶自己顯式傳遞比較規則(一般情況下按照函式指標或者仿函式來傳遞)
• Alloc：通過空間配置器來申請底層空間，不需要用戶傳遞，除非用戶不想使用標準庫提供的空間配置器
• 注意：在使用map時，需要包含頭檔案，

2. 建構式

map (const key_compare& comp = key_compare(),
     const allocator_type& alloc = allocator_type());

構造一個空的map

3. 迭代器

/* begin:首元素的位置，end最后一個元素的下一個位置 */
iterator begin();	
iterator end();

/* 與begin和end意義相同，但是所指向的元素不能修改 */
const_iterator begin();
const_iterator end();

/* 與begin和end意義相同，但cbegin和cend所指向的元素不能修改 */
const_iterator cbegin();
const_iterator cend();

/* 反向迭代器，rbegin在end位置，rend在begin位置，其++和--操作與begin和end操作移動相反 */
reverse_iterator rbegin();
reverse_iterator rend();

/* 與rbegin和rend位置相同，但所指向的元素不能修改 */
const_reverse_iterator rbegin();
const_reverse_iterator rend();

/* 與rbegin和rend位置相同，但crbegin和crend所指向的元素不能修改 */
const_reverse_iterator crbegin();
const_reverse_iterator crend();

4. 容量與元素訪問

【容量】

bool empty();	// 檢測map中的元素是否為空，是回傳true，否則回傳false
size_type size();	// 回傳map中有效元素的個數
size_type max_size();	// 回傳map最大容納量

【元素訪問】

/* 回傳key對應的value */
mapped_type& operator[] (const key_type& k);
mapped_type& operator[] (key_type&& k);

• key存在時：通過key找到與key對應的value然后回傳其參考
• key不存在時：operator[]用默認value與key構造鍵值對然后插入，回傳該默認value

/* 回傳key對應的value */
mapped_type& at (const key_type& k);
const mapped_type& at (const key_type& k) const;

• key存在時：通過key找到與key對應的value然后回傳其參考
• key不存在時：拋出例外

iterator find (const key_type& k);
const_iterator find (const key_type& k) const;

• key存在時：回傳key元素的迭代器
• key不存在時：回傳 map::end() 迭代器

size_type count (const key_type& k) const;

• 回傳map中含有該key的數量：0或1
• 常用來檢測某個元素是否存在于map中

5. 構造鍵值對

【使用pair類】

template <class T1, class T2> struct pair;

• pair類將一對不同型別的值（T1和T2）耦合在一起，單個值可以通過其公共成員(first和second)訪問
• pair是tuple的特例
• first：pair中的第一個值
• second：pair中的第二個值
• first_type：pair中的第一個值的資料型別
• second_type：pair中的第二個值的資料型別

【make_pair函式】

template <class T1, class T2>
pair<V1,V2> make_pair (T1&& x, T2&& y); 

• 作用：構造一個pair物件，第一個元素設定為x，第二個元素設定為y
• 元素型別可由元素值隱式推匯出來

【代碼演示】

pair<int, string> pair1 = make_pair(1, "first");
pair<int, string> pair2(2, "second");
pair<int, string> pair3(pair1);
pair3.first = 3;
pair3.second = "third";

6. 元素修改

6.1 value_type宏定義

typedef pair value_type;

這里的value_type就是一個pair類

6.2 插入

/* 單個元素插入 */
pair<iterator,bool> insert (const value_type& val);	// 插入一個鍵值對

/* 指定插入位置 */
iterator insert (const_iterator position, const value_type& val);

/* 范圍插入 */
template <class InputIterator>
void insert (InputIterator first, InputIterator last);

/* 初始化串列 */
void insert (initializer_list<value_type> il);

/*****************************************************/
/* 測驗代碼 */
/*****************************************************/
map<char, int> myMap;

/* single insertion */
pair<map<char, int>::iterator, bool> ret_sig = myMap.insert(pair<char, int>('a', 1));
if (ret_sig.second)	cout << "single insertion success!" << endl;

/* position insertion */
map<char, int>::iterator pos = myMap.begin();
map<char, int>::iterator ret_pos = myMap.insert(pos, pair<char, int>('b', 2));

/* range insertion */
map<char, int> anotherMap;
anotherMap.insert(myMap.begin(), myMap.find('a'));

/* initializer_list insertion */
myMap.insert({ { 'c', 3 }, { 'd', 4 }, { 'e', 5 } });

for (auto e : myMap)
    cout << e.first << "--->" << e.second << endl;

輸出：

single insertion success!
a--->1
b--->2
c--->3
d--->4
e--->5

6.3 洗掉

/* 按照位置洗掉 */
iterator  erase (const_iterator position);

/* 按照k值洗掉 */
size_type erase (const key_type& k);

/* 按照范圍洗掉 */
iterator  erase (const_iterator first, const_iterator last);

/*****************************************************/
/* 測驗代碼 */
/*****************************************************/
map<char, int> map1({{ 'a', 1 }, { 'b', 2 }, { 'c', 3 }, 
                     { 'd', 4 }, { 'e', 5 }, { 'f', 6 }});
map1.erase('f');
map1.erase(map1.find('e'));
map1.erase(map1.begin(), map1.find('b'));
for (auto e : map1)
    cout << e.first << "--->" << e.second << endl;

輸出：

b--->2
c--->3
d--->4

6.4 修改

mapped_type& operator[] (const key_type& k);
mapped_type& operator[] (key_type&& k);

/*****************************************************/
/* 測驗代碼 */
/*****************************************************/
map<char, int> myMap({ { 'a', 1 }, { 'b', 2 } });
myMap['a'] = 4;
myMap['c'] = 3;
for (auto e : myMap)
    cout << e.first << "--->" << e.second << endl;

輸出：

a--->4
b--->2
c--->3

6.5 清空

void clear();

/*****************************************************/
/* 測驗代碼 */
/*****************************************************/
map<char, int> map1({ { 'a', 1 }, { 'b', 2 }, { 'c', 3 } });
map.clear();

6.6 交換資料

void swap (map& x);

/*****************************************************/
/* 測驗代碼 */
/*****************************************************/
map<char, int> map1({ { 'a', 1 }, { 'b', 2 }, { 'c', 3 } });
map<char, int> map2({ { 'd', 4 }, { 'e', 5 }, { 'f', 6 } });
map1.swap(map2);

輸出：

========= map1 =========
a--->1
b--->2
c--->3
========= map2 =========
d--->4
e--->5
f--->6
after swap
========= map1 =========
d--->4
e--->5
f--->6
========= map2 =========
a--->1
b--->2
c--->3

multimap容器

• multimap是關聯式容器，資料組織與map容器相同
• 底層資料結構也是紅黑樹
• multimap的key是可以重復的
• multimap中沒有多載operator[]