C++学习笔记(Day17 关联容器分类和的基本功能 )

关联容器的特点和接口

关联容器的特点

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

接口

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

关联容器概念图

C++学习笔记(Day17 关联容器分类和的基本功能 )

四种关联容器

单重关联容器(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;
}

C++学习笔记(Day17 关联容器分类和的基本功能 )

 

 

 

映射(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

C++学习笔记(Day17 关联容器分类和的基本功能 )

 

C++学习笔记(Day17 关联容器分类和的基本功能 ) 

 

 

例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;
}

C++学习笔记(Day17 关联容器分类和的基本功能 )

 

 多重集合与多重映射

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

 例 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; 
} 

C++学习笔记(Day17 关联容器分类和的基本功能 )

 

 

C++学习笔记(Day17 关联容器分类和的基本功能 )C++学习笔记(Day17 关联容器分类和的基本功能 )

 

上一篇:B站最新视频下载链接的获取


下一篇:Day17学习记录