保留插入顺序的 tsl::ordered_map

作者: , 共 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_mapstd::vector的混合结构。其中std::vector按照插入顺序保存pair<K, V>unordered_map则维护了一个 hash 表(即保存了在std::vector里的索引以及 hash 值)。

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

Q. E. D.

类似文章:
编程 » C++, 数据容器
我们知道在javascript以及Python 3.6+中,所有的dict都保留了插入顺序。但在 C++中,无论是std::map还是std::unordered_map,都没有保留插入顺序。当遍历时,std::map得到的是一个根据键值排序的有序序列,而std::unordered_map则基本是乱序。
编程 » folly, C++, 数据容器
由 Facebook 开发和维护的 C++库 Folly 提供folly::sorted_vector_setfolly::sorted_vector_map,是std::mapstd::set在小数据集上的优化版。代码见: https://github.com/facebook/folly/blob/master/folly/sorted_vector_types.h
编程 » folly, C++, 数据容器
由 Facebook 开发和维护的 C++库 Folly 提供folly::small_vector,代码文件地址:https://github.com/facebook/folly/blob/master/folly/small_vector.h
编程 » C++, 数据容器, folly
folly::dynamic提供类似于C++的动态类型。和std::any可以容纳任意类型不一样,folly::dynamic只支持保存以下几种类型:
编程 » Java, Matlab
Matlab 2008b 才开始引入 containers.Map ,这是 Matlab 唯一的数据结构(这里的数据结构是指自带一定逻辑性的数据结构,不包括普通数据类型)。如果要有其它,比如 Queue、Set 等数据结构,只能自己编写一个。File Exchange 上有不少人做过这个工作,我也写过Queue、List、Vector 的 Matlab 对象。不过 Matlad 的面向对象编程效率极低,这种方法只能用于不太注重效率的场合。解决这个问题的另外一个方法是使用 Java 对象。
编程 » C++, Boost, 数据容器
Boost.Intrusive 是一个很有意思的实现,里面实现了很多侵入式容器,在特定环境下,可以大大提升性能。
编程 » C++, C++标准库
std::vector有两个大小:
编程 » C++, C++11
花括号初始化是C++11引入的一种初始化方法。
C++对一个有序序列[first, last)firstlast都是iterator,可简单理解为位置指针),以及指定值v,标准库直接提供二分查找的函数std::lower_boundstd::upper_bould
编程 » folly, C++, 数据容器
由 Facebook 开发和维护的 C++库 Folly 提供folly::sorted_vector_setfolly::sorted_vector_map,是std::mapstd::set在小数据集上的优化版。代码见: https://github.com/facebook/folly/blob/master/folly/sorted_vector_types.h
编程 » C++, 数据容器
我们知道在javascript以及Python 3.6+中,所有的dict都保留了插入顺序。但在 C++中,无论是std::map还是std::unordered_map,都没有保留插入顺序。当遍历时,std::map得到的是一个根据键值排序的有序序列,而std::unordered_map则基本是乱序。