C++Primer学习笔记11.关联容器

委员长

关联容器

• 基本使用
• 概述
• 操作
• 无序容器

key-value 形式的容器，有 set 类型（value 为空）和 map 类型。而 C++ 标准库提供了 8 个关联容器。

按关键字有序保存元素	-
map	关联数组：保存 key-value 对
set	只保存关键字
multimap	key 可重复的 map
multiset	关键字（key）可重复的 set
<b>无序集合</b>	-
unordered_map	哈希函数组织的 map
unordered_set	哈希函数组织的 set
unordered_multimap	关键字可重复出现的 set
unordered_multiset	关键字可重复出现的 map

<span style="color:orange">类型 map 和 multimap 定义在头文件 map 中；set 和 multiset 定义在头文件 set 中；无序容器则定义在头文件 unordered_map 和 unordered_set 中。</span>

基本使用

使用 map 对字符出现的次数进行计数

当从 map 中提取一个元素时，会得到一个 pair 类型的对象。pair 是一个模板类型，保存两个名为 first 和 second 的（公有）数据成员。map 所使用的 pair 用 first 成员保存关键字，用 second 成员保存对应的值。因此，输出语句的效果是打印每个字符及其关联的计数器。

void count(){
    // map 统计字符计数。
    string content = "Hello Hello ollo";
    map<char, int> word_count;
    for (size_t i = 0; i < content.length(); i++){
        ++word_count[content[i]];
    }
    for(const auto &w: word_count){
        cout<<w.first<<":"<<w.second<<endl;
    }
}
/*
 :2
H:2
e:2
l:6
o:4
*/

使用 set 统计未在 set 中出现的字符

void count(){
    string content = "Hello oollH";
    map<char, size_t> word_count;
    set<char> exclude = {' ', 'H'};
    for (size_t i = 0; i < content.size(); i++){
        if(exclude.find(content[i]) == exclude.end()){
            // 不存在则统计
            ++word_count[content[i]];
        }
    }

    for (const auto &w : word_count){
        cout<<w.first<<":"<<w.second<<endl;
    }  
}
/*
e:1
l:4
o:3
*/

关联容器概述

定义关联容器

定义一个 map/set 时，必须既指明数据类型。

• 每个关联容器都定义了一个默认构造函数，负责创建一个指定类型的空容器。
• 也可以将关联容器初始化为另一个同类型容器的拷贝，或是从一个值范围来初始化关联容器，只要这些值可以转化为容器所需类型就可以。
• 在新标准下，我们也可以对关联容器进行值初始化

map<char, int> word_count; // 空容器
set<string> exclude = {'H', ' '}; // 值初始化
map<string, string> authors = {
    {"name", "Jack"},
    {"age", "18"}
};

当初始化一个 map 时，必须提供关键字类型和值类型。将每个 key-value 对包围在花括号中 {key, value}

<b>初始化 multimap/multiset</b>

map/set 的关键字唯一，而 multimap/multiset 的关键字可以有多个。比如 multimap 可以同时保存。

#include<iostream>
#include<map>
#include<string>
using namespace std;

int main(){
    multimap<string,string> map;
    map.insert(make_pair("name","kkx"));
    map.insert(make_pair("name","kkx2"));
    map.insert({"name","kkx3"});
    // first 是 key，second 是 value
    for(auto const &w : map){
        cout<<w.first<<":"<<w.second<<endl;
    }
}
/*
name:kkx
name:kkx2
name:kkx3
*/

也可以使用其他容器的内容来进行初始化，此处就用 set 作为示例。multiset 也是一样的。

#include<iostream>
#include<vector>
#include<set>
using namespace std;

void test(){
    vector<int> vec;
    for (size_t i = 0; i < 10; i++){
        vec.push_back(i);
    }

    set<int> unique(vec.begin(),vec.end());
    multiset<int> no_unique(vec.begin(),vec.end());
    for(auto const &w : no_unique){
        cout<<w<<endl;
    }
}

