bslstl_treeiterator

Detailed Description

Outline

• Purpose
• Classes
• Description
  • Usage
    • Example 1: Navigating a Tree Using TreeIterator

Purpose

Provide an STL compliant iterator for a tree of TreeNode objects.

Classes

• bslstl::TreeIterator: an STL compliant bidirectional binary tree iterator

See also

bslstl_treenode, bslalg_rbtreeutil, bslstl_map

Description

This component provides an STL-compliant bidirectional iterator over a binary tree of bslstl::TreeNode objects. The requirements of a bidirectional STL iterator are outlined in the C++11 standard in section [24.2.6] under the tag [bidirectional.iterators]. A TreeIterator object is parameterized on VALUE, NODE, and DIFFERENCE_TYPE. The parameterized VALUE indicates the type of the value value to which this iterator provides a references, and may be const-qualified for const-iterators. The parameterized NODE indicates the type of the node objects in this tree. Note that NODE is not necessarily TreeNode<VALUE> as VALUE may be const-qualified. Finally, the parameterized DIFFERENCE_TYPE determines the, standard required, difference_type for the iterator. NODE must derives from bslalg::RbTreeNode, and contains a value method that returns a reference providing modifiable access to a type that is convertible to the parameterized VALUE (e.g., a bslstl::TreeNode object).

Usage

In this section we show intended use of this component.

Example 1: Navigating a Tree Using TreeIterator

In the following example we create a simple tree and then use a TreeIterator to navigate its elements.

First, we define a type IntNode for the nodes of our tree. IntNode inherits from bslalg::RbTreeNode (allowing it to be operated on by bslalg::RbTreeUtil), and supplies an integer payload:

class IntNode : public bslalg::RbTreeNode {
    // DATA
    int d_value;  // actual value represented by the node
 
  public:
    // MANIPULATORS
int& value() { return d_value; }
    // Return a reference providing modifiable access to the 'value' of
    // this object.
 
// ACCESSORS
const int& value() const { return d_value; }
    // Return a reference providing non-modifiable access to the
    // 'value' of this object.
};

Then, we define a comparison function for IntNode objects. This type is designed to be supplied to functions in bslalg::RbTreeUtil:

class IntNodeComparator {
  public:
    // CREATORS
    IntNodeComparator() {}
        // Create a node-value comparator.
 
    // ACCESSORS
    bool operator()(const bslalg::RbTreeNode& node, int value) const {
        return static_cast<const IntNode&>(node).value() < value;
    }
 
    bool operator()(int value, const bslalg::RbTreeNode& node) const {
       return value < static_cast<const IntNode&>(node).value();
    }
};

Next, we define the signature of the example function where we will navigate a tree using a TreeIterator:

void exampleTreeNavigationFunction()
{

Then, we define a bslalg::RbTreeAnchor object to hold our tree, and a series of nodes that we will use to populate the tree:

    enum { NUM_NODES = 5 };
 
    bslalg::RbTreeAnchor tree;
    IntNode              nodes[NUM_NODES];

Next, we assign values to each of the nodes and insert them into tree using bslalg::RbTreeUtil, supplying the insert function an instance of the comparator we defined earlier:

    for (int i = 0; i < NUM_NODES; ++i) {
        nodes[i].value() = i;
        bslalg::RbTreeUtil::insert(&tree, IntNodeComparator(), &nodes[i]);
    }
 
    assert(5 == tree.numNodes());

Then, we create a type alias for a TreeIterator providing non-modifiable access to elements in the tree. Note that in this instance, the iterator must provide non-modifiable access as modifying the key value for a node would invalidate ordering of the binary search tree:

    typedef TreeIterator<const int, IntNode, std::ptrdiff_t>
                                                         ConstTreeIterator;

Now, we create an instance of the TreeIterator and use it to navigate the elements of tree, printing their values to the console:

    ConstTreeIterator iterator(tree.firstNode());
    ConstTreeIterator endIterator(tree.sentinel());
    for (; iterator != endIterator; ++iterator) {
        printf("Node value: %d\n", *iterator);
    }
}

Finally, we observe the following console output:

Node value: 0
Node value: 1
Node value: 2
Node value: 3
Node value: 4