【C++】关联式容器——map和set的使用

一、 序列式容器和关联式容器

序列式容器：前⾯我们已经接触过STL中的部分容器如：string、vector、list、deque、array、forward_list等，这些容器统称为序列式容器，因为逻辑结构为线性序列的数据结构，两个位置存储的值之间⼀般没有紧密的关联关系，⽐如交换⼀下，他依旧是序列式容器。顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的。

关联式容器: 关联式容器也是⽤来存储数据的，与序列式容器不同的是，关联式容器逻辑结构通常是⾮线性结构，两个位置有紧密的关联关系，交换⼀下，他的存储结构就被破坏了。顺序容器中的元素是按关键字来保存和访问的。关联式容器有map/set系列和unordered_map/unordered_set系列。

本章节讲解的map和set底层是红⿊树，红⿊树是⼀颗平衡⼆叉搜索树。set是key搜索场景的结构，map是key/value搜索场景的结构。

二、set的介绍

T: set中存放元素的类型，实际在底层存储<value, value>的键值对。
Compare：仿函数，set中元素默认按照小于来比较
Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理

1.set的构造和迭代器

默认构造、迭代器区间构造、拷贝构造（深拷贝）:

void test_set()
{int arr[] = { 1,2,3,4,5 };set<int> s;//默认构造set<int> s1(arr, arr + 5);//区间构造set<int> s2(s1);//拷贝构造for (auto e : s1) cout << e << " "; cout << endl;for (auto e : s2) cout << e << " "; cout << endl;}

set的迭代器遍历采用中序遍历，可以用于排序+去重。

我们简单来看一看代码把：

void test_set1()
{set<int> s;默认是升序，如果是想要降序：使用反向迭代器 仿函数：greater：s.insert(1);s.insert(2);s.insert(1);s.insert(3);s.insert(4);s.insert(5);//排序+去重for (auto e : s){cout << e << " ";}cout << endl;//set<int>::iterator it = s.begin();auto it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << endl;}
int main()
{test_set1();return 0;
}

2.set的增删查

// 插⼊⼀段initializer_list列表值，已经存在的值插⼊失败
s.insert({ 2,8,3,9 });
for (auto e : s)
{
cout << e << " ";
}cout << endl;
set<string> strset = { "sort", "insert", "add" };
// 遍历string⽐较ascll码⼤⼩顺序遍历的
for (auto& e : strset)
{
cout << e << " ";
} 
cout << endl;

int main()
{set<int> s = { 4,2,7,2,8,5,9 };for (auto e : s){cout << e << " ";} cout << endl;// 删除最⼩值s.erase(s.begin());for (auto e : s){cout << e << " ";}cout << endl;// 直接删除xint x;cin >> x;int num = s.erase(x);if (num == 0){cout << x << "不存在！" << endl;} for (auto e : s){cout << e << " ";}cout << endl;// 直接查找在利⽤迭代器删除xcin >> x;auto pos = s.find(x);if (pos != s.end()){s.erase(pos);} else{cout << x << "不存在！" << endl;} for (auto e : s){cout << e << " ";} cout << endl;// 算法库的查找 O(N)auto pos1 = find(s.begin(), s.end(), x);// set⾃⾝实现的查找 O(logN)auto pos2 = s.find(x);// 利⽤count间接实现快速查找cin >> x;if (s.count(x)){cout << x << "在！" << endl;} else{cout << x << "不存在！" << endl;} return 0;
}

但是count不是为此设计的！是为了和multiset容器保持接口的一致性。

3.接口lower_bound和upper_bound

lower_bound返回大于等于目标值的迭代器，upper_bound返回大于目标值的迭代器，在set中用于返回目标值的迭代器。（比如找到两个边界的迭代器，就可以使用erase对数据进行删除）

int main()
{std::set<int> myset;for (int i = 1; i < 10; i++)myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90for (auto e : myset){cout << e << " ";} cout << endl;// 实现查找到的[itlow,itup)包含[30, 60]区间// 返回 >= 30auto itlow = myset.lower_bound(30);// 返回 > 60auto itup = myset.upper_bound(60);// 删除这段区间的值myset.erase(itlow, itup);for (auto e : myset){cout << e << " ";} cout << endl;return 0;
}

4.multiset和set的差异

multiset和set的使⽤基本完全类似，主要区别点在于multiset⽀持值冗余，那么
insert/find/count/erase都围绕着⽀持值冗余有所差异，具体参看下⾯的样例代码理解:

#include<iostream>
#include<set>
using namespace std;
int main()
{// 相⽐set不同的是，multiset是排序，但是不去重multiset<int> s = { 4,2,7,2,4,8,4,5,4,9 };auto it = s.begin();while (it != s.end()){cout << *it << " ";++it;} cout << endl;// 相⽐set不同的是，x可能会存在多个，find查找中序的第⼀个int x;cin >> x;auto pos = s.find(x);while (pos != s.end() && *pos == x){cout << *pos << " ";++pos;} cout << endl;// 相⽐set不同的是，count会返回x的实际个数cout << s.count(x) << endl;// 相⽐set不同的是，erase给值时会删除所有的xs.erase(x);for (auto e : s){cout << e << " ";}cout << endl;return 0;
}

三、map的介绍

key: 键值对中key的类型
T：键值对中value的类型
Compare: 比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比较，一般情况下(内置类型元素)该参数不需要传递，如果无法比较时(自定义类型)，需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)
Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器

map是关联式容器，根据特定的存储顺序，用于存储由键值及其映射值组合的元素。
可以看到Alloc中有一个键值对pair，这个pair是一个key/value结构的struct模板类。这个类将一对键值耦合在一起，所以，map的存储方式是通过在搜索二叉树中存储键值对pair，而搜索二叉树的k/v模型是在节点中存储key和value，并不相同。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){}
};

