folly 的 sorted_vector_set 和 sorted_vector_map

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

由 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::sorted_vector_set和folly::sorted_vector_map提供和std::map和std::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_map和boost::container::flat_set。

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

Q. E. D.

类似文章：
相似度: 0.323
编程 » C++, 数据容器
我们知道在javascript以及Python 3.6+中，所有的dict都保留了插入顺序。但在 C++中，无论是std::map还是std::unordered_map，都没有保留插入顺序。当遍历时，std::map得到的是一个根据键值排序的有序序列，而std::unordered_map则基本是乱序。
相似度: 0.320
编程 » C++, 数据容器
我们知道在javascript以及Python 3.6+中，所有的dict都保留了插入顺序。但在 C++中，无论是std::map还是std::unordered_map，都没有保留插入顺序。当遍历时，std::map得到的是一个根据键值排序的有序序列，而std::unordered_map则基本是乱序。
相似度: 0.304
编程 » folly, C++, 数据容器
由 Facebook 开发和维护的 C++库 Folly 提供folly::small_vector，代码文件地址：https://github.com/facebook/folly/blob/master/folly/small_vector.h。
相似度: 0.193
编程 » C++, 数据容器, folly
folly::dynamic提供类似于C++的动态类型。和std::any可以容纳任意类型不一样，folly::dynamic只支持保存以下几种类型：
相似度: 0.163
编程 » folly, 自旋锁, 多线程编程, C++
由 Facebook 开发和维护的 C++库 Folly 提供了锁folly::MicroLock，代码文件地址：https://github.com/facebook/folly/blob/master/folly/MicroLock.h。
相似度: 0.152
编程 » C++, C++标准库
std::vector有两个大小：
相似度: 0.150
编程 » C++, folly
folly::fbstring是一个完全兼容std::string的类，可以做到无缝替换，而且性能更高。其代码参见https://github.com/facebook/folly/blob/master/folly/FBString.h。
相似度: 0.142
编程 » C++, folly
高效程序总是尽量避免频繁触碰在堆上分配和释放内存，所以无论是std::string还是folly:fbstring都做了SSO（ small string optimization ）。而folly::FixedString是一个很有意思的实现，它可以把任意长度的字符串都放在堆上。代码可见https://github.com/facebook/folly/blob/master/folly/FixedString.h。
相似度: 0.134
编程 » Java, Matlab
Matlab 2008b 才开始引入 containers.Map ，这是 Matlab 唯一的数据结构(这里的数据结构是指自带一定逻辑性的数据结构，不包括普通数据类型)。如果要有其它，比如 Queue、Set 等数据结构，只能自己编写一个。File Exchange 上有不少人做过这个工作，我也写过Queue、List、Vector 的 Matlab 对象。不过 Matlad 的面向对象编程效率极低，这种方法只能用于不太注重效率的场合。解决这个问题的另外一个方法是使用 Java 对象。
相似度: 0.132
编程 » C++, Boost, 数据容器
Boost.Intrusive 是一个很有意思的实现，里面实现了很多侵入式容器，在特定环境下，可以大大提升性能。
前一篇：
户外 » 亲子徒步路线, 香山片区, 徒步强度2.0
香植线，也就是香山-植物园拉练路线，从香山邮局出发，经好汉坡到防火道，再往北从樱桃沟下到植物园。总爬升 600 米，路程约 10 公里。
后一篇：
编程 » C++, 数据容器
我们知道在javascript以及Python 3.6+中，所有的dict都保留了插入顺序。但在 C++中，无论是std::map还是std::unordered_map，都没有保留插入顺序。当遍历时，std::map得到的是一个根据键值排序的有序序列，而std::unordered_map则基本是乱序。