<b>习题</b>

• 定义一个 map，关键字是家庭的姓，值是一个 vector，保存家中孩子（们）的名。编写代码，实现添加新的家庭以及向已有家庭中添加新的孩子。
• 编写一个程序，在一个 vector 而不是一个 set 中保存不重复的单词。使用 set 的优点是什么？

关键字类型的要求

对于有序容器——map、multimap、set 以及 multiset，关键字类型必须定义元素比较的方法。

自定义容器的比较器

//'比较函数的定义方式'
bool comp(const Sales_data &lhs, const Sales_data &rhs){
    return lhs.isbn() < rhs.isbn();
}
//'定义容器对象'
multiset<Sales_data,decltype(comp)*> bookstore(comp);

注意当使用 decltype 获取函数指针时要加上 * 运算符。

pair类型

pair 类型定义在头文件 utility 中，也是一个模板。

<b>pair 的定义</b>

pair 的默认构造函数对数据成员进行值初始化，因此 string，vector 等类型会默认为空，int 会默认为 0。

//'直接定义'
pair<string, int> p;//默认初始化
pair<string, int> p(str, i);
pair<string, int> p{"LiLin", 17};
pair<string, int> p = {"LiLin", 17};

//'使用 make_pair'
auto p = make_pari(v1, v2);//pair 的类型根据 v1 和 v2 的类型推断。

<b>pair 的操作</b>

p.first  //返回 p 的第一个成员
p.second //返回 p 的第二个成员
p1 < p2;   //当 p1.first < p2.first && p1.second < p2.second 时为真。
p1<=p2; p1>p2; p1>=p2;
p1 == p2;//当 first 和 second 成员都相等时，两个 pair 相等。
p1 != p2;

<b>创建 pair 类型的返回值</b>

如果一个函数返回一个 pair，可以对返回值进行列表初始化或隐式构造返回值。

pair<string,int> process(bool a){
    if(a) 
        return {"LiLin",17};//列表初始化
    else 
        return pair<string,int>();//隐式构造返回值
}

关联容器操作

关联容器除了上面列出的类型别名，还有如下三种

关键字类型	说明
key_type	关键字类型
mapped_type	关联的类型，只适用于 map
value_type	对于 set，与 key_type 相同<br>对于 map，为 pair<const key_type,mapped_type>

<span style="color:red">注意：set 的 key_type 类型不是常量，pair 的 first 成员也不是常量，只有 map 的 value_type 中的 first 成员是常量。</span>

只有 map 类型（unordered_map、unordered_multimap、multimap 和 map）才定义了 mapped_type

迭代器

解引用关联容器迭代器得到的是 value_type 的引用。map 对应的就是 pair。pair 可以通过 first 得到 key 的值，通过 second 得到 value 的值。

#include<iostream>
#include<map>

using namespace std;

void testMapIter() {
    map<int, string> maps = {
            {1, "value1"},
            {2, "value2"},
            {3, "value3"},
    };
    auto beg = maps.begin();
    while (beg != maps.end()) {
        cout << "key=" << beg->first << "\t value=" << beg->second << endl;
        beg++;
    }
}

int main() {
    testMapIter();
}

<b>set 的迭代器是 const 的</b>

set 的关键值与 map 的关键值一样，都是不能改变的。可以用 set 的迭代器读取元素值，但不能修改。

<b>关联容器和算法</b>

当对关联容器使用泛型算法时，一般要么把它作为源序列，要么把它作为目的序列。比如从关联容器拷贝元素，向关联容器插入元素等。

<span style="color:orange">在使用算法时，优先使用关联容器定义的专用算法，速度会更快。</span>

添加元素

<span style="color:red">插入容器中已存在的元素对 map 和 set 没有影响。</span>

<b>使用 insert 添加元素</b>

关联容器添加元素一般使用 insert 成员，可以添加一个元素也可以添加一个元素范围，或者初始化列表。

