C++:关联式容器的介绍及map与set的使用

我们之前已经学习过string,vector,list,queue,priority_queue等容器，这些容器我们统称为序列式容器，因为它们的数据的逻辑结构呈线性。因为这些容器中存储的数据即便二者之间发生交换，也不会对原有的容器结构造成太大影响。

但上篇文章我们介绍到了二叉搜索树，如果之前有在leetcode上刷过题目的朋友肯定会遇到哈希表这一种题型标签。它的最简单的形式就是我们的鸽巢数组，我们能够通过下标来快速索引目标值以O(1)的时间复杂度。这种容器其实就是我们今天所要介绍的关联式容器，因为它们的位置和自身存储的值都有着密切关系，一旦数据发生交换，原有的容器结构将会造成极大的破坏，我们先从最简单的set和multiset关联式容器开始介绍：

一，set系列容器

<set> - C++ Reference

 set的底层是一棵红黑树。但我们这里先暂且不介绍红黑树的模拟实现，我们先来了解set系列容器的用法，这会对我们之后文章模拟实现红黑树有很大帮助：

1.1set类的介绍

set类的声明如下：

template < class T, // set::key_type/value_typeclass Compare = less<T>, // set::key_compare/value_compareclass Alloc = allocator<T> // set::allocator_type
> class set;

可以看到大致上与我们之前所学容器一致：1.键值(k)类型2.升或降序(仿函数，注意这里的反人设计，我们在优先级队列处也知道，传less<T>建的是大堆，而greater<T>则是小堆，这里也类似)。

其他的几点注意事项：

1. set底层存储数据的内存是从空间配置器申请的，如果需要可以⾃⼰实现内存池，传给第三个参数。
2. ⼀般情况下，我们都不需要传后两个模版参数
3. set底层是⽤红⿊树实现，增删查效率是O(logN)，迭代器遍历是⾛的搜索树的中序，所以是有序的。 

 1.2set的构造和迭代器

set的⽀持正向和反向迭代遍历，遍历默认按升序顺序，因为底层是⼆叉搜索树，迭代器遍历⾛的中序，⽀持迭代器就意味着⽀持范围for，set的iterator和const_iterator都不⽀持迭代器修改数据，修改关键字数据，破坏了底层搜索树的结构。 

1.3set的增删查改 

// 单个数据插⼊，如果已经存在则插⼊失败
pair<iterator, bool> insert(const value_type& val);
// 列表插⼊，已经在容器中存在的值不会插⼊
void insert(initializer_list<value_type> il);
// 迭代器区间插⼊，已经在容器中存在的值不会插⼊
template <class InputIterator>
void insert(InputIterator first, InputIterator last);
// 查找val，返回val所在的迭代器，没有找到返回end()
iterator find(const value_type& val);
// 查找val，返回Val的个数
size_type count(const value_type& val) const;
// 删除⼀个迭代器位置的值
iterator erase(const_iterator position);
// 删除val，val不存在返回0，存在返回1
size_type erase(const value_type& val);
// 删除⼀段迭代器区间的值
iterator erase(const_iterator first, const_iterator last);
// 返回⼤于等val位置的迭代器
iterator lower_bound(const value_type& val) const;
// 返回⼤于val位置的迭代器
iterator upper_bound(const value_type& val) const;

重点了解以上几个即可，我们注意到上面出现了一个我们之前没有见过的新类型pair，这个我们下面介绍map时会着重介绍。

这里读者可以自行下去进行实验，与我们所学过的二叉搜索树大致用法相同。

1.3multiset与set的区别 

set所存储的数据中，不会出现重复的元素。而multiset允许重复元素的存在，这就是这二者的最大区别。需要注意的是，如果我们想要删除某一特定键值结点，我们必须要传入它的迭代器位置，而不是传入它的迭代器的值，后者会把所有与输入键值相同的结点完全删除。

1.4以set的视角来看待两道力扣题 

. - 力扣（LeetCode）

这道题要求我们去找两个数组的交集，如果是我们还没有学set时，我们的第一想法可能是先分别对两个数组进行排序，然后利用双指针来找相等元素进行解决。但此时我们了解set中不能存在重复元素的特性后，我们可以用以下的这种解法：

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

