![]() |
Home | Libraries | People | FAQ | More |
Boost.Intrusive also offers associative containers
that can be very useful when creating more complex associative containers,
like containers maintaining one or more indices with different sorting semantics.
Boost.Intrusive associative containers, like most STL associative container
implemenatations are based on red-black trees.
Boost.Intrusive 也提供了關聯容器,可用於創建更為複雜的關聯容器,如維護一個或多個具有不同排序語義的索引的容器。Boost.Intrusive 的關聯容器與多數 STL 關聯容器的實現一樣,是基於紅黑樹的。
The memory overhead of these containers is usually 3 pointers and a bit (with
alignment issues, this means 3 pointers and an integer). This size can be reduced
to 3 pointers if pointers have even alignment (which is usually true in most
systems).
此類容器的空間代價通常是3個指針多一點(由於對齊的問題,這相當於3個指針加1個整數)。如果指針恰好是對齊的(在多數系統中通常都能滿足),那麼這個大小可以減少為3個指針。
An empty, non constant-time size set,
multiset or rbtree has also the size of 3 pointers
and an integer (3 pointers when optimized for size). These containers have
logarithmic complexity in many operations like searches, insertions, erasures,
etc. set and multiset are the intrusive equivalents
of standard std::set and std::multiset
containers.
一個空的、不帶常量時間 size 的 set,
multiset 或 rbtree 的大小為3個指針加1個整數(按空間優化時為3個指針)。這些容器的多數操作具有對數時間複雜度,如查找、插入、刪除等。set 和 multiset 是標準的 std::set 和 std::multiset
容器的介入式等價物。
rbtree is a superset
of set and multiset
containers that offers functions to insert unique and multiple keys.rbtree 是 set 和 multiset
容器的超集,提供了插入唯一和非唯一鍵值的函數。
set, multiset
and rbtree share the
same hooks. This is an advantage, because the same user type can be inserted
first in a multiset
and after that in set
without changing the definition of the user class.set, multiset 和 rbtree 共享相同的鉤子。這是一個優點,因為同一個用戶類型可以先被插入到 multiset 中,然後再插入到 set
中,而無需修改用戶類的定義。
template <class ...Options> class set_base_hook;
set_base_hook:
the user class derives publicly from set_base_hook
to make it set/multiset-compatible.set_base_hook: 用戶類公有派生自 set_base_hook 以兼容於 set/multiset。
template <class ...Options> class set_member_hook;
set_member_hook:
the user class contains a public set_member_hook
to make it set/multiset-compatible.set_member_hook: 用戶類包含一個公有的 set_member_hook 以兼容於 set/multiset。
set_base_hook
and set_member_hook
receive the same options explained in the section How
to use Boost.Intrusive plus a size optimization option:set_base_hook 和 set_member_hook 接受在 如何使用 Boost.Intrusive 一節中說明的各種選項,再加一個空間優化選項:
tag<class Tag>
(for base hooks only): This argument serves as a tag, so you can derive
from more than one base hook. Default: tag<default_tag>.tag<class Tag> (只用於基類鉤子):該參數作為一個標記,你可以派生自多個
slist 鉤子。缺省值:tag<default_tag>.
link_mode<link_mode_type
LinkMode>:
The linking policy. Default: link_mode<safe_link>.link_mode<link_mode_type LinkMode>: 鏈接策略。缺省值:link_mode<safe_link>.
void_pointer<class VoidPointer>:
The pointer type to be used internally in the hook and propagated to the
container. Default: void_pointer<void*>.void_pointer<class VoidPointer>: 在鉤子內部使用並被傳遞給容器的指針類型。缺省值:void_pointer<void*>.
optimize_size<bool Enable>:
The hook will be optimized for size instead of speed. The hook will embed
the color bit of the red-black tree node in the parent pointer if pointer
alignment is even. Optimizing the size will reduce speed performance a
bit since masking operations will be needed to access parent pointer and
color attributes. Default: optimize_size<false>.optimize_size<bool Enable>: 鉤子將被按空間優化而非按時間優化。如果指針是恰好對齊的,則鉤子將紅黑樹節點的顏色位嵌入到父指針中。空間優化會降低一點點速度,因為需要對父節點和顏色屬性使用掩碼操作。缺省值:optimize_size<false>.
template <class T, class ...Options> class set; template <class T, class ...Options> class multiset; template <class T, class ...Options> class rbtree;
These containers receive the same options explained in the section How to use Boost.Intrusive:這些容器接受在 如何使用 Boost.Intrusive
一節中說明的選項:
base_hook<class Hook>
/ member_hook<class T, class
Hook,
Hook T::* PtrToMember> / value_traits<class ValueTraits>: To specify the hook type
or value traits used to configure the container. (To learn about value
traits go to the section Containers
with custom ValueTraits.)base_hook<class Hook> / member_hook<class T, class Hook, Hook T::* PtrToMember> / value_traits<class ValueTraits>: 指定用於配置容器的鉤子類型或 value
traits。(要學習有關 value traits 的知識,請見 帶定制化
ValueTraits 的容器)
constant_time_size<bool Enabled>:
To activate the constant-time size() operation. Default: constant_time_size<true>constant_time_size<bool Enabled>: 激活常量時間的 size() 操作。缺省值:constant_time_size<true>
size_type<bool Enabled>:
To specify the type that will be used to store the size of the container.
Default: size_type<std::size_t>size_type<bool Enabled>: 指定用於保存容器大小的類型。缺省值:size_type<std::size_t>.
And they also can receive an additional option:它們還可以接受另一個選項:
compare<class Compare>:
Comparison function for the objects to be inserted in containers. The comparison
functor must induce a strict weak ordering. Default: compare< std::less<T> >compare<class Compare>: 被插入到容器中的對象所用的比較函數。這個比較函數必須實現一個嚴格弱序。缺省值:compare< std::less<T> >
Now let's see a small example using both hooks and both containers:
現在我們來看一個使用這些鉤子和容器的小例子:
#include <boost/intrusive/set.hpp> #include <vector> #include <algorithm> #include <cassert> using namespace boost::intrusive; //This is a base hook optimized for size
class MyClass : public set_base_hook<optimize_size<true> > { int int_; public: //This is a member hook
set_member_hook<> member_hook_; MyClass(int i) : int_(i) {} friend bool operator< (const MyClass &a, const MyClass &b) { return a.int_ < b.int_; } friend bool operator> (const MyClass &a, const MyClass &b) { return a.int_ > b.int_; } friend bool operator== (const MyClass &a, const MyClass &b) { return a.int_ < b.int_; } }; //Define a set using the base hook that will store values in reverse order
typedef set< MyClass, compare<std::greater<MyClass> > > BaseSet; //Define an multiset using the member hook
typedef member_hook<MyClass, set_member_hook<>, &MyClass::member_hook_> MemberOption; typedef multiset< MyClass, MemberOption> MemberMultiset; int main() { typedef std::vector<MyClass>::iterator VectIt; typedef std::vector<MyClass>::reverse_iterator VectRit; //Create several MyClass objects, each one with a different value
std::vector<MyClass> values; for(int i = 0; i < 100; ++i) values.push_back(MyClass(i)); BaseSet baseset; MemberMultiset membermultiset; //Check that size optimization is activated in the base hook
assert(sizeof(set_base_hook<optimize_size<true> >) == 3*sizeof(void*)); //Check that size optimization is deactivated in the member hook
assert(sizeof(set_member_hook<>) > 3*sizeof(void*)); //Now insert them in the reverse order in the base hook set
for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it){ baseset.insert(*it); membermultiset.insert(*it); } //Now test sets
{ BaseSet::reverse_iterator rbit(baseset.rbegin()), rbitend(baseset.rend()); MemberMultiset::iterator mit(membermultiset.begin()), mitend(membermultiset.end()); VectIt it(values.begin()), itend(values.end()); //Test the objects inserted in the base hook set
for(; it != itend; ++it, ++rbit) if(&*rbit != &*it) return 1; //Test the objects inserted in the member hook set
for(it = values.begin(); it != itend; ++it, ++mit) if(&*mit != &*it) return 1; } return 0; }