Component bslstl_mapcomparator [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::MapComparator

comparator for TreeNode objects and key objects

See also:

Component bslstl_map, Component bslstl_treenode, Component 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)