@[TOC]

1. 关联式容器

在初阶阶段，我们已经接触过STL中的部分容器

<font color = "#000066"> 比如：vector、list、deque、forward_list(C++11)等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。

而今天我们要学习的几个容器称为关联式容器，那什么是关联式容器？它与序列式容器有什么区别？

<font color = blue>关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key, value>结构的键值对，在数据检索时比序列式容器效率更高。

2. 树形结构的关联式容器

根据应用场景的不同，STL总共实现了两种不同结构的关联式容器：树型结构与哈希结构。

树型结构的关联式容器主要有四种：

<font color = blue>map、set、multimap、multiset。 这四种容器的共同点是：使用平衡二叉搜索树(即红黑树)作为其底层结构，容器中的元素是一个有序的序列。 <font color = black>关于平衡二叉树我们后面也会讲到，其实我们在前面几篇文章讲解搜索二叉树的时候也提到过，普通的搜索二叉树如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。 那平衡二叉树顾名思义就是在普通搜索二叉树的基础上让它变的平衡(需要对树中的结点进行调整)。 这个我们后面讲到再细说。

下面一依次介绍每一个容器。

3. set

3.1 认识set

首先我们来看一下set

<font color = "#000066">还是一个类模板，有三个模板参数，但其实平时我们使用的时候一般只需要管第一个模板参数就行了。 因为后两个都是缺省值的，当然如果你想改变它底层搜索树的排序方式你可以自己传第二个比较方式的仿函数（默认是升序）。

关于set的仔细介绍大家可以去看文档 不过是英文的，大家可以借助翻译工具查看

3.1 set的使用

<font color = black>由于我们之前已经学了好几个STL里面的容器，所以这里对于这些容器的使用，其实对我们应该是比较轻松的。所以我这里就不会像之前那样特别仔细去一个个介绍它的接口了，很多东西相信到现在这个阶段大家看着文档都能搞懂。 它提供的接口大家可以先看一下，当然其中一些都不常用。

那我们上面说到：

<font color = "#000066">这几个关联式容器它们的底层结构其实就是我们之前学的二叉搜索树，只不过是平衡搜索树罢了。 那set其实就对应我们前面学的搜索二叉树的应用里面的K模型，下面要学的map就对应KV模型。

那我们接下来就来熟悉一下它的使用：

看一下它的构造函数

<font color = black> 那我们来构造一个空的set，然后插入一些值 首先使用set要包含对于的头文件#include <set> 我们使用insert插入几个元素（这里我们看他的接口其实就没有push啥的了，一般线性的序列式容器才会有push）。 当然inset还有其它版本，不常用，大家可以自行了解。

那然后我想打印出来看看，那我们就可以使用迭代器去遍历它

<font color = black> 但是我们看到这里打印出来是1，2，3，4。 但是我们插入了好几个值啊，并且是无序的，那这里怎么回事呢？ 🆗，上面说了它的底层是平衡二叉树，那我们学过二叉搜索树其实就明白怎么回事了： <font color = "#000066">搜索二叉树一般是不能有重复值的，所以如果多次插入相同的值，后面的就会插入失败（或者可以理解成它会自动进行去重）；另外我们知道二叉搜索树也叫做二叉排序树，中序遍历就可以得到一个升序序列，所以这里默认遍历打印出来就是有序了。 <font color = blue>所以可以认为set可以实现排序+去重 <font color = black>那支持迭代器的话，我们就可以用范围for。

那大家思考一下我们可以修改它里面的值吗？

<font color = black> 当然是不行的，因为我们说了它的底层是搜索树，那搜索树如果我们可以任意修改里面的值的话，修改之后还能保证它还是一棵搜索树吗？ 就不一定了，因为搜索树是需要满足对于的大小规则的。 所以不能修改。

如果我们想判断一个元素在不在set对象里面

<font color = black>可以用find接口 但其实还可以用另一个接口——count count是统计元素的个数，但是我们的set里面不允许重复值，所以结果只有1和0，存在就是1，不存在就是0

那剩下的其它的接口，我们这里就不介绍了，有了前面的基础，相信大家一看就会，还有的就是不怎么用的，或者现阶段我们不是很能看懂的。

4. multiset

那在<set>这个头文件里面呢，出来set，还有一个multiset

<font color = black> multiset叫做多重集合，multi有多种的意思嘛。 还是这些接口。

那它跟set有什么区别呢？

<font color = blue>🆗，它跟set最大的区别就是允许里面存的key值冗余。 <font color = black>我们可以来看一下 可以认为它有排序，但没进行去重 那允许键值冗余的话它的插入怎么做呢？ 那就接着插就行了，即使插入的是已经存在的值，那搜索树的话我们说大的值要插入到右子树，小的插入到左子树，那现在相等的话其实插入到哪边都可以，可以左边也可以右边，反正平衡二叉树嘛，插入之后会对结点进行调整使得两边平衡（我们后面会讲平衡二叉树）。

