This paper proposes addition of library components covering tree structures and related concepts to the C++ Standard Library Technical Report 2. The proposal is based on work towards a Boost tree component library (see https://boost-consulting.com:8443/trac/soc/wiki/tree).
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 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 svn from https://www.boost-consulting.com:8443/svn/main/boost/soc/2006/tree/trunk. Alternatively, the source code can be viewed in a web browser at https://boost-consulting.com:8443/trac/soc/browser/boost/soc/2006/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 <algorithm> and some extensions 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 TR1's 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 [tr.hierarchy.req] 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.
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] or [mirwaisi] 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.
A hierarchy is an object that stores a finite set of objects, all of the same type, in a hierarchical manner. 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 ([lib.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 |
|---|
| X::iterator |
| X::const_iterator |
| X::reverse_iterator |
| X::const_reverse_iterator |
| a.begin() |
| a.end() |
| a.rbegin() |
| a.rend() |
| a < b |
| a > b |
| a <= b |
| a >= b |
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.
In Table 2: X denotes a hierarchy class containing objects of type T and a denotes a value of type X.
| expression | return type | assertion/note pre/post-condition |
complexity |
|---|---|---|---|
| X::cursor | cursor type pointing to T | any cursor category | compile time |
| X::const_cursor | cursor type pointing to const T | any cursor category | compile time |
| a.root() | iterator for mutable a; const_iterator for constant a |
constant | |
| a.croot() | const_iterator | constant | |
| a.shoot() | iterator for mutable a; const_iterator for constant a |
(Note A) | |
| a.cshoot() | const_iterator | (Note A) | |
| typename X::template rebind<U>::other |
Y | For all U (including T), Y::template rebind<T>::other is X. | compile time |
Notes: Those entries marked "(Note A)" should 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.1.5). 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. In Table 3, X denotes a hierarchy class, a denotes a value of X, 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, and t denotes a value of X::value_type.
| expression | return type | assertion/note pre/post-condition |
complexity |
|---|---|---|---|
| a.insert(p,t) | cursor | inserts a copy of t before p | (Note A) |
| a.clear(q) | void | deletes the subtree of q and the element
q points to. pre: q is dereferenceable. |
Should be at worst linear in the the number of elements in the subtree of q plus the distance to q's parent's end(). |
| a.clear() | void | while (a.size()) clear(a.begin()); post: a.size() == 0 |
(Note A) |
Notes: Those entries marked "(Note A)" should have at worst linear complexity. See the individual hierarchy containers for specific complexity.
A hierarchy is called 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 expression as shown in Table 4, is additionally required to be valid:
| expression | return type | assertion/note pre/post-condition |
complexity |
|---|---|---|---|
| a.insert(p,c) | cursor | inserts a copy of the subtree of c before
p. pre: c is dereferenceable. |
Should be at worst linear in the the number of elements in the subtree of c plus the distance to p's parent's end(). |
| a.insert_above(p,t) | cursor | inserts a copy of t as child of p's
parent and new parent of p and its siblings. pre: c is dereferenceable. |
Linear in the the number p's siblings. |
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 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 pre/post-condition |
complexity |
|---|---|---|---|
| a.clear(q) | void | deletes the subtree of q. If q is dereferenceable, the expression also deletes the element q points to. If q is past-the-end, the expression deletes the element q's predecessor points to. If after either of these steps q has only a non-empty past-the-end child, that child's children become q's children instead. Finally, that child is deleted. pre: q is internal. |
Should be at worst linear in the the number of elements in the subtree of c plus the distance to p's parent's end(). |
Headers <binary_tree>, <nary_tree>, <forest_tree>, and <multiway_tree>.
namespace std {
namespace tr2 {
template <class T, class Alloc = std::allocator<T> >
class binary_tree;
template <class T, class Alloc>
bool operator==( binary_tree<T, Alloc> const& x,
binary_tree<T, Alloc> const& y);
template <class T, class Alloc>
bool operator!=( binary_tree<T, Alloc> const& x,
binary_tree<T, Alloc> const& y);
template <class T, class Alloc>
void swap( binary_tree<T, Alloc>& x,
binary_tree<T, Alloc>& y);
namespace inorder {
template <class Tp, class Alloc>
inorder::iterator<binary_tree<Tp, Alloc>::cursor>
begin(binary_tree<Tp, Alloc>& h);
template <class Tp, class Alloc>
inorder::iterator<binary_tree<Tp, Alloc>::const_cursor>
cbegin(binary_tree<Tp, Alloc> const& h);
} // namespace inorder
} // namespace tr2
} // namespace std
namespace std {
namespace tr2 {
template <class T, class Alloc = std::allocator<T> >
class nary_tree;
template <class T, class Alloc>
bool operator==( binary_tree<T, Alloc> const& x,
binary_tree<T, Alloc> const& y);
template <class T, class Alloc>
bool operator!=( binary_tree<T, Alloc> const& x,
binary_tree<T, Alloc> const& y);
template <class T, class Alloc>
void swap( nary_tree<T, Alloc>& x,
nary_tree<T, Alloc>& y);
namespace inorder {
template <class T, class Alloc>
inorder::iterator<binary_tree<T, Alloc>::cursor>
begin(binary_tree<T, Alloc>& h);
template <class T, class Alloc>
inorder::iterator<binary_tree<T, Alloc>::const_cursor>
cbegin(binary_tree<T, Alloc> const& h);
} // namespace inorder
} // namespace tr2
} // namespace std
namespace std {
namespace tr2 {
template <class T, class Hierarchy = binary_tree<T> >
class forest_tree;
template <class T, class Hierarchy>
bool operator==( forest_tree<T, Hierarchy> const& x,
forest_tree<T, Hierarchy> const& y);
template <class T, class Alloc>
bool operator!=( forest_tree<T, Hierarchy> const& x,
forest_tree<T, Hierarchy> const& y);
template <class T, class Hierarchy>
void swap( forest_tree<T, Hierarchy>& x,
forest_tree<T, Hierarchy>& y);
namespace inorder {
template <class T, class Hierarchy>
inorder::iterator<forest_tree<T, Hierarchy>::cursor>
begin(forest_tree<T, Hierarchy>& h);
template <class T, class Alloc>
inorder::iterator<forest_tree<T, Hierarchy>::const_cursor>
cbegin(forest_tree<T, Hierarchy> const& h);
} // namespace inorder
} // namespace tr2
} // namespace std
namespace std {
namespace tr2 {
template <class T, class Hierarchy = nary_tree< std::vector<T> > >
class multiway_tree;
template <class T, class Hierarchy>
bool operator==( multiway_tree<T, Hierarchy> const& x,
multiway_tree<T, Hierarchy> const& y);
template <class T, class Alloc>
bool operator!=( multiway_tree<T, Hierarchy> const& x,
multiway_tree<T, Hierarchy> const& y);
template <class T, class Hierarchy>
void swap( multiway_tree<T, Hierarchy>& x,
multiway_tree<T, Hierarchy>& y);
namespace inorder {
template <class T, class Hierarchy>
inorder::iterator<multiway_tree<T, Hierarchy>::cursor>
begin(multiway_tree<T, Hierarchy>& h);
template <class T, class Alloc>
inorder::iterator<multiway_tree<T, Hierarchy>::const_cursor>
cbegin(multiway_tree<T, Hierarchy> const& h);
} // namespace inorder
} // namespace tr2
} // 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 {
namespace tr2 {
template <class T, class Alloc = std::allocator<T> >
class binary_tree
{
public:
// types:
typedef T value_type;
typedef Alloc allocator_type;
typedef implementation defined cursor;
typedef implementation defined const_cursor;
typedef typename allocator_type::pointer pointer;
typedef typename allocator_type::const_pointer const_pointer;
typedef typename allocator_type::reference reference;
typedef typename allocator_type::const_reference const_reference;
typedef typename allocator_type::size_type size_type;
typedef typename allocator_type::difference_type difference_type;
template <class U> struct rebind {
typedef binary_tree< U, typename allocator_type::template rebind<U>::other >
other;
};
// construct/copy/destroy:
explicit binary_tree (allocator_type const& = allocator_type());
template <class InputCursor>
binary_tree (InputCursor subtree,
allocator_type const& = allocator_type());
binary_tree (binary_tree<T, Alloc> const& x);
~binary_tree();
binary_tree<T, Alloc>& operator=(
binary_tree<T, Alloc> const& x);
template <class InputCursor>
void assign(InputCursor subtree);
allocator_type get_allocator() const;
// cursors:
cursor root();
const_cursor croot() const;
cursor shoot();
const_cursor cshoot() const;
cursor inorder_first();
const_cursor inorder_cfirst const();
// capacity:
bool empty() const;
size_type size() const;
size_type max_size() const;
// modifiers:
cursor insert(cursor position, value_type const& x = value_type());
template <class InputCursor>
cursor insert(cursor position, InputCursor subtree);
void rotate(cursor position);
void swap(binary_tree<T, Alloc>&);
void clear(cursor position);
void clear();
};
template <class T, class Alloc>
bool operator==( binary_tree<T, Alloc> const& x,
binary_tree<T, Alloc> const& y);
template <class T, class Alloc>
bool operator!=( binary_tree<T, Alloc> const& x,
binary_tree<T, Alloc> const& y);
// specialized algorithms:
template <class T, class Alloc>
void swap( binary_tree<T, Alloc>& x,
binary_tree<T, Alloc>& y);
namespace inorder {
template <class T, class Alloc>
inorder::iterator<binary_tree<T, Alloc>::cursor>
begin(binary_tree<T, Alloc>& h);
template <class T, class Alloc>
inorder::iterator<binary_tree<T, Alloc>::const_cursor>
cbegin(binary_tree<T, Alloc> const& h);
} // namespace inorder
} // namespace tr2
} // namespace std
typedef implementation defined cursor; typedef implementation defined const_cursor;
Both cursor and const_cursor have to fulfill the multiway cursor ([tr.cursor.flavors]) and ascending random access cursor ([tr.ascending.random.access.cursors]) requirements.
Additionally, for any instance a of either type cursor or const_cursor, a.max_size() == 1.
explicit binary_tree (allocator_type const& = allocator_type());
template <class InputCursor>
binary_tree (InputCursor subtree,
allocator_type const& = allocator_type());
binary_tree (binary_tree<T, Alloc> const& x);
Complexity: The constructor template <class InputCursor> vector(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(InputCursor i = subtree.begin(); i != subtree.end(); ++i) insert(root.end(), *i);
cursor shoot();
const_cursor cshoot() const;
Complexity: constant
cursor inorder_first();
const_cursor inorder_cfirst() const;
Returns: A cursor to the binary_tree's first element in inorder (see [tr.order.iterators], §4).
Complexity: constant.
cursor insert(cursor position, value_type const& x = value_type());
Notes: Does not affect the validity of cursors and references.
Effects: Let b be a's
parent;
if b.size() < b.max_size(), insert a copy of t
before p, as child of b;
Otherwise, if a.empty(), insert a copy of t as
child of a; and if !a.empty(), insert a copy of
t as parent of a's current child, as new child of
a.
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 value_type const& 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:
Complexity: constant
Notes: Does not affect the validity of cursors and references. Tree rotations are important inorder-preserving (see [tr.order.iterators] §4) 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 Alloc>
void swap( binary_tree<T, Alloc>& x,
binary_tree<T, Alloc>& y);
Effects: x.swap(y);
namespace inorder {
template <class T, class Alloc>
inorder::iterator<binary_tree<T, Alloc>::cursor>
begin(binary_tree<T, Alloc>& h);
} // namespace inorder
Returns: inorder::iterator<binary_tree<T, Alloc>::cursor>(h.inorder_first()).
Complexity: constant
namespace inorder {
template <class T, class Alloc>
inorder::iterator<binary_tree<T, Alloc>::const_cursor>
cbegin(binary_tree<T, Alloc> const& h);
} // namespace inorder
Returns: inorder::iterator<binary_tree<T, Alloc>::const_cursor>(h.inorder_cfirst()).
Complexity: constant
namespace std {
namespace tr2 {
template <class T, class Alloc = std::allocator<T> >
class nary_tree {
public:
// types:
typedef T value_type;
typedef Alloc allocator_type;
typedef implementation defined cursor;
typedef implementation defined const_cursor;
typedef typename allocator_type::pointer pointer;
typedef typename allocator_type::const_pointer const_pointer;
typedef typename allocator_type::reference reference;
typedef typename allocator_type::const_reference const_reference;
typedef typename allocator_type::size_type size_type;
typedef typename allocator_type::difference_type difference_type;
template <class U> struct rebind {
typedef nary_tree< U, typename allocator_type::template rebind<U>::other >
other;
};
// construct/copy/destroy:
explicit nary_tree (allocator_type const& = allocator_type());
template <class InputCursor>
nary_tree (InputCursor subtree,
allocator_type const& = allocator_type());
nary_tree (nary_tree<T, Alloc> const& x);
~nary_tree();
nary_tree<T, Alloc>& operator=(
nary_tree<T, Alloc> const& x);
template <class InputCursor>
void assign(InputCursor subtree);
allocator_type get_allocator() const;
// cursors:
cursor root();
const_cursor croot() const;
cursor shoot();
const_cursor cshoot() const;
cursor inorder_first();
const_cursor inorder_cfirst 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, value_type const& x = value_type());
template <class InputCursor>
cursor insert(cursor position, InputCursor subtree);
cursor insert_above(cursor position, value_type const& x = value_type());
void swap(nary_tree<Tp, Alloc>&);
void clear(cursor position);
void clear();
};
template <class T, class Alloc>
bool operator==( nary_tree<T, Alloc> const& x,
nary_tree<T, Alloc> const& y);
template <class T, class Alloc>
bool operator!=( nary_tree<T, Alloc> const& x,
nary_tree<T, Alloc> const& y);
// specialized algorithms:
template <class T, class Alloc>
void swap( nary_tree<T, Alloc>& x,
nary_tree<T, Alloc>& y);
namespace inorder {
template <class T, class Alloc>
inorder::iterator<nary_tree<T, Alloc>::cursor>
begin(nary_tree<T, Alloc>& h);
template <class T, class Alloc>
inorder::iterator<nary_tree<T, Alloc>::const_cursor>
cbegin(nary_tree<T, Alloc> const& h);
} // namespace inorder
} // namespace tr2
} // namespace std
typedef implementation defined cursor; typedef implementation defined const_cursor;
Both cursor and const_cursor have to fulfill the plain cursor ([tr.cursor.flavors]) and ascending random access cursor ([tr.ascending.random.access.cursors]) requirements.
explicit nary_tree (allocator_type const& = allocator_type());
template <class InputCursor>
nary_tree (InputCursor subtree,
allocator_type const& = allocator_type());
nary_tree (nary_tree<T, Alloc> const& x);
Complexity: The constructor template <class InputCursor> vector(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(InputCursor i = subtree.begin(); i != subtree.end(); ++i) insert(root.end(), *i);
cursor shoot();
const_cursor cshoot() const;
Complexity: constant
cursor inorder_first();
const_cursor inorder_cfirst() const;
Returns: A cursor to the nary_tree's first element in inorder (see [tr.order.iterators], §4).
Complexity: constant.
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 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().
cursor insert(cursor position, value_type const& x = value_type());
template <class InputCursor>
cursor insert(cursor position, InputCursor subtree);
cursor insert_above(cursor position, value_type const& x = value_type());
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 Alloc>
void swap( nary_tree<T, Alloc>& x,
nary_tree<T, Alloc>& y);
Effects: x.swap(y);
namespace inorder {
template <class T, class Alloc>
inorder::iterator<nary_tree<T, Alloc>::cursor>
begin(nary_tree<T, Alloc>& h);
} // namespace inorder
Returns: inorder::iterator<nary_tree<T, Alloc>::cursor>(h.inorder_first()).
Complexity: constant
namespace inorder {
template <class T, class Alloc>
inorder::iterator<nary_tree<T, Alloc>::const_cursor>
cbegin(nary_tree<T, Alloc> const& h);
} // namespace inorder
Returns: inorder::iterator<nary_tree<T, Alloc>::const_cursor>(h.inorder_cfirst()).
Complexity: constant
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 ([tr.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).
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 ([tr.hierarchy.bintree.modifiers], §1)), and whose cursor types cursor and const_cursor satisfy a binary_tree's cursor and const_cursor type requirements ([tr.hierarchy.bintree.types], §1-2)).
namespace std {
namespace tr2 {
template <class T, class Hierarchy = binary_tree<T> >
class forest_tree {
public:
typedef Hierarchy hierarchy_type;
protected:
hierarchy_type h;
public:
// types:
typedef T value_type;
typedef implementation defined cursor;
typedef implementation defined const_cursor;
typedef typename hierarchy_type::pointer pointer;
typedef typename hierarchy_type::const_pointer const_pointer;
typedef typename hierarchy_type::reference reference;
typedef typename hierarchy_type::const_reference const_reference;
typedef typename hierarchy_type::size_type size_type;
typedef typename hierarchy_type::difference_type difference_type;
template <class U> struct rebind {
typedef forest_tree< U, typename hierarchy_type::template rebind<U>::other >
other;
};
// construct/copy/destroy:
explicit forest_tree (hierarchy_type const& = hierarchy_type());
template <class InputCursor>
forest_tree (InputCursor subtree);
forest_tree (forest_tree<T, Hierarchy> const& x);
forest_tree<T, Hierarchy>& operator=(
forest_tree<T, Hierarchy> const& x);
template <class InputCursor>
void assign(InputCursor subtree);
// cursors:
cursor root() { return h.root(); }
const_cursor croot() { return h.croot(); }
cursor shoot();
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, value_type const& x = value_type());
template <class InputCursor>
cursor insert(cursor position, InputCursor subtree);
cursor insert_above(cursor position, value_type const& x = value_type());
void swap(forest_tree<Tp, Hierarchy>&);
void clear(cursor position);
void clear();
};
template <class T, class Hierarchy>
bool operator==( forest_tree<T, Hierarchy> const& x,
forest_tree<T, Hierarchy> const& y);
template <class T, class Hierarchy>
bool operator!=( forest_tree<T, Hierarchy> const& x,
forest_tree<T, Hierarchy> const& y);
// specialized algorithms:
template <class T, class Hierarchy>
void swap( forest_tree<T, Hierarchy>& x,
forest_tree<T, Hierarchy>& y);
namespace inorder {
template <class T, class Hierarchy>
inorder::iterator<forest_tree<T, Hierarchy>::cursor>
begin(forest_tree<T, Hierarchy>& h);
template <class T, class Hierarchy>
inorder::iterator<forest_tree<T, Hierarchy>::const_cursor>
cbegin(forest_tree<T, Hierarchy> const& h);
} // namespace inorder
} // namespace tr2
} // namespace std
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 f | adaptee cursor b | complexity |
|---|---|---|
| f = f.end() | while (!b.empty()) b = b.end(); | linear |
| ++f | b = (++b).begin(); | constant |
| --f | b = --b.parent(); | as b.parent() |
| !f | while ((!b).parity() == 1); b =
(!b).begin(); |
linear |
explicit forest_tree (hierarchy_type const& = hierarchy_type());
template <class InputCursor>
forest_tree (InputCursor subtree);
forest_tree (forest_tree<T, Hierarchy> const&);
Complexity: The constructor template <class InputCursor> vector(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(InputCursor i = subtree.begin(); i != subtree.end(); ++i) insert(root.end(), *i);
cursor insert(cursor position, value_type const& x = value_type());
template <class InputCursor>
cursor insert(cursor position, InputCursor subtree);
cursor insert_above(cursor position, value_type const& x = value_type());
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( forest_tree<T, Hierarchy>& x,
forest_tree<T, Hierarchy>& y);
Effects: x.swap(y);
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 {
namespace tr2 {
template <class T, class Hierarchy = nary_tree< std::vector<T> > >
class multiway_tree
{
public:
typedef Hierarchy hierarchy_type;
protected:
hierarchy_type h;
public:
// types:
typedef T value_type;
typedef implementation defined cursor;
typedef implementation defined const_cursor;
typedef typename hierarchy_type::pointer pointer;
typedef typename hierarchy_type::const_pointer const_pointer;
typedef typename hierarchy_type::reference reference;
typedef typename hierarchy_type::const_reference const_reference;
typedef typename hierarchy_type::size_type size_type;
typedef typename hierarchy_type::difference_type difference_type;
template <class U> struct rebind {
typedef multiway_tree< U,
typename hierarchy_type::template rebind< implementation defined >::other >
other;
};
// construct/copy/destroy:
explicit multiway_tree (hierarchy_type const& = hierarchy_type());
template <class InputCursor>
multiway_tree (InputCursor subtree);
multiway_tree (multiway_tree<T, Hierarchy> const& x);
~multiway_tree();
multiway_tree<T, Hierarchy>& operator=(
multiway_tree<T, Hierarchy> const& x);
template <class InputCursor>
void assign(InputCursor subtree);
// cursors:
cursor root();
const_cursor croot() const;
cursor shoot();
const_cursor cshoot() const;
cursor inorder_first();
const_cursor inorder_cfirst 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, value_type const& x = value_type());
template <class InputCursor>
cursor insert(cursor position, InputCursor subtree);
void rotate(cursor position);
void swap(multiway_tree<p, Hierarchy>&);
void clear(cursor position);
void clear();
};
template <class T, class Hierarchy>
bool operator==( multiway_tree<T, Hierarchy> const& x,
multiway_tree<T, Hierarchy> const& y);
template <class Tp, class Alloc>
bool operator!=( multiway_tree<T, Hierarchy> const& x,
multiway_tree<T, Hierarchy> const& y);
// specialized algorithms:
template <class T, class Hierarchy>
void swap( multiway_tree<T, Hierarchy>& x,
multiway_tree<T, Hierarchy>& y);
namespace inorder {
template <class T, class Hierarchy>
inorder::iterator<multiway_tree<T, Hierarchy>::cursor>
begin(multiway_tree<T, Hierarchy>& h);
template <class T, class Hierarchy>
inorder::iterator<multiway_tree<T, Hierarchy>::const_cursor>
cbegin(multiway_tree<T, Hierarchy> const& h);
} // namespace inorder
} // namespace tr2
} // namespace std
Types typename Hierarchy::cursor and typename Hierarchy::const_cursor are required to be random access cursors.
typedef implementation defined cursor;
typedef implementation defined const_cursor;
Both cursor and const_cursor have to fulfill the plain cursor requirements ([tr.cursor.flavors]). If typename hierarchy_type::cursor is an ascending random access cursor, cursor and const_cursor are also ascending random access cursors ([tr.ascending.random.access.cursors]); otherwise, they are descending random access cursor ([tr.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 m | adaptee cursor n | complexity |
|---|---|---|
| *m | *((p->begin())[b.parity()]) | constant |
explicit multiway_tree (hierarchy_type const& = hierarchy_type());
template <class InputCursor>
multiway_tree (InputCursor subtree);
multiway_tree (multiway_tree<T, Hierarchy> const& x);
Complexity: The constructor template <class InputCursor> vector(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(InputCursor i = subtree.begin(); i != subtree.end(); ++i) insert(root.end(), *i);
cursor shoot();
const_cursor cshoot() const;
Complexity: constant
cursor inorder_first();
const_cursor inorder_cfirst() const;
Returns: A cursor to the multiway_tree's first element in inorder (see [tr.order.iterators], §4).
Complexity: constant.
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().
cursor insert(cursor position, value_type const& x = value_type());
template <class InputCursor>
cursor insert(cursor position, InputCursor subtree);
cursor insert_above(cursor position, value_type const& x = value_type());
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);
namespace inorder {
template <class T, class Hierarchy>
inorder::iterator<multiway_tree<T, Hierarchy>::cursor>
begin(multiway_tree<T, Hierarchy>& h);
} // namespace inorder
Returns: inorder::iterator<multiway_tree<T, Hierarchy>::cursor>(h.inorder_first()).
Complexity: constant
namespace inorder {
template <class Tp, class Alloc>
inorder::iterator<multiway_tree<Tp, Alloc>::const_cursor>
cbegin(multiway_tree<Tp, Alloc> const& h);
} // namespace inorder
Returns: inorder::iterator<multiway_tree<Tp, Alloc>::const_cursor>(h.inorder_cfirst()).
Complexity: constant
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 <augment>.
namespace std {
namespace tr2 {
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 h;
public:
// types:
typedef T value_type;
typedef implementation defined cursor;
typedef implementation defined const_cursor;
typedef typename hierarchy_type::pointer pointer;
typedef typename hierarchy_type::const_pointer const_pointer;
typedef typename hierarchy_type::reference reference;
typedef typename hierarchy_type::const_reference const_reference;
typedef typename hierarchy_type::size_type size_type;
typedef typename hierarchy_type::difference_type difference_type;
template <class U> struct rebind {
typedef rank_tree< U, typename hierarchy_type::template rebind<U>::other >
other;
};
// construct/copy/destroy:
explicit rank_tree (hierarchy_type const& = hierarchy_type());
template <class InputCursor>
rank_tree (InputCursor subtree);
rank_tree (rank_tree<T, Hierarchy> const& x);
~rank_tree();
rank_tree<T, Hierarchy>& operator=(
rank_tree<T, Hierarchy> const& x);
template <class InputCursor>
void assign(InputCursor subtree);
// cursors:
cursor root();
const_cursor croot() const;
cursor shoot();
const_cursor cshoot() const;
cursor inorder_first();
const_cursor inorder_cfirst const();
cursor rank(size_type n);
const_cursor rank(size_type n) 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, value_type const& x = value_type());
template <class InputCursor>
cursor insert(cursor position, InputCursor subtree);
void rotate(cursor position);
void swap(rank_tree<T, Hierarchy>&);
void clear(cursor position);
void clear();
};
template <class T, class Hierarchy>
bool operator==( rank_tree<T, Hierarchy> const& x,
rank_tree<T, Hierarchy> const& y);
template <class T, class Hier>
bool operator!=( rank_tree<T, Hierarchy> const& x,
rank_tree<T, Hierarchy> const& y);
// specialized algorithms:
template <class T, class Hierarchy>
void swap( rank_tree<T, Hierarchy>& x,
rank_tree<T, Hierarchy>& y);
namespace inorder {
template <class T, class Hierarchy>
inorder::iterator<rank_tree<T, Hierarchy>::cursor>
begin(rank_tree<T, Hierarchy>& h);
template <class Tp, class Hierarchy>
inorder::iterator<rank_tree<T, Hierarchy>::const_cursor>
cbegin(rank_tree<T, Hierarchy> const& h);
} // namespace inorder
} // namespace tr2
} // 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(), which are newly introduced.)
cursor rank(size_type n);
const_cursor rank(size_type n) const;
Returns: A cursor (or const_cursor) to the nth element of the hierarchy in inorder, counting from inorder_first().
Complexity: logarithmic in size().
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 ([lib.container.requirements]), of a sequence ([lib.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 ([tr.hierarchy.bintree.types], §1 and §2): 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. All balancing adaptors and corresponding free functions are found in header <balance>.
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.
namespace std {
namespace tr2 {
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::value_type value_type;
typedef typename hierarchy_type::pointer pointer;
typedef typename hierarchy_type::const_pointer const_pointer;
typedef typename hierarchy_type::reference reference;
typedef typename hierarchy_type::const_reference const_reference;
typedef typename hierarchy_type::size_type size_type;
typedef typename hierarchy_type::difference_type difference_type;
typedef implementation defined iterator;
typedef implementation defined const_iterator;
typedef std::reverse_iterator<iterator> reverse_iterator;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
// construct/copy/destroy:
explicit avl_tree(hierarchy_type const& = hierarchy_type());
explicit avl_tree(size_type n, value_type const& value = value_type(),
hierarchy_type const& = hierarchy_type());
template <class InputIterator>
avl_tree (InputIterator first, InputIterator last,
hierarchy_type const& = hierarchy_type());
avl_tree (avl_tree<T, Hierarchy> const& x);
~avl_tree();
avl_tree<T, Hierarchy>& operator=(
avl_tree<T, Hierarchy> const& x);
template <class InputIterator>
void assign(InputIterator first, InputIterator last);
template <class Size, class T>
void assign(Size n, T const& t = T());
// iterators:
iterator begin();
const_iterator cbegin() const;
iterator end() { return iterator(h.shoot()); }
const_iterator cend() const { return const_iterator(h.cshoot()); }
reverse_iterator rbegin();
const_reverse_iterator crbegin() const;
reverse_iterator rend();
const_reverse_iterator crend() const;
// capacity:
bool empty() const { return h.empty(); }
size_type size() const { return h.size(); }
size_type max_size() const;
void resize(size_type sz, T c = T());
// element access:
reference front();
const_reference front() const;
reference back();
const_reference back() const;
// map operations:
iterator find(const value_type& x);
const_iterator find(const value_type& x) const;
template <class Cmp>
iterator find(const value_type& x, Cmp cmp);
const_iterator find(const value_type& x) const;
size_type count(const value_type& x) const;
template <class Cmp>
size_type count(const value_type& x, Cmp cmp) const;
iterator lower_bound(const value_type& x);
const_iterator lower_bound(const value_type& x) const;
template <class Cmp>
iterator lower_bound(const value_type& x, Cmp cmp);
template <class Cmp>
const_iterator lower_bound(const value_type& x, Cmp cmp) const;
iterator upper_bound(const value_type& x);
const_iterator upper_bound(const value_type& x) const;
template <class Cmp>
iterator upper_bound(const value_type& x, Cmp cmp);
template <class Cmp>
const_iterator upper_bound(const value_type& x, Cmp cmp) const;
pair<iterator,iterator> equal_range(const value_type& x);
pair<const_iterator,const_iterator>
equal_range(const value_type& x) const;
template <class Cmp>
pair<iterator,iterator>
equal_range(const value_type& x, Cmp cmp);
template <class Cmp>
pair<const_iterator,const_iterator>
equal_range(const value_type& x, Cmp cmp) const;
// modifiers:
void push_front(value_type const& x);
void push_back(value_type const& x);
iterator insert(iterator position, value_type const& x = value_type());
void insert(iterator position, size_type n, value_type const& x);
template <class InputIterator>
void insert(iterator position, InputIterator first, InputIterator last);
void pop_front();
void pop_back();
void erase(iterator position);
void erase(iterator first, iterator last);
void swap(avl_tree<Tp, Hierarchy>&);
void clear() { h.clear(); }
};
template <class T, class Hierarchy>
bool operator==( avl_tree<T, Hierarchy> const& x,
avl_tree<T, Hierarchy> const& y);
template <class T, class Hierarchy>
bool operator< ( avl_tree<T, Hierarchy> const& x,
avl_tree<T, Hierarchy> const& y);
template <class T, class Hierarchy>
bool operator!=( avl_tree<T, Hierarchy> const& x,
avl_tree<T, Hierarchy> const& y);
template <class T, class Hierarchy>
bool operator> ( avl_tree<T, Hierarchy> const& x,
avl_tree<T, Hierarchy> const& y);
template <class T, class Hierarchy>
bool operator>=( avl_tree<T, Hierarchy> const& x,
avl_tree<T, Hierarchy> const& y);
template <class T, class Hierarchy>
bool operator<=( avl_tree<T, Hierarchy> const& x,
avl_tree<T, Hierarchy> const& y);
// specialized algorithms:
template <class T, class Hierarchy>
void swap( avl_tree<T, Hierarchy>& x,
avl_tree<T, Hierarchy>& y);
} // namespace tr2
} // namespace std
explicit avl_tree (hierarchy_type const& = hierarchy_type());
template <class InputIterator>
avl_tree (InputIterator first, InputIterator last,
hierarchy_type const& = hierarchy_type());
avl_tree (avl_tree<T, Hierarchy> const& x);
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);
iterator find(const value_type& x);
const_iterator find(const value_type& x) const;
template <class Cmp>
iterator find(const value_type& x, Cmp cmp);
const_iterator find(const value_type& x) const;
size_type count(const value_type& x) const;
template <class Cmp>
size_type count(const value_type& x, Cmp cmp) const;
iterator lower_bound(const value_type& x);
const_iterator lower_bound(const value_type& x) const;
template <class Cmp>
iterator lower_bound(const value_type& x, Cmp cmp);
template <class Cmp>
const_iterator lower_bound(const value_type& x, Cmp cmp) const;
iterator upper_bound(const value_type& x);
const_iterator upper_bound(const value_type& x) const;
template <class Cmp>
iterator upper_bound(const value_type& x, Cmp cmp);
template <class Cmp>
const_iterator upper_bound(const value_type& x, Cmp cmp) const;
pair<iterator,iterator> equal_range(const value_type& x);
pair<const_iterator,const_iterator>
equal_range(const value_type& x) const;
template <class Cmp>
pair<iterator,iterator>
equal_range(const value_type& x, Cmp cmp);
template <class Cmp>
pair<const_iterator,const_iterator>
equal_range(const value_type& x, Cmp cmp) const;
Notes: The find, lower_bound, upper_bound and equal_range member functions each have four versions, differing in whether they return an iterator or a const_iterator, and if they take a cmp function object argument or not (count comes only in the latter two variants, as it returns a size_type, not an iterator). In each case the behavior of the four (two) functions is in principle identical.
Complexity: logarithmic (with the exception of count, which is log(size()) + count(x)
void push_front(value_type const& x);
void push_back(value_type const& x);
iterator insert(iterator position, value_type const& x = value_type());
Complexity: amortized constant
void insert(iterator position, size_type n, value_type const& x);
template <class InputIterator>
void insert(iterator position, InputIterator first, InputIterator last);
Complexity: linear in the number of elements to insert
void pop_front();
void pop_back();
void erase(iterator position);
Complexity: amortized constant
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>& x,
avl_tree<T, Hierarchy>& y);
Effects: x.swap(y);
Add before subclause 24.4, Predefined iterators ([lib.predef.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 either 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 is introduced; 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.emtpy() == true is called 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 ([lib.input.iterators]) and output iterators ([lib.output.iterators]):
| expression | return type | operational semantics | assertion/note pre/post-condition |
|---|---|---|---|
| X::value_type | T | Any non-reference, non-cv-qualified type | compile time |
| X::type | Convertible to cursor_tag, input_iterator_tag, and output_iterator_tag | compile time | |
| X::cursor | Convertible to X | compile time | |
| X::const_cursor | Convertible to const X | compile time |
A class X satisfies the requirements of a descending cursor if, in addition to satisfying the requirements for cursors ([tr.cursor.requirements]) it also conforms to the container requirements ([lib.container.requirements]) with the exception of the following expressions:
| unsupported expression |
|---|
| X::iterator |
| X::const_iterator |
| X::reverse_iterator |
| X::reverse_const_iterator |
| (&a)->~X(); |
| X(a); |
| X u(a); X u = a; |
| a.begin() |
| a.end() |
| a.rbegin() |
| a.rend() |
| a == b |
| a != b |
| a.swap(b) |
| r = a |
| a < b |
| a > b |
| a <= b |
| a >= b |
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 pre/post-condition |
|---|---|---|---|
| X::type | Convertible to descending_cursor_tag | compile time | |
| a.begin() | cursor or const_cursor for constant a | pre: a is non-leaf. | constant |
| a.end() | cursor or const_cursor for constant a | pre: a is non-leaf. | constant |
| a.cbegin() | const_cursor | pre: a is non-leaf. | constant |
| a.cend() | const_cursor | pre: a is non-leaf. | constant |
| a.parity() | size_type | std::distance(b.begin(), a) if b is
a's parent. pre: a is non-on-top. |
Linear in b.size() |
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 ([tr.descending.cursors]) and forward iterators ([lib.forward.iterators]):
| expression | return type | operational semantics | assertion/note pre/post-condition |
|---|---|---|---|
| X::type | Convertible to descending_forward_cursor_tag and forward_iterator_tag | 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 ([tr.descending.forward.cursors]) and bidirectional iterators ([lib.bidirectional.iterators]):
| expression | return type | operational semantics | assertion/note pre/post-condition |
|---|---|---|---|
| X::type | Convertible to descending_bidirectional_cursor_tag and bidirectional_iterator_tag | compile time |
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 ([tr.descending.bidirectional.cursors]) and random access iterators ([lib.random.access.iterators]):
| expression | return type | operational semantics | assertion/note pre/post-condition |
|---|---|---|---|
| X::type | Convertible to descending_random_access_cursor_tag and random_access_iterator_tag | 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 ([tr.descending.cursors]):
| expression | return type | operational semantics | assertion/note pre/post-condition |
|---|---|---|---|
| X::type | Convertible to ascending_cursor_tag | compile time | |
| a.parent() | cursor; const_cursor for a constant a | (Note A) | |
| !r | X& | r = r.parent(); | pre: r is an internal, non-on-top
cursor. post: r is internal. r == s and r is internal and non-on-top implies !r == !s. &r == &!r (Note A) |
Notes: Those entries marked "(Note A)" should 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 ([tr.ascending.cursors]) and descending forward cursors ([tr.descending.forward.cursors]):
| expression | return type | operational semantics | assertion/note pre/post-condition |
|---|---|---|---|
| X::type | Convertible to ascending_forward_cursor_tag | 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 ([tr.ascending.forward.cursors]) and descending bidirectional cursors ([tr.descending.bidirectional.cursors]):
| expression | return type | operational semantics | assertion/note pre/post-condition |
|---|---|---|---|
| X::type | Convertible to ascending_bidirectional_cursor_tag | 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 ([tr.ascending.bidirectional.cursors]) and descending random access cursors ([tr.descending.random.access.cursors]):
| expression | return type | operational semantics | assertion/note pre/post-condition |
|---|---|---|---|
| X::type | Convertible to ascending_random_access_cursor_tag | compile time |
A cursor that satisfies at least the descending cursor requirements ([tr.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 {
namespace tr2 {
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 tr2
} // 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 {
namespace tr2 {
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 tr2
} // namespace std
Cursor tags pick up the notion of iterator tags ([lib.std.iterator.tags]) and extend them by adding information about a given cursor class' descending or ascending traversal capabilities ([tr.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 {
namespace tr2 {
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 tr2
} // namespace std
Append to section introduced with // subclause 24.4, predefined iterators:
namespace std {
namespace tr2 {
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
} // namespace tr2
} // 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 tr2 {
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 tr2
} // 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 ([tr.ascending.forward.cursors]). Additionally, for the template class and operators in namespace inorder, the template parameter Cursor must be a Multiway Cursor ([tr.cursor.flavors]).
Additionally, Cursor shall meet the requirements of a Ascending Bidirectional Cursor ([tr.ascending.bidirectional.cursors]) if the member operator-- (24.4.X.3.7) is referenced in a way that requires instantiation (14.7.1).
explicit iterator(Cursor x);
Effects: Initializes current with x.
Iterator base() const; // explicit
Returns: current
Reference operator*() const;
Returns: *current
Pointer operator->() const;
Returns: &(operator*())
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;
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;
template <class Cursor>
bool operator==(
const iterator<Cursor>& x,
const iterator<Cursor>& y);
Returns: x.current == y.current
template <class Cursor>
bool operator!=(
const iterator<Cursor>& x,
const iterator<Cursor>& y);
Returns: x.current != y.current
// subclause 2.X, non-modifying hierarchy operations
namespace std {
namespace tr2 {
namespace preorder {
template <class Hierarchy>
iterator<typename Hierarchy::cursor>
begin(Hierarchy& 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>
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>
cbegin(Hierarchy const& h);
template <class Hierarchy>
iterator<typename Hierarchy::cursor>
end(Hierarchy& 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>
cbegin(MultiwayHierarchy const& m);
template <class MultiwayHierarchy>
iterator<typename MultiwayHierarchy::cursor>
end(MultiwayHierarchy& m);
template <class MultiwayHierarchy>
iterator<typename MultiwayHierarchy::const_cursor>
cend(MultiwayHierarchy const& m);
} // namespace inorder
} // namespace tr2
} // namespace std
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.
If an algorithm's template parameter is Hierarchy, the actual template argument shall satisfy the requirements of a hierarchy ([tr.hierarchy.req]). If an algorithm's template parameter is MultiwayHierarchy, the actual template argument shall satisfy the requirements of a multiway hierarchy ([tr.hierarchy.multiway]).
namespace std {
namespace tr2 {
namespace preorder {
template <class Hierarchy>
iterator<typename Hierarchy::cursor>
begin(Hierarchy& h);
template <class Hierarchy>
iterator<typename Hierarchy::const_cursor>
cbegin(Hierarchy const& h);
} // namespace preorder
} // namespace tr2
} // namespace std
Returns: An iterator pointing to the first element of h in preorder.
Complexity: constant
namespace std {
namespace tr2 {
namespace preorder {
template <class Hierarchy>
iterator<typename Hierarchy::cursor>
end(Hierarchy& h);
template <class Hierarchy>
iterator<typename Hierarchy::const_cursor>
cend(Hierarchy const& h);
} // namespace preorder
} // namespace tr2
} // namespace std
Returns: An iterator pointing one position past the last element of h in preorder.
Complexity: linear
namespace std {
namespace tr2 {
namespace postorder {
template <class Hierarchy>
iterator<typename Hierarchy::cursor>
begin(Hierarchy& h);
template <class Hierarchy>
iterator<typename Hierarchy::const_cursor>
cbegin(Hierarchy const& h);
} // namespace postorder
} // namespace tr2
} // namespace std
Returns: An iterator pointing to the first element of h in postorder.
Complexity: linear
namespace std {
namespace tr2 {
namespace postorder {
template <class Hierarchy>
iterator<typename Hierarchy::cursor>
end(Hierarchy& h);
template <class Hierarchy>
iterator<typename Hierarchy::const_cursor>
cend(Hierarchy const& h);
} // namespace postorder
} // namespace tr2
} // namespace std
Returns: An iterator pointing one position past the last element of h in postorder.
Complexity: constant
namespace std {
namespace tr2 {
namespace inorder {
template <class MultiwayHierarchy>
iterator<typename MultiwayHierarchy::cursor>
begin(MultiwayHierarchy& m);
template <class MultiwayHierarchy>
iterator<typename MultiwayHierarchy::const_cursor>
cbegin(MultiwayHierarchy const& m);
} // namespace inorder
} // namespace tr2
} // namespace std
Returns: An iterator pointing to the first element of h in inorder.
Complexity: linear
namespace std {
namespace tr2 {
namespace inorder {
template <class MultiwayHierarchy>
iterator<typename MultiwayHierarchy::cursor>
end(MultiwayHierarchy& m);
template <class MultiwayHierarchy>
iterator<typename MultiwayHierarchy::const_cursor>
cend(MultiwayHierarchy const& m);
} // namespace inorder
} // namespace tr2
} // namespace std
Returns: An iterator pointing one position past the last element of h in inorder.
Complexity: linear