bslstl_setcomparator

Detailed Description

Outline

• Purpose
• Classes
• Description
  • Usage
    • Example 1: Create a Simple Tree of TreeNode Objects

Purpose

Provide a comparator for TreeNode objects and a lookup key.

Classes

• bslstl::SetComparator: comparator for TreeNode objects and key objects

See also

bslstl_set, bslstl_treenode, bslalg_rbtreeutil

Description

This component provides a functor adapter, SetComparator, that adapts a parameterized COMPARATOR comparing objects of a parameterized KEY type into a functor comparing a object of KEY type with a object of bslstl::TreeNode type holding a object of KEY type. Note that this functor was designed to be supplied to functions in bslalg::RbTreeUtil primarily for the purpose of implementing a set container.

Usage

This section illustrates intended use of this component.

Example 1: Create a Simple Tree of TreeNode Objects

Suppose that we want to create a tree of TreeNode objects arranged according to a functor that we supply.

First, we create an array of bslstl::TreeNode objects, each holding a pair of integers:

typedef bsl::allocator<TreeNode<int> > Alloc;
 
bslma::TestAllocator oa;
Alloc allocator(&oa);
 
enum { NUM_NODES = 5 };
 
TreeNode<int>*       nodes[NUM_NODES];
 
for (int i = 0; i < NUM_NODES; ++i) {
    nodes[i] = allocator.allocate(1);
    nodes[i]->value() = i;
}

Then, we define a SetComparator object, comparator, for comparing bslstl::TreeNode<int> objects with integers.

SetComparator<int, std::less<int> > comparator;

Now, we can use the functions in bslalg::RbTreeUtil to arrange our tree:

bslalg::RbTreeAnchor tree;
 
for (int i = 0; i < NUM_NODES; ++i) {
    int comparisonResult;
    bslalg::RbTreeNode *insertLocation =
        bslalg::RbTreeUtil::findUniqueInsertLocation(
            &comparisonResult,
            &tree,
            comparator,
            nodes[i]->value());
 
    assert(0 != comparisonResult);
 
    bslalg::RbTreeUtil::insertAt(&tree,
                                 insertLocation,
                                 comparisonResult < 0,
                                 nodes[i]);
}
 
assert(5 == tree.numNodes());

Then, we use bslalg::RbTreeUtil::next() to navigate the elements of the tree, printing their values:

const bslalg::RbTreeNode *nodeIterator = tree.firstNode();
 
while (nodeIterator != tree.sentinel()) {
    printf("Node value: %d\n",
           static_cast<const TreeNode<int> *>(nodeIterator)->value());
    nodeIterator = bslalg::RbTreeUtil::next(nodeIterator);
}

Next, we destroy and deallocate each of the bslstl::TreeNode objects:

for (int i = 0; i < NUM_NODES; ++i) {
    allocator.deallocate(nodes[i], 1);
}

Finally, we observe the console output:

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