(十四)C++篇-关联容器map和set

关联容器和顺序容器的本质差别在于：关联容器通过键（key）存储和读取元素，而顺序容器则通过元素在容器中的位置顺序存储和访问元素。

关联容器（Associative containers） 支持通过键来高效地查找和读取元素。两个基本的关联容器类型是 map set。map 的元素以键－值（key-value）对的形式组织：键用作元素在 map 中的索引，而值则表示所存储和读取的数据。set仅包含一个键，并有效地支持关于某个键是否存在的查询。

一般来说，如果希望有效地存储不同值的集合，那么使用 set 容器比较合适，而 map 容器则更适用于需要存储（乃至修改）每个键所关联的值的情况。在做某种文本处理时，可使用 set 保存要忽略的单词。而字典则是 map 的一种很好的应用：单词本身是键，而它的解释说明则是值。

set 和 map 类型的对象所包含的元素都具有不同的键，不允许为同一个键添加第二个元素。如果一个键必须对应多个实例，则需使用 multimap 或 multiset，这两种类型允许多个元素拥有相同的键。

1，关联容器类型

类型	定义
map	关联数组：元素通过键来存储和读取
set	大小可变的集合，支持通过键实现的快速读取
multimap	支持同一个键多次出现的 map 类型
multiset	支持同一个键多次出现的 set 类型

pairs：在 utility 头文件中定义
pairs 类型提供的操作

函数	定义
pair<T1, T2> p1;	创建一个空的 pair 对象，它的两个元素分别是 T1 和 T2 类型，采用值初始化
pair<T1, T2> p1(v1, v2);	创建一个 pair 对象，它的两个元素分别是 T1 和 T2 ，其中 first 成员初始化为 v1，而 second 成员初始化为 v2
make_pair(v1,v2)	以 v1 和 v2 值创建一个新 pair 对象， 其元素类型分别是v1 和 v2 的类型
p1 < p2	两个 pair 对象之间的小于运算，其定义遵循字典次序：如果 p1.first < p2.first 或者 !(p2.first < p1.first) && p1.second < p2.second，则返回 true
p1 == p2	如果两个 pair 对象的 first 和 second 成员依次相等，则这两个对象相等。该运算使用其元素的 == 操作符
p.first	返回 p 中名为 first 的（公有）数据成员
p.second	返回 p 的名为 second 的（公有）数据成员

2，map 的构造函数

函数	定义
map<k, v> m;	创建一个名为 m 的空 map 对象， 其键和值的类型分别为 k 和 v
map<k, v> m(m2);	创建 m2 的副本 m，m 与 m2 必须有相同的键类型和值类型
map<k, v> m(b, e);	创建 map 类型的对象 m， 存储迭代器 b 和 e 标记的范围内所有元素的副本。元素的类型必须能转换为 pair<const k, v>

在 map 的接口时，需谨记 value_type 是 pair 类型，它的值成员可以修改，但键成员不能修改。

3，map 类定义的类型

函数	定义
map<K,V>::key_type	在 map 容器中，用做索引的键的类型
map<K,V>::mapped_type	在 map 容器中，键所关联的值的类型
map<K,V>::value_type	一个 pair 类型，它的 first 元素具有 const map<K,V>::key_type 类型，而 second 元素则为 map<K,V>::mapped_type 类型

4，map 容器提供的 insert 操作

函数	定义
m.insert(e)	e 是一个用在 m 上的 value_type 类型的值。如果键（e.first）不在 m 中， 则插入一个值为 e.second 的新元素；如果该键在 m 中已存在，则保持 m 不变。该函数返回一个pair 类型对象，包含指向键为 e.first 的元素的 map 迭代器，以及一个 bool 类型的对象，表示是否插入了该元素
m.insert(beg,end)	beg 和 end 是标记元素范围的迭代器，其中的元素必须为m.value_type 类型的键－值对。对于该范围内的所有元素，如果它的键在 m 中不存在， 则将该键及其关联的值插入到 m。返回 void 类型
m.insert(iter,e)	e 是一个用在 m 上的 value_type 类型的值。如果键（e.first）不在 m 中，则创建新元素，并以迭代器 iter 为起点搜索新元素存储的位置。返回一个迭代器，指向 m 中具有给定键的元素

