folly 的 sorted_vector_set 和 sorted_vector_map

作者: , 共 722 字

由 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::sorted_vector_setfolly::sorted_vector_map提供和std::mapstd::set类似的 API ,大多数操作可以无缝切换。只是在实现上有区别:

  • std的版本使用红黑树,结构复杂。而folly的实现底层使用排序的std::vector。结构更简单,内存连续,因此有更好的缓存命中率。
  • std的红黑树需要多余的内存空间来维护数结构。
  • folly的插入和删除都是O(n)(找到位置是O(log(n),但需要移动后面所有的数据),而std版本都是O(log(n))。因此folly的版本少量修改(最好只插不删)、大量查询的情形。查找的速度和std版本一样都是O(log(n)),但更直接,速度应该会稍快一些。
  • folly版本的插入和删除可能导致iterator失效,但std的版本不会。

这两个数据结构实现都比较直接,不多说了。

boost也提供同样的数据结构,分别位于boost::container::flat_mapboost::container::flat_set

不过根据我的测试,这些都不如std::unordered_setstd::unordered_map,后者的查找时间是O(1)

Q. E. D.

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