Chapter 17. Boost.Intrusive . Boost , The Boost C++ Libraries BoostBook Documentation Subset , Part I. The Boost C++ Libraries (BoostBook Subset)

Chapter 17. Boost.Intrusive

Olaf Krzikalla

Ion Gaztanaga

Распространяется под лицензией Boost Software License, версия 1.0. (См. сопроводительный файл LICENSE_1_0.txt или копию по адресуhttp://www.boost.org/LICENSE_1_0.txt)

Таблица содержания

Introduction

Presenting Boost.Intrusive
Building Boost.Intrusive

Intrusive and non-intrusive containers

Differences between intrusive and non-intrusive containers
Properties of Boost.Intrusive containers

How to use Boost.Intrusive

Using base hooks
Using member hooks
Using both hooks
Object lifetime

When to use?

Concept summary

Presenting Boost.Intrusive containers

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()

Intrusive singly linked list: slist

slist hooks
slist container
Example

Intrusive doubly linked list: list

list hooks
list container
Example

Intrusive associative containers: set, multiset, rbtree

set, multiset and rbtree hooks
set, multiset and rbtree containers
Example

Semi-Intrusive unordered associative containers: unordered_set, unordered_multiset

unordered_set and unordered_multiset performance notes
unordered_set and unordered_multiset hooks
unordered_set and unordered_multiset containers
Example
Custom bucket traits

Map and multimap-like interface for associative containers

Intrusive avl tree based associative containers: avl_set, avl_multiset and avltree

avl_set, avl_multiset and avltree hooks
avl_set, avl_multiset and avltree containers
Example

Intrusive splay tree based associative containers: splay_set, splay_multiset and , splay_tree

Advantages and disadvantages of splay tree based containers
splay_set, splay_multiset and splaytree containers
Example

Intrusive scapegoat tree based associative containers: sg_set, sg_multiset and sgtree

sg_set, sg_multiset and sgtree containers
Example

Intrusive treap based associative containers: treap_set, treap_multiset and treap

treap_set, treap_multiset and treap containers
Exception safety of treap-based intrusive containers
Example

Binary search tree hooks: bs_set_base_hook and bs_set_member_hook

Advanced lookup and insertion functions for associative containers

Advanced lookups
Advanced insertions
Positional insertions

Erasing and disposing values from Boost.Intrusive containers

Cloning Boost.Intrusive containers

Using function hooks

Recursive Boost.Intrusive containers

Using smart pointers with Boost.Intrusive containers

Requirements for smart pointers compatible with Boost.Intrusive

Obtaining iterators from values

Any Hooks: A single hook for any Intrusive container

Concepts explained

Node algorithms with custom NodeTraits

Intrusive singly linked list algorithms
Intrusive doubly linked list algorithms
Intrusive red-black tree algorithms
Intrusive splay tree algorithms
Intrusive avl tree algorithms
Intrusive treap algorithms

Containers with custom ValueTraits

ValueTraits interface
Custom ValueTraits example
Reusing node algorithms for different values
Simplifying value traits definition
Stateful value traits

Thread safety guarantees

Scary Iterators

Stability and insertion with hint in ordered associative containers with equivalent keys

Obtaining the same types and reducing symbol length

Design Notes

Boost.Intrusive in performance sensitive environments
Boost.Intrusive in space constrained environments
Boost.Intrusive as a basic building block
Extending Boost.Intrusive

Performance

Back insertion and destruction
Reversing
Sorting
Write access
Conclusions

Release Notes

Boost 1.62 Release
Boost 1.61 Release
Boost 1.60 Release
Boost 1.59 Release
Boost 1.58 Release
Boost 1.57 Release
Boost 1.56 Release
Boost 1.55 Release
Boost 1.54 Release
Boost 1.53 Release
Boost 1.51 Release
Boost 1.49 Release
Boost 1.48 Release
Boost 1.46 Release
Boost 1.45 Release
Boost 1.40 Release
Boost 1.39 Release
Boost 1.38 Release
Boost 1.37 Release
Boost 1.36 Release

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>

Introduction

Presenting Boost.Intrusive
Building Boost.Intrusive

Навязчивый- это библиотека, представляющая некоторые навязчивые контейнеры для мира C++. Интрузивные контейнеры - это специальные контейнеры, которые предлагаютлучшую производительностьи гарантии безопасности исключения, чем неинтрузивные контейнеры (например, контейнеры STL).

Преимущества интрузивных контейнеров делают их идеальным строительным блоком для эффективного создания сложных контейнеров, таких как мультииндексные контейнеры, или для разработки высокопроизводительного кода, такого как алгоритмы распределения памяти.

В то время как интрузивные контейнеры были и широко используются в C, они становились все более и более забытыми в C++ из-за наличия стандартных контейнеров, которые не поддерживают интрузивные методы.Boost.Intrusiveхочет продвигать использование интрузивных контейнеров, инкапсулируя реализацию в STL-подобных интерфейсах. Поэтому любой, кто знаком со стандартными контейнерами, может легко использоватьBoost.Intrusive.

Building Boost.Intrusive

Нет необходимости компилировать что-либо, чтобы использоватьBoost.Intrusive, поскольку это только заголовок библиотеки. Просто включите каталог заголовков Boost в компилятор включите путь.

Статья Chapter 17. Boost.Intrusive раздела The Boost C++ Libraries BoostBook Documentation Subset Part I. The Boost C++ Libraries (BoostBook Subset) может быть полезна для разработчиков на c++ и boost.