关联容器的元素按照关键字来保存和访问，而顺序容器的元素是按照在容器中的位置来保存和访问
关联容器支持高效的关键字查找和访问
2种关联容器：
- map中的元素是关键字-值对（key-value对），关键字作为索引，值表示与索引相关的数据
- set中的元素只包含关键字
8个关联容器：
- map 关联数组，保存关键字-值对
- set 值保存关键字的容器
- multimap 关键字可重复出现的map
- multiset 关键字可重复出现的set
- unordered_map 用哈希函数组织的map
- unordered_set 用哈希函数组织的set
- unordered_multimap 哈希组织的map；关键字可以重复出现
- unordered_multiset 哈希组织的set；关键字可以重复出现
4个头文件：
- map和multimap定义于map头文件
- set和multiset定义于set头文件
- unordered_map和unordered_multimap定义于unordered_map头文件
- unordered_set和unordered_multiset定义于unordered_set头文件

11.1 使用关联容器

map类型常称为关联数组（字典），但其下标不必是整数，且通过关键字而不是位置来查找值
set是关键字的简单集合，只想知道一个值是否存在或出现的次数时，很有用

使用map

关联容器也是模板
定义map，必须在模板参数中指定key和value类型
map的元素都是pair类型，pair也是模板，保存两个public数据成员（first和second）。map使用的pair的first成员是关键字，second是值

map<string,size_t> word_count;          //默认初始化字典

string word;

while(cin>>word)

    ++word_count[word];                 //提取word的计数器并将其加1

for(const auto &w:word_count)           //遍历字典元素

    cout<<w.first<<" occurs "<<w.second //pair类型，first成员是key，second成员是value

        <<((w.second>1)?" times":" time")<<endl;

使用set

set是模板，使用时必须在模板参数中指定元素类型
可以对关联容器（set和map都可）做列表初始化
set的find方法返回一个迭代器，若给定关键字在set中则返回指向它的迭代器，否则返回end

map<string,size_t> word_count;              //默认初始化字典

set<stirng> exclude={"The","But","And"};    //列表初始化集合

string word;

while(cin>>word)

    if(exclude.find(word)==exclude.end())   //在集合中查找元素，返回迭代器若为end则未找到

        ++word_count[word];

11.2 关联容器概述

所有关联容器都支持表9.2中的通用容器操作，但不支持顺序容器特有的操作，例如push_front或push_back。原因是关联容器中元素是根据关键字存储的
关联容器支持顺序容器不支持的操作和类型别名
关联容器的迭代器都是双向迭代器

11.2.1 定义关联容器

定义map时需在模板参数中给出key和value的类型，定义set时需在模板参数中给出关键字类型
定义关联容器的4种方法：
- 关联容器都有默认构造函数，生成空容器
- 可将关联容器初始化为另一个同类型容器的拷贝
- 可用元素范围初始化关联容器，只要这些元素可转换为关联容器所需类型
- C++11允许对关联容器使用值初始化（列表初始化）
对map做列表初始化时，每个元素也是一个花括号列表，其中包含两个值{key, value}

pair<string, string> anon; // 空容器

set<stirng> exclude={"The","But","And"};    //列表初始化

pair<string, string> author = {{"James", "Joyce"},

				 {"Austen", "Jane"}}; // 也可为每个成员提供初始化器

初始化 multimap 和multiset

map和set的关键字必唯一，但multimap和multiset允许多个元素有相同关键字

11.2.2 关键字类型的要求

set的关键字就是元素，map的关键字是元素的first的类型
对于有序关联容器（map、multimap、set、multiset），关键字类型必须有序，默认使用元素类型的<算符。

有序容器的关键字类型

可提供自定义操作代替<算符，要求自定义操作在关键字类型上定义严格弱序：
- 两关键字不能同时“小于等于”对方
- “小于等于”具有传递性
- 若两关键字都不“小于等于”对方，则称为“等价”，“等价”具有传递性
若两关键字等价，则关联容器认为它们相等。用作map的key时，只能有一个value与这两个key关联，用任一个key访问都得到这个value

使用关键字类型的比较函数

