关联容器的特点和接口

关联容器的特点

• 每个关联容器都有一个键(key)
• 可以根据键高效地查找元素

接口

• 插入：insert
• 删除：erase
• 查找：find
• 定界：lower_bound、upper_bound、equal_range
• 计数：count

关联容器概念图

四种关联容器

单重关联容器(set和map)

• 键值是唯一的，一个键值只能对应一个元素

多重关联容器(multiset和multimap)

• 键值是不唯一的，一个键值可以对应多个元素

简单关联容器(set和multiset)

• 容器只有一个类型参数，如set、multiset，表示键类型
• 容器的元素就是键本身

二元关联容器(map和multimap)

• 容器有两个类型参数，如map、multimap，分别表示键和附 加数据的类型
• 容器的元素类型是pair，即由键类型和元素类型复合而成的二元组

无序关联容器

• C++11新标准中定义了4个无序关联容器
  • unordered_set 、 unordered_map 、 unordered_multiset 、 unordered_multimap
• 不是使用比较运算符来组织元素的，而是通过一个哈希函数和键类型的==运算符。
• 提供了与有序容器相同的操作
• 可以直接定义关键字是内置类型的无序容器。
• 不能直接定义关键字类型为自定义类的无序容器，如果需要，必须提供我们自己的 hash模板。

集合（set）

集合用来存储一组无重复的元素。由于集合的元素本身是有序的，可以高效地查找指定元素，也可以方便地得到指定大小范围的元素在容器中所处的区间。

例10-9

输入一串实数，将重复的去掉，取最大和最小者的中值，分别输出小于等于此中值和大于等于此中值的实数

//10_9.cpp 本程序并不安全，如果用户直接输入零，集合为空，后续访问*iter1时会导致未定义行为
#include <set>
#include <iterator>
#include <utility>
#include <iostream>
using namespace std;

int main() {
    set<double> s;
    while (true) {
        double v;
        cin >> v;
        if (v == 0) break;  //输入0表示结束
        //尝试将v插入
       pair<set<double>::iterator,bool> r=s.insert(v); 
        if (!r.second)  //如果v已存在，输出提示信息
           cout << v << " is duplicated" << endl;
    }
  //得到第一个元素的迭代器
    set<double>::iterator iter1=s.begin();
    //得到末尾的迭代器
    set<double>::iterator iter2=s.end();    
  //得到最小和最大元素的中值    
    double medium=(*iter1 + *(--iter2)) / 2;    
    //输出小于或等于中值的元素
    cout<< "<= medium: "
    copy(s.begin(), s.upper_bound(medium), ostream_iterator<double>(cout, " "));
    cout << endl;
    //输出大于或等于中值的元素
    cout << ">= medium: ";
    copy(s.lower_bound(medium), s.end(), ostream_iterator<double>(cout, " "));
    cout << endl;
    return 0;
}

映射（map）

• 映射与集合同属于单重关联容器，它们的主要区别在于，集合的元素类型是键本身，而映射的元素类型是由键和附加数据所构成的二元组。

• 在集合中按照键查找一个元素时，一般只是用来确定这个元素是否存在，而在映射中按照键查找一个元素时，除了能确定它的存在性外，还可以得到相应的附加数据。

例10-10

有五门课程，每门都有相应学分，从中选择三门，输出学分总和

//10_10.cpp
#include <iostream>
#include <map>
#include <string>
#include <utility>
using namespace std;
int main() {
    map<string, int> courses;
    //将课程信息插入courses映射中
    courses.insert(make_pair("CSAPP", 3));
    courses.insert(make_pair("C++", 2));
    courses.insert(make_pair("CSARCH", 4));
    courses.insert(make_pair("COMPILER", 4));
    courses.insert(make_pair("OS", 5));
    int n = 3;      //剩下的可选次数
    int sum = 0;    //学分总和
    while (n > 0) {
        string name;
        cin >> name;    //输入课程名称
        map<string, int>::iterator iter = courses.find(name);//查找课程
        if (iter == courses.end()) {    //判断是否找到
            cout << name << " is not available" << endl;
        } else {
            sum += iter->second;    //累加学分
            courses.erase(iter);    //将刚选过的课程从映射中删除
            n--;
        }
    }
    cout << "Total credit: " << sum << endl;    //输出总学分
    return 0;
}
运行结果如下：
C++
COMPILER
C++
C++ is not available
CSAPP
Total credit: 9

例10-11

统计一句话中每个字母出现的次数

// 10_11.cpp
#include <iostream>
#include <map>
#include <cctype>
using namespace std;
int main() {
    map<char, int> s;   //用来存储字母出现次数的映射
    char c;     //存储输入字符
    do {
      cin >> c; //输入下一个字符
      if (isalpha(c)){ //判断是否是字母
          c = tolower(c); //将字母转换为小写
          s[c]++;      //将该字母的出现频率加1
      }
    } while (c != '.'); //碰到“.”则结束输入
    //输出每个字母出现次数
    for (map<char, int>::iterator iter = s.begin(); iter != s.end(); ++iter)
        cout << iter->first << " " << iter->second << "  ";
    cout << endl;
    return 0;
}

 多重集合与多重映射

• 多重集合是允许有重复元素的集合，多重映射是允许一个键对应多个附加数据的映射。
• 多重集合与集合、多重映射与映射的用法差不多，只在几个成员函数上有细微差异， 其差异主要表现在去除了键必须唯一的限制。

 例 10-12 上课时间查询

//10_12.cpp 
#include <iostream> 
#include <map> 
#include <utility> 
#include <string> 
using namespace std; 
int main() { 
 multimap<string, string> courses; 
 typedef multimap<string, string>::iterator CourseIter; 
 //将课程上课时间插入courses映射中 
 courses.insert(make_pair("C++", "2-6")); 
 courses.insert(make_pair("COMPILER", "3-1")); 
 courses.insert(make_pair("COMPILER", "5-2")); 
 courses.insert(make_pair("OS", "1-2")); 
 courses.insert(make_pair("OS", "4-1")); 
 courses.insert(make_pair("OS", "5-5")); 
 //输入一个课程名，直到找到该课程为止，记下每周上课次数 
 string name; 
 int count; 
 do { 
 cin >> name; 
 count = courses.count(name); 
 if (count == 0) 
 cout << "Cannot find this course!" << endl; 
 } while (count == 0); 
 //输出每周上课次数和上课时间 
 cout << count << " lesson(s) per week: "; 
 pair<CourseIter, CourseIter> range = courses.equal_range(name); 
 for (CourseIter iter = range.first; iter != range.second; ++iter) 
 cout << iter->second << " "; 
 cout << endl; 
 
 return 0; 
}