Component bslstl_setcomparator [Package bslstl]

Provide a comparator for TreeNode objects and a lookup key. More...

Namespaces
namespace	bslstl

---

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:

Component bslstl_set, Component bslstl_treenode, Component 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