然后想给大家说一下find：

<font color = black>现在允许键值冗余了，那就有一个问题： 如果我们find某个值的话，跟他有多个相同的值，那find的时候查找的是哪一个？ <font color = blue>🆗，规定呢它find的是中序遍历遇到的第一个。 它遍历的时候底层走的是中序遍历嘛，所以打印出来才是有序的。 <font color = black>我们可以验证一下的： 现在有4个1，我们find(1)，然后从返回的迭代器位置开始，如果能把4个1都打印出来，就证明是中序的第一个1 当然我们可以用count统计每个键值的个数： <font color = black>

不过在实际应用中用multiset一般比较少。

5. map

5.1 认识map

map呢其实就对应搜索二叉树的KV模型，它里面存的是<key, value>结构的键值对。即用来表示具有一 一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息。 map的接口呢也跟set几乎差不多，有需要注意的我们后面会说。

5.2 pair

那在学习map的使用之前，我们来学一个STL里面的类/结构体模板——pair

我们来看一下SGI-STL中关于pair的定义：

template <class T1, class T2>
struct pair
{
    typedef T1 first_type;
    typedef T2 second_type;
    T1 first;
    T2 second;
    pair() 
        : first(T1())
        , second(T2())
    {}
    pair(const T1& a, const T2& b) 
        : first(a)
        , second(b)
    {}
};

pair的应用：

<font color = "#000066">pair是将2个数据组合成一个数据，当需要这样的需求时就可以使用pair。 （1）STL中的map就是将key和value放在一起来保存（一般first对应key，second对应value）。 （2）另一个应用是，当一个函数需要返回2个数据的时候，可以选择pair

所以可以认为pair就是库里面提供的一个键值对的类。

5.3 map的使用

那我们看到map的insert：

<font color = black> 它的第一个版本其实就是接收一个pair类型的对象。 key是const修饰的，不能修改（即键必须是唯一的），value可以。

那我们来写写代码吧，可以用map写一个我们之前实现的那个英汉互译的词典

<font color = black>map包含在头文件<map>中 当然插入还可以用这个 那这个make_pair是啥呢？ 他其实是库里面提供的一个函数模板 它可以帮助我们创建一个pair的对象，用它的好处是我们不需要自己去指定类型，因为模板可以自动推导类型。 然后我们来遍历打印一下： 当然我们也可以这样写： 那大家看这样可以吗？ 最后一个可以插入成功吗？ <font color = "#000066">不行，因为键必须是唯一的，不能重复，值可以重复。 一个键只能对应一个值，一个值可以对应多个键 也可以直接通过find键去查找值

那我们也用map再写一下统计次数的程序：

<font color = black>跟之前的思路一样，我就直接上代码了

对map中[]的理解

然后呢，我们发现，map呢还提供了这样一个接口

<font color = black> 它的作用是啥呢？ 首先它接收的参数是键key，如果输入的键与容器中元素的键匹配，就返回该键对应的值的引用。 所以我们刚才的统计次数还可以这样写 for循环内一行代码，就搞定了

那我们接下来就来研究一下这句代码：

<font color = black> 其实文档上面也解释了，调用这个重载的[]就等效于执行这句代码 （*（（this->insert（make_pair（k，mapped_type（）））.first））.second 所以这个函数大概是这样一个样子： 我们看到这里面其实去调了一下insert，那我们来仔细研究一下insert的返回值 我再来解释一下： <font color = blue>首先要知道插入的话呢还是有成功和失败两种情况，因为键值不允许冗余；它返回的是一个pair，第一个模板参数为迭代器，第二个为bool。 当插入成功的时候，pair的first为指向新插入元素的迭代器，second为true，当插入失败的时候（其实就是插入的键已经存在了），那它的first为容器中已存在的那个相同的等效键元素的迭代器，second为false。 所以后面这个bool其实是标识插入成功还是失败。 <font color = black>那我们再来看这个函数 我们来拆解一下它，要不然不好看 然后我们再来看里面这个insert <font color = blue>我们看到这里面insert也是使用make_pair这个函数创建一个pair对象，第一个参数就是我们[]里面放的那个键key，第二个参数传的是啥呢？ 我们看到它是调了值value的类型的默认构造（之前我们说过有了模板之后内置类型就也需要有构造函数了），那我们的value是int，默认构造的值是0，所以我们第一次插入刚好它的次数就是0了。然后返回这个次数对应的value的引用，外面对它++，就正好是1。 然后后续插入相同键的话，就插入失败，不会将次数变成0，但是依然返回次数（对应pair中的second）的引用，我们从1继续往上++就行了， <font color = black>当然它这上面给的有些类型是进行了typedef的，我们不太好看，不过它提供了一个表，大家可以查阅 所以我们可以将它简化一下，方便看

