Boost C++ 库

……世界上最受推崇且设计最专业的 C++ 库项目之一。 Herb SutterAndrei Alexandrescu,《C++ 编码规范

第 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
使用基类钩子
使用成员钩子 (member hooks)
同时使用两个钩子
对象生命周期
何时使用?
概念总结
介绍 Boost.Intrusive 容器
安全钩子
安全模式的特性
配置安全模式断言
自动解除链接钩子
什么是自动解除链接钩子?
自动解除链接钩子示例
自动取消链接钩子 (auto-unlink hooks) 与具有常数时间复杂度 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 示例
为不同值重用节点算法
简化值特征 (value traits) 的定义
有状态的值特性
线程安全保证
Boost.Intrusive 迭代器特性
空前向迭代器
Scary 迭代器
在具有等效键的有序关联容器中进行稳定插入和带提示插入
获取相同的类型并减少符号长度
设计说明
性能敏感环境下的 Boost.Intrusive
空间受限环境下的 Boost.Intrusive
作为基础构建块的 Boost.Intrusive
扩展 Boost.Intrusive
性能
后部插入和销毁
反转
排序
写访问
结论
索引
类索引
类型定义索引
函数索引
发布说明
Boost 1.91 发布
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