Boost C++ 库

...世界上最受尊敬和专业设计的 C++ 库项目之一。 Herb SutterAndrei Alexandrescu, C++ 编码标准

PrevUpHomeNext

第 16 章。Boost.Intrusive

Olaf Krzikalla

Ion Gaztanaga

根据 Boost 软件许可协议 1.0 版分发。(请参阅随附文件 LICENSE_1_0.txt 或访问 https://boost.ac.cn/LICENSE_1_0.txt

目录

简介
Boost.Intrusive 介绍
构建 Boost.Intrusive
已测试的编译器
侵入式和非侵入式容器
侵入式和非侵入式容器之间的差异
Boost.Intrusive 容器的属性
如何使用 Boost.Intrusive
使用基类钩子
使用成员钩子
同时使用两种钩子
对象生命周期
何时使用?
概念总结
Boost.Intrusive 容器介绍
安全钩子
安全模式的特性
配置安全模式断言
自动取消链接钩子
什么是自动取消链接钩子?
自动取消链接钩子示例
具有常量时间 size() 的自动取消链接钩子和容器
侵入式单链表:slist
slist 钩子
slist 容器
示例
侵入式双链表:list
list 钩子
list 容器
示例
侵入式关联容器:set、multiset、rbtree
set、multiset 和 rbtree 钩子
set、multiset 和 rbtree 容器
示例
半侵入式无序关联容器:unordered_set、unordered_multiset
unordered_set 和 unordered_multiset 性能注意事项
unordered_set 和 unordered_multiset 钩子
unordered_set 和 unordered_multiset 容器
示例
自定义 bucket traits
关联容器的 Map 和 multimap 类接口
侵入式 avl 树型关联容器:avl_set、avl_multiset 和 avltree
avl_set、avl_multiset 和 avltree 钩子
avl_set、avl_multiset 和 avltree 容器
示例
侵入式伸展树型关联容器:splay_set、splay_multiset 和 splay_tree
基于伸展树的容器的优点和缺点
splay_set、splay_multiset 和 splaytree 容器
示例
侵入式替罪羊树型关联容器:sg_set、sg_multiset 和 sgtree
sg_set、sg_multiset 和 sgtree 容器
示例
侵入式 treap 树型关联容器:treap_set、treap_multiset 和 treap
treap_set、treap_multiset 和 treap 容器
基于 treap 的侵入式容器的异常安全性
示例
二叉搜索树钩子:bs_set_base_hook 和 bs_set_member_hook
关联容器的高级查找和插入函数
高级查找
高级插入
位置插入
从 Boost.Intrusive 容器中擦除和处置值
克隆 Boost.Intrusive 容器
使用函数钩子
递归 Boost.Intrusive 容器
将智能指针与 Boost.Intrusive 容器一起使用
与 Boost.Intrusive 兼容的智能指针的要求
从值中获取迭代器
Any Hooks:用于任何侵入式容器的单个钩子
概念解释
具有自定义 NodeTraits 的节点算法
侵入式单链表算法
侵入式双链表算法
侵入式红黑树算法
侵入式伸展树算法
侵入式 avl 树算法
侵入式 treap 算法
具有自定义 ValueTraits 的容器
ValueTraits 接口
自定义 ValueTraits 示例
为不同的值重用节点算法
简化 value traits 定义
有状态 value traits
线程安全保证
Boost.Intrusive 迭代器特性
空前向迭代器
可怕的迭代器
具有等效键的有序关联容器中的稳定性和提示插入
获取相同类型并减少符号长度
设计说明
性能敏感环境中的 Boost.Intrusive
空间受限环境中的 Boost.Intrusive
Boost.Intrusive 作为基本构建块
扩展 Boost.Intrusive
性能
后向插入和销毁
反转
排序
写入访问
结论
索引
类索引
Typedef 索引
函数索引
发行说明
Boost 1.86 发行版
Boost 1.85 发行版
Boost 1.82 发行版
Boost 1.81 发行版
Boost 1.80 发行版
Boost 1.79 发行版
Boost 1.77 发行版
Boost 1.76 发行版
Boost 1.75 发行版
Boost 1.73 发行版
Boost 1.71 发行版
Boost 1.70 发行版
Boost 1.67 发行版
Boost 1.65 发行版
Boost 1.64 发行版
Boost 1.63 发行版
Boost 1.62 发行版
Boost 1.61 发行版
Boost 1.60 发行版
Boost 1.59 发行版
Boost 1.58 发行版
Boost 1.57 发行版
Boost 1.56 发行版
Boost 1.55 发行版
Boost 1.54 发行版
Boost 1.53 发行版
Boost 1.51 发行版
Boost 1.49 发行版
Boost 1.48 发行版
Boost 1.46 发行版
Boost 1.45 发行版
Boost 1.40 发行版
Boost 1.39 发行版
Boost 1.38 发行版
Boost 1.37 发行版
Boost 1.36 发行版
参考文献
致谢
参考
Header <boost/intrusive/any_hook.hpp>
Header <boost/intrusive/avl_set.hpp>
Header <boost/intrusive/avl_set_hook.hpp>
Header <boost/intrusive/avltree.hpp>
Header <boost/intrusive/avltree_algorithms.hpp>
Header <boost/intrusive/bs_set.hpp>
Header <boost/intrusive/bs_set_hook.hpp>
Header <boost/intrusive/bstree.hpp>
Header <boost/intrusive/bstree_algorithms.hpp>
Header <boost/intrusive/circular_list_algorithms.hpp>
Header <boost/intrusive/circular_slist_algorithms.hpp>
Header <boost/intrusive/derivation_value_traits.hpp>
Header <boost/intrusive/hashtable.hpp>
Header <boost/intrusive/intrusive_fwd.hpp>
Header <boost/intrusive/linear_slist_algorithms.hpp>
Header <boost/intrusive/link_mode.hpp>
Header <boost/intrusive/list.hpp>
Header <boost/intrusive/list_hook.hpp>
Header <boost/intrusive/member_value_traits.hpp>
Header <boost/intrusive/options.hpp>
Header <boost/intrusive/pack_options.hpp>
Header <boost/intrusive/parent_from_member.hpp>
Header <boost/intrusive/pointer_plus_bits.hpp>
Header <boost/intrusive/pointer_rebind.hpp>
Header <boost/intrusive/pointer_traits.hpp>
Header <boost/intrusive/priority_compare.hpp>
Header <boost/intrusive/rbtree.hpp>
Header <boost/intrusive/rbtree_algorithms.hpp>
Header <boost/intrusive/set.hpp>
Header <boost/intrusive/set_hook.hpp>
Header <boost/intrusive/sg_set.hpp>
Header <boost/intrusive/sgtree.hpp>
Header <boost/intrusive/sgtree_algorithms.hpp>
Header <boost/intrusive/slist.hpp>
Header <boost/intrusive/slist_hook.hpp>
Header <boost/intrusive/splay_set.hpp>
Header <boost/intrusive/splaytree.hpp>
Header <boost/intrusive/splaytree_algorithms.hpp>
Header <boost/intrusive/treap.hpp>
Header <boost/intrusive/treap_algorithms.hpp>
Header <boost/intrusive/treap_set.hpp>
Header <boost/intrusive/trivial_value_traits.hpp>
Header <boost/intrusive/unordered_set.hpp>
Header <boost/intrusive/unordered_set_hook.hpp>

Boost.Intrusive 是一个库,向 C++ 世界介绍了一些侵入式容器。侵入式容器是特殊的容器,与非侵入式容器(如 STL 容器)相比,它们提供更好的性能和异常安全保证。

侵入式容器的性能优势使其成为高效构建复杂容器(如多索引容器)或设计高性能代码(如内存分配算法)的理想构建块。

虽然侵入式容器在 C 语言中被广泛使用,但由于标准容器的存在,它们在 C++ 中变得越来越被遗忘,而标准容器不支持侵入式技术。Boost.Intrusive 旨在通过将实现封装在类似 STL 的接口中来推动侵入式容器的使用。因此,任何熟悉标准容器的人都可以轻松使用 Boost.Intrusive

无需编译任何内容即可使用 Boost.Intrusive,因为它是一个仅包含头文件的库。只需将您的 Boost 头文件目录包含在编译器包含路径中即可。

Boost.Intrusive 已在以下编译器/平台上进行了测试

  • Visual C++ >= 7.1。
  • GCC >= 4.1。
[Warning] 警告

GCC < 4.3 和 MSVC < 9.0 已被弃用,将在下一版本中删除。


PrevUpHomeNext