虽然时间复杂度与前者别无二至，但确实是一种在博主看来比较新颖的一种做法。

 下面这道题我们在学习链表数据结构时做过，就是leetcode的环形链表II，当时我们第一次做的时候可能还废了点力气去推导为甚么快指针最后一定会与慢指针相遇且在环口处相遇。但这里如果用上了set那简直就是降维打击：

. - 力扣（LeetCode）

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

简介明了，而且在使用过set后会非常容易想到，虽然要耗费额外的空间，但在大家都会双指针的情况下，这种方式是不是更新颖，而且能够耗费更少的时间去推导呢？所以不仅仅是对博主自己的建议，也是对大家的建议，或许我们选择解法时都会尽可能的选择最优算法，但最优的算法往往没有那么容易想到，或许我们退而求其次，不追求极致的优化，或许也会逊色于最优，但却也能让人眼前一亮。

二，Pair类型介绍

map底层的红⿊树节点中的数据，使⽤pair存储键值对数据。 所以在介绍map之前，我们先来了解一下pair。有助于我们接下来了解 map。

typedef pair<const Key, T> value_type;
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){}template<class U, class V>pair(const pair<U, V>& pr) : first(pr.first), second(pr.second){}
};template <class T1, class T2>
inline pair<T1, T2> make_pair(T1 x, T2 y)
{return (pair<T1, T2>(x, y));
}

 现在我们转过来了解下set中的这串声明：

// 单个数据插⼊，如果已经存在则插⼊失败
pair<iterator, bool> insert(const value_type& val);

我们知道，在set中插入元素后，根据我们以往的经验，它应该是返回插入元素的下标。但这里又多了个bool。因此我们结合上面pair的定义可以大致推出，无论是否插入成功，insert函数都会返回插入元素的迭代器所在位置，而bool类型数据则是记录插入是否成功：

//比如我们有以下一个定义式
pair<iterator,bool> n = Set.insert(9);//n.first = ...:插入的数据的迭代器位置
//n.second = true/false//插入成功/失败

三，map系列容器

 3.1map的定义

<map> - C++ Reference

map的声明如下，Key就是map底层关键字的类型，T是map底层value的类型，set默认要求Key⽀持⼩于⽐较，如果不⽀持或者需要的话可以⾃⾏实现仿函数传给第⼆个模版参数，map底层存储数据的 内存是从空间配置器申请的。⼀般情况下，我们都不需要传后两个模版参数。map底层是⽤红⿊树实现，增删查改效率是 O(logN) ，迭代器遍历是⾛的中序，所以是按key有序顺序遍历的。 

template < class Key, // map::key_typeclass T, // map::mapped_typeclass Compare = less<Key>, // map::key_compareclass Alloc = allocator<pair<const Key, T> > //map::allocator_type
> class map;

 3.2map的构造

map的⽀持正向和反向迭代遍历，遍历默认按key的升序顺序，因为底层是⼆叉搜索树，迭代器遍历⾛的中序。⽀持迭代器就意味着⽀持范围for，map⽀持修改value数据，不⽀持修改key数据，修改关键字数据，破坏了底层搜索树的结构。

// empty (1) ⽆参默认构造
explicit map(const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());
// range (2) 迭代器区间构造
template <class InputIterator>
map(InputIterator first, InputIterator last,const key_compare& comp = key_compare(),const allocator_type & = allocator_type());
// copy (3) 拷⻉构造
map(const map& x);
// initializer list (5) initializer 列表构造
map(initializer_list<value_type> il,const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());
// 迭代器是⼀个双向迭代器
iterator->a bidirectional iterator to const value_type
// 正向迭代器
iterator begin();
iterator end();
// 反向迭代器
reverse_iterator rbegin();
reverse_iterator rend();

3.3map的增删查

map增接⼝,插⼊的pair键值对数据,跟set所有不同,但是查和删的接⼝只⽤关键字key跟set是完全类似的,不过find返回iterator,不仅仅可以确认key在不在,还找到key映射的value,同时通过迭代 还可以修改value。

