Hierarchical Data Structures and Related Concepts for the C++ Standard Library

Bernhard Reiter

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)


Table of Contents
1. Hierarchical Data Structures and Related Concepts for the C++ Standard Library
1.1. Introduction
1.2. Motivation and Scope
1.2.1. Why is this important?
1.2.2. What kinds of problems does it address, and what kinds of programmers is it intended to support?
1.2.3. Is it based on existing practice?
1.2.4. Is there a reference implementation?
1.3. Impact on the Standard
1.3.1. What does it depend on, and what depends on it?
1.3.2. Is it a pure extension, or does it require changes to standard components?
1.3.3. Can it be implemented using today's compilers, or does it require language features that will only be available as part of C++11
1.4. Important Design Decisions
1.4.1. Why did you choose the specific design that you did?
1.4.2. What alternatives did you consider, and what are the tradeoffs?
1.4.3. What are the consequences of your choices, for users and implementors?
1.4.4. What decisions are left up to implementors?
1.4.5. If there are any similar libraries in use, how do their design decisions compare to yours?
1.5. Future Directions
2. Proposed Text
23. Container library
23.7. Hierarchy containers
23.7.1. Hierarchy containers requirements
23.7.1.1. General hierarchy requirements
23.7.2. Plain hierarchies
23.7.3. Multiway hierarchies
23.7.4. Trees
23.7.4.1. Class template binary_tree
23.7.4.2. Class template nary_tree
23.7.4.3. Hierarchy adaptors
24. Iterators library
24.3. Headers <iterator> synopsis
24.7. Cursors
24.7.1. Cursor requirements
24.7.1.1. Descending Cursor
24.7.1.2. Descending Forward Cursor
24.7.1.3. Descending Bidirectional Cursor
24.7.1.4. Descending Random Access Cursor
24.7.1.5. Ascending Cursor
24.7.1.6. Ascending Forward Cursor
24.7.1.7. Ascending Bidirectional Cursor
24.7.1.8. Ascending Random Access Cursor
24.7.2. Cursor flavors
24.7.3. Header <cursor> synopsis
24.7.4. Cursor primitives
24.7.4.1. Cursor traits
24.7.4.2. Basic cursor
24.7.4.3. Standard cursor tags
24.8. Linear order traversal iterators
24.8.1. Class template iterator
24.8.2. Linear order iterator requirements
24.8.3. inorder::iterator operations
24.8.3.1. inorder::iterator constructor
24.8.3.2. Conversion
24.8.3.3. operator*
24.8.3.4. operator->
24.8.3.5. operator++
24.8.3.6. operator--
24.8.3.7. operator==
24.8.3.8. operator!=
25. Algorithms library
25.3. Non-modifying hierarchy algorithms
25.3.1. Non-modifying hierarchy preorder range algorithms
25.3.1.1. Preorder begin
25.3.1.2. Preorder end
25.3.2. Non-modifying hierarchy postorder range algorithms
25.3.2.1. Postorder begin
25.3.2.2. Postorder end
25.3.3. Non-modifying hierarchy inorder range algorithms
25.3.3.1. Inorder begin
25.3.3.2. Inorder end
3. References

Bernhard Reiter and René Rivera

Document No.

WG21/N3700

Supercedes

WG21/N2101=J16/06-0171

Date

2013-06-22

Project

Programming Language C++, Library Working Group

Reply to

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 of trees

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.

Augmentors/balancers as policies

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.

Note

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:

Table 1. Container requirements that are not required for hierarchy containers

unsupported expression

X::iterator

X::const_iterator

X::difference_type

a.begin()

a.end()

a.cbegin()

a.cend()

a == b

a != b

X::reverse_iterator

X::const_reverse_iterator

a.rbegin()

a.rend()

a.crbegin()

a.crend()

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.

Table 2. Hierarchy requirements (in addition to container)

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()

cursor for mutable a;
const_cursor for constant a

 

constant

a.croot()

const_cursor

 

constant

a.shoot()

cursor for mutable a;
const_cursor for constant a

 

(Note A)

a.cshoot()

const_cursor

 

(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)" 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.

Table 3. Mutable hierarchy requirements

expression

return type

assertion/note
pre/post-condition

complexity

a.emplace(p, args);

cursor

Requires: T is EmplaceConstructable into X from args, T is also MoveInsertable into X and MoveAssignable.
Effects: Inserts an object of type T constructed with std::forward<Args>(args)... before p.

(Note A)

a.insert(p,t)

cursor

Requires: T shall be CopyInsertable into X. Effects: Inserts a copy of t before p.

(Note A)

a.insert(p,rv)

cursor

Requires: T shall be MoveInsertable into X. Effects: Inserts a copy of rv before p.

(Note A)

