46 map与set

目录

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

二、set系列的使用

（一）set和mutilset参考文档链接

（二）set类模板介绍

1、set类声明

2、set的构造和迭代器

3、set的增删查

（三）multiset类模板

1、multiset和set的差异

（四）set的oj题

1、两个数组的交集

2、环形链表

三、map系列的使用

（一）map和multimap参考文档链接

（二）map类介绍

1、map类声明

2、pair类型介绍

 3、map的构造

4、map的增删查

5、map的数据修改

（1）数据修改的接口代码如下

（2）讲解说明

（3）总结

（三）multimap类

1、multimap与map的差异

2、multimapOJ题

（1）随机链表的复制

（2）前K个高频单词

---

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

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

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

        map和set底层是红黑树，红黑树是⼀颗平衡⼆叉搜索树。unordered_map/unordered_set底层为哈希表，后续会进行学习。

        set是key搜索场景的结构，map是key/value搜索场景的结构。

二、set系列的使用

（一）set和mutilset参考文档链接

        https://legacy.cplusplus.com/reference/set/

        set头文件包含两大类，一个是set（不允许数据冗余，即不能插入重复值），一个是multiset（允许数据冗余，可以插入重复值）。

        平常一般是set使用较多。

（二）set类模板介绍

1、set类声明

        • set的声明中的T就是set底层关键字的类型。

        • set默认要求T支持小于比较，如果不支持或者想按自己的需求可以自行实现仿函数传给第二个模版参数。

        • set底层存储数据的内存是从空间配置器申请的，如果需要可以自己实现内存池，传给第三个参数。

        • 一般情况下，我们都不需要传后两个模版参数。

        • set底层是⽤红⿊树实现，增删查效率是O(logN) ，迭代器遍历是走的搜索树的中序，所以是有序的。

        • 前面部分已经学习了vector/list等容器的使用，STL容器接口设计高度相似，所以这里就不再一个个的介绍接口了，而是直接看文档，挑重要的接口进行介绍。

2、set的构造和迭代器

        set的构造我们关注以下几个接口即可。

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

// empty (1) ⽆参默认构造
explicit set (const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());// range (2) 迭代器区间构造
template <class InputIterator>
set (InputIterator first, InputIterator last,const key_compare& comp = key_compare(),const allocator_type& = allocator_type());// copy (3) 拷⻉构造
set (const set& x);// initializer list (5) initializer 列表构造
set (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();

        支持initializer list够着也就是能进行以下方式的构造：

set::set<int> s1 = {1,2,3,4,5,6};

3、set的增删查

        set的增删查关注以下几个接口即可：

Member types
key_type -> The first template parameter (T)
value_type -> The first template parameter (T)
//key_type和value_type指的都是T类型，这样设计是为了与multiset兼容

//① 插入
// 单个数据插⼊，如果已经存在则插⼊失败
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;

        注意：

        ① 在set的插入中，因为要维护关联式容器中存储数据位置之间的关联性，这些容器的方法并没有push（头/尾）方法，只有insert方法。

        ② 在set的查找中，算法库中也存在find函数，为什么要set自己实现一个？因为效率问题：算法库的查找效率为O(N)，为遍历查找，效率低；set自身实现的查找效率为O(logN)，是按照平衡二叉排序树的结构进行查找，效率高。（此外，swap方法也有自身实现的，因为使用算法库的swap要创造中间变量进行两次深拷贝，代价太大了，所以set自己实现了一个。）

        ③ 在set的查找中，set中的count的结果虽然只有0或1，但设计出来是为了与multiset进行兼容。count在set的使用：因为find方法若找到则放回该值的迭代器，没找到就会返回迭代器中的end()，得出结果后还需要比较一下，较为麻烦；而直接count一下看返回值是0或1就可以了。

        示例代码如下：

// 算法库的查找 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;
}

        ④ 在迭代器相关中，lower_bound与upper_bound一般是配合来查找区间的，因为C++中的迭代区间要求为左闭右开（无论是在插入或删除的迭代器区间操作中，都可以配合lower_bound与upper_bound使用）。lower_bound与upper_bound就完美符合该要求，例子如下：

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);// 返回 > 60，位置是指向60后面auto itup = myset.upper_bound(60);// 删除这段区间的值myset.erase(itlow, itup);for (auto e : myset){cout << e << " ";}// 10 20 70 80 90cout << endl;return 0;
}

        算法库中也有lower_bound与upper_bound，但需要进行排序后才能使用。

       insert和迭代器的示例代码如下：

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<set>
using namespace std;int main()
{// 去重+升序排序set<int> s;// 去重+降序排序（给一个大于的仿函数）//set<int, greater<int>> s;s.insert(5);s.insert(2);s.insert(7);s.insert(5);//set<int>::iterator it = s.begin();auto it = s.begin();while (it != s.end()){// error C3892: “it”: 不能给常量赋值// *it = 1;cout << *it << " ";++it;}cout << endl;// 插如一段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;
}

        find和erase示例代码如下：

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;// 直接删除x
int x;
cin >> x;
int num = s.erase(x);
if (num == 0)
{cout << x << "不存在！" << endl;
}
for (auto e : s)
{cout << e << " ";
}
cout << endl;// 直接查找再利用迭代器删除x
cin >> 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;

