一、关联容器简述
容器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=)