a.clear(q)

void

Effects: Deletes the subtree of q and the element q points to.
pre: q is dereferenceable.

Shall 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

Effects: while (a.size()) clear(a.begin());
post: a.size() == 0

(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:

Table 4. Plain hierarchy requirements

expression

return type

assertion/note
pre/post-condition

complexity

a.insert(p,c)

cursor

Requires: T shall be CopyInsertable into X
Effects: Inserts a copy of the subtree of c before p.
pre: c is dereferenceable.

Shall be at worst linear in the number of elements in the subtree of c plus the distance to p's parent's end().

a.insert_above(p,t)

cursor

Requires: T shall be CopyInsertable into X
Effects: Inserts a copy of t as a child of p's parent; the new child becomes new parent of p and its siblings.
pre: p is dereferenceable.

Linear in the number p's siblings.

a.insert_above(p,rv)

cursor

Requires: T shall be MoveInsertable into X. Effects: Inserts a copy of rv as a child of p's parent; the new child becomes the parent of p and its siblings.
pre: p is dereferenceable.

Linear in 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 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.

Table 5. Multiway hierarchy requirements

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.

Shall 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>, 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
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);
cursor        shoot();
const_cursor  shoot() const;
const_cursor  cshoot() const;

Complexity: constant

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);

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
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);
cursor        shoot() noexcept;
const_cursor  shoot() const noexcept;
const_cursor  cshoot() const noexcept;

Complexity: constant

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().

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

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
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):

Table 6. forest_tree/binary tree cursor operational semantics correspondences

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


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);
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.

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 {
  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.

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):

Table 7. Multiway/nary tree cursor operational semantics correspondences

adaptor cursor m

adaptee cursor n

complexity

*m

*((p->begin())[b.parity()])

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);
cursor        shoot();
const_cursor  shoot() const;
const_cursor  cshoot() const;

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, 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
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.)

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().

Note

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
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);

Note

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

Note

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]):

Table 8.  Cursor requirements (in addition to input and 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 ([cursor.requirements]) it also conforms to the container requirements ([container.requirements]) with the exception of the following expressions:

Table 9.  Container requirements that are not supported

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:

Table 10.  Descending cursor requirements (in addition to cursor)

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 ([descending.cursors]) and forward iterators ([forward.iterators]):

Table 11.  Descending forward cursor requirements (in addition to descending cursors and 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 ([descending.forward.cursors]) and bidirectional iterators ([bidirectional.iterators]):

Table 12.  Descending bidirectional cursor requirements (in addition to forward descending cursors and 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


Note

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]):

Table 13.  Descending random access cursor requirements (in addition to descending bidirectional cursors and 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 ([descending.cursors]):

Table 14.  Ascending cursor requirements (in addition to 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)" 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]):

Table 15.  Ascending forward cursor requirements (in addition to ascending cursors and 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 ([ascending.forward.cursors]) and descending bidirectional cursors ([descending.bidirectional.cursors]):

Table 16.  Ascending bidirectional cursor requirements (in addition to ascending forward cursors and 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 ([ascending.bidirectional.cursors]) and descending random access cursors ([descending.random.access.cursors]):

Table 17.  Ascending random access cursor requirements (in addition to ascending bidirectional cursors and 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 ([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.

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

Note

Append to paragraph 2, Header <iterator> synopsis, after // 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

Note

[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)

Note

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.

Note

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]).

Note

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

References
austern

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

Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. Introduction to Algorithms. Second Edition (MIT Press, 2001)

dreizin

Dreizin, Vladimir; Kosnik, Benjamin; Tavory, Ami. Policy-Based Data Structures, http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/

ekman

Ekman, Rasmus. Structured Associative Containers, http://www.abc.se/~re/code/tst/tst_docs/index.html

gottschlich

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

Haas, Mitchell. Tree Container Library, http://www.datasoftsolutions.net/tree_container_library/overview.php

karas

Karas, Walt. C++ AVL Tree Template, http://wkaras.webs.com/gen_cpp/avl_tree.html

knuth97

Knuth, Donald E. The Art of Computer Programming. Volume 1: Fundamental Algorithms. Third Edition (Reading, Massachusetts: Addison-Wesley, 1997)

knuth98

Knuth, Donald E. The Art of Computer Programming. Volume 3: Sorting and Searching. Second Edition (Reading, Massachusetts: Addison-Wesley, 1998)

parent

Parent, Sean et al. forest, http://stlab.adobe.com/group__forest__related.html

peeters

Peeters, Kasper. tree.hh: an STL-like C++ tree class, http://tree.phi-sci.com/

rivera

Rivera, René. rank_tree.h, http://redshift-software.com/sites/redshift-software.com/files/grafik/rank_tree.h