Member types
key_type->The first template parameter(Key)
mapped_type->The second template parameter(T)
value_type->pair<const key_type, mapped_type>
// 单个数据插⼊，如果已经key存在则插⼊失败,key存在相等value不相等也会插⼊失败
pair<iterator, bool> insert(const value_type& val);
// 列表插⼊，已经在容器中存在的值不会插⼊
void insert(initializer_list<value_type> il);
// 迭代器区间插⼊，已经在容器中存在的值不会插⼊
template <class InputIterator>
void insert(InputIterator first, InputIterator last);
// 查找k，返回k所在的迭代器，没有找到返回end()
iterator find(const key_type& k);
// 查找k，返回k的个数
size_type count(const key_type& k) const;
// 删除⼀个迭代器位置的值
iterator erase(const_iterator position);
// 删除k，k存在返回0，存在返回1
size_type erase(const key_type& k);
// 删除⼀段迭代器区间的值
iterator erase(const_iterator first, const_iterator last);
// 返回⼤于等k位置的迭代器
iterator lower_bound(const key_type& k);
// 返回⼤于k位置的迭代器
const_iterator lower_bound(const key_type& k) const;

3.4map的数据修改 

map第⼀个⽀持修改的⽅式时通过迭代器，迭代器遍历时或者find返回key所在的iterator修改，map 还有⼀个⾮常重要的修改接⼝operator[]，但是operator[]不仅仅⽀持修改，还⽀持插⼊数据和查找数据，所以他是⼀个多功能复合接⼝需要注意从内部实现⻆度，map这⾥把我们传统说的value值，给的是T类型，typedef为 mapped_type。⽽value_type是红⿊树结点中存储的pair键值对值。⽇常使⽤我们还是习惯将这⾥的T映射值叫做value。

value_type->pair<const key_type, mapped_type>
// 查找k，返回k所在的迭代器，没有找到返回end()，如果找到了通过iterator可以修改key对应的
//mapped_type值
iterator find(const key_type& k);
// ⽂档中对insert返回值的说明
// The single element versions (1) return a pair, with its member pair::first
//set to an iterator pointing to either the newly inserted element or to the
//element with an equivalent key in the map.The pair::second element in the pair
//is set to true if a new element was inserted or false if an equivalent key
//already existed.
// insert插⼊⼀个pair<key, T>对象
// 1、如果key已经在map中，插⼊失败，则返回⼀个pair<iterator,bool>对象，返回pair对象
//first是key所在结点的迭代器，second是false
// 2、如果key不在在map中，插⼊成功，则返回⼀个pair<iterator,bool>对象，返回pair对象
//first是新插⼊key所在结点的迭代器，second是true
// 也就是说⽆论插⼊成功还是失败，返回pair<iterator,bool>对象的first都会指向key所在的迭
//代器
// 那么也就意味着insert插⼊失败时充当了查找的功能，正是因为这⼀点，insert可以⽤来实现
//operator[]
// 需要注意的是这⾥有两个pair，不要混淆了，⼀个是map底层红⿊树节点中存的pair<key, T>，另
//⼀个是insert返回值pair<iterator, bool>
pair<iterator, bool> insert(const value_type & val);
mapped_type& operator[] (const key_type& k);
// operator的内部实现
mapped_type& operator[] (const key_type& k)
{// 1、如果k不在map中，insert会插⼊k和mapped_type默认值，同时[]返回结点中存储// mapped_type值的引⽤，那么我们可以通过引⽤修改返映射值。所以[]具备了插⼊ + 修改功能// 2、如果k在map中，insert会插⼊失败，但是insert返回pair对象的first是指向key结点的//迭代器，返回值同时[]返回结点中存储mapped_type值的引⽤，所以[]具备了查找 + 修改的功能pair<iterator, bool> ret = insert({ k, mapped_type() });iterator it = ret.first;return it->second;
}

 3.5map与multimap的区别

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

下面两道是可以使用map来解决的两道题目，这里我们就不再给出解决方法了，我们可以先用一般思路来做这两道题，之后再用map相关知识来做，能够对map有一个更深的了解:

. - 力扣（LeetCode）

. - 力扣（LeetCode）