multiset<关键字类型>
若使用自定义的严格弱序函数，则定义关联容器时，必须在模板参数中给出该函数指针类型，在构造函数参数中给出该函数

//定义严格弱序

bool compareIsbn(const Sales_data &lhs, const Sales_data &rhs){

    return lhs.isbn()<rhs.isbn();

}

using SalesSetType=multiset<Sales_data,decltype(compareIsbn) *>;    //自定义了严格弱序的multiset类型

SalesSetType bookstore(compareIsbn);                                //自定义了严格弱序的multiset对象

11.2.3 pair 类型

pair类型定义于utility头文件中
一个pair保存两个public的数据成员，分别叫first和second
pair是模板，创建时需在模板参数中指定两个数据成员的类型，两个类型不要求一样
pair的默认构造函数对数据成员做值初始化

创建 pair 对象的函数

pair<string int> process(vector<string> &v){

    if(!v.empty())

        return {v.back(),v.back().size()};  //列表初始化返回值

    else

        return pair<string,int>();          //隐式构造返回值

}

if(!v.empty())

        return make_pair(v.back(),v.back().size());  //列表初始化返回值

11.3 关联容器操作

关联容器额外的类型别名

key_type 此容器类型的关键字类型
mapped_type 每个关键字关联的类型，只适用于map
value_type 对于set，与key_type相同；

对于map，为pair<const key_type, mapped_type>

11.3.1 关联容器迭代器

迭代器解引用

解引用关联容器迭代器时，得到一个类型为容器的value_type的引用。
set迭代器解引用得到的都是关键字引用，都是const。虽然同时存在iterator和const_iterator类型，但都不可写
map迭代器解引用得到的是pair的引用，first为const。其iterator可写second，const_iterator不可写

遍历关联容器

map和set都有begin和end成员函数，可得到迭代器用于遍历元素

关联容器和算法

关联容器很少使用泛型算法
- 通常不对关联容器使用泛型算法。因为关键字是const，元素不可改变也不可重排。
- 关联容器只可使用只读算法，但这些算法在关联容器中搜索时效率低下。例如用关联容器的find成员函数比泛型find函数快得多
- 如果真要对关联容器使用泛型算法，则只能把它当源序列，或当zuo目的位置用inserter插入

11.3.2 添加元素

对于无重复关键字的map和set，若插入元素的key在容器中已存在，则插入失败，insert不做任何事
insert有两个版本
- 接受一对迭代器，这些迭代器指向的类型可转为该容器的value_type
- 接受initializer_list，即花括号列表，该列表用于构造一个value_type

vector<int> ivec={2,4,6,8,2,4,6,8};

set<int> set2;

set2.insert(ivec.begin(), ivec.end());//4个元素

set2.insert({1,3,5,7,1,3,5,7}); //8个元素

word_count.insert({word,1});                            //花括号列表转为initializer_list

word_count.insert(make_pair(word,1));                       //make_pair函数生成pair

word_count.insert(pair<string,size_t>(word,1));             //显式构造pair

word_count.insert(map<string,size_t>::value_type(word,1));  //显式构造value_type

检测 insert 的返回值

insert/emplace的返回值依赖于容器类型和参数
向set/map添加单一元素，则insert/emplace返回一个pair，其first为迭代器，second为bool。
- 若关键字不在容器中，则插入。first指向插入的元素，second为true
- 若关键字在容器中，则插入失败。first指向给定元素，second为false

map<string,size_t> word_count;

string word;

while(cin>>word){

    //ret的类型是pair<map<string,size_t>::iterator,bool>

    auto ret=word_count.insert({word,1});   //尝试插入关键字和初始计数值1

    if(!ret.second)                         //如果插入失败，说明关键字已存在，只需将值递增

        ++ret.first->second;                //ret.first指向插入的元素，其second是值

}

向multiset/multimap添加元素

向multiset/multimap添加单一元素，总是插入成功，insert/emplace返回一个迭代器指向插入的元素

11.3.3 删除元素

表：从关联容器删除元素

c.erase(k)

从c中删除每个关键字为k的元素。返回一个size_type值，指出删除的元素的数量
c.erase(p)

