Boost C++ Libraries Home Libraries People FAQ More


Chapter 10. Boost.Intrusive

Olaf Krzikalla

Ion Gaztanaga

Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at

Table of Contents 目錄

Introduction 簡介
Presenting Boost.Intrusive 介紹 Boost.Intrusive
Building Boost.Intrusive 構建 Boost.Intrusive
Intrusive and non-intrusive containers 介入式與非介入式容器
Differences between intrusive and non-intrusive containers 介入式與非介入式容器的區別
Properties of Boost.Intrusive containers  Boost.Intrusive 容器的特點
How to use Boost.Intrusive 如何使用 Boost.Intrusive
Using base hooks 使用基類鉤子
Using member hooks 使用成員鉤子
Using both hooks 使用兩種鉤子
Object lifetime 對像生存期
When to use? 何時使用?
Concept summary 概念摘要
Presenting Boost.Intrusive containers 介紹 Boost.Intrusive 容器
Safe hooks 安全鉤子
Features of the safe mode 安全模式的特點
Configuring safe-mode assertions 配置安全模式的斷言
Auto-unlink hooks 自解鉤子
What's an auto-unlink hook? 什麼是自解鉤子?
Auto-unlink hook example 自解鉤子的例子
Auto-unlink hooks and containers with constant-time size() 自解鉤子與常量時間 size() 的容器
Intrusive singly linked list: slist 介入式單鏈表:slist
slist hooks  slist鉤子
slist container  slist容器
Example 例子
Intrusive doubly linked list: list 介入式雙鏈表:list
list hooks  list鉤子
list container  list 容器
Example 例子
Intrusive associative containers: set, multiset, rbtree 介入式關聯容器:set, multiset, rbtree
set, multiset and rbtree hooks  set, multiset, rbtree 鉤子
set, multiset and rbtree containers  set, multiset, rbtree 容器
Example 例子
Semi-Intrusive unordered associative containers: unordered_set, unordered_multiset 半介入式無序關聯容器:unordered_set, unordered_multiset
unordered_set and unordered_multiset performance notes  unordered_set 和 unordered_multiset 的性能說明
unordered_set and unordered_multiset hooks  unordered_set 和 unordered_multiset 鉤子
unordered_set and unordered_multiset containers  unordered_set 和 unordered_multiset 容器
Example 例子
Custom bucket traits 定制化桶 traits
Intrusive splay tree based associative containers: splay_set, splay_multiset and , splay_tree 介入式 splay 樹關聯容器:splay_set, splay_multiset 和 splay_tree
Advantages and disadvantages of splay tree based containers 基於 splay 樹的容器的優缺點
splay_set, splay_multiset and splaytree hooks  splay_set, splay_multiset 和 splaytree 鉤子
splay_set, splay_multiset and splaytree containers  splay_set, splay_multiset 和 splaytree 容器
Splay trees with BST hooks  帶 BST 鉤子的 splay 樹
Example 例子
Intrusive avl tree based associative containers: avl_set, avl_multiset and avltree 介入式 avl 樹關聯容器:avl_set, avl_multiset 和 avltree
avl_set, avl_multiset and avltree hooks  avl_set, avl_multiset 和 avltree 鉤子
avl_set, avl_multiset and avltree containers  avl_set, avl_multiset 和 avltree 容器
Example 例子
Intrusive scapegoat tree based associative containers: sg_set, sg_multiset and sgtree 介入式替罪羊樹關聯容器:sg_set, sg_multiset 和 sgtree
Using binary search tree hooks: bs_set_base_hook and bs_set_member_hook 使用二分查找樹鉤子:bs_set_base_hook 和 bs_set_member_hook
sg_set, sg_multiset and sgtree containers  sg_set, sg_multiset 和 sgtree 容器
Example 例子
Advanced lookup and insertion functions for associative containers 關聯容器的高級查找和插入函數
Advanced lookups 高級查找
Advanced insertions 高級插入
Erasing and disposing values from Boost.Intrusive containers 從 Boost.Intrusive 容器中刪除和處置值
Cloning Boost.Intrusive containers 克隆 Boost.Intrusive 容器
Using smart pointers with Boost.Intrusive containers 和 Boost.Intrusive 容器一起使用智能指針
Requirements for smart pointers compatible with Boost.Intrusive 兼容於 Boost.Intrusive 的智能指針的要求
Obtaining iterators from values 從值獲得迭代器
Any Hooks: A single hook for any Intrusive container 任意鉤子:用於任意介入式容器的單鉤子
Concepts explained 概念的說明
Node algorithms with custom NodeTraits 帶定制化 NodeTraits 的節點算法
Intrusive singly linked list algorithms 介入式單鏈表算法
Intrusive doubly linked list algorithms 介入式雙鏈表算法
Intrusive red-black tree algorithms 介入式紅黑樹算法
Intrusive splay tree algorithms 介入式 splay 樹算法
Intrusive avl tree algorithms 介入式 avl 樹算法
Containers with custom ValueTraits 帶定制化 ValueTraits 的容器
ValueTraits interface  ValueTraits 接口
Custom ValueTraits example 定制化 ValueTraits 的例子
Reusing node algorithms for different values 為不同的值重用節點算法
Simplifying value traits definition 簡化 value traits 的定義
Stateful value traits 有狀態的 value traits
Thread safety guarantees 線程安全保證
Obtaining the same types and reducing symbol length 獲得相同類型及縮短符號長度
Design Notes 設計說明
Boost.Intrusive in performance sensitive environments 性能敏感環境下的 Boost.Intrusive
Boost.Intrusive in space constrained environments 空間受限環境下的 Boost.Intrusive
Boost.Intrusive as a basic building block 作為基本構建塊的 Boost.Intrusive
Extending Boost.Intrusive 擴展 Boost.Intrusive
Performance 性能
Back insertion and destruction 後端插入和析構
Reversing 反序
Sorting 排序
Write access 寫訪問
Conclusions 總結
Release Notes 發佈說明
Boost 1.37 Release
Boost 1.36 Release
Tested compilers 已測試的編譯器
References 參考文獻
Acknowledgements 鳴謝
Reference 詳細參考
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_hook.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/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/pointer_plus_bits.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/splay_set_hook.hpp>
Header <boost/intrusive/splaytree.hpp>
Header <boost/intrusive/splaytree_algorithms.hpp>
Header <boost/intrusive/trivial_value_traits.hpp>
Header <boost/intrusive/unordered_set.hpp>
Header <boost/intrusive/unordered_set_hook.hpp>
License notices 許可證說明