5，查找并读取 map 中的元素

下标操作符给出了读取一个值的最简单方法：
map<string,int> word_count;
int occurs = word_count["foobar"];
但是，使用下标存在一个很危险的副作用：如果该键不在 map 容器中，那
么下标操作会插入一个具有该键的新元素。

不修改 map 对象的查询操作

函数	定义
m.count(k)	返回 m 中 k 的出现次数
m.find(k)	如果 m 容器中存在按 k 索引的元素，则返回指向该元素的迭代器。如果不存在，则返回超出末端迭代器

6，从 map 对象中删除元素

erase 函数返回被删除元素的个数。对于 map 容器，该值必然是 0 或 1。
如果返回 0，则表示欲删除的元素在 map 不存在。

函数	定义
m.erase(k)	删除 m 中键为 k 的元素。返回 size_type 类型的值，表示删除的元素个数
m.erase(p)	从 m 中删除迭代器 p 所指向的元素。p 必须指向 m 中确实存在的元素，而且不能等于 m.end()。返回 void
m.erase(b,e)	从 m 中删除一段范围内的元素， 该范围由迭代器对 b 和 e 标记。b 和 e 必须标记 m 中的一段有效范围： 即 b 和 e 都必须指向 m中的元素或最后一个元素的下一个位置。而且，b 和 e 要么相等（此时删除的范围为空），要么 b 所指向的元素必须出现在 e 所指向的元素之前。返回 void 类型

7，multimap 和 multiset 类型

map 和 set 容器中，一个键只能对应一个实例。而 multiset 和 multimap类型则允许一个键对应多个实例。例如，在电话簿中，每个人可能有单独的电话号码列表。在作者的文章集中，每位作者可能有单独的文章标题列表。multimap和 multiset 类型与相应的单元素版本具有相同的头文件定义：分别是 map 和set 头文件。

返回迭代器的关联容器操作

函数	定义
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)

关联容器共享了顺序容器的许多操作。除此之外，关联容器还定义一些新操作，并对某些顺序容器同样提供的操作重新定义了其含义或返回类型，这些操作的差别体现了关联容器中键的使用。

关联容器的元素可用迭代器访问。标准库保证迭代器按照键的次序访问元素。begin 操作将获得拥有最小键的元素，对此迭代器作自增运算则可以按非降序依次访问各个元素。

测试代码(map)：

#include <iostream>
#include <map>
using namespace std;

int main()
{
    map<string, int> word_count;
    string word;
    cout << word_count["Anna"]<<endl; // print 0
    ++word_count["Anna"];
    cout << word_count["Anna"] << endl; // print 1
    return 0;
}

测试代码(set)：

#include<stdio.h>
#include<set>
using namespace std;
int main()
{
    set<int> st;
    for (int i = 1; i <= 5; i++)
    {
        st.insert(i);
    }
    for (set<int>::iterator it = st.begin(); it != st.end(); it++)
    {
        printf("%d ", *it);
    }
    printf("\r\n");
    return 0;
}

输出结果：

tekken@tekken:~/C++WS$ ./a.out 
1 2 3 4 5 

测试代码(mutimap)：

第一种输入表示要添加一个学生的信息，碰到这种输入，就记下学生的姓名、id 和分数。
第二种输入表示要查询分数为 score 的学生的信息，碰到这种输入，就输出已有记录中分数比查询分数低的最高分获得者的姓名、学号和分数。如果有多个学生满足条件，则输出学号最大的学生的信息。如果找不到满足条件的学生，则输出“Nobody”。