从c中删除迭代器p指定的元素。p必须指向c中一个真实元素，不能等于c.end()。返回一个指向p之后元素的迭代器，若p指向c中的尾元素，则返回.end()
c.erase(b, e)

删除迭代器b和e所表示的范围中的元素。返回e

11.3.4 map的下标操作

表：map和unorder_map的下标操作

c[k]

返回关键字为k的元素；如果k不在c中，添加一个关键字为k的元素，对其进行值初始化
c.at[k]

访问关键字为k的元素，带参数检查；若k不在c中，抛出一个out_of_range异常
只适用于关键字不可重复的map容器，set不支持下标：
- map和unordered_map都有下标算符和at函数
- multimap和unordered_multimap都不支持下标，因为一个关键字可能有多个值
- 所有的set类型都不支持下标，因为没有值
map/unordered_map下标接受一个关键字，访问与其关联的值。若关键字不在容器中，则创建元素插入容器，关联值进行值初始化

map<string,size_t> word_count;

word_count["Anna"]=1;

/*上一行的操作步骤：

 *1、容器中搜索关键字"Anna"，未找到

 *2、创建新key-value对，key是const string，value被值初始化为0

 *3、提取新插入的元素，为其赋值为1

 */

11.3.5 访问元素

c.find(k)  // 返回一个迭代器，指向第一个关键字k的元素，如k不在容器中，则返回尾后迭代器

c.count(k)  // 返回关键字等于k的元素的数量。对于不允许重复关键字的容器，返回值永远是0或1

c.lower_bound(k)  // 返回一个迭代器，指向第一个关键字不小于k的元素;不适用于无序容器

c.upper_bound(k)  // 返回一个迭代器，指向第一个关键字大于k的元素；不适用于无序容器

c.equal_bound(k)  // 返回一个迭代器pair，表示关键字等于k的元素的范围。如k不存在，pair的两个成员均等于c.end()

对 map 使用 find 代替下标操作

查找时应用find而不是下标，因为下标的副作用会导致元素未找到时插入，即改变容器

在 multiset/multimap 中查找元素

若multiset/multimap中有重复关键字，则它们相邻存放，因此可找到第一个，然后递增迭代器

multimap<string,string> authors;

authors.insert({"Barth, John","Sot-Weed Factor"});

authors.insert({"Barth, John","Lost in the Funhouse"});

string search_item("Alain de Botton");

//法1：用find查找迭代器，count计数

auto entries=authors.count(search_item);

auto iter=authors.find(search_item);

while(entries){

    cout<<iter->second<<endl;

    ++iter;

    --entries;

}

lower_bound和upper_bound

lower_bound和upper_bound成员函数查找范围：
- 若给定关键字在容器中，则lower_bound返回第一个匹配元素的迭代器，upper_bound返回最后一个匹配元素之后的迭代器
- 若给定关键字不在容器中，则lower_bound和upper_bound都返回指向第一个大于该关键字的元素的迭代器，该位置称为安全插入点，即在此处insert该关键字可保持容器中关键字的顺序
- lower_bound和upper_bound都不支持无序容器
```
//用lower_bound和upper_bound查找范围

for(auto beg=ahthors.lower_bound(search_item),

				end=ahthors.upper_bound(search_item);

    beg!=end;++beg)

    cout<<beg->second<<endl;
```

equal_range 函数

用equal_range查找范围

for(auto pos=authors.equal_range(search_item);

    pos.first!=pos.second;++pos.first)

    cout<<pos.first->second<<endl;

11.3.6 一个单词转换的map

缩写对照表示例：

brb be right back

k okay?

y why

r are

u you

pic picture

thk thanks!

l8r later

要转换文本示例：

where r u

y dont u send me a pic

k thk l8r

转换后的文本：

where are you

why dont you send me a picture

okay? thanks! later

//读取对照表，存为字典