1.map的构造

void test_map()
{map<int, int> m;int arr[] = { 1,1,1,2,3,4,5,6 };for (auto& e : arr){m.insert(make_pair(e, e));}map<int, int>m1(m.begin(), m.end());//迭代器区间构造for (auto& e : m1)cout << e.first<<":"<<e.second << " "; cout << endl;map<int, int> m2(m1);//拷贝构造for (auto& e : m2)cout << e.first << ":" << e.second << " "; cout << endl;
}

2.map的增删查

map的insert

// insert插⼊pair对象的4种⽅式，对⽐之下，最后⼀种最⽅便
pair<string, string> kv1("first", "第⼀个");
dict.insert(kv1);
dict.insert(pair<string, string>("second", "第⼆个"));
dict.insert(make_pair("sort", "排序"));
dict.insert({ "auto", "⾃动的" });
// "left"已经存在，插⼊失败
dict.insert({ "left", "左边，剩余" });
// 范围for遍历
for (const auto& e : dict)
{cout << e.first << ":" << e.second << endl;
} 
cout << endl;

map[]的使用：

举一个应用的例子：

void test_map2()
{//统计水果出现的次数string arr[] = { "苹果", "西瓜", "香蕉", "草莓", "苹果", "西瓜", "苹果","苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };map<string, int> countMap;for (auto& e : arr){countMap[e]++;}for (const auto& kv : countMap){cout << kv.first << ":" << kv.second << endl;}
}

operator[]的内部实现:

mapped_type& operator[] (const key_type& k)
{pair<iterator, bool> ret = insert({ k, mapped_type() });iterator it = ret.first;return it->second;
}

1、如果k不在map中，insert会插⼊k和mapped_type默认值，同时[]返回结点中存储
mapped_type值的引⽤，那么我们可以通过引⽤修改返映射值。所以[]具备了插⼊+修改功能

2、如果k在map中，insert会插⼊失败，但是insert返回pair对象的first是指向key结点的
迭代器，返回值同时[]返回结点中存储mapped_type值的引⽤，所以[]具备了查找+修改的功能

3.multimap和map的差异

multimap和map的使⽤基本完全类似，主要区别点在于multimap⽀持关键值key冗余，那么
insert/find/count/erase都围绕着⽀持关键值key冗余有所差异，这⾥跟set和multiset完全⼀样，⽐如find时，有多个key，返回中序第⼀个。其次就是multimap不⽀持[]，因为⽀持key冗余，[]就只能⽀持插⼊了，不能⽀持修改。

四、map和set相关OJ

1.两个数组的交集

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {vector<int>ret;set<int> s1(nums1.begin(), nums1.end());set<int> s2(nums2.begin(), nums2.end());auto p1 = s1.begin();auto p2 = s2.begin();while(p1 != s1.end() && p2 != s2.end()){if(*p1 < *p2) p1++;else if(*p1 > *p2) p2++;else {ret.push_back(*p1);p1++;p2++;}}return ret;}
};

2.环形链表 II

class Solution 
{
public:ListNode *detectCycle(ListNode *head) {set<ListNode*> s;ListNode* cur = head;while(cur){if(s.count(cur))return cur;elses.insert(cur);cur = cur->next;}return nullptr;}
};