Навязчивыйпредлагает широкий ассортимент интрузивных контейнеров:
Список: Навязчивый единичный список. Накладные расходы очень малы для пользовательских классов (обычно размер одного указателя), но многие операции имеют линейную временную сложность, поэтому пользователь должен быть осторожным, если он хочет избежать проблем с производительностью.
список:<std::list>как навязчивый связанный список. Накладные расходы довольно малы для пользовательских классов (обычно размер двух указателей). Многие операции имеют постоянную временную сложность.
набор/мультисет/рбтри:<std::set/std::multiset>как интрузивные ассоциативные контейнеры на основе красно-черных деревьев. Размер накладных расходов является умеренным для классов пользователей (обычно размер трех указателей). Многие операции имеют логарифмическую временную сложность.
avl_set/avl_multiset/avltree: A<std::set/std::multiset>как интрузивные ассоциативные контейнеры на основе деревьев AVL. Размер накладных расходов является умеренным для классов пользователей (обычно размер трех указателей). Многие операции имеют логарифмическую временную сложность.
splay_set/splay_multiset/splaytree:<std::set/std::multiset>как интрузивные ассоциативные контейнеры на основе деревьев сплея. Деревья Splay не имеют постоянных операций, но обладают интересными свойствами кэширования. Размер накладных расходов является умеренным для классов пользователей (обычно размер трех указателей). Многие операции имеют логарифмическую временную сложность.
sg_set/sg_multiset/sgtree: A<std::set/std::multiset>как интрузивные ассоциативные контейнеры на основе деревьев козлов отпущения. Козерог может быть сконфигурирован с желаемым коэффициентом баланса для достижения желаемого компромисса частоты/времени поиска. Размер накладных расходов является умеренным для классов пользователей (обычно размер трех указателей). Многие операции имеют логарифмическую временную сложность.
Boost.Intrusiveтакже предлагает полуинтрузивные контейнеры:
unordered_set/unordered_multiset:<std::tr1::unordered_set/std::tr1::unordered_multiset>как интрузивные неупорядоченные ассоциативные контейнеры. Накладные расходы являются умеренными для классов пользователей (в среднем два указателя на элемент). Многие операции амортизировали постоянную сложность времени.
Большинство из этих интрузивных контейнеров могут быть сконфигурированы с постоянным или линейным размером времени:
Размер линейного времени: Назойливый контейнер не содержит элемент размера, который обновляется с каждой вставкой / стиркой. Это означает, что функция<size()>не имеет постоянной сложности времени. С другой стороны, контейнер меньше, и некоторые операции, такие как<splice()>с использованием ряда итераторов в связанных списках, имеют постоянную временную сложность вместо линейной сложности.
Постоянный размер времени: Назойливый контейнер содержит элемент размера, который обновляется с каждой вставкой / стиркой. Это означает, что функция<size()>имеет постоянную временную сложность. С другой стороны, увеличивается размер контейнера, и некоторые операции, такие как<splice()>с использованием ряда итераторов, имеют линейную временную сложность в связанных списках.
Чтобы сделать классы пользователей совместимыми с этими интрузивными контейнерамиBoost.Intrusiveпредлагает два типа крючков для каждого типа контейнера:
Базовый крюк: Крючок хранится как общедоступный базовый класс класса пользователя.
Членский крюк: Крючок хранится как общедоступный член класса пользователя.
Кроме того,Boost.Intrusiveпредлагает дополнительные функции:
Крючки безопасного режима: Конструктор крюка инициализирует внутреннее<node>в хорошо известное безопасное состояние, и интрузивные контейнеры проверяют это состояние, прежде чем вставлять значение в контейнер с помощью этого крючка. При стирании элемента из контейнера контейнер снова ставит<node>крючка в безопасное состояние. Это обеспечивает более безопасный режим использования и может использоваться для обнаружения ошибок программирования. Это подразумевает небольшую накладную производительность в некоторых операциях и может преобразовывать некоторые постоянные временные операции в линейные временные операции.
Автоматические крючки: Крючковый деструктор автоматически удаляет объект из контейнера, и пользователь может безопасно удалить объект из контейнера, не ссылаясь на контейнер.
Необработанные указатели: Если пользователь хочет использовать умные указатели вместо необработанных указателей,Boost.Intrusiveкрючки могут быть сконфигурированы для использования любого типа указателя. Эта информация о конфигурации также передается в контейнеры, поэтому все внутренние указатели, используемые навязчивыми контейнерами, сконфигурированными с помощью этих крючков, будут интеллектуальными указателями. В качестве примера,Boost.Interprocessопределяет интеллектуальный указатель, совместимый с общей памятью, называемый<offset_ptr>.Boost.Intrusiveможет быть сконфигурирован для использования этого умного указателя, чтобы позволить совместно используемой памяти навязчивых контейнеров.
Статья Presenting Boost.Intrusive containers раздела The Boost C++ Libraries BoostBook Documentation Subset Chapter 17. Boost.Intrusive может быть полезна для разработчиков на c++ и boost.
