A way to learn more when you study

"You can truly understand a topic when you have to teach it." Many teachers have heard and agreed with this statement. The Feynman Technique for studying is based on this advice. Check it out!

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.

Passwords: Should they die?

Source: Commit Strip via http://www.codeproject.com 

And check out the survey posted on networkworld.

Why Walls and Mirrors:C++ uses templates.

Our data structures book with C++ (Data Abstraction and Problem Solving with C++: Walls and Mirrors 7th ed.) covers and uses templates from the beginning. We do so in a simple straightforward way. The code that we present enables a student to create a data structure that stores data of any one data type (all strings, all Car objects, and so on). As we state in the book, "Templates enable the programmer to separate the functionality of an implementation from the type of data used in the class." We feel that introducing and using templates as we do is not difficult. 

Code that creates the same kinds of data structures as just described and that does not use templates is inflexible, since it is hardwired for one particular data type. Changing the type of data to be stored would be an error-prone process and take a substantial amount of work. Such code would not look like the code that a student is likely to see in the standard libraries or in the real world.

Inheritance and Base Class Constructors in C++

(An update of a post made on Jan 16, 2013.)

In the 7th edition of Walls & Mirrors: C++, C++ Interlude 1 describes three types of boxes for a video game:

• Plain box—a plain old box that holds only one item.

• Toy box—a box that has color and holds only one item.

• Magic box—a box that holds only one item, but magically changes it to the first item that was ever stored in the box.

The three classes of boxes are related by inheritance: PlainBox is the base class, and both ToyBox and MagicBox are derived from PlainBox. For simplicity, let’s just focus on the classes PlainBox and ToyBox.

Suppose that we define PlainBox as in Listing C1-3:

/** @file PlainBox.h */

#ifndef PLAIN_BOX_

#define PLAIN_BOX_

#include "BoxInterface.h"

template<class ItemType>

class PlainBox

{

private:

   ItemType item;

    

public:

   PlainBox();

   PlainBox(const ItemType& theItem);

   virtual void setItem(const ItemType& theItem);

   virtual ItemType getItem() const;

};

#include "PlainBox.cpp"

#endif

This class has a simple implementation, as you can see next and in Listing C1-4:

/** @file PlainBox.cpp */

template<class ItemType>

PlainBox::PlainBox()

{

   std::cout << "PlainBox() called" << std::endl;

} // end default constructor

template<class ItemType>

PlainBox::PlainBox(const ItemType& theItem) : item(theItem)

{

   std::cout << "PlainBox(theItem) called" << std::endl;

} // end constructor

template<class ItemType>

void PlainBox::setItem(const ItemType& theItem)

{

   item = theItem;

} // end setItem

template<class ItemType>

ItemType PlainBox::getItem() const

{

   return item;

} // end getItem

We included cout statements in the constructors so we could tell when they are called.

Now let’s derive the class ToyBox from PlainBox. An instance of ToyBox is an enhanced PlainBox object that has a color. We can write the header file for ToyBox as in Listing C1-5:

/* @file ToyBox.h */

#ifndef TOYBOX_

#define TOYBOX_

#include "PlainBox.h"

enum Color {BLACK, RED, BLUE, GREEN, YELLOW, WHITE};

template<class ItemType>

class ToyBox : public PlainBox

{

private:

   Color boxColor;

public:

   ToyBox();

   ToyBox(const Color& theColor);

   ToyBox(const ItemType& theItem, const Color& theColor);

   Color getColor() const;

}; // end ToyBox

#include "ToyBox.cpp"

#endif

Although we could provide the class with a setColor method, we choose to prevent the client from altering the color of these boxes. In particular, a ToyBox object created by the default constructor will have a default color that cannot be changed.

The constructors of ToyBox are the focus of our discussion here, so let’s review how the constructors of a derived class relate to the constructors of its base class in C++:

• The derived class does not inherit the base class constructors.

• Each derived class constructor can, and should, call a base class constructor.

• If a derived class constructor does not explicitly call a base class constructor, C++ will call the base class default constructor for you. 

For example, the definition of ToyBox’s default constructor in Listing C1-6 is

template<class ItemType>

ToyBox::ToyBox() : boxColor(BLACK)

{

}  // end default constructor

