![]() |
Home | Libraries | People | FAQ | More |
A scapegoat tree is a self-balancing binary search tree, that provides worst-case
O(log n) lookup time, and O(log n) amortized insertion and deletion time. Unlike
other self-balancing binary search trees that provide worst case O(log n) lookup
time, scapegoat trees have no additional per-node overhead compared to a regular
binary search tree.
替罪羊樹是一種自平衡的二分查找樹,它提供了最壞情況下的
O(log n) 查找時間,以及 O(log n) 的分期插入和刪除時間。和其它的提供了最壞情況 O(log n) 查找時間的自平衡二分查找樹不同,替罪羊樹與普通的二分查找樹相比,並沒有對每個節點增加額外的開銷。
A binary search tree is said to be weight balanced if half the nodes are on
the left of the root, and half on the right. An a-height-balanced tree is defined
with defined with the following equation:
一個二分查找樹被稱為是重量平衡的,如果它的一半節點在根的左邊,另一半節點在根的右邊。而一個a高度平衡的樹則由以下公式定義:
height(tree) <= log1/a(tree.size())
Scapegoat trees are loosely a-height-balanced so:
替罪羊樹是非嚴格的 a高度平衡,因此:
height(tree) <= log1/a(tree.size()) + 1
Scapegoat trees support any a between 0.5 and 1. If a is higher, the tree is
rebalanced less often, obtaining quicker insertions but slower searches. Lower
a values improve search times. Scapegoat-trees implemented in Boost.Intrusive
offer the possibility of changing a at run-time
taking advantage of the flexibility of scapegoat trees. For more information
on scapegoat trees see Wikipedia
entry.
替罪羊樹支持位於 0.5 到 1 之間的任意 a。如果 a 較高,則樹會較少被重新平衡,插入較快但查找較慢。較低的值則提高查找的速度。在 Boost.Intrusive
中實現的替罪羊樹提供了在運行期改變 a 值的可能性,利用了替罪羊樹的靈活性。有關替罪羊樹的更多信息,請見 Wikipedia
的相關條目。
Scapegoat trees also have downsides:
替罪羊樹也具有弱點:
auto_unlink hooks.
The size of an empty scapegoat tree is also considerably increased.auto_unlink 鉤子。一個空的替罪羊樹的大小也有顯著增加。
Boost.Intrusive offers 3 containers based
on scapegoat trees: sg_set,
sg_multiset and
sgtree. The first two
are similar to set or multiset and the latter is a generalization
that offers functions both to insert unique and multiple keys.
Boost.Intrusive 提供了3種基於 splay 樹的容器:sg_set,
sg_multiset 和
sgtree。前兩種類似於 set 或 multiset,而最後一種則是一個提供了插入唯一鍵和重複鍵功能的泛型。
The memory overhead of these containers with Boost.Intrusive hooks is 3 pointers.
這些帶有 Boost.Intrusive 鉤子的容器的空間開銷通常為3個指針。
An empty, sg_set, sg_multiset or sgtree
has also the size of 3 pointers, two integers and two floating point values
(equivalent to the size of 7 pointers on most systems).
一個空的 sg_set, sg_multiset 或 sgtree 也具有3個指針、2個整數和2個浮點值的大小(在多數系統上相當於7個指針的大小)。
sg_set, sg_multiset and sgtree don't use their own hooks
but plain binary search tree hooks. This has many advantages since binary
search tree hooks can also be used to insert values in splay containers.sg_set, sg_multiset 和 sgtree 不使用它們自己的鉤子,而是使用普通的二分查找樹鉤子。這有許多優點,因為二分查找樹鉤子還可以用於將值插入到 splay 容器中。
template <class ...Options> class bs_set_base_hook;
bs_set_base_hook:
the user class derives publicly from this class to make it compatible with
scapegoat tree based containers.set_base_hook: 用戶類公有派生自
set_base_hook 以兼容於基於替罪羊樹的容器。
template <class ...Options> class bs_set_member_hook;
set_member_hook:
the user class contains a public member of this class to make it compatible
with scapegoat tree based containers.set_member_hook: 用戶類包含一個公有的
set_member_hook 以兼容於基於替罪羊樹的容器。
bs_set_base_hook
and bs_set_member_hook
receive the same options explained in the section How
to use Boost.Intrusive plus an option to optimize the size of the
node:bs_set_base_hook 和 bs_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*>.
template <class T, class ...Options> class sg_set; template <class T, class ...Options> class sg_multiset; template <class T, class ...Options> class sgtree;
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 的容器)
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 additional options:它們還可以接受其它的選項:
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> >
floating_point<bool Enable>:
When this option is deactivated, the scapegoat tree loses the ability to
change the balance factor a at run-time, but the size of an empty container
is reduced and no floating point operations are performed, normally increasing
container performance. The fixed a factor that is used when this option
is activated is 1/sqrt(2) ~ 0,70711. Default: floating_point<true>floating_point<bool Enable>: 當這一選項被去激活時,替罪羊樹將失去在運行期改變平衡因子的能力,但空容器的大小將會減少,並且不再執行浮點運算,通常會提高容器的性能。當該選項被激活時使用的因子為 1/sqrt(2) ~ 0,70711。缺省值:floating_point<true>
Now let's see a small example using both hooks and sg_set/
sg_multiset containers:
現在我們來看一個使用這些鉤子和 sg_set/
sg_multiset 容器的小例子:
#include <boost/intrusive/sg_set.hpp> #include <vector> #include <algorithm> #include <cassert> using namespace boost::intrusive; class MyClass : public bs_set_base_hook<> { int int_; public: //This is a member hook
bs_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 an sg_set using the base hook that will store values in reverse order
//and won't execute floating point operations.
typedef sg_set < MyClass, compare<std::greater<MyClass> >, floating_point<false> > BaseSet; //Define an multiset using the member hook
typedef member_hook<MyClass, bs_set_member_hook<>, &MyClass::member_hook_> MemberOption; typedef sg_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; //Now insert them in the reverse order in the base hook sg_set
for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it){ baseset.insert(*it); membermultiset.insert(*it); } //Change balance factor
membermultiset.balance_factor(0.9f); //Now test sg_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 sg_set
for(; it != itend; ++it, ++rbit) if(&*rbit != &*it) return 1; //Test the objects inserted in the member hook sg_set
for(it = values.begin(); it != itend; ++it, ++mit) if(&*mit != &*it) return 1; } return 0; }