【C++】map和set的使用 _c++中遍历set集合

3.4 map的构造

map的构造我们关注以下几个接口即可。
map的支持正向和反向迭代遍历，遍历默认按key的升序顺序，因为底层是二叉搜索树，迭代器遍历走的中序；支持迭代器就意味着支持范围for，map支持修改value数据，不支持修改key数据，因为key还是作为关键字数据，修改关键字数据，会破坏底层搜索树的结构。

// empty (1) 无参默认构造explicit map(const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());// range (2) 迭代器区间构造template 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 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();

#include

3.5 map的增删查

map的增删查关注以下几个接口即可：
map增接口，插入的pair键值对数据，跟set所有不同，但是查和删的接口只用关键字key跟set是完全类似（value的值是否相同不会影响pair的数据的插入，但是key必须保持不同）；不过map的find返回iterator，不仅仅可以确认key在不在，还找到通过pair结构找到key映射的value，同时通过迭代还可以修改value。

Member typeskey_type->The first template parameter(Key)mapped_type->The second template parameter(T)value_type->pair// 单个数据插入，如果已经key存在则插入失败,key存在相等value不相等也会插入失败pair insert(const value_type& val);// 列表插入，已经在容器中存在的值不会插入void insert(initializer_list il);// 迭代器区间插入，已经在容器中存在的值不会插入template 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，存在返回1size_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.6 map的数据修改

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

map第一个支持修改的方式是通过迭代器，迭代器遍历时或者find返回key所在的iterator修改。使用find时，我们传入对应关键值key在容器中搜索，找到对应的关键字，我们返回对应的迭代器，需要注意的是这个迭代器指向的是一个pair类型对象，我们pair的.first和.second来访问对应数据。

Member typeskey_type->The first template parameter(Key)mapped_type->The second template parameter(T)value_type->pair// 查找k，返回k所在的迭代器，没有找到返回end()，如果找到了通过iterator可以修改key对应的//mapped_type值iterator find(const key_type& k);

map还有一个非常重要的修改接口operator[]，但是与之前所介绍不同的是map的operator[]不仅仅支持修改，还支持插入数据和查找数据，他是一个多功能复合接口（因为map容器我们根据key查找数据，key不能改变，而value可以改变，因此operator[]接口如果可以查到数据的同时可以修改对应的value就非常有价值）。

3.6.1关于operator[]底层实现的特殊说明

要理解operator[]复合功能实现之前，需要先介绍一下map的insert。

// 文档中对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对象会出现以下两种情况
 1、如果key已经在map中，插入失败（map是根据key查找的，T不同不影响），则返回一个pair对象，返回pair对象的first是key所在结点的迭代器，second是false，表明插入失败

 2、如果key不在map中，插入成功，则返回一个pair对象，返回pair对象
first是新插入key所在结点的迭代器，second是true，表示插入成功

 也就是说无论插入成功还是失败，返回pair对象的first都会指向key所在的迭
代器，那么也就意味着insert插入失败时充当了查找的功能（注：如果不确定map中释放有对应key，不推荐insert来查找的，因为一旦没有对应key，insert就会插入key,污染原来的数据），正是因为这一点，insert可以用来实现operator[]，

需要注意的是这里有两个pair，不要混淆了，一个是map底层红黑树节点中存的pair，另一个是insert返回值pair。

pair insert(const value_type& val);

3.6.2关于operator[]底层实现的具体说明

operator[]底层封装了insert,通过insert插入对应的数据，然后insert返回pair，取到对应的数据，然后将通过value的引用返回，我们就可以在外部通过key修改容器内部的value.

详细情况分为以下两种：

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

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

总的来说，我们就可以以operator[]，通过key修改对应的value了。

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

mapped_type& operator[] (const key_type& k);// operator的内部实现mapped_type& operator[] (const key_type& k){pair ret = insert({ k, mapped_type() });iterator it = ret.first;return it->second;}

3.7 构造遍历及增删查使用样例

#include#include

3.8 map的迭代器和[]功能样例：

#include#include

#include#include

3.9 multimap和map的差异

multimap和map的使用基本完全类似，主要区别点在于multimap支持关键值key冗余，那么
insert/find/count/erase都围绕着支持关键值key冗余有所差异，这里跟set和multiset完全一样，

比如find时，有多个key，返回中序第一个。

其次就是multimap不支持[]，因为支持key冗余，[]就只能支持插入了，不能支持修改，不然无法确定具体修改的是哪个value值。

练习

3.10 138. 随机链表的复制 - 力扣（LeetCode）

对于这一道题，数据结构初阶阶段，为了控制随机指针，我们将拷贝结点链接在原节点的后面解决，后面拷贝节点还得解下来链接，非常麻烦。【初阶数据结构】链表经典OJ（8道）_oj题-CSDN博客

这里我们直接让{原结点,拷贝结点}建立映射关系放到map中，原链表中随机指针指向对应原链表中节点，由于{原结点,拷贝结点}映射关系，我们根据原链表指向关系，我们拷贝节点指向对应映射的节点

这样控制随机指针会非常简单方便，这里体现了map在解决一些问题时的价值，完全是降维打击。

class Solution {public:Node* copyRandomList(Node* head) {map 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;}};

3.11 692. 前K个高频单词 - 力扣（LeetCode）

本题目我们利用map根据对应单词统计对应的出现次数以后，返回的答案还应该按单词出现频率由高到低排序，但是这里有一个特殊要求，如果不同的单词有相同出现频率，按字典顺序排序。

解决思路1：

用排序找前k个单词，因为map中已经对key单词排序过，也就意味着遍历map时，次数相同的单词，字典序小的在前面，字典序大的在后面。那么我们将数据放到vector中用一个稳定的排序就可以实现上面特殊要求，但是sort底层是快排，是不稳定的，所以我们要用stable_sort，他是稳定的。

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

解决思路2：

将map统计出的次数的数据放到vector中排序，或者放到priority_queue中来选出前k个。利用仿函数强行控制次数相等的，字典序小的在前面。

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

class Solution {public:struct Compare{bool operator()(const pair& x, const pair& y)const{// 要注意优先级队列底层是反的，大堆要实现小于比较，所以这里次数相等，想要字典序小的在前面要比较字典序大的为真return x.second y.first);}};vector topKFrequent(vector& words, int k) {map countMap;for (auto& e : words){countMap[e]++;}// 将map中的放到priority_queue中，仿函数控制大堆，次数相同按照字典序规则排序priority_queue<pair, vector<pair>, Compare>p(countMap.begin(), countMap.end());vector strV;for (int i = 0; i < k; ++i){strV.push_back(p.top().first);p.pop();}return strV;}};