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.
