C++ primer 第十一章
11.1 使用关联容器
关联容器：元素是按关键字来保存和访问的
顺序容器：元素是按它们在容器中的位置来顺序保存和访问的
使用关联容器
使用 MAP
/* 统计每个数字在输入中出现的次数 */ std::map<int, size_t> word_cout; int number; while (std::cin >> number){ ++word_cout[number]; } for (const auto& w : word_cout){ std::cout << w.first << " occurs " << w.second << " times" << std::endl; }
使用 SET
/* 只统计不在set里面的数字 */ std::map<int, size_t> word_cout; std::set<int> set1 = { 0, 1, 4, 9, 2, 3, 1 }; int number; while (std::cin >> number){ if (set1.find(number) == set1.end()){ ++word_cout[number]; } } for (const auto& w : word_cout){ std::cout << w.first << " occurs " << w.second << " times" << std::endl; }
11.2 关联容器概述
map 或 set 中的关键字必须是唯一的
关联容器初始化
初始化 multimap 或 multiset
//定义一个有20个元素的vector,保存0-9每个整数的两个拷贝 std::vector<int> ivec; for (std::vector<int>::size_type i =0; i !=10; ++i){ ivec.push_back(i); ivec.push_back(i); } std::set<int> set1(ivec.begin(), ivec.end()); std::multiset<int> set2(ivec.begin(), ivec.end()); std::cout << ivec.size() << std::endl; //20 std::cout << set1.size() << std::endl; //10 std::cout << set2.size() << std::endl; //20
关键字要求
有序容器：map，multimap，set，multiset 关键字必须定义元素的比较方法
如果一个类型定义了严格弱序的 < 运算符，则可以用作关键字类型
struct Demo{ int number; }; bool compareDemo(const Demo& demo1, const Demo& demo2){ return demo1.number > demo2.number; } int main(){ std::multiset<Demo, decltype(compareDemo)*> demoSet(compareDemo); }
函数指针使用记录
struct HashHelper{ public: static int INT_INT(void* valueBuffer) { return 1; } }; typedef int(*GetHashCode)(void* valueBuffer); struct Hash{ Hash(){ caseTypeFillFuncPtrs(1); } void caseTypeFillFuncPtrs(int x){ switch (x) { case 1:m_dim_funcPtrs.emplace_back(&HashHelper::INT_INT); } } int operator() const{ int totalHashCode =0; void* val =0; for (int i =0; i < 5; ++i){ totalHashCode += m_dim_funcPtrs[i](val); } } private: std::vector<GetHashCode> m_dim_funcPtrs; }
pair 类型
pair 是一个用来生成特定类型的模板，默认对数据成员值初始化
std::pair<std::string, std::string> anon; std::pair<std::string, size_t> word_count; std::pair<std::string, std::vector<int>> line; std::pair<std::string, std::string> author = {"James","Joyce"};
pair 的数据成员时 public 的，两个成员分别是 first 和 second
std::cout << w.first << " occurs " << w.second << " times" << std::endl;
此处，w 是指向 map 中某个元素的引用，map 的元素时是 pair
创建 pair 对象的函数
std::pair<std::string, int> process(){ //return std::pair<std::string, int>(); std::vector<std::string> v1; return std::make_pair(v1.back(),v1.size()); }
11.3 关联容器操作
std::set<std::string>::key_type v1; //string std::set<std::string>::value_type v2; //string std::map<std::string,int>::value_type v3; //pair<const std::string,int> std::map<std::string, int>::key_type v4; //string std::map<std::string, int>::mapped_type v5; //int
关联容器迭代器
一个 map 的 value_type 是一个 pair，可以改变 pair 的值，但不能改变关键字成员的值
std::map<int, size_t> word_cout; //指向word_cout中一个元素的迭代器 auto map_it = word_cout.begin(); //*map_it是指向pair<const int, size_t>对象的引用 std::cout << map_it->first; //打印此元素的关键字 std::cout << map_it->second; //打印此元素的值 map_it->first =1; //错误,关键字是 const 的 ++map_it->second; //正确
set 的迭代器是 const 的
std::set<int> set1 = { 0, 1, 2, 3, 4 }; std::set<int>::iterator set_it = set1.begin(); if (set_it != set1.end()){ *set_it =42;//错误,set的关键字是只读的 std::cout << *set_it << std::endl; }
当迭代器遍历一个map，multimap，set，multiset 迭代器按关键字升序遍历元素
添加元素
删除元素
Map 下标操作
map 下标操作和其它下标操作不同在于返回类型。通常解引用一个迭代器返回的类型和下标运算符返回类型一样。但对于 map，进行下标操作时，会获得一个 mapped_type 对象，但当解引用时会得到一个 value_type 对象
std::map<std::string,size_t> word_cout; //插入一个关键字为 Anna 的元素,关联值并进行初始化,然后将 1 赋给它 word_cout["Anna"] =1;
下标运算符可能插入一个新元素，因此只能对非 const map 使用下标
访问元素
set<int> iset = {0,1,2,3,4}; iset.find(1); //返回一个迭代器,指向 key ==1 的元素 iset.find(11); //返回一个迭代器,指向 iset.end() iset.count(1); // 1iset.count(11); // 0
在 multimap 中查找元素
具有相同关键字的这些元素在容器中会相邻存储
如果 lower_bound 和 upper_bound 返回相同的迭代器，则给定关键字不在容器中
for(auto beg = authors.lower_bound(search_item), end = authors.upper_bound (search_item);beg != end;++beg){ cout << beg -> second << endl; }
//pos保存迭代器对,表示和关键字匹配的元素范围 for(auto pos = authors.equal_range(search_item);pos.first != pos.second;++pos.first){ cout << pos.first -> second << endl; }
11.4 无序容器
无序容器：不使用比较运算符来组织元素，而是使用哈希函数和关键字类型的 == 运算符
//统计出现次数,但单次不按字典排序 unorder_map<string,size_t> word_count; string word; while(cin>>word){ ++word_count[word]; } for(const auto& w : word_count){ cout << w.first << "--" w.second << endl; }
无序容器默认情况下：
使用关键字类型的 == 运算符比较元素
使用一个 hash<key_type> 类型的对象来生成每个元素的哈希值
标准库为内置类型（包含指针），string，智能指针提供了哈希模板
不能直接定义自定义类型为无序容器的关键字类型（需重写哈希函数和比较方法）