#include <iostream>
#include <map>  //使用multimap需要包含此头文件
#include <string>
using namespace std;
class CStudent
{
public:
    struct CInfo  //类的内部还可以定义类
    {
        int id;
        string name;
    };
    int score;
    CInfo info;  //学生的其他信息
};
typedef multimap <int, CStudent::CInfo> MAP_STD;
int main()
{
    MAP_STD mp;
    CStudent st;
    string cmd;
    while (cin >> cmd) 
    {
        if (cmd == "Add") 
        {
            cin >> st.info.name >> st.info.id >> st.score;
            mp.insert(MAP_STD::value_type(st.score, st.info));
        }
        else if (cmd == "Query") 
        {
            int score;
            cin >> score;
            MAP_STD::iterator p = mp.lower_bound(score);
            if (p != mp.begin()) 
            {
                --p;
                score = p->first;  //比要查询分数低的最高分
                MAP_STD::iterator maxp = p;
                int maxId = p->second.id;
                for (; p != mp.begin() && p->first == score; --p) 
                {
                    //遍历所有成绩和score相等的学生
                    if (p->second.id > maxId) 
                    {
                        maxp = p;
                        maxId = p->second.id;
                    }
                }
                if (p->first == score) 
                { //如果上面的循环因为 p == mp.begin()
                    //而终止，则p指向的元素还要处理
                    if (p->second.id > maxId) 
                    {
                        maxp = p;
                        maxId = p->second.id;
                    }
                }
                cout << maxp->second.name << " " << maxp->second.id << " "<< maxp->first << endl;
            }
            else  //lower_bound 的结果就是 begin，说明没有分数比查询分数低
                cout << "Nobody" << endl;
        }
    }
    return 0;
}

输入案例：

Add Jack 12 78
Query 78
Query 81
Add Percy 9 81
Add Marry 8 81
Query 82
Add Tom 11 79
Query 80
Query 81

输出结果：

Nobody
Jack 12 78
Percy 9 81
Tom 11 79
Tom 11 79

测试代码(mutiset)：

#include <iostream>
#include <set>  //使用multiset须包含此头文件
using namespace std;
template <class T>
void Print(T first, T last)
{
    for (; first != last; ++first)
    cout << *first << " ";
    cout << endl;
}
class A
{
private:
    int n;
public:
    A(int n_) { n = n_; }
    friend bool operator < (const A & a1, const A & a2)
    { return a1.n < a2.n; }
    friend ostream & operator << (ostream & o, const A & a2)
    { o << a2.n; return o; }
    friend class MyLess;
};
class MyLess
{
public:
    bool operator() (const A & a1, const A & a2)  //按个位数比较大小
    { return (a1.n % 10) < (a2.n % 10); }
};
typedef multiset <A> MSET1;  //MSET1 用“<”运算符比较大小
typedef multiset <A, MyLess> MSET2;  //MSET2 用 MyLess::operator() 比较大小
int main()
{
    const int SIZE = 6;
    A a[SIZE] = { 4, 22, 19, 8, 33, 40 };
    MSET1 m1;
    m1.insert(a, a + SIZE);
    m1.insert(22);
    cout << "1)" << m1.count(22) << endl;  //输出 1)2
    cout << "2)"; Print(m1.begin(), m1.end());  //输出 2)4 8 19 22 22 33 40
    MSET1::iterator pp = m1.find(19);
    if (pp != m1.end())  //条件为真说明找到
        cout << "found" << endl;  //本行会被执行，输出 found
    cout << "3)"; cout << *m1.lower_bound(22)<< "," << *m1.upper_bound(22) << endl; //输出 3)22,33
    pp = m1.erase(m1.lower_bound(22), m1.upper_bound(22));
    //pp指向被删元素的下一个元素
    cout << "4)"; Print(m1.begin(), m1.end());  //输出 4)4 8 19 33 40
    cout << "5)"; cout << *pp << endl;  //输出 5)33
    MSET2 m2;  //m2中的元素按n的个位数从小到大排序
    m2.insert(a, a + SIZE);
    cout << "6)"; Print(m2.begin(), m2.end());  //输出 6)40 22 33 4 8 19
    return 0;
}

输出结果：

tekken@tekken:~/C++WS$ ./a.out 
1)2
2)4 8 19 22 22 33 40 
found
3)22,33
4)4 8 19 33 40 
5)33
6)40 22 33 4 8 19