set<int> s;
// 插入一个元素（s中没有关键字时才插入）。返回一个pair，pair包含一个迭代器指向具有指定关键字的元素，和一个表明是否插入成功的 bool 值
s.insert(10);
// 插入迭代器范围。返回 void
s.insert(vec.begin(), vec.end());
// 插入初始化列表。返回 void
s.insert({1, 2, 3});
// 类似于 insert(10),iter 是一个迭代器，提示从哪里开始搜索新元素应该存储的位置。返回一个迭代器，指向具有制定关键字的元素。
s.insert(iter, 10);

<b>向 map 添加临时构造的元素</b>

map<string, int> m;
'四种方法'
m.insert({str, 1}); //最简单的方法，直接使用花括号
m.insert(make_pair(str, 1));
m.insert(pair<string, int>(str, 1)); //pair 类型直接定义
m.insert(map<string, int>::value_type(str, 1));

<b>使用 emplace 添加元素</b>

//args用来构造一个元素，其他和 s.insert(10) 相同
s.emplace(args);
//除了 args 其他和 s.insert(iter, 10) 相同
s.emplace(iter, args);

使用 emplace 的优点是避免产生不必要的临时变量，避免不必要的临时对象的产生，举个例子

#include<iostream>
#include<vector>

using namespace std;

struct Foo {
    Foo(int n, double x) {
        cout << "构造方法" << endl;
    }
};

int main() {
    std::vector<Foo> v;
    v.emplace(v.begin(), 42, 32.0);     //<-- 没有临时变量产生
    v.insert(v.begin(), Foo(42, 3.1416)); //<-- 需要产生一个临时变量
    v.insert(v.begin(), {42, 3.1416});    //<-- 需要产生一个临时变量
}

emplace 相较于 insert，emplace 的语法看起来比较特别，<u>后面两个参数自动用来构造</u> vector 内部的 Foo 对象。这是因为其内部利用了 C++11 的两个新特性 —— 变参模板和完美转发。

• [变参模板] 使得 emplace 可以接受任意参数，这样就可以适用于任意对象的构建。
• [完美转发] 使得接收下来的参数能够原样完美地传递给对象的构造函数，这带来另一个方便性就是即使是构造函数声明为 explicit 它还是可以正常工作，因为它不存在临时变量和隐式转换。

struct Bar{
    Bar(int a) {}
    explicit Bar(int a, double b) {} ///< 必须显示调用
};

int main(void){
    vector<Bar> bv;
    bv.push_back(1);      ///< 隐式转换生成临时变量
    bv.push_back(Bar(1)); ///< 显示构造临时变量
    bv.emplace_back(1);   ///< 没有临时变量

    //bv.push_back({1, 2.0}); ///< 无法进行隐式转换
    bv.push_back(Bar(1, 2.0));///< 显示构造临时变量
    bv.emplace_back(1, 2.0);  ///< 没有临时变量

    return 0;
}

<b>检测 insert 的返回值</b>

注意 insert 返回的值不是固定的，依赖于容器类型和参数

1. 对于不重复的 map 和 set，添加的单一元素的 insert 和 emplace 都返回一个 pair，pair 内是具有给定关键字的元素的迭代器和一个 bool 值
2. 对于不重复的 map 和 set，添加多个元素都返回 void

在向 map 或 set 添加元素时，检测 insert 的返回值可以很有用，要灵活使用。

while(cin>>word){
    auto ret = word_count.insert({word,1});
    if(ret.second = false)
        ++ret.first->second;
}

<b>向 multiset 或 multimap 添加元素</b>

在 multiset 或 multimap 上调用 insert 总会插入元素。插入单个元素的 insert 返回一个指向新元素的迭代器。

multimap<string, string> authors;
authors.insert({"Barth, John", "Sot"});
authors.insert({"Barth, John", "Sot th"});

删除元素

关联容器定义了三个版本的 erase