This constructor implicitly calls PlainBox’s default constructor as its first step before giving a value to boxColor. The same is true of ToyBox’s second constructor:

template<class ItemType>

ToyBox::ToyBox(const Color& theColor) : boxColor(theColor) 

{

}  // end constructor

For either of these two constructors, we could explicitly call PlainBox’s default constructor by using an initializer as follows:

template<class ItemType>

ToyBox::ToyBox() : PlainBox(), boxColor(BLACK)

{

}  // end default constructor

template<class ItemType>

ToyBox::ToyBox(const Color& theColor) : PlainBox(), boxColor(theColor)

{

}  // end constructor

In this case,

• If the C++ compiler detects an initializer call to a base class constructor, it does not add its own call to such a constructor.

There is another way for us to call a base class constructor that you should NOT use. For example, we could define ToyBox’s default constructor as

template<class ItemType>

ToyBox::ToyBox() : boxColor(BLACK)

{

   PlainBox();

}  // end default constructor

Although this will work, the compiler will insert its own call to PlainBox’s default constructor, because of our previous bulleted rule. We can restate this rule as

• If the C++ compiler does not detect an initializer call to a base class constructor, it adds its own call to the base class’s default constructor.

If you create an instance of ToyBox using the previous constructor, you will see the result of two executions of the cout statement in PlainBox’s default constructor.

Finally, let’s define ToyBox’s third constructor, which sets both the item and color of a ToyBox object. We can call setItem to set the item:

template<class ItemType>

ToyBoxTry::ToyBoxTry(const ItemType& theItem, const Color& theColor): boxColor(theColor) 

{

   setItem(theItem);

}  // end constructor

Or we could use an initializer to call PlainBox’s second constructor:

template<class ItemType>

ToyBox::ToyBox(const ItemType& theItem, const Color& theColor)  

                : PlainBox(theItem), boxColor(theColor)

{

}  // end constructor

In the first case, PlainBox’s default constructor is called implicitly. In the second case, PlainBox’s second constructor is called explicitly by the initializer, so the compiler does not insert a call to PlainBox’s default constructor.

To summarize, we can define the implementation file for ToyBox, shown in Listing C1-6:

/* @file ToyBox.cpp */

#include “ToyBox.h”

template<class ItemType>

ToyBox::ToyBox() : boxColor(BLACK) 

{

   // Implicit call to PlainBox's default constructor

}  // end default constructor

template<class ItemType>

ToyBox::ToyBox(const Color& theColor) : boxColor(theColor)

{

   // Implicit call to PlainBox's default constructor

}  // end constructor

template<class ItemType>

ToyBox::ToyBox(const ItemType& theItem, const Color& theColor)

                : PlainBox(theItem), boxColor(theColor)

{

   // No call to PlainBox's default constructor

}  // end constructor

template<class ItemType>

Color ToyBox::getColor() const

{

   return boxColor;

}  // end getColor

Walls and Mirrors, 6th ed., receives the 2016 McGuffey Longevity Award

On Friday June 24, my co-author and I were honored to have the 6th edition of Data Abstraction & Problem Solving: Walls and Mirrors receive the McGuffey Longevity Award from the Textbook & Academic Authors Association at their 29th annual conference, which took place in San Antonio, Texas. This award honors textbooks whose "excellence has been demonstrated over time." Indeed, the first edition of this book was published in 1995. Shortly after we learned of this honor, our 7th edition was released!

I am both excited and honored to have the 6th edition of Data Abstraction & Problem Solving with C++: Walls and Mirrors receive the 2016 TAA McGuffey Longevity Award. I share this honor with my co-author for the sixth and seventh editions, Timothy Henry, all of the people who have helped to improve the book over the course of its long life, and everyone at Pearson Education. —Frank M. Carrano

I have been incredibility fortunate to work on this textbook with Frank, and I’m grateful for his insights and guidance and for the support of the Pearson team. This recognition honors the tremendous amount work required to keep the material current and relevant. —Timothy M. Henry

Ladybug Photography by Bekky Murphy

Platform Change

I am changing platforms from Wordpress to Blogger, and so have moved from makingitreal.com to makingCSreal.com. Nothing against Wordpress, but keeping it updated on my university's server was tedious. Eventually, I'll move the more interesting posts—including my interviews with former students—from my old blog to this one. More to come!