Boost.Intrusive is a library presenting some intrusive containers to the world of C++. Intrusive containers are special containers that offer better performance and exception safety guarantees than non-intrusive containers (like STL containers). 
Boost.Intrusive 是一個將介入式容器引入到C++世界的庫。介入式容器是一種特殊的容器,它提供比非介入式容器(如STL容器) 更好的性能 和異常安全保證。

The performance benefits of intrusive containers makes them ideal as a building block to efficiently construct complex containers like multi-index containers or to design high performance code like memory allocation algorithms.

While intrusive containers were and are widely used in C, they became more and more forgotten in C++ due to the presence of the standard containers which don't support intrusive techniques.Boost.Intrusive not only reintroduces this technique to C++, but also encapsulates the implementation in STL-like interfaces. Hence anyone familiar with standard containers can easily use Boost.Intrusive.
雖然介入式容器在C中被廣泛使用,但是在C++中卻被日漸遺忘,這是由於不支持介入式技術的標準容器的出現。Boost.Intrusive 不僅重新將這一技術引入到C++,而且還將實現封裝為類似於STL的接口。所以每一個熟悉標準容器的人都可以很容易地使用 Boost.Intrusive

There is no need to compile anything to use Boost.Intrusive, since it's a header only library. Just include your Boost header directory in your compiler include path.
使用 Boost.Intrusive 不需要編譯任何東西,因為它是一個僅有頭文件的庫。只需要將你的 Boost 頭文件目錄包含在你的編譯器包含路徑中就可以了。

Last revised: November 02, 2008 at 13:06:44 GMT