目录

一、关联式容器

二、键值对

三、set

3.1 set 的介绍

3.2 set 的使用

3.3. set 的使用举例

四、map

4.1 map的介绍

3.2 map 的使用

4.3 map的使用举例

五、经典练习题

1.set的使用

2.map的使用

思路一(稳定排序)：

思路二(priority_queue)：

在之前，我们接触过 vector、list、deque……，这些容器被称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。那么什么是关联式容器呢？

关联式容器：关联式容器也是用来存储数据的，与序列式容器不同的是，其中存储的是结构的键值对，在数据检索时比序列式容器效率更高。

用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量 key 、value。

key代表键值，value 表示与 key 对应的信息。比如：现在要建立一个英汉互译的字典，那该字典必然有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该英文单词，在字典中就可以找到其对应的中文含义。

SGI-STL中关于键值对的定义：

templatestruct 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)
    {}
};

这里是 set 的文档介绍：set的介绍_C++reference 以下是几个重要点。 

1. set 是按照一定次序存储的容器
2. 在 set 中，元素的 value 也标识它(value 就是 Key，类型为 T)，并且每个 value 必须是唯一的。set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。
3. 在内部，set 中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。
4. set 容器通过 key 访问单个元素的速度通常比 unordered_set 容易慢，但它们允许根据顺序对子集进行直接迭代。
5. set 在底层是用二叉搜索树(红黑树)实现的。

1. set 的模板参数列表

T：set 中存放元素的类型，实际在底层存储的键值对。

Compare：set 中元素默认按照小于来比较。

Alloc：set 中元素空间的管理方式，使用STL提供的空间配置器管理。

2. set 的构造函数

3. set 的迭代器

4. set 的修改操作

map的文档简介 以下是几个重要点：

1. map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。
2. 在map中，键值key通常用于排序和唯一的标识元素，而值value中存储与此key关联的内容。简直key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取名别称为pair
3. 在内部，map中的元素总是按照及那只key进行排序的。
4. map中通过简直访问但各国元素的熟读通常比unordered_map容器慢，但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)
5. map支持下标访问操作符，即在[]中放入key，就饿可以找到与key对应的value。
6. map通常被实现为二叉搜索树(准确的说是红黑树)

1.map的模板参数说明

• key：键值对中key的类型
• T：键值对中value的类型
• Compare：比较器的类型。默认为less，如果存在特殊的比较，需要用户自己显示传入比较规则(函数指针或仿函数进行传递)

2.map的构造函数

3.map的迭代器

4.insert

首先我们来看看insert的使用，首先要知道map的insert是插入pair类型的数据

然后我们举例进行插入一下

void test_map1()
{
	//创建字典
	mapdict1;
	mapdict2;
	mapdict3;
	//插入数据——方式1、
	pairkv1("sort", "排序");
	pairkv2("insert", "插入");
	dict1.insert(kv1);
	dict1.insert(kv2);

	//插入数据——方式2、匿名对象
	dict2.insert(pair("sort", "排序"));
	dict2.insert(pair("insert", "插入"));

	//插入数据——方式3、make_pair()
	dict3.insert(make_pair("sort", "排序"));
	dict3.insert(make_pair("insert", "插入"));
}

插入方式3，make_pair其实是一个模板函数，就是为了方便我们进行pair结构的插入数据。

4. 下标访问操作符

这里我们实现一个统计水果次数功能的map，如下：

但是这样的插入方式，非常的麻烦，所以map将下标访问操作符进行了重载，让其插入数据变得十分轻松。以下是 map中下标访问操作符：

功能解析：

1. map中有这个key，返回value的引用。(查找、修改value)
2. map中没有这个key，会插入pair(key,V())，并返回value的引用。(插入+修改)

其实下标访问操作符的本质是调用了 insert 函数，下面的文档中的实现方式：

这种方式其实不是太好理解，这里我们可以将其分为两步，就非常好理解了。

因为返回的是其value的引用，所以我们可以对其进行赋值，这也是一种插入方式，也是最简单的一种插入方式。

所以，在上面实现统计水果次数的map中，我们可以将其插入方式改为 [] 插入：

题目链接：349. 两个数组的交集

题目介绍：

算法思路1：

