bslstl_mapcomparator

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::MapComparator: comparator for TreeNode objects and key objects

See also

bslstl_map, bslstl_treenode, bslalg_rbtreeutil

Description

This component provides a functor adapter, MapComparator, that adapts a parameterized COMPARATOR comparing objects of a parameterized KEY type into a functor comparing a object of KEY type with objects of TreeNode type holding a bsl::pair<KEY, VALUE> object. Note that this functor was designed to be supplied to functions in bslalg::RbTreeUtil, primarily for the purpose of implementing a map container using the utilities defined in bslalg::RbTreeUtil.

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<bsl::pair<int, int> > > Alloc;
 
bslma::TestAllocator oa;
Alloc allocator(&oa);
 
enum { NUM_NODES = 5 };
 
bslstl::TreeNode<bsl::pair<int, int> >* nodes[NUM_NODES];
 
typedef bsl::allocator_traits<Alloc>  AllocTraits;
 
for (int i = 0; i < NUM_NODES; ++i) {
    nodes[i] = AllocTraits::allocate(allocator, 1);
    AllocTraits::construct(allocator, &nodes[i]->value(),
                           i, 2*i);
}

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

MapComparator<int, 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().first);
 
    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()) {
    const TreeNode<bsl::pair<int, int> > *node =
    static_cast<const TreeNode<bsl::pair<int, int> >*>(nodeIterator);
    printf("Node value: (%d, %d)\n",
           node->value().first, node->value().second);
    nodeIterator = bslalg::RbTreeUtil::next(nodeIterator);
}

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

for (int i = 0; i < NUM_NODES; ++i) {
    AllocTraits::destroy(allocator, &nodes[i]->value());
    AllocTraits::deallocate(allocator, nodes[i], 1);
}

Finally, we observe the console output:

Node value: (0, 0)
Node value: (1, 2)
Node value: (2, 4)
Node value: (3, 6)
Node value: (4, 8)