C++ Primer学习笔记：(十一)关联容器

11.1 使用关联容器

关联容器和顺序容器有着根本的不同：关联容器中的元素是按关键字来保存和访问的。与之相对，顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的。

关联容器类型

关联容器类型	含义
按关键字有序保存元素
map	关联数组，保存关键字-值对
set	关键字即值，即只保存关键字的容器
multimap	关键字可重复出现的map
multiset	关键字可重复出现的set
无序集合
unordered_map	用哈希函数组织的map
unordered_set	用哈希函数组织的set
unordered_multimap	哈希组织的map；关键字可以重复出现
unordered_multiset	哈希组织的set；关键字可以重复出现

map是关键字-值对的集合，因此map类型被称为关联数组(associative array)。
set就是关键字的简单集合。当想知道一个值是否存在的时候，set是最有用的。

//chap11_1_word_count_exclude_some_words.cpp
#include<iostream>
#include<map>
#include<string>
#include<set>
using namespace std;
/*
 *统计每个单词在输入中出现的次数。
 *Linux g++ 5.4.0 编译通过。
 *命令：
 *      g++  -std=c++11 chap11_1_word_count_exclude_some_words.cpp
 *      ./a.out
 */
int main() {
    map<string, size_t> word_count;
    //对关联容器的元素进行列表初始化
    set<string> exclude = {"The", "But", "And", "Or", "An", "A",
                           "the", "but", "and", "or", "an", "a"};
    string word;
    //在新的一行按CTRL+Z（或者LINUX类系统中按CTRL+D）即可终止循环。
    while(cin >> word) {
        //find调用返回一个迭代器，只统计不在exclude中的单词。
        if(exclude.find(word) == exclude.end())
            ++word_count[word];
    }
    for(const auto &w : word_count) {
        cout << w.first << " occur " << w.second 
             << ((w.second > 1) ? " times" : " time") << endl;
    }
	return 0;
}

练习11.4

统计每个单词在输入中出现的次数。要求：忽略标点符号且大小写无关。

//chap11_exersize_4.cpp
#include<iostream>
#include<map>
#include<string>
#include<set>
#include<cctype>
#include<algorithm>
using namespace std;
/*
 *统计每个单词在输入中出现的次数。[忽略标点符号且大小写无关]
 *Linux g++ 5.4.0 编译通过。
 *命令：
 *      g++  -std=c++11 chap11_exersize_4.cpp
 *      ./a.out
 */
int main() {
    map<string, size_t> word_count;
    //对关联容器的元素进行列表初始化
    set<string> exclude = {"The", "But", "And", "Or", "An", "A",
                           "the", "but", "and", "or", "an", "a"};
    string word;
    //在新的一行按CTRL+Z（或者LINUX类系统中按CTRL+D）即可终止循环。
    while(cin >> word) {
        //将字母统一转化为小写形式
        for(auto &ch : word) {
            ch = tolower(ch); //针对每一字母
        }
        //删去标点
        word.erase(remove_if(word.begin(), word.end(), static_cast<int(*)(int)>(&ispunct)), word.end());
    
        //find调用返回一个迭代器，只统计不在exclude中的单词。
        if(exclude.find(word) == exclude.end())
            ++word_count[word];
    }
    for(const auto &w : word_count) {
        cout << w.first << " occur " << w.second 
             << ((w.second > 1) ? " times" : " time") << endl;
    }
	return 0;
}

11.2 关联容器概述

关联容器都支持普通容器操作。关联容器不支持顺序容器的位置相关的操作，原因是关联容器中元素都是根据关键字存储的，这些操作对关联容器没有意义。而且，关联容器也不支持构造函数或插入操作这些接受一个元素值和一个数量值的操作。

pair标准库类型，位于头文件utility中。

#include<utility>
#include<iostream>
#include<string>
using namespace std;
// error: in C++98 ‘p’ must be initialized by constructor, not by ‘{...}’
// command:
//      g++ chap11_2_pair.cpp -std=c++11
//      ./a.out
int main()
{
    string s = "hello";
    //初始化方式有很多，这是列表初始化
	pair<string,size_t> p = {s, s.size()};
	cout << "The size of string \""<< p.first << "\" is " << p.second << "." << endl;
	return 0;
}

11.3 关联容器操作

关联容器额外的类型别名

关联容器额外的类型别名	含义
key_type	此容器类型的关键字类型
mapped_type	每个关键字关联的类型：只适用于map
value_type	对于set，与key_type相同，对于map，为`pair<const key_type,mapped_type>`

关联容器insert操作

关联容器额外的类型别名	含义
c.insert(v)
c.elmpace(args)	v是value_type类型对象；args用来构造一个元素。对于map和set，只有当元素关键字不在c中才插入(或构造)元素。函数返回一个pair，包含一个迭代器，指向具有指定关键字的元素，以及一个指示插入是否是否成功的bool值。对于multimap和multiset，总会插入(或构造)给定元素，并返回一个指向新元素的迭代器。
c.insert(b,e)
c.insert(il)	b和e是迭代器，表示一个c::value_type类型值的范围；il是这种值的花括号列表。函数返回void。对于map和set，只插入关键字不在c中的元素。对于multimap和multiset，则会插入范围中的每个元素。
c.insert(p,v)
c.insert(p,args)	类似insert(v)(或emplace(args))，但迭代器p作为一个提示，指出从哪里开始搜索新元素应该存储的位置。返回一个迭代器，指向具有给定关键字的元素。

map和unordered_map的下标操作

map和unordered_map的下标操作	含义
c[k]	返回关键字为k的元素；如果k不在c中，添加一个关键字为k的元素，对其进行值初始化
c.at[k]	访问关键字为k的元素，带参数检查；若k不在c中，抛出一个out_of_range异常

在一个关联容器中查找元素

关联容器中查找元素	含义
lower_bound和upper_bound	不适用于无序容器。
下标和at操作只适用于	非const的map和unordered_map
c.find(k)	返回一个迭代器，指向第一个关键字为k的元素，若k不在容器中，则返回尾后迭代器
c.count(k)	返回关键字等于k的元素的数量。对于不允许重复关键字的容器，返回值永远是0和1
c.lower_bound(k)	返回一个迭代器，指向第一个关键字不小于k的元素
c.upper_bound(k)	返回一个迭代器，指向第一个关键字大于k的元素
c.equal_range(k)	返回一个迭代器pair，表示关键字等于k的元素的范围。若k不存在，pair的两个成员均等于c.end()

11.4 无序容器

无序容器管理操作

关联容器中查找元素	含义
桶接口
c.bucket_count()	正在使用的桶的数目
c.max_bucket_count()	容器能容纳的最多的桶的数量
c.bucket_size()	第n个桶中有多少个元素
c.bucket(k)	关键字为k的元素在哪个桶中
桶迭代
local_iterator	可以用来访问桶中元素的迭代器类型
const_local_iterator	桶迭代器的const版本
c.begin(n),c.end(n)	桶n的首元素迭代器和尾后迭代器
c.cbegin(n),c.cend(n)	与前两个函数类似，但返回`const_local_iterator`
哈希策略
c.load_factor()	每个桶的平均元素数量，返回float值
c.max_load_factor()	c试图维护的平均桶大小，返回float值。c会在需要时添加新的桶，以使得`load_factor<=max_load_factor`
c.rehash(n)	重组存储，使得bucket_count>=n且bucket_count>size/max_load_factor
c.reserve(n)	重组存储，使得c可以保存n个元素且不必rehash