一宁赤、關(guān)聯(lián)容器
關(guān)聯(lián)容器（associative container）是對(duì)容器概念的另一個(gè)改進(jìn)筹燕。關(guān)聯(lián)容器將值與鍵關(guān)聯(lián)在一起，并使用鍵來查找值蛹含。例如毅厚，值可以是表示雇員信息（如姓名、地址浦箱、電話）的結(jié)構(gòu)吸耿，而鍵可以是唯一的員工編號(hào)。為獲取雇員信息酷窥，程序?qū)⑹褂面I查找雇員結(jié)構(gòu)咽安。對(duì)容器X，表達(dá)式X::key_type指出了鍵的類型蓬推。
關(guān)聯(lián)容器的優(yōu)點(diǎn)在于妆棒，它提供了對(duì)元素的快速訪問。與序列相似沸伏，關(guān)聯(lián)容器也允許插入新元素糕珊，但不能指定元素的插入位置。原因是關(guān)聯(lián)容器通常有用于確定數(shù)據(jù)放置位置的算法毅糟，以便能夠快速檢索信息红选。
二、map
2.1 簡介
map 是一類關(guān)聯(lián)式容器姆另。它的特點(diǎn)是增加和刪除節(jié)點(diǎn)對(duì)迭代器的影響很小喇肋，除了那個(gè)操作節(jié)點(diǎn)坟乾，對(duì)其他的節(jié)點(diǎn)都沒有什么影響。對(duì)于迭代器來說蝶防，可以修改實(shí)值糊渊，而不能修改key。
在map中慧脱，值與鍵的類型不同渺绒，鍵是唯一的，每個(gè)鍵只對(duì)應(yīng)一個(gè)值菱鸥。multimap與map相似宗兼，只是一個(gè)鍵可以與多個(gè)值相關(guān)聯(lián)。
2.2 頭文件
#include <map> （以前的map.h）
2.3 構(gòu)造函數(shù)
map對(duì)象是模板類氮采，需要關(guān)鍵字和存儲(chǔ)對(duì)象兩個(gè)模板參數(shù)：
std:map<int, string> personnel;
這樣就定義了一個(gè)用 int 作為索引,并擁有相關(guān)聯(lián)的指向 string 的指針殷绍。
為了使用方便，可以對(duì)模板類進(jìn)行一下類型定義鹊漠，
typedef map<int, CString> UDT_MAP_INT_CSTRING;
UDT_MAP_INT_CSTRING enumMap;
2.4 基本操作函數(shù)
| 函數(shù) | 作用 |
|---|---|
| begin() | 返回指向map頭部的迭代器 |
| clear() | 刪除所有元素 |
| count() | 返回指定元素出現(xiàn)的次數(shù) |
| empty() | 如果map為空則返回true |
| end() | 返回指向map末尾的迭代器 |
| equal_range() | 返回特殊條目的迭代器對(duì) |
| erase() | 刪除一個(gè)元素 |
| find() | 查找一個(gè)元素 |
| get_allocator() | 返回map的配置器 |
| insert() | 插入元素 |
| key_comp() | 返回比較元素key的函數(shù) |
| lower_bound() | 返回鍵值>=給定元素的第一個(gè)位置 |
| max_size() | 返回可以容納的最大元素個(gè)數(shù) |
| rbegin() | 返回一個(gè)指向map尾部的逆向迭代器 |
| rend() | 返回一個(gè)指向map頭部的逆向迭代器 |
| size() | 返回map中元素的個(gè)數(shù) |
| swap() | 交換兩個(gè)map |
| upper_bound() | 返回鍵值>給定元素的第一個(gè)位置 |
| value_comp() | 返回比較元素value的函數(shù) |
2.4.1 遍歷元素
2.4.1.1 迭代器遍歷
反相迭代器：
Map<int, string> mapStudent;
mapStudent.insert(pair<int, string>(1, “student_one”));
mapStudent.insert(pair<int, string>(2, “student_two”));
mapStudent.insert(pair<int, string>(3, “student_three”));
map<int, string>::reverse_iterator iter;
for(iter = mapStudent.rbegin(); iter != mapStudent.rend(); iter++)
{
cout<<iter->first<<" "<<iter->second<<endl;
}
2.4.1.2 數(shù)組遍歷
Map<int, string> mapStudent;
mapStudent.insert(pair<int, string>(1, “student_one”));
mapStudent.insert(pair<int, string>(2, “student_two”));
mapStudent.insert(pair<int, string>(3, “student_three”));
int nSize = mapStudent.size();
for(int nIndex = 1; nIndex <= nSize; nIndex++)
{
cout<<mapStudent[nIndex]<<endl;
}
2.4.1.3 基于范圍的for循環(huán)（C++11）
Map<int, string> mapStudent;
mapStudent.insert(pair<int, string>(1, “student_one”));
mapStudent.insert(pair<int, string>(2, “student_two”));
mapStudent.insert(pair<int, string>(3, “student_three”));
for(auto & iter : mapStudent)
{
cout<<iter->second<<endl;
}
在這種for循環(huán)中主到，括號(hào)內(nèi)的代碼聲明一個(gè)類型與容器存儲(chǔ)的內(nèi)容相同的變量，然后指出了容器的名稱躯概。接下來登钥，循環(huán)體使用指定的變量依次訪問容器的每個(gè)元素。
2.4.2 插入元素
2.4.2.1 用數(shù)組方式插入數(shù)據(jù)
Map<int, string> mapStudent;
mapStudent[1] = “one”;
mapStudent[2] = “two”;
這樣非常直觀娶靡，但存在一個(gè)性能的問題牧牢。插入2時(shí),先在mapStudent中查找主鍵為2的項(xiàng)，沒發(fā)現(xiàn)姿锭，然后將一個(gè)新的對(duì)象插入mapStudent塔鳍，鍵是2，值是一個(gè)空字符串呻此，插入完成后轮纫，將字符串賦為"two"; 該方法會(huì)將每個(gè)值都賦為缺省值，然后再賦為顯示的值焚鲜，如果元素是類對(duì)象掌唾，則開銷比較大。我們可以用以下方法來避免開銷：
mapStudent.insert(map<int, string> :: value_type(2, "two"));
2.4.2.2 用insert函數(shù)插入value_type數(shù)據(jù)
#include <map>
#include <string>
#include <iostream>
using namespace std;
Int main()
{
Map<int, string> mapStudent;
mapStudent.insert(map<int, string>::value_type (1, “student_one”));
mapStudent.insert(map<int, string>::value_type (2, “student_two”));
mapStudent.insert(map<int, string>::value_type (3, “student_three”));
map<int, string>::iterator iter;
for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
{
cout<<iter->first<<” ”<<iter->second<<endl;
}
}
2.4.2.3 用insert函數(shù)插入pair數(shù)據(jù)
Map<int, string> mapStudent;
mapStudent.insert(pair<int, string>(1, “student_one”));
mapStudent.insert(pair<int, string>(2, “student_two”));
可用make_pair代替為：
Map<int, string> mapStudent;
mapStudent.insert(make_pair(1, “student_one”));
mapStudent.insert(make_pair(2, “student_two”));
2.4.3 刪除元素
這里要用到erase函數(shù)恃泪，它有三個(gè)重載了的函數(shù)郑兴，下面在例子中詳細(xì)說明它們的用法
首先犀斋，
Map<int, string> mapStudent;
mapStudent.insert(pair<int, string>(1, “student_one”));
mapStudent.insert(pair<int, string>(2, “student_two”));
mapStudent.insert(pair<int, string>(3, “student_three”));
2.4.3.1 用迭代器刪除
map<int, string>::iterator iter;
iter = mapStudent.find(1);
mapStudent.erase(iter);
2.4.3.2 用關(guān)鍵字刪除
int n = mapStudent.erase(1); // 如果刪除了會(huì)返回1贝乎，否則返回0
2.4.3.3 用迭代器，成片的刪除
mapStudent.earse(mapStudent.begin(), mapStudent.end());
// 成片刪除要注意的是叽粹，也是STL的特性览效，刪除區(qū)間是一個(gè)前閉后開的集合
相當(dāng)于clear()
2.4.4 查找元素
2.4.4.1 count函數(shù)
用count函數(shù)來判定關(guān)鍵字是否出現(xiàn)却舀，其缺點(diǎn)是無法定位數(shù)據(jù)出現(xiàn)位置,由于map的特性，一對(duì)一的映射關(guān)系锤灿，就決定了count函數(shù)的返回值只有兩個(gè)挽拔，要么是0，要么是1但校，出現(xiàn)的情況螃诅，當(dāng)然是返回1了。
2.4.4.2 find函數(shù)
用find函數(shù)來定位數(shù)據(jù)出現(xiàn)位置状囱，它返回的一個(gè)迭代器术裸，當(dāng)數(shù)據(jù)出現(xiàn)時(shí)，它返回?cái)?shù)據(jù)所在位置的迭代器亭枷，如果map中沒有要查找的數(shù)據(jù)袭艺，它返回的迭代器等于end函數(shù)返回的迭代器，程序說明：
map<int, string> mapStudent;
mapStudent.insert(pair<int, string>(1, “student_one”));
mapStudent.insert(pair<int, string>(2, “student_two”));
mapStudent.insert(pair<int, string>(3, “student_three”));
map<int, string>::iterator iter;
iter = mapStudent.find(1);
if(iter != mapStudent.end())
{
cout<<"Find, the value is "<<iter->second<<endl;
}
else
{
cout<<"Do not Find"<<endl;
}
2.4.4.3 lower_bound和upper_bound函數(shù)
成員函數(shù)lower_bound()和upper_bound()將鍵作為參數(shù)叨粘，且工作原理與處理set時(shí)相同猾编。
2.4.4.4 equal_range函數(shù)
成員函數(shù)equal_range函數(shù)用鍵作為參數(shù)，且返回兩個(gè)迭代器升敲，它們表示的區(qū)間與該鍵匹配答倡。為返回兩個(gè)值，該方法將它們封裝在一個(gè)pair對(duì)象中驴党，這里pair的兩個(gè)模板參數(shù)都是迭代器苇羡。
map<int, string> mapStudent;
mapStudent.insert(pair<int, string>(1, “student_one”));
mapStudent.insert(pair<int, string>(2, “student_two”));
mapStudent.insert(pair<int, string>(3, “student_three”));
pair<map<int, string>::iterator, map<int, string>::iterator> range = mapStudent.equal_range(2);
std::map<int, string>::iterator it;
for (it = range.first; it != range.second; ++it)
cout << (*it).second << endl;
在聲明中可使用C++11自動(dòng)類型推斷功能，簡化代碼如下：
auto range = mapStudent.equal_range(2);
for (auto it = range.first; it != range.second; ++it)
cout << (*it).second << endl;
三鼻弧、pair
C++標(biāo)準(zhǔn)程序庫中凡是“必須返回兩個(gè)值”的函數(shù)设江， 也都會(huì)利用pair對(duì)象。
pair可以將兩個(gè)值視為一個(gè)單元攘轩。容器類別map和multimap就是使用pairs來管理其健值/實(shí)值(key/value)的成對(duì)元素叉存。
pair被定義為struct,因此可直接存取pair中的個(gè)別值。
兩個(gè)pairs互相比較時(shí)度帮， 第一個(gè)元素正具有較高的優(yōu)先級(jí)歼捏。
例：
namespace std
{
template <class T1, class T2>
bool operator< (const pair<T1, T2>&x, const pair<T1, T2>&y)
{
return x.first<y.first || ((y.first<x.first)&&x.second<y.second);
}
}
3.1 pair的應(yīng)用
pair是將2個(gè)數(shù)據(jù)組合成一個(gè)數(shù)據(jù)，當(dāng)需要這樣的需求時(shí)就可以使用pair笨篷，如stl中的map就是將key和value放在一起來保存瞳秽。另一個(gè)應(yīng)用是，當(dāng)一個(gè)函數(shù)需要返回2個(gè)數(shù)據(jù)的時(shí)候率翅，可以選擇pair练俐。pair的實(shí)現(xiàn)是一個(gè)結(jié)構(gòu)體，主要的兩個(gè)成員變量是first second 因?yàn)槭鞘褂胹truct不是class冕臭，所以可以直接使用pair的成員變量腺晾。
四燕锥、make_pair
無需寫出型別， 就可以生成一個(gè)pair對(duì)象
例：
std::make_pair(42, '@');
而不必費(fèi)力寫成：
std::pair<int, char>(42, '@')
當(dāng)有必要對(duì)一個(gè)接受pair參數(shù)的函數(shù)傳遞兩個(gè)值時(shí)悯蝉， make_pair()尤其顯得方便归形，
void f(std::pair<int, const char*>);
void foo
{
f(std::make_pair(42, '@')); //pass two values as pair
}
4.1 make_pair函數(shù)
template pair make_pair(T1 a, T2 b) { return pair(a, b); }
很明顯，我們可以使用pair的構(gòu)造函數(shù)也可以使用make_pair來生成我們需要的pair鼻由。一般make_pair都使用在需要pair做參數(shù)的位置暇榴，可以直接調(diào)用make_pair生成pair對(duì)象很方便，代碼也很清晰蕉世。 另一個(gè)使用的方面就是pair可以接受隱式的類型轉(zhuǎn)換跺撼，這樣可以獲得更高的靈活度。靈活度也帶來了一些問題如：
std::pair<int, float>(1, 1.1);
std::make_pair(1, 1.1);
是不同的讨彼，第一個(gè)就是float歉井，而第2個(gè)會(huì)自己匹配成double。
? 由 Leung 寫于 2018 年 9 月 8 日
? 參考：C++ map的基本操作和使用
stl map用法和make_pair函數(shù)
C++ Primer Plus(第6版)
