一、背景介绍
在前面反复提到过,其实所有的编程语言总体的方向是朝着自然语言化和简单在发展,速度有快慢,但方向基本没有错。这里先回顾一下,在STL中有六大组件(侯捷老师的《STL源码剖析》),这其中开发者经常见到的还是以容器为主。容器主要分成两大类:顺序容器和关联容器。这里主要是讲关联容器,即std::map,std::set,std::multimap,std::multiset.这是早期的c++标准中的四个关联容器,在后来又增加了线程安全的unordered系列。但是无论怎么变,它的基本组织方式原理相同,都是通过KEY来确定Value。这其实就是大家经常提到的字典。
早期的四个属于有序的关联容器,这种情况一般是使用二叉搜索树来实现,在STL中一般使用红黑书;而后来新增的线程安全的unordered四个,肯定是使用哈希表来实现。这种应用也没有什么稀奇也没有什么错误。
但是,人类的缺点就在于不满足。
树的操作太慢了,特别是对于查询。而哈希肯定浪费间,如果再加上链表,效率也是慢。人们不由得想到了数组,这玩意儿快啊,给个索引就找到了。可数组不容易插入删除啊?有人会问。先解决查询的效率问题,没见互联网上弄得缓存,重中之重就解决查询的速度。
二、平坦容器
所谓平坦的,线性的,序列化的,在某种程度上都可以认为是一种情况(有些情况不同,可以查看一下《数据密集型系统应用设计》)。平坦的意思就是一条直线,没有坑洼(内存中没有空洞)。它的好处就是可以直接定位到数据的地址,这个很好理解,知道基地址,想跳到一个指定的地址,只要在基地址上加一个值即可。在实际的内存中,这种操作几乎是不耗费时间的。
现在再说平坦容器,就容易明白了,其实就是把底层的数据结构直接替换成数组。
不过现在,STL中只是替换了有序的关联容器,也就是以树为底层数据结构的几个容器,而哈希的几个还在探索中(讨论中)。也就是说在STL库中,有flat_map,flat_set,flat_multimap,flat_multiset四个平坦容器。看其中一个的英文:“adapts a container to provide a collection of key-value pairs, sorted by keys, keys are unique”。这说明这四个也是容器适配器。
不过看标准委员会这群大佬的节奏,肯定最终会把所有的关联容器平坦化,这个前面早有类似的例子。
平坦容器既然以有序的数组为基础数据结构,那么它的优点和缺点就很容易分析出来:
1、查询速度快:这个是现在应用的一个痛点,几乎大部分的工作都是查询
2、插入删除太慢
3、空间更紧凑
4、可以使用缓存
5、随机访问稳定
6、灵活性低:迭代器删除会失效,移动存储对象成本太高
看上面的优缺点就可以知道,其实平坦容器不是带着使命来拯救关联容器的,而是在某些方向上帮助关联容器的。
这里需要对flat_map和flat_set简说明一下,前者使用了两个数组进行存储KEY和VALUE,而后者则是使用一个键值对来存储K和V,然后再存储到底层的数组中(std::pair<k,v>)。这样做的结果就是flat_map可以手动的指定底层的数组数据结构,例如vector或者deque。不过有缺点就有好处,flat_map的迭代器就不如flat_set的容易操作,前者同时操作两个数组,变得复杂多了。
整体上看,平坦容器更类似于细而微的查询优化容器。
更多的细节可以参看:
https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2022/p0429r9.pdf
https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2022/p1222r4.pdf
三、例程
平坦容器的使用和原来的关联容器使用没有不同,但是c++23毕竟还在完善中,下面看一个其中的例程:
#include <flat_set>
#include <iostream>int main()
{flat_set<int> fs;fs.emplace(3);fs.emplace(5,65,7,8);//看文档中支持变参for (auto x&:fs){std::cout<<x<<std::endl;}
}
上面的代码不保证准确,只是一种示意。insert不支持变参但支持列表初始化,而empalce则支持变参,看最终的应用吧。
四、总结
c++26的蓝图前些天都通过了,下来肯定又是吵吵嚷嚷的三年,然后再通过一批新功能。其实c++20的功能就已经很强大了,当然除了协程。网络和并行库其实倒不必急于一时,好多高人就是凭这个吃饭呢。标准委员会要是弄进来且很简单,估计这些大牛的饭碗肯定端不稳了。
科技在进步,标准也在进步,得紧跟着,不然,不知道什么时候儿,就落伍了。AI让人看到了希望,同时也看到了绝望。新技术一定是毁灭一些旧的秩序,但一定会诞生更多的新秩序。总之,不能灰心。