所以我们也可以这样玩：

<font color = black> 插入，查找、修改啥的操作这样写

【==总结==】

<font color = black>1. map中的的元素是键值对 <font color = black>2. map中的key是唯一的，并且不能修改 <font color = black>3. 默认按照小于的方式对key进行比较 <font color = black>4. map中的元素如果用迭代器去遍历，可以得到一个有序的序列 <font color = black>5. map的底层为平衡搜索树(红黑树)，查找效率比较高$O(log_2 N)$ <font color = black>6. 支持[]操作符，operator[]中实际进行插入查找

6. multimap

那和set一样：

<font color = black>除了map还有multimap

我们看一下

<font color = black> 同样的，跟map相比，multimap允许键key冗余 所以它的接口里面就没有[]了

简单演示一下：

<font color = black> 当然key和value都相同也是可以的。

然后其它的就不多说了，有需要大家可以自己查阅文档。

7. 源码

#define _CRT_SECURE_NO_WARNINGS
​
#include <iostream>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
​
void test_set1()
{
    set<int> s;
    s.insert(3);
    s.insert(1);
    s.insert(4);
    s.insert(2);
    s.insert(1);
    s.insert(2);
​
    int x;
    while (cin >> x)
    {
        if (s.count(x))
        {
            cout << "在" << endl;
        }
        else
        {
            cout << "不在" << endl;
        }
    }
    /*while (cin >> x)
    {
        auto ret = s.find(x);
        if (ret != s.end())
        {
            cout << "在" << endl;
        }
        else
        {
            cout << "不在" << endl;
        }
    }*/
​
    //for (set<int>::iterator it = s.begin(); it != s.end(); it++)
    //{
    //  cout << *it << " ";
    //}
    //cout << endl;
​
    //for (auto e : s)
    //{
    //  cout << e << " ";
    //}
    //cout << endl;
}
void test_set2()
{
    multiset<int> s;
    s.insert(3);
    s.insert(1);
    s.insert(4);
    s.insert(2);
    s.insert(1);
    s.insert(1);
    s.insert(1);
    s.insert(2);
​
    //for (auto e : s)
    //{
    //  cout << e << " ";
    //}
    //cout << endl;
​
    auto ret = s.find(1);
    for (auto it = ret; it != s.end(); ++it)
    {
        cout << *it << " ";
    }
    cout << endl;
​
    cout << s.count(1) << endl;
}
​
void test_map1()
{
    map<string, string> m;
    //m.insert(pair<string, string>("sort", "排序"));
    m.insert(make_pair("sort", "排序"));
    m.insert(make_pair("string", "字符串"));
    m.insert(make_pair("left", "左"));
    m.insert(make_pair("right", "右"));
    m.insert(make_pair("english", "英语"));
    m.insert(make_pair("eng", "英语"));
​
    m["gril"];//插入
    m["boy"] = "男孩";//插入加修改（string默认构造值为""，将它修改成男孩）
    m["sort"] = "(排序)";//修改
    cout << (m["eng"])<< endl;//查找
​
    //for (map<string, string>::iterator it = m.begin(); it != m.end(); it++)
    //{
    //  //cout << (*it).first << ":" << (*it).second << endl;
    //  cout << it->first << ":" << it->second << endl;
​
    //}
    cout << endl;
}
​
void test_map2()
{
    string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
"苹果", "香蕉", "苹果", "香蕉" };
    map<string, int> m;
    /*for (auto& e : arr)
    {
        auto ret = m.find(e);
        if (ret == m.end())
        {
            m.insert(make_pair(e, 1));
        }
        else
        {
            ret->second++;
        }
    }*/
    for (auto& e : arr)
    {
        m[e]++;
    }
    for (auto& e : m)
    {
        cout << e.first << ":" << e.second << endl;
    }
    cout << endl;
}
​
void test_map3()
{
    multimap<string, string> m;
    //m.insert(pair<string, string>("sort", "排序"));
    m.insert(make_pair("sort", "排序"));
    m.insert(make_pair("string", "字符串"));
    m.insert(make_pair("left", "左"));
    m.insert(make_pair("right", "右"));
    m.insert(make_pair("english", "英语"));
    m.insert(make_pair("english", "(--英语--)"));
​
    for (auto& e : m)
    {
        cout << e.first << ":" << e.second << endl;
    }
    cout << endl;
}
​
int main()
{
    test_map3();
​
    return 0;
}
​
​