操作	说明
c.erase(k)	从 c 中删除每个关键字为 k 的元素，返回一个 size_type，指出删除的元素的数量。
c.erase(p)	从 c 中删除迭代器 p 指定的元素。p 必须指向 c 中一个真实元素，不能等于 c.end()。返回一个指向 p 之后元素的迭代器，若 p 指向 c 中的尾元素，则返回 c.end()
c.erase(b, e)	删除迭代器 b 和 e 范围内的元素，返回 e。

访问元素

map 可以直接使用下标来访问指定 key 的 value。出了 map 的下标访问外，关联容器还提供多种查找一个指定元素的方法

操作	说明
c.find(k)	查找第一个关键字为 k 的元素，并返回一个指向该元素的迭代器，如果 k 不在容器中则返回尾后迭代器。
c.count(k)	返回关键字等于 k 的元素的数量。
c.lower_bound(k)	返回一个迭代器，指向第一个关键字不小于 k 的元素。
c.upper_bound(k)	返回一个迭代器，指向第一个关键字大于 k 的元素。
c.equal_range(k)	返回一个迭代器 pair，表示关键字等于 k 的元素的范围。若 k 不存在，pair 的两个成员均等于 c.end()

<span style="color:orange">lower_bound 和 upper_bound 不适用于无序容器.</span>

<span style="color:orange">下标和 at 操作只适用于非 const 的 map 和 unordered_map.</span>

#include<iostream>
#include<map>

using namespace std;

void testMapVisitor() {
    using address = string;
    map<string, address> name2addr{
            {"小明", "北京"},
            {"小红", "上海"},
            {"小蓝", "南昌"},
    };
    // 根据 key 找 value
    auto ans = name2addr.find("小明");
    cout << ans->first << "==" << ans->second << endl;
    auto ansC = name2addr.count("小明");
    cout << ansC << endl;
}

int main() {
    testMapVisitor();
}

<b>在 multimap 或 multiset 中查找元素</b>

最直观的方法是使用 find 和 count。

#include<iostream>
#include<map>

using namespace std;

void travelMulti() {
    multimap<string, string> test = { {"小明", "北京"},
                                     {"小红", "上海1"},
                                     {"小红", "上海2"},
                                     {"小红", "上海3"},
                                     {"小蓝", "南昌"},};
    auto ans = test.find("小红");
    auto count = test.count("小红");
    while (count) {
        cout << ans->first << ":" << ans->second << endl;
        count--;
        ans++;
    }
}

int main() {
    travelMulti();
}
/*
小红:上海1
小红:上海2
小红:上海3
*/

<b>一种不同的，面向迭代器的解决方法</b>

void travelMulti2() {
    multimap<string, string> test = { {"小明", "北京"},
                                     {"小红", "上海1"},
                                     {"小红", "上海2"},
                                     {"小红", "上海3"},
                                     {"小蓝", "南昌"},};
    for (auto beg = test.lower_bound("小红"),
                 end = test.upper_bound("小红"); beg != end; beg++) {
        cout << beg->second << endl;
    }
}

<b>equals_range 函数</b>

解决此问题的最后一种方法是三种方法中最直接的：不必再调用 upper_bound 和 lower_bound，直接调用 equal_range 即可。

此函数接受一个关键字，<u>返回一个迭代器 pair。</u>若关键字存在，则第一个迭代器指向第一个与关键字匹配的元素，第二个迭代器指向最后一个匹配元素之后的位置。若未找到匹配元素，则两个迭代器都指向关键字可以插入的位置。

void travelMulti3() {
    multimap<string, string> test = { {"小明", "北京"},
                                     {"小红", "上海1"},
                                     {"小红", "上海2"},
                                     {"小红", "上海3"},
                                     {"小蓝", "南昌"},};
    for (auto pos = test.equal_range("小红");
         pos.first != pos.second; ++pos.first) {
        cout << pos.first->second << endl;
    }
}

无序容器

新标准定义了 4 个无序关联容器（unordered associative container）。这些容器不是使用比较运算符来组织元素，而是使用一个哈希函数（hash function）和关键字类型的 == 运算符。