（三）multiset类模板

1、multiset和set的差异

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

        

void test03()
{// 相比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;}

（四）set的oj题

1、两个数组的交集

        解题思路：分别在每个数组的首元素设置指针，依次比较，小的++，相等的则是交集，放进vector里面，然后同时++，当其中一个结束时就结束了。

        解题代码如下：

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());// 因为set遍历是有序的，有序值，依次⽐较// ⼩的++，相等的就是交集vector<int> ret;auto it1 = s1.begin();auto it2 = s2.begin();while (it1 != s1.end() && it2 != s2.end()){if (*it1 < *it2){it1++;}else if (*it1 > *it2){it2++;}else{ret.push_back(*it1);it1++;it2++;}}return ret;}
};

        注意：前提是需要排序序且去重。而set容器则完美契合。

        该类算法的一般使用场景：数据同步：过程①交集不动，②差集同步。

2、环形链表

        解题思路：把环链表的节点放入set中，若遇到了插入不了的情况，就是环的入口点，也就是相遇点。

        代码如下：

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

三、map系列的使用

（一）map和multimap参考文档链接

        https://legacy.cplusplus.com/reference/map/

        map头文件分为map类模板与multimap类模板。

（二）map类介绍

1、map类声明

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

2、pair类型介绍

        map底层的红黑树节点中的数据，使用pair<Key, T>存储键值对数据，如下代码所示：

typedef pair<const Key, T> value_type;

        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){}//拷贝构造template<class U, class V>pair(const pair<U, V>& pr) : first(pr.first), second(pr.second){}
};

        还可以使用函数模版make_pair创造pair的匿名对象：

template <class T1,class T2>
inline pair<T1,T2> make_pair (T1 x, T2 y)
{return ( pair<T1,T2>(x,y) );
}

 3、map的构造

        map的构造关注以下几个接口即可。

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

        注意：

        ① 可以使用initializer_list进行构造，会先把花括号中的两个字符串隐式类型装换为一个pair对象拷贝到initializer_list中，再插入到dict中，如下代码所示：

void test04()
{pair<string, string> kv = { "pizza","披萨" };map<string, string> dict = { {"pizza","披萨"},{"lemon","柠檬"},{"tea","茶"} };
}

        ② 遍历map想要输出pair的内容时需要指定输出的是key还是value，如下代码所示：

void test04()
{map<string, string> dict = { {"pizza","披萨"},{"lemon","柠檬"},{"tea","茶"} };auto it = dict.begin();while (it != dict.end()){cout << it->first << " : " << it->second << endl;++it;}
}

        此处->是一个重载过的运算符，返回值是一个指针，it->表示的是pair的指针，后面再省略了一个->来引用pair的值，不省略则为：

it.operator->()->first;

        ③ 其他两种遍历map的方法：

        结构化绑定（在c++17中才能使用）：

for (auto [k, v] : dict)
{cout << k << ":" << v << endl;
}
cout << endl;

        范围for：

for (const auto& kv : dict)
{cout << kv.first << ":" << kv.second << endl;
}
for (const auto& [k,v] : dict)
{cout << k << ":" << v << endl;
}

4、map的增删查

        map的增删查关注以下几个接口即可。

        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;

5、map的数据修改

        前面提到map支持修改mapped_type 数据，不支持修改key数据，修改关键字数据，就破坏了底层搜索树的结构。

        map第一个支持修改的方式是通过迭代器，迭代器遍历时或者find返回key所在的iterator修改，map还有⼀个非常重要的修改接口：operator[]，operator[]不仅仅支持修改，还支持插入数据和查找数据，所以他是一个多功能复合接口。

        需要注意的是，从内部实现角度度来看，map把我们传统说的value值，给的是T类型，typedef为mapped_type。而value_type是红黑树结点中存储的pair键值对值。日常使用还是习惯将这里的T映射值叫做value。如下所示：

key_type -> The first template parameter (Key)
mapped_type -> The second template parameter (T)
value_type -> pair<const key_type,mapped_type>

（1）数据修改的接口代码如下

// 查找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;
}

（2）讲解说明

        operator[]方括号接口，实现的是通过下标实现随机访问。

        给key的值，返回对应的value类型的引用。支持插入、查找和修改功能。

        调用operator[]等价于调用如下代码：

(*((this->insert(make_pair(k,mapped_type()))).first)).second

        其中使用了insert方法，该方法的返回值为pair类模板，其中值为迭代器与bool值（因为插入有可能失败，需要返回值提示），参数列表中是插入值的pair，这就实现了插入功能：

