Boost C++ 库

……世界上评价最高、设计最精良的 C++ 库项目之一。 Herb SutterAndrei Alexandrescu《C++ Coding Standards》

第 16 章 Boost.Intrusive - Boost 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 容器
示例
自定义桶特性
关联容器的 Map 和 Multimap 接口
基于侵入式 avl 树的关联容器:avl_set, avl_multiset 和 avltree
avl_set、avl_multiset 和 avltree 钩子
avl_set, avl_multiset 和 avltree 容器
示例
基于侵入式 splay 树的关联容器: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 兼容的智能指针的要求
从值获取迭代器
任意钩子:用于任何侵入式容器的单一钩子
概念解释
带有自定义 NodeTraits 的节点算法
侵入式单向链表算法
侵入式双向链表算法
侵入式红黑树算法
侵入式伸展树算法
侵入式 AVL 树算法
侵入式 Treap 算法
带有自定义 ValueTraits 的容器
ValueTraits 接口
自定义 ValueTraits 示例
为不同值重用节点算法
简化值特征定义
有状态的值特性
线程安全保证
Boost.Intrusive 迭代器特性
空前向迭代器
棘手的迭代器
在具有等效键的有序关联容器中进行稳定插入和带提示插入
获取相同的类型并减少符号长度
设计说明
Boost.Intrusive 在性能敏感环境中的应用
Boost.Intrusive 在空间受限环境中的应用
Boost.Intrusive 作为基本构建块
扩展 Boost.Intrusive
性能
后部插入和销毁
反转
排序
写访问
结论
索引
类索引
类型定义索引
函数索引
发布说明
Boost 1.89 Release
Boost 1.86 发布
Boost 1.85 发布
Boost 1.82 发布
Boost 1.81 Release
Boost 1.80 发布
Boost 1.79 发布
Boost 1.77 发布
Boost 1.76 版本
Boost 1.75 发布
Boost 1.73 Release
Boost 1.71 发布
Boost 1.70 发布
Boost 1.67 发布
Boost 1.65 发布
Boost 1.64 发布
Boost 1.63 Release
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 Release
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 发布
参考文献
致谢
参考
头文件 <boost/intrusive/any_hook.hpp>
头文件 <boost/intrusive/avl_set.hpp>
头文件 <boost/intrusive/avl_set_hook.hpp>
头文件 <boost/intrusive/avltree.hpp>
头文件 <boost/intrusive/avltree_algorithms.hpp>
头文件 <boost/intrusive/bs_set.hpp>
头文件 <boost/intrusive/bs_set_hook.hpp>
头文件 <boost/intrusive/bstree.hpp>
头文件 <boost/intrusive/bstree_algorithms.hpp>
头文件 <boost/intrusive/circular_list_algorithms.hpp>
头文件 <boost/intrusive/circular_slist_algorithms.hpp>
头文件 <boost/intrusive/derivation_value_traits.hpp>
头文件 <boost/intrusive/hashtable.hpp>
头文件 <boost/intrusive/intrusive_fwd.hpp>
头文件 <boost/intrusive/linear_slist_algorithms.hpp>
头文件 <boost/intrusive/link_mode.hpp>
头文件 <boost/intrusive/list.hpp>
头文件 <boost/intrusive/list_hook.hpp>
头文件 <boost/intrusive/member_value_traits.hpp>
头文件 <boost/intrusive/options.hpp>
头文件 <boost/intrusive/pack_options.hpp>
头文件 <boost/intrusive/parent_from_member.hpp>
头文件 <boost/intrusive/pointer_plus_bits.hpp>
头文件 <boost/intrusive/pointer_rebind.hpp>
头文件 <boost/intrusive/pointer_traits.hpp>
头文件 <boost/intrusive/priority_compare.hpp>
头文件 <boost/intrusive/rbtree.hpp>
头文件 <boost/intrusive/rbtree_algorithms.hpp>
头文件 <boost/intrusive/set.hpp>
头文件 <boost/intrusive/set_hook.hpp>
头文件 <boost/intrusive/sg_set.hpp>
头文件 <boost/intrusive/sgtree.hpp>
头文件 <boost/intrusive/sgtree_algorithms.hpp>
头文件 <boost/intrusive/slist.hpp>
头文件 <boost/intrusive/slist_hook.hpp>
头文件 <boost/intrusive/splay_set.hpp>
头文件 <boost/intrusive/splaytree.hpp>
头文件 <boost/intrusive/splaytree_algorithms.hpp>
头文件 <boost/intrusive/treap.hpp>
头文件 <boost/intrusive/treap_algorithms.hpp>
头文件 <boost/intrusive/treap_set.hpp>
头文件 <boost/intrusive/trivial_value_traits.hpp>
头文件 <boost/intrusive/unordered_set.hpp>
头文件 <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