loki::AssocVector 保留插入顺序的关系型结构

作者: , 共 576 字 , 共阅读 0

我们知道在javascript以及Python 3.6+中，所有的dict都保留了插入顺序。但在 C++中，无论是std::map还是std::unordered_map，都没有保留插入顺序。当遍历时，std::map得到的是一个根据键值排序的有序序列，而std::unordered_map则基本是乱序。

loki::AssocArray弥补了该特性，它有兼容std::map的 API ，同时又确保了在begin()到end()循环时，保留了插入时的顺序。在这方面它和tsl::ordered_map一样，只是效率没后者那么高，但胜在代码和内存布局简单清晰。

loki::AssocArray的代码位于https://github.com/brkpt/loki/blob/master/include/loki/AssocVector.h，该文件没有其它依赖，可以直接复制使用。

其原理特别简单，就是一个std::vector<pair<K, V>>，连顺序都不排（可对照folly::sorted_vector_map），直接按照添加顺序在尾部插入。只是添加了一些仿std::map的 API。

也因为如此，只有新增数据很快，其余的操作，如修改、删除，甚至访问，都需要O(n)的时间，基本只适合不到三位数的元素个数时使用。

Q. E. D.

类似文章：
相似度: 0.529
编程 » C++, 数据容器
我们知道在javascript以及Python 3.6+中，所有的dict都保留了插入顺序。但在 C++中，无论是std::map还是std::unordered_map，都没有保留插入顺序。当遍历时，std::map得到的是一个根据键值排序的有序序列，而std::unordered_map则基本是乱序。
相似度: 0.319
编程 » folly, C++, 数据容器
由 Facebook 开发和维护的 C++库 Folly 提供folly::sorted_vector_set和folly::sorted_vector_map，是std::map和std::set在小数据集上的优化版。代码见： https://github.com/facebook/folly/blob/master/folly/sorted_vector_types.h。
相似度: 0.142
编程 » folly, C++, 数据容器
由 Facebook 开发和维护的 C++库 Folly 提供folly::small_vector，代码文件地址：https://github.com/facebook/folly/blob/master/folly/small_vector.h。
相似度: 0.121
编程 » C++, 数据容器, folly
folly::dynamic提供类似于C++的动态类型。和std::any可以容纳任意类型不一样，folly::dynamic只支持保存以下几种类型：
相似度: 0.097
编程 » C++, Boost, 数据容器
Boost.Intrusive 是一个很有意思的实现，里面实现了很多侵入式容器，在特定环境下，可以大大提升性能。
相似度: 0.087
编程 » C++, folly
folly::fbstring是一个完全兼容std::string的类，可以做到无缝替换，而且性能更高。其代码参见https://github.com/facebook/folly/blob/master/folly/FBString.h。
相似度: 0.074
编程 » C++, folly
高效程序总是尽量避免频繁触碰在堆上分配和释放内存，所以无论是std::string还是folly:fbstring都做了SSO（ small string optimization ）。而folly::FixedString是一个很有意思的实现，它可以把任意长度的字符串都放在堆上。代码可见https://github.com/facebook/folly/blob/master/folly/FixedString.h。
相似度: 0.069
编程 » Java, Matlab
Matlab 2008b 才开始引入 containers.Map ，这是 Matlab 唯一的数据结构(这里的数据结构是指自带一定逻辑性的数据结构，不包括普通数据类型)。如果要有其它，比如 Queue、Set 等数据结构，只能自己编写一个。File Exchange 上有不少人做过这个工作，我也写过Queue、List、Vector 的 Matlab 对象。不过 Matlad 的面向对象编程效率极低，这种方法只能用于不太注重效率的场合。解决这个问题的另外一个方法是使用 Java 对象。
相似度: 0.065
编程 » C++, C++标准库
std::vector有两个大小：
相似度: 0.061
编程 » folly, 自旋锁, 多线程编程, C++
由 Facebook 开发和维护的 C++库 Folly 提供了自旋锁的实现folly::MicroSpinLock，代码文件地址：https://github.com/facebook/folly/blob/master/folly/synchronization/MicroSpinLock.h。
前一篇：
编程 » C++, 数据容器
我们知道在javascript以及Python 3.6+中，所有的dict都保留了插入顺序。但在 C++中，无论是std::map还是std::unordered_map，都没有保留插入顺序。当遍历时，std::map得到的是一个根据键值排序的有序序列，而std::unordered_map则基本是乱序。
后一篇：
编程 » C++, 数据容器, folly
folly::dynamic提供类似于C++的动态类型。和std::any可以容纳任意类型不一样，folly::dynamic只支持保存以下几种类型：