pair<iterator,bool> insert (const value_type& val);

        这个迭代器指向【成功插入的元素】或者【与key相等的元素（插入失败的元素）】，即返回值pair中的first始终指向与【参数列表中插入pair中的key的值】相等的map中节点的iterator。

        value值插入成功就是ture，失败就是false，所以插入失败了可以充当查找功能。

（3）总结

        ① 在operator[]的实现代码中，mapped_type() 就是value值，这里insert中是调用了value值的默认构造，这里达到了插入的目的。若插入失败，bool值为false，iterator指向与【插入pair中的key值】相等的map中节点的key值，即指向已经存在的key值，而这就达到了查找功能。

        所以后面再用一个迭代器（iterator2）进行接收返回值pair的first（指向key的迭代器iterator1），且返回的是这个迭代器（iterator2）所指向的second，这样就能达到修改secnod的目的。

        示例代码如下：

void test05()
{map<string, string> dict = { {"pizza","披萨"},{"lemon","柠檬"},{"tea","茶"} };//key不存在->插入{"OREO",string()}dict["OREO"];//key不存在->插入+修改dict["computer"] = "电脑";//key存在->查找cout << dict["pizza"] << endl;//key存在->修改dict["OREO"] = "奥利奥";
}

        若未有key，则可以插入key的value值与修改value值；若已有key，则可以获得key的value值与修改value值；

        ② operator[]的活用：统计次数。

void test06()
{string arr[] = { "披萨" ,"柠檬","茶","披萨" ,"披萨" ,"茶","披萨","柠檬" ,"披萨","茶" };map<string, int> count;for (auto& str : arr){count[str]++;}for (const auto& e : count){cout << e.first << ":" << e.second << endl;}
}

        结果如下：

（三）multimap类

1、multimap与map的差异

        multimap和map的使用基本完全类似，主要区别点在于multimap支持关键值key冗余，那么 insert/find/count/erase都围绕着支持关键值key冗余有所差异，这里跟set和multiset完全⼀样，比如 find 时，有多个key，返回中序第⼀个；给key值进行删除的时候，会把所有的key值给删掉。

        其次就是multimap不支持[]，因为支持key冗余，存在多个key，不知道返回那个value值。就只能支持插入insert了，不能支持持修改。

2、multimapOJ题

（1）随机链表的复制

        以前的解决方案是把复制节点放在原节点的后面链接起来，然后再根据原节点的关系来操作新的复制节点，使其具有与原节点相同的链接关系。

        新的解决方法：设置一个map，里面的key是原节点，value是拷贝节点。这样就不用将新链表与原链表链接起来，而是通过map来建立联系，并且通过map联系来获得旧链表中的random的关系来给到新链表中。

        解题思路：先深拷贝出一个新的链表，新链表的值与原链表相同。并且与原链表建立map关系。随后通过map的key与value关系获得旧链表的random的指针指向的key节点，再把指向key节点对应的value节点赋给新链表。

        以后遇到需要记录一个值对应另一个值的情况，就可以用map进行操作。

        解题代码如下：

class Solution {
public:Node* copyRandomList(Node* head) {map<Node*, Node*> nodeMap;Node* copyhead = nullptr, * copytail = nullptr;Node* cur = head;while (cur){if (copytail == nullptr){copyhead = copytail = new Node(cur->val);}else{copytail->next = new Node(cur->val);copytail = copytail->next;}// 原节点和拷⻉节点map kv存储nodeMap[cur] = copytail;cur = cur->next;}// 处理randomcur = head;Node* copy = copyhead;while (cur){if (cur->random == nullptr){copy->random = nullptr;}else{copy->random = nodeMap[cur->random];}cur = cur->next;copy = copy->next;}return copyhead;}
};

（2）前K个高频单词

        解题思路：将单词列表中的单词给map中进行统计次数，然后用稳定的排序按照value值大小进行排序即可，然后输出前K个单词。

        解题代码如下：

class Solution {
public:struct Compare{bool operator()(const pair<string, int>& x, const pair<string, int>& y)const{return x.second > y.second;}};vector<string> topKFrequent(vector<string>& words, int k) {map<string, int> countMap;for (auto& e : words){countMap[e]++;}vector<pair<string, int>> v(countMap.begin(), countMap.end());// 仿函数控制降序stable_sort(v.begin(), v.end(), Compare());//sort(v.begin(), v.end(), Compare());// 取前k个vector<string> strV;for (int i = 0; i < k; ++i){strV.push_back(v[i].first);}return strV;}
};

        注意：sort排序不是稳定的，稳定的排序有：冒泡排序，插入排序，归并排序。算法库中稳定的排序为：stable_sort函数。 

---

        以上内容仅供分享，若有错误，请多指正。