map<string,string> buildMap(ifstream &map_file){

    map<string,string> trans_map;

    string key,value;

    while(map_file>>key && getline(map_file,value)) //先读第一个单词存入key，再取行中剩下

        if(value.size()>1)                          //若转换规则存在

            trans_map[key]=value.substr(1);         //取子串，忽略getline读到的第一个空格

        else

            throw runtime_error("no rule for "+key);

    return trans_map;

}

//转换单个词语

const string &transform(const string &s, const map<string,string> &m){

    auto map_it=m.find(s);  //在字典中查找

    if(map_it!=m.cend())    //不等于end则查找到

        return map_it->second;

    else

        return s;

}

//读取对照表和输入，打印输出

void word_transform(ifstream &map_file, ifstream &input){

    auto trans_map=buildMap(map_file);          //对照表生成字典

    string text;

    while(getline(input,text)){                 //逐行处理

        istringstream stream(text);             //一行字符串作为一个流处理

        string word;

        bool firstword=true;

        while(stream>>word){                    //逐个单词处理

            if(firstword)   firstword=false;    //如果不是第一个单词，则输出之前打印空格

            else            cout<<" ";

            cout<<transform(word,trans_map);    //转换单词

        }

        cout<<endl;

    }

}

11.4 无序容器

C++11定义了4个无序关联容器，它们组织元素的方式不是关键字的序，而是哈希函数和==算符
使用无序容器的情形：
- 关键字类型的元素没有明显的序关系
- 维护关键字的序代价较高

管理桶

无序容器在存储上组织为一组桶，每个桶中保存0个或多个元素。即，层次化的存储
无序容器使用一个哈希函数，将关键字映射到桶。访问元素时先计算关键字的哈希值来判断在哪个桶中，再在桶内搜索。
哈希值相同的关键字放在同一桶中，因此关键字相同的元素都在同一桶中
无序容器的性能依赖于：哈希函数的质量、桶数量、桶大小
C++允许查询无序容器的状态，并可改变映射和存储的策略，管理桶的函数如表11.8：

无序容器对关键字类型的要求

默认情况下，无序容器用关键字类型的==算符比较元素，用hash<key_type>类型的对象来生成元素的哈希值。
标准库为内置类型(包括指针)、string、智能指针提供了hash函数，因此可直接定义这些类型为无序容器的关键字
无序容器可使用自定义的==算符和哈希函数，只需在模板参数中给出函数指针类型，并在构造函数参数中给出函数指针即可
对于有==算符的类型，可以只自定义哈希函数

//定义哈希函数

size_t hasher(const Sales_data &sd){

    return hash<string>()(sd.isbn()); //用一个成员的哈希作为该类的哈希

}

//定义==算符

bool eqOp(const Sales_data &lhs, const Sales_data &rhs){

    return lhs.isbn()==rhs.isbn(); //用一个成员的==算符作为该类的==算符

}

//使用自定义的哈希函数和==算符定义类型并初始化

using SD_multiset=unordered_multiset<Sales_data, decltype(hasher) *, decltype(eqOp) *>;

SD_multiset bookstore(42,hasher,eqOp);

//如果类定义了==运算符，则可以只重载哈希函数

unordered_set<Foo, decltype(FooHash) *> fooSet(10, FooHash);

巴特西

【c++ Prime 学习笔记】第11章关联容器

11.1 使用关联容器

11.2 关联容器概述

11.2.1 定义关联容器

11.2.2 关键字类型的要求

11.2.3 pair 类型

11.3 关联容器操作

11.3.1 关联容器迭代器

11.3.2 添加元素

11.3.3 删除元素

11.3.4 map的下标操作

11.3.5 访问元素

11.3.6 一个单词转换的map

11.4 无序容器

最新文章

热门文章

巴特西

【c++ Prime 学习笔记】第11章 关联容器

11.1 使用关联容器

11.2 关联容器概述

11.2.1 定义关联容器

11.2.2 关键字类型的要求

11.2.3 pair 类型

11.3 关联容器操作

11.3.1 关联容器迭代器

11.3.2 添加元素

11.3.3 删除元素

11.3.4 map的下标操作

11.3.5 访问元素

11.3.6 一个单词转换的map

11.4 无序容器

最新文章

热门文章

【c++ Prime 学习笔记】第11章关联容器