保留插入顺序的 tsl::ordered_map

作者: 张志强 , 2019-09-05 , 共 609 字 , 共阅读 0

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

tsl::ordered_map弥补了该特性，它有兼容std::map的 API ，同时又确保了在begin()到end()循环时，保留了插入时的顺序。其代码在https://github.com/Tessil/ordered-map。该地址还实现了tsl::ordered_set，一个保留插入顺序的set实现。

但为之而妥协的是：

删除会导致iterator失效，更接近于std::vector。
删除的效率是O(n)，而且有一个非常大的系数。但查找键值和插入仍保留了O(1)的性能。

在实现上，基本是一个unordered_map和std::vector的混合结构。其中std::vector按照插入顺序保存pair<K, V>，unordered_map则维护了一个 hash 表（即保存了在std::vector里的索引以及 hash 值）。

在大多数应用中，基本只有查找和添加，删除的操作很少。因此，在大多数情况下，该实现都有很好的性能。该库的缺陷是知名度一般，可能有潜在 bug。

Q. E. D.

类似文章：

loki::AssocVector 保留插入顺序的关系型结构相似度: 0.528

2019-09-10, 编程 » C++, 数据容器

folly 的 sorted_vector_set 和 sorted_vector_map 相似度: 0.324

2019-09-02, 编程 » 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。

Folly 的 small_vector 容器相似度: 0.139

2019-12-29, 编程 » folly, C++, 数据容器

由 Facebook 开发和维护的 C++库 Folly 提供folly::small_vector，代码文件地址：https://github.com/facebook/folly/blob/master/folly/small_vector.h。

动态数据类型 folly::dynamic 相似度: 0.126

2019-09-15, 编程 » C++, 数据容器, folly

folly::dynamic提供类似于C++的动态类型。和std::any可以容纳任意类型不一样，folly::dynamic只支持保存以下几种类型：

侵入式容器 Boost.Intrusive 相似度: 0.105

2020-01-10, 编程 » C++, Boost, 数据容器

Boost.Intrusive 是一个很有意思的实现，里面实现了很多侵入式容器，在特定环境下，可以大大提升性能。

Matlab 使用 Java 的数据结构类型相似度: 0.103

2012-12-09, 编程 » Java, Matlab

Matlab 2008b 才开始引入 containers.Map ，这是 Matlab 唯一的数据结构(这里的数据结构是指自带一定逻辑性的数据结构，不包括普通数据类型)。如果要有其它，比如 Queue、Set 等数据结构，只能自己编写一个。File Exchange 上有不少人做过这个工作，我也写过Queue、List、Vector 的 Matlab 对象。不过 Matlad 的面向对象编程效率极低，这种方法只能用于不太注重效率的场合。解决这个问题的另外一个方法是使用 Java 对象。