在关键字类型的元素没有明显的序关系的情况下，无序容器是非常有用的。在某些应用中，维护元素的序代价非常高昂，此时无序容器也很有用。

<b>使用无序容器</b>

使用方式和常规容器一样。

#include<unordered_map>

void unOrderMap() {
    unordered_map<string, string> test = { {"小明", "北京"},
                                          {"小红", "上海1"},
                                          {"小红", "上海2"},
                                          {"小红", "上海3"},
                                          {"小蓝", "南昌"},};
    for (auto pos = test.equal_range("小红");
         pos.first != pos.second; ++pos.first
            ) {
        cout << pos.first->second << endl;
    }
}
// 上海1

<b>管理哈希桶</b>

无序容器在存储上组织为一组桶，每个桶保存零个或多个元素。

graph LR
访问元素-->|计算哈希值|定位搜索那个桶-->|搜索|元素

无序容器提供了一组管理桶的函数，这些成员函数允许我们查询容器的状态以及在必要时强制容器进行重组。

<div align="center"><img src="./mdimg/cppprimer/image-20221205185020033.png"></div>

<b>无序容器对关键字类型的要求</b>

默认情况下，无序容器使用关键字类型的 == 运算符来比较元素，它们还使用一个 hash<key_type> 类型的对象来生成每个元素的哈希值。

标准库为内置类型（包括指针）提供了 hash 模板。还为一些标准库类型，包括 string 和智能指针类型定义了 hash。因此，我们可以直接定义关键字是内置类型（包括指针类型）、string 还是智能指针类型的无序容器。

如果我们像用自己定义的数据类型作为 key，那么需要自定以 hash 模板和重载 eqOp 函数。

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);

后期再补补。

温故知新

<b>问题</b>

1. 关联容器删除元素有哪些方法？
2. 关联容器添加元素有哪些方法？
3. 关联容器定义了哪些类型别名？
4. 如何使用 decltype 获取函数指针类型
5. pair 的默认构造函数对数据成员进行什么初始化
6. 可以使用花括号列表来对 pair 初始化吗
7. 定义一个 pair 类型对象的方式
8. set 的元素可以改变值吗
9. insert 有哪些应用方式
10. 循环删除 map 中元素的方式。
11. map 访问元素的方式？set 访问元素的方式？
12. map 和 set 查找元素的方式
13. 在 multimap 和 multiset 中查找元素的方法
14. 无序容器如何使用

<b>回答</b>

1. 使用 s.erase 删除元素，erase 除了接受迭代器为参数（返回void，不同于顺序容器）外，也可以直接接受关键值作为参数（返回删除的元素数量）。
2. 可以使用 insert 函数和 emplace 函数，map 还可以直接通过索引添加。
3. 迭代器类型、value_type、reference、const_reference、key_type、mapped_type（只用于 map）
4. 后面加上 运算符：decltype(comp)
5. 值初始化
6. 可以，比如 pair p = {"LiLin",17};
7. 直接定义和使用 makr_pair 两种方法
8. 不可以，set 的元素即是关键字又是值。理解：改变关键字实际上就相当于变为了另一个元素，所以不能改变。
9. 两种基础应用是可以直接接受一个元素值或接受一个迭代器范围。注意：添加单一元素的 insert 返回的是一个 pair，这个很有用。其他 insert 都返回 void
10. 循环内删除时使用 m.erase(iter++)。
11. map 可以使用下标和 at() 函数访问元素，注意两者在遇到不包含元素时的不同处理。set 可以使用 at() 函数访问元素，不能使用下标。
12. 可以使用 find 和 count 查找元素，此外还有 lower_bound, upper_bound, equal_range 三个查找大于某个值或等于某个值的元素的方式。
13. 比较麻烦，有三种方法：
14. 默认情况下，无序容器的关键字只能是内置类型、string、智能指针。无序容器也可以使用 find、insert、迭代器。无序容器还有一些桶相关的操作。