1. 因为是求交集，所以我们可以使用set对nums1、nums2进行排序+去重。
2. 遍历set1，判断set1中的值是否存在于set2中，如果存在，则放到结果数组中，不存在则跳过(时间复杂度：O(N*N))。

算法思路2：

1. 因为是求交集，所以我们可以使用set对nums1、nums2进行排序+去重。
2. 同时处理两个区间，让it1指向的值与it2指向的值进行比较，如果相等则为交集，两个迭代器同时向后移动，如果不相等，结果小的迭代器进行向后移动(时间复杂度:O(N))

两种算法就是找交集的代码不同，这里一并给出源代码：

class Solution {
public:
    vectorintersection(vector& nums1, vector& nums2) {
        sets1;
        sets2;
        //去重  
        for(auto& e: nums1)
            s1.insert(e);
            
        for(auto& e: nums2)
            s2.insert(e);
        //找交集
        vectorresult;
        //方法1：
        for(auto& e: s1)
        {
            if (s2.find(e)!=s2.end())
                result.push_back(e);
        }
        //============================================
        //方法2：
        set::iterator it1=s1.begin();
        set::iterator it2=s2.begin();
        while(it1!=s1.end()&&it2!=s2.end())
        {
            if (*it1==*it2)
            {
                result.push_back(*it1);
                it1++,it2++;
            }
            else if (*it1>*it2) it2++;
            else it1++;
        }
        return result;
    }
};

题目链接：692. 前K个高频单词

题目介绍：

这题的难点就在于出现频率相等的情况下，要按照字典序排序，这就意味着不能简单的使用一次排序解决。

算法思路：

1. 使用map根据其字典序进行排序，并统计单词的出现次数。
2. 通过sort根据单词的出现次数进行排序。

使用了map存储后，单词在map中都按出现次数进行排序，但是此时，如果我们使用一种稳定排序，让其在符合次数相同时，并进行字典序的排序，就可以完成最终的排序。

首先 sort 是一个的迭代器是随机迭代器(RandomAccess Iterator)，而map双向迭代器(bidirectional iterator)，所以我们要先将map中的数据放入到一个数组中。

因为sort是快速排序，不稳定的排序，所以我们要编写仿函数控制其排序的结果。

仿函数的比较规则：

1. 如果出现次数多，则排在前面，返回true。
2. 出现次数相同时再比较字典序，如果kv1的字典序小于kv2，即kv1在kv2前，则返回true，编写这条规则可以间接控制稳定性。
3. 其他情况直接返回false。

class Solution {
public:
    struct Greater{
        bool operator()(const pair& kv1,const pair& kv2)
        {
            //按次数比较
            if (kv1.second >kv2.second)
                return true;
            //次数相同，按字典序比较。
            if (kv1.second==kv2.second&&kv1.first< kv2.first)
                return true;
            return false;
        }
    };
    vectortopKFrequent(vector& words, int k) {
        mapcountMap;
        for(auto& str:words)
        {
            countMap[str]++;
        }
        //导数据，因为迭代器类型不同
        vector>sortV(countMap.begin(),countMap.end());
        sort(sortV.begin(),sortV.end(),Greater());

        vectorresult;
        for(int i=0;i

因为map中已经按照字典序进行了排序，所以我们只需要使用一种稳定的排序，将出现次数多的调整到前面，出现次数相同则不进行调整。

库中的稳定排序(stable_sort)：

进行以下修改即可：

struct Less {
	bool operator()(const pair& kv1, const pair& kv2)
	{
		//按次数比较
		if (kv1.second< kv2.second)
			return true;
		//次数相同，按字典序比较。
		if (kv1.second == kv2.second && kv1.first >kv2.first)
			return true;
		return false;
	}
};

class Solution {
public:
    struct Less{
        bool operator()(const pair& kv1,const pair& kv2)
        {
            //按次数比较
            if (kv1.secondkv2.first)
                return true;
            return false;
        }
    };
    vectortopKFrequent(vector& words, int k) {
        mapcountMap;
        for(auto& str:words)
        {
            countMap[str]++;
        }
        //迭代器区间初始化
        priority_queue,vector>,Less>maxHeap(countMap.begin(),countMap.end());
        vectorresult;
        while(k--)
        {
            result.push_back(maxHeap.top().first);
            maxHeap.pop();
        }
        return result;
    }
};