一、關聯容器簡述
容器containers是用來管理某對象資料的集合，每種容器都有其優缺點，為了應對不同應用需求，标準庫準備了不同的容器類型，容器可以是數組、連結清單或者是每個元素有一個特别的鍵值（KEY）組織起來。标準庫以KEY組織對象資料的容器類型-關聯容器。
關聯容器和順序容器的本質差别在于：
- 關聯容器通過鍵（key）存儲和讀取元素，而順序容器則通過元素在容器中的位置順序存儲和通路元素。
- 由于關聯容器是通過鍵（key）組織資料的，是以已序（sorted）集合，根據KEY提供的某排序準則在元素對象加入集合自動為其進行了排序，其在集合中的位置取決于其KEY值。而順序容器是可序（ordered）集合,元素對象在集合中的位置取決于加入集合的時機與地點，與值無關（順序容器關聯的容器擴充卡-優先隊列除外）。
關聯容器（Associative containers）支援通過鍵來高效地查找和讀取元素。标準庫提供四種關聯容器，map、multimap、set、multiset，其中兩個基本的關聯容器類型是 map、set。
map 的元素以鍵－值（key-value）對的形式組織：鍵用作元素在 map 中的索引，而值則表示所存儲和讀取的資料。
set僅包含一個鍵，并有效地支援關于某個鍵是否存在的查詢。
一般來說，如果希望有效地存儲不同值的集合，那麼使用 set 容器比較合适，而 map 容器則更适用于需要存儲（乃至修改）每個鍵所關聯的值的情況。例如，在做某種文本處理時，可使用 set 儲存要忽略的單詞。而字典則是 map 的一種很好的應用：單詞本身是鍵，而它的解釋說明則是值。
set 和 map 類型的對象所包含的元素都具有不同的鍵，不允許為同一個鍵添加第二個元素。如果一個鍵必須對應多個執行個體，則需使用 multimap 或 multiset，這兩種類型允許多個元素擁有相同的鍵。multimap 支援同一個鍵多次出現的 map 類型；multiset 支援同一個鍵多次出現的 set 類型。關聯容器支援很多順序容器也提供的相同操作，此外，還提供管理或使用鍵的特殊操作。
關聯容器可以被視為特殊的順序容器，因為有序集合是通過某種排列準則排列而成。關聯容器自動對其元素排序，并不意味着它們就是用來排序的。我們也可以對順序容器的元素加以手動排序也能獲得已序集合。自動排序帶來的主要優點就是，在搜尋元素時，可以獲得更加的效率，或更準确地說，可以放心使用二分搜尋法而始終具有最優的算法效率。
二、pair類型
對于定義關聯容器，标準庫通過标準庫類型pair類型來支撐關聯容器的。與容器一樣，pair 也是一種模闆類型，該類型在 utility 頭檔案中定義，pair 包含兩個資料值。
//pair僞代碼
template <typename T1,typename T2>
class pair
{
public:
pair();//建立一個空的 pair 對象，它的兩個元素分别是 T1 和 T2類型，采用值初始化
pair(T1 &val1, T2 &val2);//建立一個 pair 對象，它的兩個元素分别是 T1 和 T2 ，其中 first 成員初始化為 v1，而 second 成員初始化為 v2.
...
};
template <typename T1,typename T2>
pair& make_pair(T1 &val1, T2 &val2);//以 v1 和 v2 值建立一個新 pair 對象，其元素類型分别是T1 和 T2 的類型
在建立 pair 對象時，必須提供兩個類型名：pair 對象所包含的兩個資料成員各自對應的類型名字，這兩個類型必相同。
#include <string>
#include <vector>
#include <utility>
using namespace std;
pair<string, string> anon; // holds two strings
pair<string, int> word_count; // holds a string and an int
pair<string, vector<int> > line; // holds string and vecto
//
pair<string, string> anons("hi","hello"); // holds two strings
pair<string, int> word_counts("hi",100); // holds a string and an int
vector<int> i_vec = {1,2,3};
pair<string, vector<int> > lines("hi",i_vec); // holds string and vector
//
anon = make_pair<string, string>("hi","hello");
pair類也和容器一樣提供了關系操作符，通過比對pair類型内的兩個模闆參數來判定，是以模闆參數類型必須具有對于的比較操作符支援：
pair<T1, T2> p1,p2;
...
p1 < p2 //兩個 pair 對象之間的小于運算，其定義遵循字典次序：如果 p1.first < p2.first 或者 !(p2.first < p1.first) &&p1.second < p2.second，則傳回 true
p1 == p2 //如果兩個 pair 對象的 first 和 second 成員依次相等，則這兩個對象相等。該運算使用其元素的 == 操作符
pair類型對象關系比較和普通類型是一緻的：
cout << ((anon==anons)?"true":"false") << endl;//true
同樣地，pair類型和普通類型一樣，也能作為容器類的模闆參數，若覺得直接使用pair 類型的使用相當繁瑣，也可以通過typedef來簡化其聲明：
//
typedef pair<int,int> IPair;
vector<IPair> p_i_vecs;
int vecs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
for (int i=0; i<4; i++)
{
p_i_vecs.push_back(make_pair(vecs[i][0],vecs[i][1]));
}
pair類型隻有兩個資料值，并且是公有成員first和second，可以直接通路：
pair<T1,T2> p;
p.first //傳回 p 中名為 first 的（公有）資料成員
p.second //傳回 p 的名為 second 的（公有）資料成員
//
pair<string,string> anon = make_pair<string, string>("hi","hello");
cout << anon.first <<","<< anon.second << endl;
三、關聯容器
介紹了pair類型後，再回過頭來看關聯容器，關聯容器共享大部分——但并非全部——的順序容器操作。關聯容器不提供front、 push_front、 pop_front、back、push_back 以及 pop_back 操作。通常關聯容器由二叉樹(binary tree)作出來，在二叉樹中，每個節點（元素）都有一個父節點和兩個子節點；左子樹節點的所有元素都比自己小，右子樹節點的所有元素都比自己大。關聯容器的差别主要在于元素的類型以及處理重複元素的方法。
3.1 四種關聯容器
标準庫主要預定義了四種關聯容器，map、multimap、set、multiset：
- map,元素都是“實值/鍵值”所形成的一個對組(key/value pair)，每個元素有一個鍵值，是排序準則的基礎。每一個鍵值隻能出現一次，不允許重複。map可以被看作是關聯式數組，是具有任意索引（index）類别的數組。
- multimap幾乎與map類型，但允許重複元素，即multimap可以包含多個鍵值(key)相同的元素，比較典型的應用就是“字典”使用。
- set是單類型資料對象集合，内部元素依據其值自動排序，每個元素值隻能出現一次，不允許重複。
- multiset和set相同，但允許重複元素，即multiset可以包括多個數值相同的元素。
3.2 關聯容器構造
和順序容器一樣，關聯容器支援預設構造，拷貝構造以及指定一緻容器疊代器範圍構造三種方式，但與順序容器不同的是，關聯容器不能通過容器大小來定義，因為這樣的話就無法知道鍵所對應的值是什麼。在定義關聯容器時，需要明确指定模闆參數類型，傳入實參，編譯器才能識别及推演：
//
map<int,string> m_vec; //預設構造
m_vec.insert(make_pair(2,"hello")); //insert添加元素
m_vec[1] = "hi"; //下标方式添加元素
map<int,string> m_vec1(m_vec); //拷貝構造
map<int,string> m_vec2(m_vec.begin(),m_vec.end()); //指定疊代器範圍構造
cout << ((m_vec1==m_vec2)?"true":"false") << endl; //true
set<int> i_set;
i_set.insert(100);
i_set.insert(10);
四、 map 和multimap容器的操作
map 和multimap容器是包含在#include <map>标準庫内。
4.1 添加元素操作
定義了 map 容器後，可使用 insert 成員添加鍵－值元素對；或者，先用下标操作符擷取元素，然後給擷取的元素指派。在這兩種情況下，一個給定的鍵隻能對應于一個元素這一事實影響了這些操作的行為。
/*e 是一個用在 m 上的 value_type 類型的值。如果鍵（e.first）不在 m 中，
*則插入一個值為 e.second 的新元素；如果該鍵在 m 中已存在，則保持 m 不變。
*該函數傳回一個pair 類型對象，包含指向鍵為 e.first 的元素的 map 疊代器，
*以及一個 bool 類型的對象，表示是否插入了該元素
*/
m.insert(e)
/*beg 和 end 是标記元素範圍的疊代器，其中的元素必須為m.value_type 類型的鍵－值對。
*對于該範圍内的所有元素，如果它的鍵在 m 中不存在，則将該鍵及其關聯的值插入到 m。傳回 void 類型
*/
m.insert(beg,end)
/*e 是一個用在 m 上的 value_type 類型的值。如果鍵（e.first）不在 m 中，
*則建立新元素，并以疊代器 iter 為起點搜尋新元素存儲的位置。傳回一個疊代器，
*指向 m 中具有給定鍵的元素
*/
m.insert(iter,e)
往map容器添加資料，若存在key相同的，則會保持容器不變，不做調整：
//
m_vec1.insert(make_pair(3,"test"));
cout << "m_vec1.size() = " << m_vec1.size() << endl; //3
m_vec1.insert(m_vec.begin(),m_vec.end());
cout << "m_vec1.size() = " << m_vec1.size() << endl; //3,是以傳入資料key已經存在
map<int,string>::iterator it_mvec = m_vec1.begin();
m_vec1.insert(it_mvec,make_pair(4,"test2"));
cout << "m_vec1.size() = " << m_vec1.size() << endl; //4,是以傳入資料key不存在
//
4.2 元素擷取操作
map容器是鍵－值對的集合。map 類型通常可了解為關聯數組（associativearray）：可使用鍵作為下标來擷取一個值，正如内置數組類型一樣。而關聯的本質在于元素的值與某個特定的鍵相關聯，而并非通過元素在數組中的位置來擷取。同樣，map容器也支援通過疊代器擷取數值。
//
cout << m_vec.begin()->second <<","<< m_vec[2] << endl; //true
但是，使用下标存在一個很危險的副作用：如果該鍵不在 map 容器中，那麼下标操作會插入一個具有該鍵的新元素，即下标為key，預設構造T2()為value。
//
cout << m_vec.begin()->second <<","<< m_vec[2] << endl; //hi,hello
cout << m_vec.begin()->second <<","<< m_vec[3] << endl; //hi, 這是危險行為，因為key==3不存在
4.3 元素查找與确認操作
map 容器提供了兩個操作：count 和 find，用于檢查某個鍵是否存在而不會插入該鍵。
map<int,string> m;
m.count(k) //傳回 m 中 key 的出現次數
m.find(k) //如果 m 容器中存在按 key 索引的元素，則傳回指向該元素的疊代器。如果不存在，則傳回超出末端疊代器
對于 map 對象，count 成員的傳回值隻能是 0 或 1。map 容器隻允許一個鍵對應一個執行個體，是以 count 可有效地表明一個鍵是否存在。而對于 multimaps容器，count 的傳回值[0~N]。
//
map<int,string> m_vec1;
m_vec1.insert(make_pair(1,"test1"));
m_vec1.insert(make_pair(1,"test2"));
cout << "m_vec[1] = " <<","<< m_vec[1] << endl;
cout << "m_vec1.count(1) = " << m_vec1.count(1) << endl; //1
cout << "m_vec1.count(10) = " << m_vec1.count(10) << endl; //0
multimap<int,string> multi_vec;
multi_vec.insert(make_pair(1,"test1"));
multi_vec.insert(make_pair(1,"test2"));
cout << "multi_vec.count(1) = " << multi_vec.count(1) << endl; //2
find 操作傳回指向元素的疊代器，如果元素不存在，則傳回 疊代器end 。
map<int,string>::iterator it_find = m_vec.find(1);
if (it_find != m_vec.end()){
cout << "it_find->second = " << it_find->second << endl; //hi
}
4.4 删除元素操作
從關聯容器map中删除元素，可以通過key值或容器疊代器來删除元素：
map<T1,T2> m;
/*删除 m 中鍵為 k 的元素。傳回 size_type 類型的值，表示删除的元素個數*/
m.erase(k)
/*
*從 m 中删除疊代器 p 所指向的元素。p 必須指向 m 中确實存在的元素，而且不能等于 m.end()。
*傳回 void
*/
m.erase(p) //
/*
*從 m 中删除一段範圍内的元素，該範圍由疊代器對 begin 和 end 标記。
*b 和 e 必須标記 m 中的一段有效範圍：
即 b 和 e 都必須指向 m中的元素或最後一個元素的下一個位置。
而且，b 和 e 要麼相等（此時删除的範圍為空），要麼 b 所指向的元素必須出現在 e 所指向的元素之前。 *傳回 void 類型
*/
m.erase(b,e)//
采用疊代器删除元素時，需要注意疊代器指向是否有效，而通過key值删除元素時，會自動尋找比對到相應的key，然後删除，并傳回删除個數，對于map來說，隻有1或0，而multimap才會傳回多個數量：
cout << "m_vec1.size() = " << m_vec1.size() << endl; //4
/*map<int,string>::iterator*/ it_find = m_vec1.find(2);
if (it_find != m_vec.end()){
m_vec1.erase(it_find);
}
cout << "m_vec1.size() = " << m_vec1.size() << endl; //3
m_vec1.erase(3);// 删除key==3的元素
cout << "m_vec1.size() = " << m_vec1.size() << endl; //2
4.5 容器周遊操作
關聯容器采用疊代器周遊時，和順序容器是一緻的：
//
map<int,string>::iterator it_r = m_vec1.begin();
while (it_r != m_vec1.end())
{
cout << "key = "<< it_r->first<<" "<< "val = "<< it_r->second << endl;
/* code */
it_r++;
}
//
for (it_r = m_vec1.begin();it_r!=m_vec1.end();it_r++)
{
cout << "key = "<< it_r->first<<" "<< "val = "<< it_r->second << endl;
/* code */
}
map容器元素是key/value對出現的，其value是支援變更的，和周遊一樣，value的修改支援通過下标或疊代器指向來修改：
//
m_vec1.begin()->second = "hi->he";
m_vec1[4] = "test2->test_new";
for (it_r = m_vec1.begin();it_r!=m_vec1.end();it_r++)
{
cout << "key = "<< it_r->first<<" "<< "val = "<< it_r->second << endl;
/* code */
}
//out log
key = 1 val = hi->he
key = 4 val = test2->test_new
4.6 自定義類型作為關聯容器模闆參數
關聯式容器依據特定排序準則，自動為其元素排序。排序準則以函數形式呈現，用來比較元素值(value)或元素鍵值(Key)，預設情況下以operator<來比較，使用者也可以提供自己的比較函數，定義出不同的排序準則。在疊代周遊關聯容器時，我們可確定按鍵的順序的通路元素，而與元素在容器中的存放位置完全無關。
例如下面代碼，自定義了KeyObj類型作為map 的key，自定義類型提供map排序準則函數及比較操作符配套的操作符:< > <= >= == !=，為了支援cout輸出，還為自定義類型配套了<<操作符支援。
class KeyObj
{
public:
KeyObj(int pid,int cid):p_id(pid),c_id(cid){};
//
static int cmp_Key(const KeyObj &obj1, const KeyObj &obj2)
{
int diff = obj1.p_id - obj2.p_id;
if (diff != 0)
return diff;
diff = obj1.c_id - obj2.c_id;
if (diff != 0)
return diff;
return 0;
};
int p_id;
int c_id;
private:
};
inline bool operator==(const KeyObj& obj1, const KeyObj& obj2) { return KeyObj::cmp_Key(obj1, obj2) == 0; }
inline bool operator!=(const KeyObj& obj1, const KeyObj& obj2) { return KeyObj::cmp_Key(obj1, obj2) != 0; }
inline bool operator>=(const KeyObj& obj1, const KeyObj& obj2) { return KeyObj::cmp_Key(obj1, obj2) >= 0; }
inline bool operator<=(const KeyObj& obj1, const KeyObj& obj2) { return KeyObj::cmp_Key(obj1, obj2) <= 0; }
inline bool operator>(const KeyObj& obj1, const KeyObj& obj2) { return KeyObj::cmp_Key(obj1, obj2) > 0; }
inline bool operator<(const KeyObj& obj1, const KeyObj& obj2) { return KeyObj::cmp_Key(obj1, obj2) < 0; }
inline std::ostream &operator<<(std::ostream &os, const KeyObj& obj)
{
os << "(";
os << obj.p_id << "," << obj.c_id;
os <<")";
return os;
};
//
map<KeyObj,string> mykey_Vec;
mykey_Vec.insert(make_pair(KeyObj(1,2),"test12"));
mykey_Vec.insert(make_pair(KeyObj(2,2),"test22"));
mykey_Vec.insert(make_pair(KeyObj(1,3),"test13"));
mykey_Vec.insert(make_pair(KeyObj(2,1),"test21"));
map<KeyObj,string>::iterator it_mykey;
for (it_mykey = mykey_Vec.begin();it_mykey!=mykey_Vec.end();it_mykey++)
{
cout << "key = "<< it_mykey->first<<" "<< "val = "<< it_mykey->second << endl;
/* code */
}
//out log
key = (1,2) val = test12
key = (1,3) val = test13
key = (2,1) val = test21
key = (2,2) val = test22
五、set和multiset容器操作
相比起map是鍵/值的集合，set 容器隻是單純的鍵的集合。set 容器支援大部分的 map 操作，像前面論述過的關于map的構造、插入與删除、疊代與周遊、計數與查找等。但又與map有些例外，如set 不支援下标操作符，而且沒有定義 mapped_type 類型。在 set 容器中，value_type 不是 pair 類型，而是與 key_type 相同的類型。它們指的都是 set 中存儲的元素類型。這一差别也展現了 set 存儲的元素僅僅是鍵，而沒有所關聯的值。與 map 一樣，set 容器存儲的鍵也必須唯一，而且不能修改。
5.1 構造、插入元素、周遊相關操作
set 容器，包含 <set> 頭檔案。set 支援的操作基本上與 map提供的相同。set容器支援預設構造及指定疊代器範圍構造，也支援直接插入key和通過疊代器指向插入資料。
//
set<int> ::iterator it_set;
vector<int> ivec;
for (vector<int>::size_type i = 0; i != 10; ++i) {
ivec.push_back(i);
ivec.push_back(i); // duplicate copies of each number
}
set<int> i_set1(ivec.begin(),ivec.end());
for (it_set = i_set1.begin();it_set!=i_set1.end();it_set++)
{
cout << "key = "<< *it_set << " ";
}
cout << "\n";
cout << "i_set1.size() = " << (int)i_set1.size() << endl;//size = 10
//
set<int> i_set;
i_set.insert(100);
i_set.insert(10);
i_set.insert(ivec.begin(),ivec.begin()+1);
for (it_set = i_set.begin();it_set!=i_set.end();it_set++)
{
cout << "key = "<< *it_set << " ";
}
cout << "\n";
5.2 元素查找與确認操作
set 容器不提供下标操作符。為了通過鍵從 set 中擷取元素，可使用 find運算。如果隻需簡單地判斷某個元素是否存在，同樣可以使用 count 運算，傳回 set 中該鍵對應的元素個數。當然，對于 set 容器，count 的傳回值隻能是1（該元素存在）或 0（該元素不存在）。 set 中的鍵也為 const。在獲得指向 set 中某元素的疊代器後，隻能對其做讀操作，而不能做寫操作。
//
it_set = i_set.find(10);
if(it_set != i_set.end())
{
cout << "find_key = "<< *it_set << endl;
//*it_set = 1000; //error
}
cout << "i_set.count(1) = " << i_set.count(1) << endl; //0
cout << "i_set.count(10) = " << i_set.count(10) << endl; //1
5.3 自定義類型作為容器模闆參數
set容器支援通過疊代器周遊整個容器。同樣地，set容器也支援自定義類型作為模闆參數類型，例如将前面自定義的KeyObj傳遞給set容器：
//
set<KeyObj> mykey_set;
mykey_set.insert(KeyObj(1,2));
mykey_set.insert(KeyObj(2,2));
mykey_set.insert(KeyObj(1,3));
mykey_set.insert(KeyObj(2,1));
set<KeyObj>::iterator itset_mykey;
//周遊及os輸出
for (itset_mykey = mykey_set.begin();itset_mykey!=mykey_set.end();itset_mykey++)
{
cout << "key = "<< *itset_mykey << " ";
}
cout << "\n";
六、multimap 和 multiset 的特殊性
map 和 set 容器中，一個鍵隻能對應一個執行個體。而 multiset 和 multimap類型則允許一個鍵對應多個執行個體。multimap和 multiset 類型與相應的單元素版本具有相同的頭檔案定義：分别是 map 和set 頭檔案。
6.1 添加、删除、周遊重複元素支援
multimap 和 multiset 所支援的操作分别與 map 和 set 的操作相同，隻有一個例外：multimap 不支援下标運算。不能對 multimap 對象使用下标操作，因為在這類容器中，某個鍵可能對應多個值。為了順應一個鍵可以對應多個值這一性質，map 和 multimap，或 set 和 multiset 中相同的操作都以不同的方式做出了一定的修改。在使用 multimap 或 multiset 時，對于某個鍵，必須做好處理多個值的準備，而非隻有單一的值。
//
multimap<int,string> multi_vec;
multi_vec.insert(make_pair(1,"test1"));
multi_vec.insert(make_pair(1,"test2"));
cout << "multi_vec.count(1) = " << multi_vec.count(1) << endl; //2
//
multiset<KeyObj> mykey_mset;
mykey_mset.insert(KeyObj(1,2));
mykey_mset.insert(KeyObj(1,2));
mykey_mset.insert(KeyObj(2,2));
cout << "mykey_mset.count(KeyObj(1,2)) = " << mykey_mset.count(KeyObj(1,2)) << endl; //2
mykey_mset.erase(KeyObj(1,2));//當然删除時,指定key一并删除
cout << "mykey_mset.count(KeyObj(1,2)) = " << mykey_mset.count(KeyObj(1,2)) << endl; //0
關聯容器 map 和 set 的元素是按順序存儲的。而 multimap 和multset 也一樣。是以，在 multimap 和 multiset 容器中，如果某個鍵對應多個執行個體，則這些執行個體在容器中将相鄰存放。疊代周遊 multimap 或 multiset 容器時，可保證依次傳回特定鍵所關聯的所有元素。
multiset<KeyObj>::iterator it_mykey_mset;
for (it_mykey_mset = mykey_mset.begin();it_mykey_mset!=mykey_mset.end(); it_mykey_mset++)
{
cout << "key = "<< *it_mykey_mset << " ";
}
cout << "\n";
//out log
key = (1,2) key = (1,2) key = (2,2)
6.2 重複元素特定通路政策
在 map 或 set 容器中查找一個元素很簡單——該元素要麼在要麼不在容器中。但對于 multimap 或 multiset，該過程就複雜多了：某鍵對應的元素可能出現多次。對此，标準庫給出了三種政策解決。而且三種政策都基于一個事實：在 multimap 中，同一個鍵所關聯的元素必然相鄰存放。
政策1，調用 count 确定某key數目，然後調用 find 獲得指向第一個該鍵所關聯的元素的疊代器。for 循環疊代的次數依賴于 count 傳回的值。在特殊情況下，如果 count 傳回 0 值，則該循環永不執行。
multi_vec.insert(make_pair(2,"test3"));
multi_vec.insert(make_pair(2,"test4"));
typedef multimap<int, string>::size_type map_size;
typedef multimap<int,string>::iterator map_iter;
map_size mvec_size = multi_vec.count(2);
map_iter iter = multi_vec.find(2);
for (map_size cnt = 0; cnt != mvec_size; ++cnt, ++iter)
{
cout << "key = "<< iter->first<<" "<< "val = "<< iter->second << endl;
}
//out log
key = 2 val = test3
key = 2 val = test4
政策2，采用關聯容器的一種新操作：lower_bound 和 upper_bound。如下文列出的這些操作适用于所有的關聯容器，也可用于普通的 map 和 set 容器，但更常用于 multimap 和 multiset。
所有這些操作都需要傳遞一個鍵，并傳回一個疊代器。
m.lower_bound(k) //傳回一個疊代器，指向鍵不小于 k 的第一個元素
m.upper_bound(k) //傳回一個疊代器，指向鍵大于 k 的第一個元素
m.equal_range(k) //傳回一個疊代器的 pair 對象，它的 first 成員等價于 m.lower_bound(k)。而 second 成員則等價于 m.upper_bound(k)
在同一個鍵上調用 lower_bound 和 upper_bound，将産生一個疊代器範圍，訓示出該鍵所關聯的所有元素。如果該鍵在容器中存在，則會獲得兩個不同的疊代器：lower_bound 傳回的疊代器指向該鍵關聯的第一個執行個體，而 upper_bound 傳回的疊代器則指向最後一個執行個體的下一位置。如果該鍵不在 multimap 中，這兩個操作将傳回同一個疊代器，指向依據元素的排列順序該鍵應該插入的位置。
//
map_iter iter_start = multi_vec.lower_bound(2);
map_iter iter_end = multi_vec.upper_bound(2);
while (iter_start!=iter_end)
{
cout << "key = "<< iter_start->first<<" "<< "val = "<< iter_start->second << endl;
/* code */
iter_start++;
}
//out log
key = 2 val = test3
key = 2 val = test4
政策三，調用 equal_range 函數來取代調用 upper_bound 和 lower_bound 函數。equal_range 函數傳回存儲一對疊代器的 pair 對象。如果該值存在，則 pair 對象中的第一個疊代器(first)指向該鍵關聯的第一個執行個體，第二個疊代器(second)指向該鍵關聯的最後一個執行個體的下一位置。如果找不到比對的元素，則 pair 對象中的兩個疊代器都将指向此鍵應該插入的位置。
//
pair<map_iter, map_iter> pos_range = multi_vec.equal_range(2);
while (pos_range.first!=pos_range.second)
{
cout << "key = "<< pos_range.first->first<<" "<< "val = "<< pos_range.first->second << endl;
/* code */
pos_range.first++;
}
//out log
key = 2 val = test3
key = 2 val = test4
7、測試與源代碼
7.1 關聯容器綜述
關聯容器支援通過鍵高效地查找和讀取元素。鍵的使用，使關聯容器差別于順序容器，順序容器的元素是根據位置通路的。
map 和 multimap 類型存儲的元素是鍵－值對。它們使用在 utility 頭檔案中定義的标準庫 pair 類，來表示這些鍵－值對元素。對 map 或 multimap 疊代器進行解引用将獲得 pair 類型的值。pair 對象的 first 成員是一個 const鍵，而 second 成員則是該鍵所關聯的值。
set 和 multiset 類型則專門用于存儲鍵。在 map 和 set 類型中，一個鍵隻能關聯一個元素。而 multiset 類型則允許多個元素擁有相同的鍵。
關聯容器共享了順序容器的許多操作，并還定義一些新操作，并對某些順序容器同樣提供的操作重新定義了其含義或傳回類型，這些操作的差别展現了關聯容器中鍵的使用。關聯容器的元素可用疊代器通路。标準庫保證疊代器按照鍵的次序通路元素。begin 操作将獲得擁有最小鍵的元素，對此疊代器作自增運算則可以按非降序依次通路各個元素。
7.2 編譯及測試
建立test.h/cpp源檔案，通過g++ test.cpp - test.exe編譯，運作輸出程式：
7.3 測試源代碼
test.h
#ifndef _TEST_H_
#define _TEST_H_
#include <string>
#include <vector>
#include <utility>
#include <iostream>
#include <ostream>
#include <map>
#include <set>
class KeyObj
{
public:
KeyObj(int pid,int cid):p_id(pid),c_id(cid){};
//
static int cmp_Key(const KeyObj &obj1, const KeyObj &obj2)
{
int diff = obj1.p_id - obj2.p_id;
if (diff != 0)
return diff;
diff = obj1.c_id - obj2.c_id;
if (diff != 0)
return diff;
return 0;
};
int p_id;
int c_id;
private:
};
inline bool operator==(const KeyObj& obj1, const KeyObj& obj2) { return KeyObj::cmp_Key(obj1, obj2) == 0; }
inline bool operator!=(const KeyObj& obj1, const KeyObj& obj2) { return KeyObj::cmp_Key(obj1, obj2) != 0; }
inline bool operator>=(const KeyObj& obj1, const KeyObj& obj2) { return KeyObj::cmp_Key(obj1, obj2) >= 0; }
inline bool operator<=(const KeyObj& obj1, const KeyObj& obj2) { return KeyObj::cmp_Key(obj1, obj2) <= 0; }
inline bool operator>(const KeyObj& obj1, const KeyObj& obj2) { return KeyObj::cmp_Key(obj1, obj2) > 0; }
inline bool operator<(const KeyObj& obj1, const KeyObj& obj2) { return KeyObj::cmp_Key(obj1, obj2) < 0; }
inline std::ostream &operator<<(std::ostream &os, const KeyObj& obj)
{
os << "(";
os << obj.p_id << "," << obj.c_id;
os <<")";
return os;
};
#endif //_TEST_H_
test.cpp
#include "test.h"
using namespace std;
int main(int argc, char* argv[])
{
pair<string, string> anon; // holds two strings
pair<string, int> word_count; // holds a string and an int
pair<string, vector<int> > line; // holds string and vecto
//
pair<string, string> anons("hi","hello"); // holds two strings
pair<string, int> word_counts("hi",100); // holds a string and an int
vector<int> i_vec = {1,2,3};
pair<string, vector<int> > lines("hi",i_vec); // holds string and vecto
//
anon = make_pair<string, string>("hi","hello");
cout << ((anon==anons)?"true":"false") << endl;
//
cout << anon.first <<","<< anon.second << endl;
//
typedef pair<int,int> IPair;
vector<IPair> p_i_vecs;
int vecs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
for (int i=0; i<4; i++)
{
p_i_vecs.push_back(make_pair(vecs[i][0],vecs[i][1]));
}
//
map<int,string> m_vec; //預設構造
m_vec.insert(make_pair(2,"hello"));
m_vec[1] = "hi"; //下标方式添加元素
map<int,string> m_vec1(m_vec); //拷貝構造
map<int,string> m_vec2(m_vec.begin(),m_vec.end()); //指定疊代器範圍構造
cout << ((m_vec1==m_vec2)?"true":"false") << endl; //true
//
m_vec1.insert(make_pair(3,"test"));
cout << "m_vec1.size() = " << m_vec1.size() << endl; //3
m_vec1.insert(m_vec.begin(),m_vec.end());
cout << "m_vec1.size() = " << m_vec1.size() << endl; //3,是以傳入資料key已經存在
map<int,string>::iterator it_mvec = m_vec1.begin();
m_vec1.insert(it_mvec,make_pair(4,"test2"));
cout << "m_vec1.size() = " << m_vec1.size() << endl; //4,是以傳入資料key不存在
//
cout << m_vec.begin()->second <<","<< m_vec[2] << endl; //hi.hello
cout << m_vec.begin()->second <<","<< m_vec[3] << endl; //hi,
//
cout << "m_vec1.count(1) = " << m_vec1.count(1) << endl; //1
cout << "m_vec1.count(10) = " << m_vec1.count(10) << endl; //0
//
map<int,string>::iterator it_find = m_vec.find(1);
if (it_find != m_vec.end()){
cout << "it_find->second = " << it_find->second << endl; //hi
}
//
cout << "m_vec1.size() = " << m_vec1.size() << endl; //4
/*map<int,string>::iterator*/ it_find = m_vec1.find(2);
if (it_find != m_vec.end()){
m_vec1.erase(it_find);
}
cout << "m_vec1.size() = " << m_vec1.size() << endl; //3
m_vec1.erase(3);
cout << "m_vec1.size() = " << m_vec1.size() << endl; //2
//
map<int,string>::iterator it_r = m_vec1.begin();
while (it_r != m_vec1.end())
{
cout << "key = "<< it_r->first<<" "<< "val = "<< it_r->second << endl;
/* code */
it_r++;
}
for (it_r = m_vec1.begin();it_r!=m_vec1.end();it_r++)
{
cout << "key = "<< it_r->first<<" "<< "val = "<< it_r->second << endl;
/* code */
}
//
m_vec1.begin()->second = "hi->he";
m_vec1[4] = "test2->test_new";
for (it_r = m_vec1.begin();it_r!=m_vec1.end();it_r++)
{
cout << "key = "<< it_r->first<<" "<< "val = "<< it_r->second << endl;
/* code */
}
//
map<KeyObj,string> mykey_Vec;
mykey_Vec.insert(make_pair(KeyObj(1,2),"test12"));
mykey_Vec.insert(make_pair(KeyObj(2,2),"test22"));
mykey_Vec.insert(make_pair(KeyObj(1,3),"test13"));
mykey_Vec.insert(make_pair(KeyObj(2,1),"test21"));
map<KeyObj,string>::iterator it_mykey;
for (it_mykey = mykey_Vec.begin();it_mykey!=mykey_Vec.end();it_mykey++)
{
cout << "key = "<< it_mykey->first<<" "<< "val = "<< it_mykey->second << endl;
/* code */
}
//
set<int> ::iterator it_set;
vector<int> ivec;
for (vector<int>::size_type i = 0; i != 10; ++i) {
ivec.push_back(i);
ivec.push_back(i); // duplicate copies of each number
}
set<int> i_set1(ivec.begin(),ivec.end());
for (it_set = i_set1.begin();it_set!=i_set1.end();it_set++)
{
cout << "key = "<< *it_set << " ";
}
cout << "\n";
cout << "i_set1.size() = " << (int)i_set1.size() << endl;
//
set<int> i_set;
i_set.insert(100);
i_set.insert(10);
i_set.insert(ivec.begin(),ivec.begin()+1);
for (it_set = i_set.begin();it_set!=i_set.end();it_set++)
{
cout << "key = "<< *it_set << " ";
}
cout << "\n";
//
it_set = i_set.find(10);
if(it_set != i_set.end())
{
cout << "find_key = "<< *it_set << endl;
//*it_set = 1000; //error
}
cout << "i_set.count(1) = " << i_set.count(1) << endl; //0
cout << "i_set.count(10) = " << i_set.count(10) << endl; //1
//
set<KeyObj> mykey_set;
mykey_set.insert(KeyObj(1,2));
mykey_set.insert(KeyObj(2,2));
mykey_set.insert(KeyObj(1,3));
mykey_set.insert(KeyObj(1,3));
mykey_set.insert(KeyObj(2,1));
set<KeyObj>::iterator itset_mykey;
for (itset_mykey = mykey_set.begin();itset_mykey!=mykey_set.end();itset_mykey++)
{
cout << "key = "<< *itset_mykey << " ";
}
cout << "\n";
//
multimap<int,string> multi_vec;
multi_vec.insert(make_pair(1,"test1"));
multi_vec.insert(make_pair(1,"test2"));
cout << "multi_vec.count(1) = " << multi_vec.count(1) << endl; //2
multi_vec.insert(make_pair(2,"test3"));
multi_vec.insert(make_pair(2,"test4"));
typedef multimap<int, string>::size_type map_size;
typedef multimap<int,string>::iterator map_iter;
map_size mvec_size = multi_vec.count(2);
map_iter iter = multi_vec.find(2);
for (map_size cnt = 0; cnt != mvec_size; ++cnt, ++iter)
{
cout << "key = "<< iter->first<<" "<< "val = "<< iter->second << endl;
}
//
map_iter iter_start = multi_vec.lower_bound(2);
map_iter iter_end = multi_vec.upper_bound(2);
while (iter_start!=iter_end)
{
cout << "key = "<< iter_start->first<<" "<< "val = "<< iter_start->second << endl;
/* code */
iter_start++;
}
//
pair<map_iter, map_iter> pos_range = multi_vec.equal_range(2);
while (pos_range.first!=pos_range.second)
{
cout << "key = "<< pos_range.first->first<<" "<< "val = "<< pos_range.first->second << endl;
/* code */
pos_range.first++;
}
//
multiset<KeyObj> mykey_mset;
mykey_mset.insert(KeyObj(1,2));
mykey_mset.insert(KeyObj(1,2));
mykey_mset.insert(KeyObj(2,2));
cout << "mykey_mset.count(KeyObj(1,2)) = " << mykey_mset.count(KeyObj(1,2)) << endl; //2
multiset<KeyObj>::iterator it_mykey_mset;
for (it_mykey_mset = mykey_mset.begin();it_mykey_mset!=mykey_mset.end();it_mykey_mset++)
{
cout << "key = "<< *it_mykey_mset << " ";
}
cout << "\n";
mykey_mset.erase(KeyObj(1,2));
cout << "mykey_mset.count(KeyObj(1,2)) = " << mykey_mset.count(KeyObj(1,2)) << endl; //0
return 0;
};
![C語言第四章自述2第四章 選擇結構程式設計[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)