Tree traversals and C++11 lambda functions

One of our readers of Walls and Mirrors 7th edition had a problem with the traversal operation for TreeDictionary, which is described in section 18.2.2 of Chapter 18 (page 559). My co-author, Tim Henry, fielded the question, and I’m happy to share his response with you. The problem involves the data type of the traversal’s parameter, and the solution involves lambda functions, a feature of C++11 but one that we do not cover in the current edition of our book.

PROBLEM:

Recall that TreeDictionary stores its key-value entries in a binary search tree. The traversal operation is declared as follows:

/** Traverses the entries in this dictionary in sorted search-key order

    and calls a given client function once for the value in each entry. */

void TreeDictionaryValueType>::traverse(void visit(ValueType&)) const;

This function has a single parameter, which is a function whose only parameter is of type ValueType.

Our BinarySearchTree, as described in Chapter 16, stores entries of type ItemType, and declares the operation inorderTraverse as

void BinarySearchTree::inorderTraverse(void visit(ItemType&)) const;

TreeDictionary stores key-value pairs as objects of type Entry into the binary search tree entryTree. When you call TreeDictionary::traverse, the visit function you pass to it expects an argument of type ValueType. But when TreeDictionary::traverse calls BinarySearchTree::inorderTraverse using the statement

entryTree.inorderTraverse(visit);

visit expects an argument of type Entry. Therefore, the wrong type of argument is passed, and we get a compilation error.

GOAL: 

Find a way to “convert” visit into a function whose parameter is of type Entry  so we can pass it to inorderTraverse. Maybe a function something like this:

void someFunction(EntryValueType>& someEntry)

{

   auto someItem = someEntry.getItem(); // Must have an address for someItem

   visit(someItem);

}

But how do we give the function access to visit without changing its signature?

SOLUTION:

Lambda functions! Here is the new implementation for TreeDictionary::traverse:

TreeDictionary::traverse(void visit(ValueType&)) const

{

   auto treeVisit = [=](EntryValueType>& someEntry)

   {

      auto someItem = someEntry.getItem();

      visit(someItem);

   };

   entryTree.inorderTraverse(treeVisit);

}

The meaning of the previous lambda syntax follows:

[] means a lambda definition will follow. 

Only [] indicates to not “capture” or access local variables from the parent local environment. 

[&] means to access local variables as pass-by-reference. (This works for our scenario also.)

[=] means to access local variables as pass-by-copy (value). 

After the square brackets is the parameter list for the lambda function. In our case, it is the parameter type our tree needs: 

(EntryValueType>& someEntry)

Then we have the function implementation inside a pair of braces { } followed by a semicolon.

This works when the lambda function does not capture any local variables. 

BUT . . . 

We need to capture the local variable/parameter visit.

So we must use a more formal definition for the function parameters in the tree classes. (We could do this in TreeDictionary also, but it works without that change).

In BinaryTreeInterface.h, add:

#include

Then in the tree files

BinaryTreeInterface.h

BinaryNodeTree.h

BinaryNodeTree.cpp

BinarySearchTree.h

BinarySearchTree.cpp

change the signature of inorderTraverse so that it has the following parameter in red:

inorderTraverse(std::function visit)

This change relaxes some restrictions on how the lambda function can be passed as an argument. 

In BinaryNodeTree.h and BinaryNodeTree.cpp, you should also change the protected function inorder:

void inorder(std::function visit, 

                   std::shared_ptr> treePtr) const;

Make analogous changes to inorderTraverse and postorderTraverse.