Copyright © 2006-2009 Bernhard Reiter
Copyright © 2006-2013 René Rivera
Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
<iterator> synopsis [iterator.synopsis]<cursor>
synopsis [cursor.synopsis]iterator
[order.iterator]iterator
requirements [order.iter.requirements]inorder::iterator
operations [order.iter.ops]inorder::iterator
constructor [order.iter.cons]operator*
[order.iter.op.star]operator->
[order.iter.op.ref]operator++
[order.iter.op.inc]operator--
[order.iter.op.dec]operator==
[order.iter.op.eq]operator!=
[order.iter.op.ne]Bernhard Reiter and René Rivera
WG21/N3700
WG21/N2101=J16/06-0171
2013-06-22
Programming Language C++, Library Working Group
René Rivera <rrivera@acm.org>
This paper proposes the addition of library components covering tree structures and related concepts to Programming Languages -- C++. The proposal is based on work towards a Boost Tree component library.
The library strives to cover many of the relevant aspects within the vast field linked to the notion of trees in computer science.
This proposal is motivated by the wish to establish methods of dealing with hierarchical data structures in a manner that is similar to that of the Standard Template Library (STL) for linear ones. That is, it seeks to provide clear, straight-forward, versatile and comprehensive concepts, data structures and algorithms for trees and related structures that allow efficient implementation while not exposing implementation details.
In particular, this proposal strives to unite types of hierarchical data structures that have historically been treated separately, although there is arguably good reason to view their role for algorithms as different aspects of common underlying concepts. Formally, this proposal's desired scope is covering all rooted ordered connected acyclic graphs.
Existing tree implementations as listed in the References section as well as the number of posts on C++ related newsgroups give an evidence of very general, high interest in tree and related data structures. Formalization of how to deal with hierarchical data structures seems to be relevant as programmers of any level of skill working in any given field is likely to need such a structure at one point.
No; this proposal originates in an effort to create a generic tree container component for Boost in the course of Google Summer of Code™ 2006, so at the time of this writing, implementation work is still unfinished and, however inspired by and striving to avoid past issues and such ones arising from current implementation efforts (see below) it is, it has not been used in practice yet.
Yes; the current state is available from https://github.com/grafikrobot/boost-tree.
It depends on some standard library components, such as std::allocator
which is used as the default allocator template argument at some points.
Concepts like allocators or iterators are reused and in some cases adapted.
Most of the proposed library is a pure extension.
Some extensions to <algorithm> and to <iterator>
are proposed.
Additionally, while not proposed herein, it has sometimes been suggested
to add a template parameter to the STL associative containers set,
multiset, map, and multimap
(and possibly an argument to their constructors) specifying a policy for
storing elements, or, more concretely, what tree. The balancers presented
in this proposal would lend themselves to such use. Indicating what type
of balanced hierarchy to use for associative containers would create some
amount of symmetry to unordered containers that allow
specification of a hash functor; it is however a momentous decision in
which position to put such a parameter. The same position as for unordered
containers (before the comparison functor) would require changes in existing
code; making it the last parameter (after the allocator) would allow existing
code to remain unchanged, but seems somewhat irritating when compared to
unordered containers.
It can be, and partly has been, implemented with today's compilers.
Note that it might be worthwhile to investigate if the present Container concept should be modified so that it only covers the requirements as of paragraph 2 of section [hierarchy.req.general] of this proposal, which correspond to the current Container concept with the exception of any expressions that implicitly assume linear internal structure and outsource those to a "Linear Container" concept as similarly formalized in the Boost Range concept (http://boost.org/libs/range/doc/range.html) externally to the Standard.
One of the most important assets of the present design is the cursor concept as a hierarchical continuation to the STL's iterator concept, and the externally defined range concept. Among their benefits, cursors allow to handle both client data access, by dereference, and subtree access while hiding the normally underlying node structure and providing a uniform interface to algorithms that are thus enabled to deal with a number of different kinds of trees. On the other hand, this abstraction achieves independence of implementation details, such as nodes for storage in many cases, allowing the underlying concepts to be applicable to other possible implementations as well.
Trees, being recursively defined data structures, seem to somewhat lend themselves to recursive implementation, i.e. declaring them in a way so they consist of a client value part and a certain number of trees in turn (as e.g. in case of [haas]). Such an approach would allow for uniform treatment of the subtrees, but would duplicate allocators and imply structure that need not be present. The tree, like existing STL containers, should be responsible for data representation and storage.
Inspired by [austern] and [dreizin],
the original approach undertaken when working on the reference implementation
was to pass policy template arguments to template class binary_tree.
While reproducing the (otherwise unbalanced) tree/cursor interface seemed
logical at first, it turned out that this was conceptually not entirely
clean, as e.g. it preferred one type of linear order, namely inorder, over
the others by putting such strong focus on inorder-invariant balancing
and its possible applications; also, balancing and augmenting metadata
would inevitably have been much more visible. It seemed more appropriate
to have different balancing adaptors and augmenting adaptors that would
replicate the interface to do that work.
As focus was put on versatility and comprehensiveness, we hope users will find this a powerful framework that covers most important aspects of dealing with hierarchical data structures in a rather intuitive way, once they have adapted to the notion of cursors which, although being the interface relevant portion of the well-known node implementation of trees, partly diverge in their usage from plain node objects.
Wherever reasonably possible, strong time complexity guarantees are given, which mostly, while trying not to require much space overhead, demand implementations that make use of any time and space saving techniques available (e.g. using arrays for both children of a binary tree node, see e.g. [austern]), which may partly restrict implementors to one "proper" way of doing things.
Most of the requirements for the library components presented in this proposal are rather tightly formulated in order to allow for them being both efficient and general enough. It is however hoped that the conceptual abstraction of hierarchies and cursors may be of general use, also allowing for more specific implementations where required (although probably not as part of the library; ideally comparable to the role of containers and iterators in modern C++ code).
Trees, having attracted much attention in the C++ community, are found in various implementations and as subjects of a number of papers. Contrary to the present proposal, practically all of them deal either with trees as used for sorted associative containers (with logarithmic time complexity for more relevant operations, achieved by some sort of balancing; examples are [dreizin], [ekman] and [karas]; plus, most current STL implementations use a red-black tree as their associative containers' base) or with what we call "external" hierarchies in the following (whose structure is dictated e.g. by a file system directory tree, an XML file or an AST; see e.g. [gottschlich], [haas], [parent] and [peeters]), but rarely both fields of application.
Approaches as found in [austern] go some steps further and have provided valuable inspiration for this project, but still do not formalize anything similar as the cursor-based interface in this proposal for dealing with a tree's contents.
The BGL, finally, deals with graphs that are even more general than hierarchical ones, which does not allow them to profit from specific hierarchy properties as much as the ones presented in this proposal. Making cursors logical extensions of iterators would probably also have been more difficult with a BGL-based approach.
While it is hoped that the current proposal somewhat reunites balanced binary trees, B-trees and "external" hierarchies, which should also facilitate work with some higher-level structures (e.g. n-ary trees to implement tries), some of those higher-level components might be an interesting feature to add to the library, such as patricia tries or ternary search tries.
Notes that are not part of the proposed text appear in gray boxes.
In this section's tables, X denotes a hierarchy class,
a denotes a value of X containing elements
of type T, c denotes a valid, non-on-top
cursor satisfying input cursor requirements, p denotes a
valid, non-on-top cursor to a, q denotes
a valid, dereferenceable cursor to a, t
denotes an lvalue or a const rvalue of X::value_type, and
rv denotes a non-const rvalue of X::value_type.
Args denotes a template parameter pack; args
denotes a function parameter pack with the pattern Args&&.
A hierarchy is an object that stores a finite set of objects, all of the
same type, in a hierarchical manner, i.e. as a rooted ordered connected acyclic
graph. Hierarchies introduce a cursor concept for navigation instead of iterators.
The library provides two kinds of native hierarchies: binary_tree,
and nary_tree, along with hierarchy-yielding hierarchy
adaptors forest_tree, and multiway_tree.
Hierarchy containers conform to the requirements of Containers ([container.requirements]),
except that the expressions in Table 1 are not required to be valid, where
a and b denote values of a type X,
and X is a hierarchy container class:
|
unsupported expression |
|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Non-constant complexity requirements in this clause are stated in one of
a number of possible different ways: unless specified otherwise, they are
expressed in terms of the number of operations n, which
stands for the total number of elements in the hierarchy; in some cases,
however, they are stated in terms of another value.
|
expression |
return type |
assertion/note |
complexity |
|---|---|---|---|
|
|
cursor type pointing to |
any cursor category |
compile time |
|
|
cursor type pointing to |
any cursor category |
compile time |
|
|
|
|
constant |
|
|
|
|
constant |
|
|
|
|
(Note A) |
|
|
|
|
(Note A) |
|
|
|
For all |
compile time |
Notes: Those entries marked "(Note A)" shall have at worst linear complexity. See the individual hierarchy containers for specific complexity.
root() and croot() return a cursor
which is the on-top value for the hierarchy. shoot() and
cshoot() return a cursor which is the past-the-end value
that is found one past the hierarchy's rightmost element. If the hierarchy
is empty, then root() == shoot();
Copy constructors for all hierarchy types defined in this clause copy the
allocator argument from their respective first parameters. All other constructors
for these hierarchy types take an Allocator& argument
(20.6.9). A copy of this argument is used for any memory allocation performed,
by these constructors and by all member functions, during the lifetime of
each hierarchy object. In all hierarchy types defined in this clause, the
member get_allocator() returns a copy of the Allocator
object used to construct the hierarchy.
The member class template rebind in the table above is
effectively a typedef template: if the name Hierarchy
is bound to SomeHierarchy<T>, then Hierarchy::rebind<U>::other
is the same type as SomeHierarchy<U>. Additionally,
because of the related assertion, given SomeHierarchy<T,R0,...,Rn>
for all template arguments present is bound to the name Hierarchy,
then Hierarchy::rebind<U>::other is the same type
as SomeHierarchy<U,S0,...,Sn> such that the types
S0 through Sn are the same as R0
through Rn, respectively, when U is
the same type as T.
A hierarchy satisfying the requirements shown in Table 3 is called a mutable hierarchy.
|
expression |
return type |
assertion/note |
complexity |
|---|---|---|---|
|
|
|
Requires: |
(Note A) |
|
|
|
Requires: |
(Note A) |
|
|
|
Requires: |
(Note A) |
|
|
|
Effects: Deletes the subtree of |
Shall be at worst linear in the the number of elements in the subtree
of |
|
|
|
Effects: |
(Note A) |
Notes: Those entries marked "(Note A)" shall have at worst linear complexity. See the individual hierarchy containers for specific complexity.
The cursor returned from a.insert(p,
t)
points to the copy of t inserted into a.
Its parent cursor is the same as that of p.
The cursor returned from a.insert(p,
rv)
points to the copy of rv inserted into a.
Its parent cursor is the same as that of p.
The cursor returnd from a.emplace(p,
args)
points to the new element constructed from args into
a. Its parent cursor is the same as that of p.
A hierarchy is called a plain hierarchy if its cursor
and const_cursor types satisfy the requirements of a plain
cursor.
The library provides one native kind of plain hierarchy, nary_tree,
and a hierarchy adaptor that in turn yields a plain hierarchy, forest_tree.
For a mutable plain hierarchy, the following expressions as shown in Table 4, are additionally required to be valid:
|
expression |
return type |
assertion/note |
complexity |
|---|---|---|---|
|
|
|
Requires: |
Shall be at worst linear in the number of elements in the subtree
of |
|
|
|
Requires: |
Linear in the number |
|
|
|
Requires: |
Linear in the number |
The cursor returned from a.insert(p,c) points to the copy
of the element that c points to, inserted into a.
Its parent cursor is the same as that of p.
A hierarchy is called a multiway hierarchy if its cursor
and const_cursor types satisfy the requirements of a multiway
cursor.
The library provides one native kind of multiway hierarchy, binary_tree,
and a hierarchy adaptor that in turn yields a multiway hierarchy, multiway_tree.
For a mutable multiway hierarchy, the semantics of some expressions from Table 3 are modified as shown in Table 5.
|
expression |
return type |
assertion/note |
complexity |
|---|---|---|---|
|
|
|
Deletes the subtree of |
Shall be at worst linear in the the number of elements in the subtree
of |
Headers <binary_tree>, and <nary_tree>
define template classes that meet the requirements for hierarchies.
Header <binary_tree> synopsis
namespace std { template <class T, class Allocator = std::allocator<T> > class binary_tree; template <class T, class Allocator> bool operator==(const binary_tree<T, Allocator>&, const binary_tree<T, Allocator>&); template <class T, class Allocator> bool operator!=(const binary_tree<T, Allocator>&, const binary_tree<T, Allocator>&); template <class T, class Allocator> void swap(binary_tree<T, Allocator>&, binary_tree<T, Allocator>&); } // namespace std
Header <nary_tree> synopsis
namespace std { template <class T, class Allocator = std::allocator<T> > class nary_tree; template <class T, class Allocator> bool operator==(const nary_tree<T, Allocator>&, const nary_tree<T, Allocator>&); template <class T, class Allocator> bool operator!=(const nary_tree<T, Allocator>&, const nary_tree<T, Allocator>&); template <class T, class Allocator> void swap(nary_tree<T, Allocator>&, nary_tree<T, Allocator>&); } // namespace std
A binary_tree is a kind of hierarchy that satisfies
multiway hierarchy requirements. Additionally, it supports (inorder-invariant)
cursor rotation. Descriptions are provided here only for operations on
binary_tree that are not described in one of these tables
or for operations where there is additional semantic information.
namespace std { template <class T, class Allocator = std::allocator<T> > class binary_tree { public: // types: typedef value_type& reference; typedef const value_type& const_reference; typedef implementation-defined cursor; typedef implementation-defined const_cursor; typedef implementation-defined size_type; typedef implementation-defined difference_type; typedef T value_type; typedef Allocator allocator_type; typedef typename allocator_traits<Allocator>::pointer pointer; typedef typename allocator_traits<Allocator>::const_pointer const_pointer; template <class U> struct rebind { typedef binary_tree< U, typename Allocator::template rebind<U>::other > other; }; // construct/copy/destroy: explicit binary_tree(const Allocator& = Allocator()); template <class InputCursor> binary_tree(InputCursor subtree, const Allocator& = Allocator()); binary_tree(const binary_tree&); binary_tree(binary_tree&&); binary_tree(const binary_tree&, const Allocator&); binary_tree(binary_tree&&, const Allocator&); ~binary_tree(); binary_tree& operator=(const binary_tree&); binary_tree& operator=(binary_tree&&); template <class InputCursor> void assign(InputCursor subtree); Allocator get_allocator() const noexcept; // cursors: cursor root() noexcept; const_cursor root() const noexcept; const_cursor croot() const noexcept; cursor shoot() noexcept; const_cursor shoot() const noexcept; const_cursor cshoot() const noexcept; // capacity: bool empty() const noexcept; size_type size() const noexcept; size_type max_size() const noexcept; // modifiers: cursor insert(const_cursor position, const T&); cursor insert(const_cursor position, T&&); template <class InputCursor> cursor insert(const_cursor position, InputCursor subtree); void rotate(const_cursor position); void swap(binary_tree&); void clear(cursor position); void clear(); }; template <class T, class Allocator> bool operator==( const binary_tree<T, Allocator>& x, const binary_tree<T, Allocator>& y); template <class T, class Allocator> bool operator!=( const binary_tree<T, Allocator>& x, const binary_tree<T, Allocator>& y); // specialized algorithms: template <class T, class Allocator> void swap( binary_tree<T, Allocator>& x, binary_tree<T, Allocator>& y); } // namespace std
binary_tree
types [bintree.types]typedef implementation-defined cursor; typedef implementation-defined const_cursor;
Both cursor and const_cursor have
to fulfill the multiway cursor ([cursor.flavors]) and ascending random
access cursor ([ascending.random.access.cursors]) requirements.
Additionally, for any instance a of either type cursor
or const_cursor, a.max_size() == 1.
explicit binary_tree (const Allocator& = Allocator()); template <class InputCursor> binary_tree (InputCursor subtree, const Allocator& = Allocator()); binary_tree (const binary_tree& x);
Complexity: The constructor template
<class
InputCursor>
binary_tree(InputCursor subtree) makes only N calls
to the copy constructor of T (where N
is the number of elements in subtree) and no reallocations
if the cursor subtree is of (either descending or ascending)
forward, bidirectional, or random access categories. It does at most 2N
calls to the copy constructor of T and logN
reallocations if they are just cursors, since it is impossible to determine
the size of subtree and then do copying.
template <class InputCursor> void assign(InputCursor subtree);
Effects:
clear(); for(auto v : subtree) insert(root().end(), v);
binary_tree
cursors [bintree.cursors]cursor shoot(); const_cursor shoot() const; const_cursor cshoot() const;
Complexity: constant
binary_tree
modifiers [bintree.modifiers]cursor insert(cursor position, const T& x); cursor insert(const_cursor position, T&& x);
Notes: Does not affect the validity of cursors and references.
Effect: Let parent be position's
parent; if parent.size() < parent.max_size(), insert a copy of x
before position, as child of parent;
Otherwise, if position.empty(), insert a copy of x
as child of position; and if !position.empty(),
insert a copy of x as parent of position's
current child, as new child of position.
Complexity: constant
template <class InputCursor> cursor insert(cursor position, InputCursor subtree);
Notes: Does not affect the validity of cursors and references.
Effects: as above, substituting InputCursor
subtree to insert instead of const
T&
x.
Complexity: linear in the number of elements in subtree.
void rotate(cursor position);
Precondition: position and its
parent are internal and non-on-top
Effects: Performs a left tree rotation around the
parent of position if position.parity() == 0
or a right tree rotation if position.parity() == 1.
Postcondition: If par
== position.parity() as of before the rotation, then, after
the rotation:
*position.begin() yields the same value it yielded
before the rotation
position.parity()
== !par
*(((position.begin())[par]).begin()) yields what *(p.begin())
yielded before, if p was position's
parent
position's parent's value is what position's
parent's parent's value yielded before. The ancestors of that cursor,
and their structure, remain unchanged
(position.begin())[!par]'s subtree is what (position.begin())[!par]'s
was before.
((position.begin()[!par]).begin())\[par]'s subtree is what (p.begin())[!par]'s
was before, if p was position's
parent.
((position.begin()[!par]).begin())[par]'s subtree is what (position.begin())[!par]'s
was before.
Complexity: constant
Notes: Does not affect the validity of cursors and references. Tree rotations are important inorder-preserving (see [order.iterators]) operations on binary trees that are especially required by balancers.
void clear(cursor position);
Notes: Invalidates only the cursors and references to the erased elements.
template <class T, class Allocator> void swap( binary_tree<T, Allocator>& x, binary_tree<T, Allocator>& y);
Effects: x.swap(y);
nary_tree
[narytree]nary_tree
overview [narytree.overview]namespace std { template <class T, class Allocator = std::allocator<T> > class nary_tree { public: // types: typedef value_type& reference; typedef const value_type& const_reference; typedef implementation-defined cursor; typedef implementation-defined const_cursor; typedef implementation-defined size_type; typedef implementation-defined difference_type; typedef T value_type; typedef Allocator allocator_type; typedef typename allocator_traits<Allocator>::pointer pointer; typedef typename allocator_traits<Allocator>::const_pointer const_pointer; template <class U> struct rebind { typedef nary_tree< U, typename Allocator::template rebind<U>::other > other; }; // construct/copy/destroy: explicit nary_tree (const Allocator& = Allocator()); template <class InputCursor> nary_tree (InputCursor subtree, const Allocator& = Allocator()); nary_tree (const nary_tree&); nary_tree (nary_tree&&); nary_tree (const nary_tree&, const Allocator&); nary_tree (nary_tree&&, const Allocator&); ~nary_tree(); nary_tree& operator=(const nary_tree&); nary_tree& operator=(nary_tree&&); template <class InputCursor> void assign(InputCursor subtree); Allocator get_allocator() const noexcept; // cursors: cursor root() noexcept; const_cursor root() const noexcept; const_cursor croot() const noexcept; cursor shoot() noexcept; const_cursor shoot() const noexcept; const_cursor cshoot() const noexcept; // capacity: bool empty() const noexcept; size_type size() const noexcept; size_type max_size() const noexcept; size_type capacity(cursor position) const noexcept; void reserve(cursor position, size_type n); void shrink_to_fit(cursor position); // modifiers: cursor insert(cursor position, const T&); cursor insert(cursor position, T&&); template <class InputCursor> cursor insert(cursor position, InputCursor subtree); cursor insert_above(cursor position, const T&); cursor insert_above(cursor position, T&&); void swap(nary_tree&); void clear(cursor position); void clear(); }; template <class T, class Allocator> bool operator==( const nary_tree<T, Allocator>& x, const nary_tree<T, Allocator>& y); template <class T, class Allocator> bool operator!=( const nary_tree<T, Allocator>& x, const nary_tree<T, Allocator>& y); // specialized algorithms: template <class T, class Allocator> void swap( nary_tree<T, Allocator>& x, nary_tree<T, Allocator>& y); } // namespace std
nary_tree
types [narytree.types]typedef implementation-defined cursor; typedef implementation-defined const_cursor;
Both cursor and const_cursor have
to fulfill the plain cursor ([cursor.flavors]) and ascending random access
cursor ([ascending.random.access.cursors]) requirements.
explicit nary_tree (const Allocator& = Allocator()); template <class InputCursor> nary_tree (InputCursor subtree, const Allocator& = Allocator()); nary_tree (const nary_tree& x);
Complexity: The constructor template
<class
InputCursor>
nary_tree(InputCursor subtree) makes only N calls
to the copy constructor of T (where N
is the number of elements in subtree) and no reallocations
if the cursor subtree is of (either descending or ascending)
forward, bidirectional, or random access categories. It does at most 2N
calls to the copy constructor of T and logN
reallocations if they are just cursors, since it is impossible to determine
the size of subtree and then do copying.
template <class InputCursor> void assign(InputCursor subtree);
Effects:
clear(); for(auto v : subtree) insert(root().end(), *i);
nary_tree
cursors [narytree.cursors]cursor shoot() noexcept; const_cursor shoot() const noexcept; const_cursor cshoot() const noexcept;
Complexity: constant
nary_tree
capacity [narytree.capacity]size_type capacity(cursor position) const noexcept;
Returns: The total number of child elements that the
cursor position can hold without requiring reallocation.
void reserve(cursor position, size_type n);
Effects: A directive that informs an nary_tree
of a planned change in a given cursor's size, so that it can manage the
storage allocation accordingly. After reserve(position, n),
capacity(position)
is greater or equal to the size_type argument n
of reserve if reallocation happens; and equal to the previous value of
capacity(position)
otherwise. Reallocation happens at this point if and only if the current
capacity is less than the size_type argument n
of reserve().
Complexity: It does not change the size of the nary_tree
and takes at most linear time in position.size().
Notes: Reallocation invalidates all the references,
pointers, and cursors referring to the child elements of position.
It is guaranteed that no reallocation takes place during insertions to
position that happen after a call to reserve() until the time when an insertion would
make position.size()
greater than the size specified in the most recent call to reserve().
nary_tree
modifiers [narytree.modifiers]cursor insert(cursor position, const T&); cursor insert(cursor position, T&&); template <class InputCursor> cursor insert(cursor position, InputCursor subtree); cursor insert_above(cursor position, const T&); cursor insert_above(cursor position, T&&);
Notes: Does not affect the validity of cursors and references.
void clear(cursor position);
Notes: Invalidates only the cursors and references to the erased elements.
template <class T, class Allocator> void swap( nary_tree<T, Allocator>& x, nary_tree<T, Allocator>& y);
Effects: x.swap(y);
Hierarchy adaptors each take a Hierarchy template parameter,
and each of their constructors takes a Hierarchy reference
argument. This hierarchy is copied into the Hierarchy
member of each adapter. Most hierarchy adaptors satisfy most of the hierarchy
requirements (except for anything that deals with allocators, as storage
management is done by the adaptees). The exception is the group of balancing
hierarchy adaptors ([hierarchy.balance]), whose members satisfy most of
the requirements of a container, of a sequence and most of the optional
sequence requirements instead (again except for anything allocation related,
and some other exceptions).
Headers <forest_tree>, and <multiway_tree>
define template classes that meet the requirements for hierarchies.
Header forest_tree synopsis
namespace std { template <class T, class Hierarchy = binary_tree<T> > class forest_tree; template <class T, class Hierarchy> bool operator==(const forest_tree<T, Hierarchy>&, const forest_tree<T, Hierarchy>&); template <class T, class Hierarchy> bool operator!=(const forest_tree<T, Hierarchy>&, const forest_tree<T, Hierarchy>&); template <class T, class Hierarchy> void swap(forest_tree<T, Hierarchy>&, forest_tree<T, Hierarchy>&); } // namespace std
Header multiway_tree synopsis
namespace std { template <class T, class Hierarchy = nary_tree< std::vector<T> > > class multiway_tree; template <class T, class Hierarchy> bool operator==( const multiway_tree<T, Hierarchy>&, const multiway_tree<T, Hierarchy>&); template <class T, class Hierarchy> bool operator!=( const multiway_tree<T, Hierarchy>&, const multiway_tree<T, Hierarchy>&); template <class T, class Hierarchy> void swap(multiway_tree<T, Hierarchy>&, multiway_tree<T, Hierarchy>&); } // namespace std
forest_tree
[foresttree]forest_tree
definition [foresttree.defn]
A forest_tree is a kind of mutable plain hierarchy
that is instantiated with a mutable multiway hierarchy that has insertion
semantics as a binary_tree ([bintree.modifiers])),
and whose cursor types cursor and const_cursor
satisfy a binary_tree's cursor
and const_cursor type requirements ([bintree.types])).
namespace std { template <class T, class Hierarchy = binary_tree<T> > class forest_tree { public: typedef Hierarchy hierarchy_type; protected: Hierarchy h; public: // types: typedef typename Hierarchy::reference reference; typedef typename Hierarchy::const_reference const_reference; typedef implementation-defined cursor; typedef implementation-defined const_cursor; typedef typename Hierarchy::size_type size_type; typedef typename Hierarchy::difference_type difference_type; typedef T value_type; typedef typename Hierarchy::pointer pointer; typedef typename Hierarchy::const_pointer const_pointer; template <class U> struct rebind { typedef forest_tree< U, typename Hierarchy::template rebind<U>::other > other; }; // construct/copy/destroy: explicit forest_tree(const Hierarchy&); explicit forest_tree(Hierarchy&& = Hierarchy()); template <class InputCursor> forest_tree(InputCursor subtree); forest_tree(const forest_tree&); forest_tree(forest_tree&&); forest_tree& operator=(const forest_tree&); template <class InputCursor> void assign(InputCursor subtree); // cursors: cursor root() { return h.root(); } const_cursor root() const { return h.root(); } const_cursor croot() const { return h.croot(); } cursor shoot(); const_cursor shoot() const; const_cursor cshoot() const; // capacity: bool empty() const { return h.empty(); } size_type size() const { return h.size(); } size_type max_size() const; // modifiers: cursor insert(cursor position, const value_type&); cursor insert(cursor position, value_type&&); template <class InputCursor> cursor insert(cursor position, InputCursor subtree); cursor insert_above(cursor position, const value_type&); cursor insert_above(cursor position, value_type&&); void swap(forest_tree&); void clear(cursor position); void clear(); }; template <class T, class Hierarchy> bool operator==( const forest_tree<T, Hierarchy>& x, const forest_tree<T, Hierarchy>& y); template <class T, class Hierarchy> bool operator!=( const forest_tree<T, Hierarchy>& x, const forest_tree<T, Hierarchy>& y); // specialized algorithms: template <class T, class Hierarchy> void swap( forest_tree<T, Hierarchy>& x, forest_tree<T, Hierarchy>& y); } // namespace std
forest_tree
types [foresttree.types]typedef implementation-defined cursor; typedef implementation-defined const_cursor;
Notes: If (the adaptee) Hierarchy's
cursor types are at least ascending bidirectional cursors, both cursor
and const_cursor are ascending bidirectional cursors.
Otherwise, they are descending forward cursors. The adaptee binary tree
is "tilted" to yield an n-ary tree, meaning that the operational
semantics of the adaptor cursor are as follows in terms of the adaptee
cursor (only valid if present in the adaptor cursor's category; only
given for mutable versions of expressions, const ones as according; expressions
missing from the list mean operational semantics and complexity are for
b as they are for f):
|
adaptor cursor |
adaptee cursor |
complexity |
|---|---|---|
|
|
|
linear |
|
|
|
constant |
|
|
|
as |
|
|
|
linear |
template <class InputCursor> forest_tree (InputCursor subtree); forest_tree (const forest_tree&);
Complexity: The constructor template
<class
InputCursor>
forest_tree(InputCursor subtree) makes only N calls
to the copy constructor of T (where N
is the number of elements in subtree) and no reallocations
if the cursor subtree is of (either descending or
ascending) forward, bidirectional, or random access categories. It does
at most 2N calls to the copy constructor of T
and logN reallocations if they are just cursors, since
it is impossible to determine the size of subtree
and then do copying.
template <class InputCursor> void assign(InputCursor subtree);
Effects:
clear(); for(auto v : subtree) insert(root().end(), v);
forest_tree
cursors [foresttree.cursors]forest_tree
modifiers [foresttree.modifiers]cursor insert(cursor position, const value_type& x); cursor insert(cursor position, value_type&& x); template <class InputCursor> cursor insert(cursor position, InputCursor subtree); cursor insert_above(cursor position, const value_type& x); cursor insert_above(cursor position, value_type&& x);
Notes: Does not affect the validity of cursors and references.
void clear(cursor position);
Notes: Invalidates only the cursors and references to the erased elements.
forest_tree
specialized algorithms [foresttree.special]template <class T, class Hierarchy> void swap( forest_tree<T, Hierarchy>& x, forest_tree<T, Hierarchy>& y);
Effects: x.swap(y);
multiway_tree
[multiwaytree]multiway_tree
definition [multiwaytree.defn]
A multiway_tree is a kind of mutable multiway hierarchy
that is instantiated with a mutable plain hierarchy whose value type
in turn is a container holding elements of multiway_tree's
value_type.
namespace std { template <class T, class Hierarchy = nary_tree< std::vector<T> > > class multiway_tree { public: typedef Hierarchy hierarchy_type; protected: Hierachy h; public: // types: typedef typename Hierachy::reference reference; typedef typename Hierachy::const_reference const_reference; typedef implementation-defined cursor; typedef implementation-defined const_cursor; typedef typename Hierachy::size_type size_type; typedef typename Hierachy::difference_type difference_type; typedef T value_type; typedef typename Hierachy::pointer pointer; typedef typename Hierachy::const_pointer const_pointer; template <class U> struct rebind { typedef multiway_tree< U, typename Hierachy::template rebind< implementation defined >::other > other; }; // construct/copy/destroy: explicit multiway_tree(const Hierachy&); explicit multiway_tree(Hierachy&& = Hierachy()); template <class InputCursor> multiway_tree (InputCursor subtree); multiway_tree(const multiway_tree&); multiway_tree(multiway_tree&&) ~multiway_tree(); multiway_tree& operator=(const multiway_tree&); template <class InputCursor> void assign(InputCursor subtree); // cursors: cursor root(); const_cursor root() const; const_cursor croot() const; cursor shoot(); const_cursor shoot() const; const_cursor cshoot() const; // capacity: bool empty() const; size_type size() const; size_type max_size() const; size_type capacity(cursor position) const; void reserve(cursor position, size_type n); // modifiers: cursor insert(cursor position, const value_type&); cursor insert(cursor position, value_type&& x = value_type()); template <class InputCursor> cursor insert(cursor position, InputCursor subtree); void rotate(cursor position); void swap(multiway_tree&); void clear(cursor position); void clear(); }; template <class T, class Hierarchy> bool operator==( const multiway_tree<T, Hierarchy>& x, const multiway_tree<T, Hierarchy>& y); template <class T, class Hierarchy> bool operator!=( const multiway_tree<T, Hierarchy>& x, const multiway_tree<T, Hierarchy>& y); // specialized algorithms: template <class T, class Hierarchy> void swap( multiway_tree<T, Hierarchy>& x, multiway_tree<T, Hierarchy>& y); } // namespace std
Types typename Hierarchy::cursor
and typename Hierarchy::const_cursor
are required to be random access cursors.
multiway_tree
types [multiwaytree.types]typedef implementation-defined cursor; typedef implementation-defined const_cursor;
Both cursor and const_cursor have
to fulfill the plain cursor requirements ([cursor.flavors]). If typename hierarchy_type::cursor
is an ascending random access cursor, cursor and
const_cursor are also ascending random access cursors
([ascending.random.access.cursors]); otherwise, they are descending random
access cursor ([descending.random.access.cursors]).
Notes: The operational semantics of the adaptor
cursor are as follows in terms of the adaptee cursor (only valid if present
in the adaptor cursor's category; only given for mutable versions of
expressions, const ones as according; expressions missing from the list
mean operational semantics and complexity are for m
as they are for n):
|
adaptor cursor |
adaptee cursor |
complexity |
|---|---|---|
|
|
|
constant |
explicit multiway_tree(const Hierachy&); explicit multiway_tree(Hierachy&& = Hierachy()); template <class InputCursor> multiway_tree (InputCursor subtree); multiway_tree(const multiway_tree&); multiway_tree(multiway_tree&&)
Complexity: The constructor template
<class
InputCursor>
multiway_tree(InputCursor subtree) makes only N calls
to the copy constructor of T (where N
is the number of elements in subtree) and no reallocations
if the cursor subtree is of (either descending or
ascending) forward, bidirectional, or random access categories. It does
at most 2N calls to the copy constructor of T
and logN reallocations if they are just cursors, since
it is impossible to determine the size of subtree
and then do copying.
template <class InputCursor> void assign(InputCursor subtree);
Effects:
clear(); for(auto v : subtree) insert(root().end(), v);
multiway_tree
cursors [multiwaytree.cursors]cursor shoot(); const_cursor shoot() const; const_cursor cshoot() const;
Complexity: constant
multiway_tree
capacity [multiwaytree.capacity]size_type capacity(cursor position) const;
Returns: The total number of child elements that
the cursor position can hold without requiring reallocation.
void reserve(cursor position, size_type n);
Effects: A directive that informs an multiway_tree
of a planned change in a given cursor's size, so that it can manage the
storage allocation accordingly. After reserve(position, n), capacity(position) is greater or equal to the size_type
argument n of reserve if reallocation happens; and
equal to the previous value of capacity(position) otherwise. Reallocation happens at this
point if and only if the current capacity is less than the size_type
argument n of reserve().
Complexity: It does not change the size of the
multiway_tree and takes at most linear time in position.size().
Notes: Reallocation invalidates all the references,
pointers, and cursors referring to the child elements of position.
It is guaranteed that no reallocation takes place during insertions to
position that happen after a call to reserve()
until the time when an insertion would make position.size() greater than the size specified in
the most recent call to reserve().
multiway_tree
modifiers [multiwaytree.modifiers]cursor insert(cursor position, const value_type&); cursor insert(cursor position, value_type&& x = value_type()); template <class InputCursor> cursor insert(cursor position, InputCursor subtree);
Notes: Does not affect the validity of cursors and references.
void clear(cursor position);
Notes: Invalidates only the cursors and references to the erased elements.
template <class T, class Hierarchy> void swap( multiway_tree<T, Hierarchy>& x, multiway_tree<T, Hierarchy>& y);
Effects: x.swap(y);
An augmenting hierarchy "augments" a mutable multiway hierarchy
which it is given as a template parameter by associating additional information
with its elements and modeling a mutable multiway hierarchy in turn.
This additional information is not directly exposed, but only readable
via certain member functions of the augmentor; it is updated internally
in order to adapt to structural or content-wise changes in the hierarchy.
The library provides one augmenting hierarchy adaptor template class:
rank_tree, found in header <rank_tree>.
Header <rank_tree> synopsis
#include <initializer_list> namespace std { template <class T, class Hierarchy = binary_tree<T> > class rank_tree; template <class T, class Hierarchy> bool operator==(const rank_tree<T, Hierarchy>&, const rank_tree<T, Hierarchy>&); template <class T, class Hierarchy> bool operator!=(const rank_tree<T, Hierarchy>&, const rank_tree<T, Hierarchy>&); template <class T, class Hierarchy> void swap(rank_tree<T, Hierarchy>&, rank_tree<T, Hierarchy>&); } // namespace std
rank_tree [ranktree]rank_tree
definition [ranktree.defn]namespace std { template <class T, class Hierarchy = binary_tree<T> > class rank_tree { public: typedef Hierarchy hierarchy_type; protected: typename hierarchy_type::template rebind< pair<T,size_t> >::other rank_tree_type; public: // types: typedef typename hierarchy_type::reference reference; typedef typename hierarchy_type::const_reference const_reference; typedef implementation-defined cursor; typedef implementation-defined const_cursor; typedef typename hierarchy_type::size_type size_type; typedef typename hierarchy_type::difference_type difference_type; typedef T value_type; typedef typename hierarchy_type::pointer pointer; typedef typename hierarchy_type::const_pointer const_pointer; template <class U> struct rebind { typedef rank_tree< U, typename hierarchy_type::template rebind<U>::other > other; }; // construct/copy/destroy: template <class InputCursor> rank_tree(InputCursor subtree); rank_tree(const rank_tree&); rank_tree(rank_tree&&); rank_tree& operator=(const rank_tree&); rank_tree& operator=(rank_tree&&); template <class InputCursor> void assign(InputCursor subtree); // cursors: cursor root() noexcept; const_cursor root() const noexcept; const_cursor croot() const noexcept; cursor shoot() noexcept; const_cursor shoot() const noexcept; const_cursor cshoot() const noexcept; cursor rank_is(size_type n); const_cursor rank_is(size_type n) const; size_type rank_of(cursor); size_type rank_of(const_cursor) const; // capacity: bool empty() const noexcept; size_type size() const noexcept; size_type max_size() const noexcept; // modifiers: cursor insert(cursor position, const T&); cursor insert(cursor position, T&& = T()); template <class InputCursor> cursor insert(cursor position, InputCursor subtree); void rotate(cursor position); void swap(rank_tree&); void clear(cursor position); void clear(); }; template <class T, class Hierarchy> bool operator==(const rank_tree<T, Hierarchy>&, const rank_tree<T, Hierarchy>&); template <class T, class Hierarchy> bool operator!=(const rank_tree<T, Hierarchy>&, const rank_tree<T, Hierarchy>&); // specialized algorithms: template <class T, class Hierarchy> void swap(rank_tree<T, Hierarchy>&, rank_tree<T, Hierarchy>&); } // namespace std
Each function listed in the public interface of rank_tree
as above calls a function of the same name for its adaptee object
h, plus possibly other operations with guaranteed
logarithmic time complexity in total. This means that operational semantics
and time complexities are as specified by the hierarchy_type;
and that a function can only be called if a function of the same name
is present in the public interface of hierarchy_type.
(The only exception to the above stated are the functions rank_is()
and rank_of(), which are newly introduced.)
rank_tree
cursors [ranktree.cursors]cursor rank_is(size_type n); const_cursor rank_is(size_type n) const;
Returns: A cursor (or const_cursor)
to the nth element of the hierarchy in inorder,
counting from inorder::begin(h).
Complexity: logarithmic in size().
size_type rank_of(cursor position); size_type rank_of(cons_cursor position) const;
Returns: The rank of element for cursor position
counting from inorder::begin(h).
Complexity: logarithmic in size().
These do not model AssociativeContainer yet but Sequence as they permit insertion in arbitrary positions. (This way, they are not required to take care of extracting, sorting and searching.)
A balancing hierarchy adaptor uses some kind of balancing method in order to guarantee logarithmic time complexity for many important operations while keeping the inorder of the adaptee hierarchy as its invariant.
A balancing hierarchy adaptor satisfies all of the requirements of a
container ([container.requirements]), of a sequence ([sequence.reqmts]),
with the exception that its erase() member functions
return void, and most of the optional sequence requirements,
except for the =operator[]= and at member functions,
which are not provided. If the adaptee hierarchy supports at least descending
bidirectional cursors, it also satisfies the requirements of a reversible
container. Descriptions are provided here only for operations on balancing
hierarchy adaptors that are not described in one of these tables or for
operations where there is additional semantic information.
The library provides four balancing hierarchy adaptor template classes
which take a mutable multiway template parameter that provides a rotate()
operation and whose cursor and const_cursor
types satisfy the requirements of a binary tree cursor ([bintree.types]):
avl_tree, red_black_tree, splay_tree,
and treap. Furthermore, two balancing hierarchy adaptor
template classes that take a mutable multiway tree template parameter
are provided: b_tree and b_star_tree.
In the following, only the template class avl_tree
and related operators are shown. Note that also red_black_tree,
splay_tree, and treap must be present
and have identical interfaces (with all occurrences of avl_tree
replaced accordingly). The same holds true for b_tree
and b_star_tree, as well, except that the standard
value for the template parameter reads multiway_tree<T>
(instead of binary_tree<T>) in their case.
Header <avl_tree> synopsis
#include <initializer_list> namespace std { template <class T, class Hierarchy = binary_tree<T> > class avl_tree; template <class T, class Hierarchy> bool operator==(const avl_tree<T, Hierarchy> const&, const avl_tree<T, Hierarchy>&); template <class T, class Hierarchy> bool operator< (const avl_tree<T, Hierarchy> const&, const avl_tree<T, Hierarchy>&); template <class T, class Hierarchy> bool operator!=(const avl_tree<T, Hierarchy> const&, const avl_tree<T, Hierarchy>&); template <class T, class Hierarchy> bool operator> (const avl_tree<T, Hierarchy> const&, const avl_tree<T, Hierarchy>&); template <class T, class Hierarchy> bool operator>=(const avl_tree<T, Hierarchy> const&, const avl_tree<T, Hierarchy>&); template <class T, class Hierarchy> bool operator<=(const avl_tree<T, Hierarchy> const&, const avl_tree<T, Hierarchy>&); template <class T, class Hierarchy> void swap(avl_tree<T, Hierarchy>&, avl_tree<T, Hierarchy>&); } // namespace std
Header <red_black_tree>
synopsis
#include <initializer_list> namespace std { template <class T, class Hierarchy = binary_tree<T> > class red_black_tree; template <class T, class Hierarchy> bool operator==(const red_black_tree<T, Hierarchy> const&, const red_black_tree<T, Hierarchy>&); template <class T, class Hierarchy> bool operator< (const red_black_tree<T, Hierarchy> const&, const red_black_tree<T, Hierarchy>&); template <class T, class Hierarchy> bool operator!=(const red_black_tree<T, Hierarchy> const&, const red_black_tree<T, Hierarchy>&); template <class T, class Hierarchy> bool operator> (const red_black_tree<T, Hierarchy> const&, const red_black_tree<T, Hierarchy>&); template <class T, class Hierarchy> bool operator>=(const red_black_tree<T, Hierarchy> const&, const red_black_tree<T, Hierarchy>&); template <class T, class Hierarchy> bool operator<=(const red_black_tree<T, Hierarchy> const&, const red_black_tree<T, Hierarchy>&); template <class T, class Hierarchy> void swap(red_black_tree<T, Hierarchy>&, red_black_tree<T, Hierarchy>&); } // namespace std
Header <splay_tree> synopsis
#include <initializer_list> namespace std { template <class T, class Hierarchy = binary_tree<T> > class splay_tree; template <class T, class Hierarchy> bool operator==(const splay_tree<T, Hierarchy> const&, const splay_tree<T, Hierarchy>&); template <class T, class Hierarchy> bool operator< (const splay_tree<T, Hierarchy> const&, const splay_tree<T, Hierarchy>&); template <class T, class Hierarchy> bool operator!=(const splay_tree<T, Hierarchy> const&, const splay_tree<T, Hierarchy>&); template <class T, class Hierarchy> bool operator> (const splay_tree<T, Hierarchy> const&, const splay_tree<T, Hierarchy>&); template <class T, class Hierarchy> bool operator>=(const splay_tree<T, Hierarchy> const&, const splay_tree<T, Hierarchy>&); template <class T, class Hierarchy> bool operator<=(const splay_tree<T, Hierarchy> const&, const splay_tree<T, Hierarchy>&); template <class T, class Hierarchy> void swap(splay_tree<T, Hierarchy>&, splay_tree<T, Hierarchy>&); } // namespace std
Header <treap> synopsis
#include <initializer_list> namespace std { template <class T, class Hierarchy = binary_tree<T> > class treap; template <class T, class Hierarchy> bool operator==(const treap<T, Hierarchy> const&, const treap<T, Hierarchy>&); template <class T, class Hierarchy> bool operator< (const treap<T, Hierarchy> const&, const treap<T, Hierarchy>&); template <class T, class Hierarchy> bool operator!=(const treap<T, Hierarchy> const&, const treap<T, Hierarchy>&); template <class T, class Hierarchy> bool operator> (const treap<T, Hierarchy> const&, const treap<T, Hierarchy>&); template <class T, class Hierarchy> bool operator>=(const treap<T, Hierarchy> const&, const treap<T, Hierarchy>&); template <class T, class Hierarchy> bool operator<=(const treap<T, Hierarchy> const&, const treap<T, Hierarchy>&); template <class T, class Hierarchy> void swap(treap<T, Hierarchy>&, treap<T, Hierarchy>&); } // namespace std
Header <b_tree> synopsis
#include <initializer_list> namespace std { template <class T, class Hierarchy = multiway_tree<T> > class b_tree; template <class T, class Hierarchy> bool operator==(const b_tree<T, Hierarchy> const&, const b_tree<T, Hierarchy>&); template <class T, class Hierarchy> bool operator< (const b_tree<T, Hierarchy> const&, const b_tree<T, Hierarchy>&); template <class T, class Hierarchy> bool operator!=(const b_tree<T, Hierarchy> const&, const b_tree<T, Hierarchy>&); template <class T, class Hierarchy> bool operator> (const b_tree<T, Hierarchy> const&, const b_tree<T, Hierarchy>&); template <class T, class Hierarchy> bool operator>=(const b_tree<T, Hierarchy> const&, const b_tree<T, Hierarchy>&); template <class T, class Hierarchy> bool operator<=(const b_tree<T, Hierarchy> const&, const b_tree<T, Hierarchy>&); template <class T, class Hierarchy> void swap(b_tree<T, Hierarchy>&, b_tree<T, Hierarchy>&); } // namespace std
Header <b_star_tree> synopsis
#include <initializer_list> namespace std { template <class T, class Hierarchy = multiway_tree<T> > class b_star_tree; template <class T, class Hierarchy> bool operator==(const b_star_tree<T, Hierarchy> const&, const b_star_tree<T, Hierarchy>&); template <class T, class Hierarchy> bool operator< (const b_star_tree<T, Hierarchy> const&, const b_star_tree<T, Hierarchy>&); template <class T, class Hierarchy> bool operator!=(const b_star_tree<T, Hierarchy> const&, const b_star_tree<T, Hierarchy>&); template <class T, class Hierarchy> bool operator> (const b_star_tree<T, Hierarchy> const&, const b_star_tree<T, Hierarchy>&); template <class T, class Hierarchy> bool operator>=(const b_star_tree<T, Hierarchy> const&, const b_star_tree<T, Hierarchy>&); template <class T, class Hierarchy> bool operator<=(const b_star_tree<T, Hierarchy> const&, const b_star_tree<T, Hierarchy>&); template <class T, class Hierarchy> void swap(b_star_tree<T, Hierarchy>&, b_star_tree<T, Hierarchy>&); } // namespace std
avl_tree [balance.avltree]avl_tree
definition [balance.defn]namespace std { template <class T, class Hierarchy = binary_tree<T> > class avl_tree { public: typedef Hierarchy hierarchy_type; protected: hierarchy_type h; public: // types: typedef typename hierarchy_type::reference reference; typedef typename hierarchy_type::const_reference const_reference; typedef implementation-defined iterator; typedef implementation-defined const_iterator; typedef typename hierarchy_type::size_type size_type; typedef typename hierarchy_type::difference_type difference_type; typedef typename hierarchy_type::value_type value_type; typedef typename hierarchy_type::allocator_type alocator_type; typedef typename hierarchy_type::pointer pointer; typedef typename hierarchy_type::const_pointer const_pointer; typedef std::reverse_iterator<iterator> reverse_iterator; typedef std::reverse_iterator<const_iterator> const_reverse_iterator; // construct/copy/destroy: explicit avl_tree(const Hierarchy&); explicit avl_tree(Hierarchy&& = Hierarchy()); avl_tree(size_type n, const Hierarchy&); avl_tree(size_type n, Hierarchy&& = Hierarchy()); avl_tree(size_type n, const T& value, const Hierarchy&); avl_tree(size_type n, const T& value, Hierarchy&& = Hierarchy()); template <class InputIterator> avl_tree(InputIterator first, InputIterator last, Hierarchy const& = Hierarchy()); avl_tree(const avl_tree<T,Hierarchy>&); avl_tree(avl_tree&&); avl_tree(initializer_list<T>); avl_tree& operator=(const avl_tree&); avl_tree& operator=(avl_tree&&); avl_tree& operator=(initializer_list<T>); template <class InputIterator> void assign(InputIterator first, InputIterator last); void assign(size_type n, const T&); void assign(initializer_list<T>); // iterators: iterator begin() noexcept; const_iterator begin() const noexcept; iterator end() noexcept{ return iterator(h.shoot()); } const_iterator end() const noexcept { return const_iterator(h.cshoot()); } reverse_iterator rbegin() noexcept; const_reverse_iterator rbegin() const noexcept; reverse_iterator rend() noexcept; const_reverse_iterator rend() const noexcept; const_iterator cbegin() const noexcept; const_iterator cend() const noexcept { return const_iterator(h.cshoot()); } const_reverse_iterator crbegin() const noexcept; const_reverse_iterator crend() const noexcept; // capacity: size_type size() const noexcept { return h.size(); } size_type max_size() const noexcept; void resize(size_type sz); void resize(size_type sz, const T&); bool empty() const noexcept { return h.empty(); } // element access: reference front(); const_reference front() const; reference back(); const_reference back() const; // modifiers: template <class... Args> void emplace_front(Args&&...); template <class... Args> void emplace_back(Args&&...); void push_front(const T&); void push_front(T&&); void push_back(const T&); void push_back(T&&); void pop_front(); void pop_back(); template <class... Args> iterator emplace(const_iterator position, Args&&); iterator insert(const_iterator position, const T&); iterator insert(const_iterator position, T&&); iterator insert(iterator position, size_type n, const T&); template <class InputIterator> iterator insert(const_iterator position, InputIterator first, InputIterator last); iterator insert(const_iterator position, initializer_list<T>); iterator erase(const_iterator position); iterator erase(const_iterator position, const_iterator last); void swap(avl_tree&); void clear() noexcept { h.clear(); } }; template <class T, class Hierarchy> bool operator==(const avl_tree<T, Hierarchy> const&, const avl_tree<T, Hierarchy>&); template <class T, class Hierarchy> bool operator< (const avl_tree<T, Hierarchy> const&, const avl_tree<T, Hierarchy>&); template <class T, class Hierarchy> bool operator!=(const avl_tree<T, Hierarchy> const&, const avl_tree<T, Hierarchy>&); template <class T, class Hierarchy> bool operator> (const avl_tree<T, Hierarchy> const&, const avl_tree<T, Hierarchy>&); template <class T, class Hierarchy> bool operator>=(const avl_tree<T, Hierarchy> const&, const avl_tree<T, Hierarchy>&); template <class T, class Hierarchy> bool operator<=(const avl_tree<T, Hierarchy> const&, const avl_tree<T, Hierarchy>&); // specialized algorithms: template <class T, class Hierarchy> void swap(avl_tree<T, Hierarchy>&, avl_tree<T, Hierarchy>&); } // namespace std
template <class InputIterator> avl_tree(InputIterator first, InputIterator last, Hierarchy const& = Hierarchy());
Effects: constructs a balanced tree equal to the
range [first, last).
Complexity: Linear.
template <class InputIterator> void assign(InputIterator first, InputIterator last);
Effects:
clear(); while(first++ != last) insert(end(), *first);
template <class... Args> void emplace_front(Args&&...); template <class... Args> void emplace_back(Args&&...); void push_front(const T&); void push_front(T&&); void push_back(const T&); void push_back(T&&); void pop_front(); void pop_back(); template <class... Args> iterator emplace(const_iterator position, Args&&); iterator insert(const_iterator position, const T&); iterator insert(const_iterator position, T&&); iterator insert(iterator position, size_type n, const T&); template <class InputIterator> iterator insert(const_iterator position, InputIterator first, InputIterator last); iterator insert(const_iterator position, initializer_list<T>);
Complexity: linear in the number of elements to insert when inserting more than one element, otherwise amortized contant.
void erase(iterator first, iterator last);
Complexity: log(size())+N where
N is the distance from first
to last
void clear();
Complexity: log(size())+N
template <class T, class Hierarchy> void swap(avl_tree<T, Hierarchy>&, avl_tree<T, Hierarchy>&);
Effects: x.swap(y);
Insert after section introduced with // 24.6.5,
range access:
// 24.7, linear order traversal iterators namespace preorder { template <class Cursor> class iterator; template <class Cursor> bool operator==( const iterator<Cursor>& x, const iterator<Cursor>& y); template <class Cursor> bool operator!=( const iterator<Cursor>& x, const iterator<Cursor>& y); } // namespace preorder namespace postorder { template <class Cursor> class iterator; template <class Cursor> bool operator==( const iterator<Cursor>& x, const iterator<Cursor>& y); template <class Cursor> bool operator!=( const iterator<Cursor>& x, const iterator<Cursor>& y); } // namespace postorder namespace inorder { template <class Cursor> class iterator; template <class Cursor> bool operator==( const iterator<Cursor>& x, const iterator<Cursor>& y); template <class Cursor> bool operator!=( const iterator<Cursor>& x, const iterator<Cursor>& y); } // namespace inorder
Add after subclause 24.7, Stream iterators ([stream.iterators]):
Cursors provide a uniform way of applying algorithms to hierarchical data structures. In order to also allow for algorithms relevant when dealing with linear data structures, any cursor class is actually a refinement of a corresponding iterator class.
If exactly one application of the expression i
= i.begin(),
followed by a finite sequence of applications of the expression ++j makes
i ==
j, j
is a child (or immediate descendant)
of i, and i
is the parent (or the immediate ancestor)
of j. A cursor j is another cursor i's
descendant if there is a finite sequential combination of applications of the
expressions ++i
and i =
i.begin() that
makes i ==
j; i
is then called j's ancestor.
If two cursors i and j share at least one common ancestor, they
refer to the same container. The descending traversal capabilities of a class
relate to the range of children of a given instance of that class.
In addition to a cursor's descending traversal tags, two of them are reused to indicate a cursor's ascending traversal abilities, namely forward and bidirectional traversal in order to indicate whether a given cursor provides traversal to the parent.
Apart from cursors that are past-the-end (like their iterator counterparts can be), the notion of a cursor on-top is introduced, denoting a cursor that is ancestor to all other cursors within a hierarchy; and just as for past-the-end ones, the library generally does not assume on-top cursors be dereferenceable.
A cursor c for which c.empty() == true
is called a leaf cursor. A leaf cursor's children are never
assumed to be dereferenceable. A cursor which is either on-top or a descendant
of an on-top cursor, but in either case not a leaf cursor, nor a descendant of
a leaf cursor, is called an internal cursor.
A cursor, like an iterator, can have a singular value that is not associated with any hierarchy, meaning that most expressions are undefined for it, with the exception of assignment of a non-singular value to a cursor that holds a singular value. The children of a leaf cursor's child are never assumed to be non-singular; nor is the parent of an on-top node.
Like for iterators, the Standard defines a number of categories of cursors according to the operations defined on them: cursor, descending cursor, descending forward cursor, descending bidirectional cursor, descending random access cursor, ascending cursor, ascending forward cursor, ascending bidirectional , and ascending random access cursor. The cursors of any ascending category generally support all the operations of their descending counterpart, plus a method to obtain their parent; relations between the forward, bidirectional and random access parts are as for iterators of those categories.
In the following sections X denotes a cursor over values of
type T, a and b denotes
an identifier, r denotes a value of T&
and t denotes a value of type T.
A class X satisfies the requirements of a cursor if the
following expressions are valid, as shown in Table 8, in addition to satisfying
the requirements of input iterators ([input.iterators]) and output iterators
([output.iterators]):
|
expression |
return type |
operational semantics |
assertion/note |
|---|---|---|---|
|
|
|
Any non-reference, non-cv-qualified type |
compile time |
|
|
Convertible to |
compile time | |
|
|
Convertible to |
compile time | |
|
|
Convertible to |
compile time |
A class X satisfies the requirements of a descending cursor
if, in addition to satisfying the requirements for cursors ([cursor.requirements])
it also conforms to the container requirements ([container.requirements])
with the exception of the following expressions:
|
unsupported expression |
|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Notes: The expressions a.begin() and a.end()
are, as shown in Table 9, replaced with equivalent expressions for cursors.
Additionally, for a descending cursor, the following expression are valid, as shown in Table 10:
|
expression |
return type |
operational semantics |
assertion/note |
|---|---|---|---|
|
|
Convertible to |
compile time | |
|
|
|
pre: |
constant |
|
|
|
pre: |
constant |
|
|
|
pre: |
constant |
|
|
|
pre: |
constant |
|
|
|
|
Linear in |
A class type X satisfies the requirements of a descending
forward cursor if the following expressions are valid, as shown in Table
11, in addition to the requirements of descending cursors ([descending.cursors])
and forward iterators ([forward.iterators]):
|
expression |
return type |
operational semantics |
assertion/note |
|---|---|---|---|
|
|
Convertible to |
compile time |
A class type X satisfies the requirements of a descending
bidirectional cursor if the following expressions are valid, as shown in
Table 12, in addition to satisfying the requirements for descending forward
cursors ([descending.forward.cursors]) and bidirectional iterators ([bidirectional.iterators]):
|
expression |
return type |
operational semantics |
assertion/note |
|---|---|---|---|
|
|
Convertible to |
compile time |
rbegin() and rend() do not seem very useful for multiway trees, as they hide end() and its possible children. Are different semantics or maybe having rend() stand in for end() sensible solutions? Or just ignore this aspect?
A class type X satisfies the requirements of a descending
random access cursor if the following expressions are valid, as shown in
Table 13, in addition to satisfying the requirements for descending bidirectional
cursors ([descending.bidirectional.cursors]) and random access iterators
([random.access.iterators]):
|
expression |
return type |
operational semantics |
assertion/note |
|---|---|---|---|
|
|
Convertible to |
compile time |
A class type X satisfies the requirements of an ascending
cursor if the following expressions are valid, as shown in Table 14, in addition
to satisfying the requirements for descending cursors ([descending.cursors]):
|
expression |
return type |
operational semantics |
assertion/note |
|---|---|---|---|
|
|
Convertible to |
compile time | |
|
|
|
(Note A) | |
|
|
|
|
pre: |
Notes: Those entries marked "(Note A)" shall have at worst linear complexity. See the individual hierarchy containers for specific complexity.
A class type X satisfies the requirements of an ascending
forward cursor if the following expressions are valid, as shown in Table
15, in addition to satisfying the requirements for ascending cursors ([ascending.cursors])
and descending forward cursors ([descending.forward.cursors]):
|
expression |
return type |
operational semantics |
assertion/note |
|---|---|---|---|
|
|
Convertible to |
compile time |
A class type X satisfies the requirements of an ascending
bidirectional cursor if the following expressions are valid, as shown in
Table 16, in addition to satisfying the requirements of ascending forward
cursors ([ascending.forward.cursors]) and descending bidirectional cursors
([descending.bidirectional.cursors]):
|
expression |
return type |
operational semantics |
assertion/note |
|---|---|---|---|
|
|
Convertible to |
compile time |
A class type X satisfies the requirements of an ascending
random access cursor if the following expressions are valid, as shown in
Table 17, in addition to satisfying the requirements for ascending bidirectional
cursors ([ascending.bidirectional.cursors]) and descending random access
cursors ([descending.random.access.cursors]):
|
expression |
return type |
operational semantics |
assertion/note |
|---|---|---|---|
|
|
Convertible to |
compile time |
A cursor that satisfies at least the descending cursor requirements ([descending.cursors])
can be either a plain cursor or a multiway cursor.
If the expressions a.begin(), a.cbegin(),
a.end() and a.cend() are valid for any
internal cursor a of type X, except for
past-the-end ones, X satisfies the plain cursor
requirements. If those expressions are valid for any internal cursor including
past-the-end ones, X satisfies the multiway cursor
requirements.
namespace std { // 24.7.4, cursor primitives template <class Cursor> struct cursor_value; template <class Cursor> struct cursor_reference; template <class Cursor> struct cursor_const_reference; template <class Cursor> struct cursor_pointer; template <class Cursor> struct cursor_difference; template <class Cursor> struct cursor_size; template <class Cursor> struct cursor_category; template <class Category, class T, class Distance = ptrdiff_t, class Size = size_t, class Pointer = T*, class Reference = T&> struct cursor; struct cursor_tag : public input_iterator_tag, public output_iterator_tag {}; struct descending_cursor_tag : public cursor_tag {}; struct descending_forward_cursor_tag : public descending_cursor_tag, public forward_iterator_tag {}; struct descending_bidirectional_cursor_tag : public descending_cursor_tag, public bidirectional_iterator_tag {}; struct descending_random_access_cursor_tag : public descending_cursor_tag, public random_access_iterator_tag {}; struct ascending_cursor_tag : public descending_cursor_tag {}; struct ascending_forward_cursor_tag : public descending_forward_cursor_tag {}; struct ascending_bidirectional_cursor_tag : public descending_bidirectional_cursor_tag {}; struct ascending_random_access_cursor_tag : public descending_random_access_cursor_tag {}; } // namespace std
To simplify the task of defining cursors, the library provides several classes and functions:
The following classes are required to be defined appropriately for a cursor
of type Cursor:
template <class Cursor> struct cursor_value { typedef typename Cursor::value_type type; }; template <class Cursor> struct cursor_reference { typedef typename Cursor::reference type; }; template <class Cursor> struct cursor_const_reference { typedef typename Cursor::const_reference type; }; template <class Cursor> struct cursor_pointer { typedef typename Cursor::pointer type; }; template <class Cursor> struct cursor_difference { typedef typename Cursor::difference_type type; }; template <class Cursor> struct cursor_size { typedef typename Cursor::size_type type; }; template <class Cursor> struct cursor_category { typedef typename Cursor::cursor_category type; };
The cursor template may be used as a base class to ease
the definition of required types for new cursors.
namespace std { template <class Category, class T, class Distance = ptrdiff_t, class Size = size_t, class Pointer = T*, class Reference = T&> struct cursor { typedef Category cursor_category; typedef T value_type; typedef Distance difference_type; typedef Size size_type; typedef Pointer pointer; typedef Reference reference; }; } // namespace std
Cursor tags pick up the notion of iterator tags ([std.iterator.tags]) and
extend them by adding information about a given cursor class' descending
or ascending traversal capabilities ([cursor.requirements]). This yields
the cursor tags cursor_tag, descending_cursor_tag,
descending_forward_cursor_tag, descending_bidirectional_cursor_tag,
descending_random_access_cursor_tag, ascending_cursor_tag,
ascending_forward_cursor_tag, ascending_bidirectional_cursor_tag
and ascending_random_access_cursor_tag. For every cursor
of type Cursor, cursor_category<Cursor>::type
must be defined to be the most specific category tag that describes the cursor's
behavior.
namespace std { struct cursor_tag : public input_iterator_tag, public output_iterator_tag {}; struct descending_cursor_tag : public cursor_tag {}; struct descending_forward_cursor_tag : public descending_cursor_tag, public forward_iterator_tag {}; struct descending_bidirectional_cursor_tag : public descending_cursor_tag, public bidirectional_iterator_tag {}; struct descending_random_access_cursor_tag : public descending_cursor_tag, public random_access_iterator_tag {}; struct ascending_cursor_tag : public descending_cursor_tag {}; struct ascending_forward_cursor_tag : public descending_forward_cursor_tag {}; struct ascending_bidirectional_cursor_tag : public descending_bidirectional_cursor_tag {}; struct ascending_random_access_cursor_tag : public descending_random_access_cursor_tag {}; } // namespace std
For linear traversal of hierarchies, the library offers a number of useful predefined
iterators, namely for preorder, postorder
and inorder traversal in namespaces named accordingly.
Preorder traversal means that after a given element, first the subtree to its left, then the one to its right will be visited.
Postorder traversal means that before a given element, first the subtree to its left, then the one to its right will be visited.
Inorder traversal means that a given element will be visited after the subtree to its left and before the one to its right will be visited.
For each of the above kinds of traversal order, the library offers a kind of order traversal iterator adaptor template class whose template parameter is a bidirectional or random access (either ascending or descending) cursor class. Increment and decrement operations for these iterator adaptor classes are implemented to allow stepwise iteration according to the respective requirements.
In the following, the template class iterator and related
operators only as in namespace preorder
are shown. Note that template classes and operators of same name and interface
must also be present in namespace postorder
as well as in namespace inorder.
namespace std { namespace preorder { template <class Cursor> class iterator : public iterator< /* see Note A */, typename iterator_traits<Cursor>::value_type, typename iterator_traits<Cursor>::difference_type, typename iterator_traits<Cursor>::pointer, typename iterator_traits<Cursor>::reference> { protected: Cursor current; public: typedef Cursor cursor_type; iterator(); explicit iterator(Cursor x); Cursor base() const; // explicit Reference operator*() const; Pointer operator->() const; iterator& operator++(); iterator operator++(int); iterator& operator--(); iterator operator--(int); }; template <class Cursor> bool operator==( const iterator<Cursor>& x, const iterator<Cursor>& y); template <class Cursor> bool operator!=( const iterator<Cursor>& x, const iterator<Cursor>& y); } // namespace preorder } // namespace std
Note A: If typename
iterator_traits<Cursor>::iterator_category is equivalent to random_access_iterator_tag,
put in bidirectional_iterator_tag; otherwise put in typename iterator_traits<Cursor>::iterator_category.
The template parameter Cursor shall meet all the requirements
of an Ascending Forward Cursor ([ascending.forward.cursors]). Additionally,
for the template class and operators in namespace inorder,
the template parameter Cursor must be a Multiway Cursor
([cursor.flavors]).
Additionally, Cursor shall meet the requirements of a Ascending
Bidirectional Cursor ([ascending.bidirectional.cursors]) if the member operator--
([order.iter.op.eq]) is referenced in a way that requires instantiation (14.7.1).
explicit iterator(Cursor x);
Effects: Initializes current with
x.
operator++
[order.iter.op.inc]iterator& operator++() const;
Effects: Sets current to the next
cursor in the given order.
Returns: *this
iterator operator++(int) const;
Effects:
iterator tmp = *this; this->operator++(); return tmp;
operator--
[order.iter.op.dec]iterator& operator--() const;
Effects: Sets current to the previous
cursor in the given order.
Returns: *this
iterator operator--(int) const;
Effects:
iterator tmp = *this; this->operator--(); return tmp;
operator==
[order.iter.op.eq]template <class Cursor> bool operator==( const iterator<Cursor>& x, const iterator<Cursor>& y);
Returns: x.current == y.current
operator!=
[order.iter.op.ne]template <class Cursor> bool operator!=( const iterator<Cursor>& x, const iterator<Cursor>& y);
Returns: x.current != y.current
Append to paragraph 2, Header , after <iterator>
synopsis// subclause 25.2,
non-modifying sequence operations.
// subclause 25.3, non-modifying hierarchy operations namespace preorder { template <class Hierarchy> iterator<typename Hierarchy::cursor> begin(Hierarchy& h); template <class Hierarchy> iterator<typename Hierarchy::const_cursor> begin(Hierarchy const& h); template <class Hierarchy> iterator<typename Hierarchy::const_cursor> cbegin(Hierarchy const& h); template <class Hierarchy> iterator<typename Hierarchy::cursor> end(Hierarchy& h); template <class Hierarchy> iterator<typename Hierarchy::const_cursor> end(Hierarchy const& h); template <class Hierarchy> iterator<typename Hierarchy::const_cursor> cend(Hierarchy const& h); } // namespace preorder namespace postorder { template <class Hierarchy> iterator<typename Hierarchy::cursor> begin(Hierarchy& h); template <class Hierarchy> iterator<typename Hierarchy::const_cursor> begin(Hierarchy const& h); template <class Hierarchy> iterator<typename Hierarchy::const_cursor> cbegin(Hierarchy const& h); template <class Hierarchy> iterator<typename Hierarchy::cursor> end(Hierarchy& h); template <class Hierarchy> iterator<typename Hierarchy::const_cursor> end(Hierarchy const& h); template <class Hierarchy> iterator<typename Hierarchy::const_cursor> cend(Hierarchy const& h); } // namespace postorder namespace inorder { template <class MultiwayHierarchy> iterator<typename MultiwayHierarchy::cursor> begin(MultiwayHierarchy& m); template <class MultiwayHierarchy> iterator<typename MultiwayHierarchy::const_cursor> begin(MultiwayHierarchy const& m); template <class MultiwayHierarchy> iterator<typename MultiwayHierarchy::const_cursor> cbegin(MultiwayHierarchy const& m); template <class MultiwayHierarchy> iterator<typename MultiwayHierarchy::cursor> end(MultiwayHierarchy& m); template <class MultiwayHierarchy> iterator<typename MultiwayHierarchy::const_cursor> end(MultiwayHierarchy const& m); template <class MultiwayHierarchy> iterator<typename MultiwayHierarchy::const_cursor> cend(MultiwayHierarchy const& m); } // namespace inorder
[c]rbegin(...) and [c]rend(..) are not
provided as they can be achieved via reverse_iterator({[c]begin(...)|[c]end(...)})
(which also defines requirements when this is possible)
Change paragraph 3 to read:
All of the algorithms are separated from the particular implementations of data structures and are parameterized by iterator or hierarchy types. Because of this, they can work with program-defined data structures, as long as these data structures have iterator or cursor types satisfying the assumptions on the algorithms.
Append to paragraph 5:
If an algorithm's template parameter is Hierarchy, the actual
template argument shall satisfy the requirements of a hierarchy ([hierarchy.req]).
If an algorithm's template parameter is MultiwayHierarchy,
the actual template argument shall satisfy the requirements of a multiway hierarchy
([hierarchy.multiway]).
Insert after section 25.2 Non-modifying sequence operations [alg.nonmodifying]
namespace preorder { template <class Hierarchy> iterator<typename Hierarchy::cursor> begin(Hierarchy& h); template <class Hierarchy> iterator<typename Hierarchy::const_cursor> begin(Hierarchy const& h); template <class Hierarchy> iterator<typename Hierarchy::const_cursor> cbegin(Hierarchy const& h); } // namespace preorder
Returns: An iterator pointing to the first element of
h in preorder.
Complexity: constant
namespace preorder { template <class Hierarchy> iterator<typename Hierarchy::cursor> end(Hierarchy& h); template <class Hierarchy> iterator<typename Hierarchy::const_cursor> end(Hierarchy const& h); template <class Hierarchy> iterator<typename Hierarchy::const_cursor> cend(Hierarchy const& h); } // namespace preorder
Returns: An iterator pointing one position past the
last element of h in preorder.
Complexity: linear
namespace postorder { template <class Hierarchy> iterator<typename Hierarchy::cursor> begin(Hierarchy& h); template <class Hierarchy> iterator<typename Hierarchy::const_cursor> begin(Hierarchy const& h); template <class Hierarchy> iterator<typename Hierarchy::const_cursor> cbegin(Hierarchy const& h); } // namespace postorder
Returns: An iterator pointing to the first element of
h in postorder.
Complexity: linear
namespace postorder { template <class Hierarchy> iterator<typename Hierarchy::cursor> end(Hierarchy& h); template <class Hierarchy> iterator<typename Hierarchy::const_cursor> end(Hierarchy const& h); template <class Hierarchy> iterator<typename Hierarchy::const_cursor> cend(Hierarchy const& h); } // namespace postorder
Returns: An iterator pointing one position past the
last element of h in postorder.
Complexity: constant
namespace inorder { template <class MultiwayHierarchy> iterator<typename MultiwayHierarchy::cursor> begin(MultiwayHierarchy& m); template <class MultiwayHierarchy> iterator<typename MultiwayHierarchy::const_cursor> begin(MultiwayHierarchy const& m); template <class MultiwayHierarchy> iterator<typename MultiwayHierarchy::const_cursor> cbegin(MultiwayHierarchy const& m); } // namespace inorder
Returns: An iterator pointing to the first element of
h in inorder.
Complexity: linear
namespace inorder { template <class MultiwayHierarchy> iterator<typename MultiwayHierarchy::cursor> end(MultiwayHierarchy& m); template <class MultiwayHierarchy> iterator<typename MultiwayHierarchy::const_cursor> end(MultiwayHierarchy const& m); template <class MultiwayHierarchy> iterator<typename MultiwayHierarchy::const_cursor> cend(MultiwayHierarchy const& m); } // namespace inorder
Returns: An iterator pointing one position past the
last element of h in inorder.
Complexity: linear
Austern, Matthew H.; Stroustrup, Bjarne; Thorup, Mikkel; Wilikinson, John. Untangling the Balancing and Searching of Balanced Binary Search Trees, Software: Practice and Experience 33(13): 1273-1298 (2003) Electronic Appendix: http://www.stroustrup.com/tree-appendix.pdf
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. Introduction to Algorithms. Second Edition (MIT Press, 2001)
Dreizin, Vladimir; Kosnik, Benjamin; Tavory, Ami. Policy-Based Data Structures, http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/
Ekman, Rasmus. Structured Associative Containers, http://www.abc.se/~re/code/tst/tst_docs/index.html
Gottschlich, Justin. C++ Trees, http://www.gamedev.net/page/resources/_/technical/general-programming/c-trees-part-1-r2192 and http://www.gamedev.net/page/resources/_/technical/general-programming/c-trees-part-2-basic-coretreefun-r2233
Haas, Mitchell. Tree Container Library, http://www.datasoftsolutions.net/tree_container_library/overview.php
Karas, Walt. C++ AVL Tree Template, http://wkaras.webs.com/gen_cpp/avl_tree.html
Knuth, Donald E. The Art of Computer Programming. Volume 1: Fundamental Algorithms. Third Edition (Reading, Massachusetts: Addison-Wesley, 1997)
Knuth, Donald E. The Art of Computer Programming. Volume 3: Sorting and Searching. Second Edition (Reading, Massachusetts: Addison-Wesley, 1998)
Parent, Sean et al. forest, http://stlab.adobe.com/group__forest__related.html
Peeters, Kasper. tree.hh: an STL-like C++ tree class, http://tree.phi-sci.com/
Rivera, René. rank_tree.h, http://redshift-software.com/sites/redshift-software.com/files/grafik/rank_tree.h