map中被你忽视的四个功能

零、背景

c++ 语言中， map 这个数据结构小学生都知道怎么使用。

但是大家使用的又都是最最基本的增删改查功能。

有几个功能大多数人都不知道，今天分享给大家。

一、有序性

如果问一个小学生，map 内部是怎么实现的？
几乎所有人都可以回答出来，使用红黑树实现的，操作复杂度是 log(n)。

那使用红黑树意味着什么呢？
很遗憾，大家只知道复杂度是 log 级别的，而不知道其他性质了。

红黑树说到底还是一个二叉搜索树。
而搜索树最重要的一个性质就是有序性，即左二儿子所有节点都不大于当前根，右儿子所有节点都不小于当前根。

所以map这个数据结构也满足有序性。

知道了map具有有序性这个特性，我们就可以使用map代替很多复杂的算法与数据结构了。

二、最值

给你出一道面试题。
原先有一个空数组，有一系列增删改查来操作数组。

增：插入一个数字。
删：删除指定数字。
查：求当前最小值和最大值。

面对这到面试题你会怎么做呢？

利用map的有序性，我们很容易就可以得到最值答案。

结论1：map 第一个就是最小的，最后一个就是最大的。

三、排序

再出一道面试题。
原先有一个空数组，有一系列增删改查来操作数组。

增：插入一个数字。
删：删除指定数字。
查：返回排序后的数组。

面对这道题你又该如何做呢？

通用利用map的有序性，直接就可以得到答案。

结论2：map 可以直接有序遍历元素。

三、优先队列

在《leetcode 第180场算法比赛》的最后一题中，需要维护一个 TOP K 的数据。

TOP K 问题在算法中，显然需要优先队列（堆）才能实现的。

而我的代码是一个 map 搞定，为什么？
因为 map 是有序的，天然的优先队列。

结论3：map 是更高级的优先队列。

四、区间统计

对于边界查找，例如给一个数组[13,17,19,23]，查找第一个大于等于XX的值，或者第一个大于XX的值等，小学生闭着眼就就可以知道怎么做，显然是二分查找啦。

但是问题稍微换一下，给一个区间[13,17), [17,19),[19,23)，问数字在哪个区间里，竟然大部分人都不会做了。

实际上区间这类问题，在之前的比赛题解中我分享了无数次了。

我懒得去找题了。
恰好我四五年前做项目时，我自己给自己提出了这样一个区间相关的需求。
当时我还写了好几个测试程序，就拿其中一个测试程序来举例吧。

项目实际问题：监控系统需要对一些数据进行区间统计。
比如统计耗时区间的分布情况、包大小的分布情况等等。

由于被统计的数据是一个连续的整数，直接按每个数字来统计数据量太大。
所以需要划分一些区间，即进行区间统计。

最简单的方法是写 if/else 了，当时我写了一个很强大的宏可以自动嵌套展开为 if/else， 当时还发朋友圈了。

当然，这个也可以使用 vector 排序，然后使用二分来快速查找。

再后来，而当年我的实现方式是使用map储存左区间，然后使用 upper_bound 来查找的。

这样就可以快速的实现区间查找了。

结论4：map支持二分查找，即upper_bound和lower_bound。

五、最后

其实 map 的这四个功能都是因为使用红黑树实现才特有的性质。
平常算法比赛的时候，如果你知道这四个功能，就会如虎添翼了吧。

当然，如果使用 unordered_map的话，就没有顺序了，自然没有这些性质了。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code