c++23中的新功能之十平坦容器

news/2024/11/8 17:12:55/

一、背景介绍

在前面反复提到过,其实所有的编程语言总体的方向是朝着自然语言化和简单在发展,速度有快慢,但方向基本没有错。这里先回顾一下,在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让人看到了希望,同时也看到了绝望。新技术一定是毁灭一些旧的秩序,但一定会诞生更多的新秩序。总之,不能灰心。


http://www.ppmy.cn/news/748947.html

相关文章

【算法与数据结构】459、LeetCode重复的子字符串

文章目录 一、题目二、解法2.1 暴力破解法2.2 KMP算法2.3 Sunday算法2.4 官方查找算法 三、完整代码 所有的LeetCode题解索引&#xff0c;可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 2.1 暴力破解法 思路分析&#xff1a;子串多次循环才能构成整个…

CES2013前瞻:1080p屏幕手机集中爆发

新浪数码讯 1月4日上午消息&#xff0c;每年一度的美国国际消费电子展(CES)将于1月8日在美国拉斯维加斯正式开展&#xff0c;作为年初的业界盛会&#xff0c;各大厂商均会不同程度地推出本年度的亮点产品。去年&#xff0c;首款X86智能手机联想K800、6.68mm超薄机身华为Ascend …

未来计算机游戏,未来可追 ROG光刃G15游戏电脑首发登场

2020年下半年游戏市场再度发力&#xff0c;催生了整个游戏电脑的销量增长&#xff0c;随着第十代酷睿处理器的问世以及RTX20系列显卡整体价格的降低。游戏用户更加倾向于购买高配置的台式机&#xff0c;尤其是学生群体&#xff0c;而近日华硕ROG败家之眼又给大家带来了全新的产…

【李宏毅机器学习2021春】01-机器学习基本概念介绍

01 - 机器学习基本概念介绍 1. 机器学习的基本任务 1.1 Regression 回归 如&#xff0c;输入过去的数据&#xff0c;对未来的数据进行预测。对数据进行拟合的过程叫做回归。 1.2 Classifiation 分类 给出选项&#xff0c;函数输出正确的选项。 如&#xff0c;下棋&#x…

通过串口控制LED-单片机

1.输入数据控制LED灯状态00-ff。同时会接收输入的数据。 中断和定时器配置 void UART_Init() //4800bps11.0592MHz { SCON0X50;//sm00,sm11,ren1 PCON & 0x7F; //波特率不倍速 TMOD & 0x0F; //设置定时器模式 T1 TMOD | 0x20; …

老K包邮送一台笔记本!4G内存,128G固态!看片、吃鸡贼爽

为回馈广大读者粉丝们的大力支持&#xff0c;老K特地选了这款华硕笔记本作为抽奖礼品送给大家。这礼物呢&#xff0c;可手捧追剧玩游戏&#xff0c;也可写字撰文搞创作。无论是自己玩&#xff0c;还是当礼物送人&#xff0c;都是理想佳品。 祝所有人工作顺利&#xff0c;工…

Java_17_斗地主游戏思想

斗地主游戏思想 创建新牌 要创建一个牌组数组 public class Cards {private String number;private String color;private int index;public Cards() {}public Cards(String number, String color, int index) {this.number number;this.color color;this.index index;}p…

stm32驱动MCP2515芯片,项目已通过测试

最近公司做一个项目&#xff0c;需要3路can通道&#xff0c;但是stm32看了很久&#xff0c;最多也就只有2个can&#xff0c;所以找到了一款MCP2515芯片&#xff0c;可以用spi驱动can。 已经实现了can的发送和接收&#xff0c;接收采用的是外部中断接收的方式。和单片机本身带的…