private and public functions

Question

I'm trying to teach myself about classes in C++, and I'm running into a bit of a stumbling block, which I can't seem to clear up. I was hoping someone might be able to point me in the correct direction.

I decided to construct a small Tree class, which constructs a new BST. I want to be able to call certain methods on my object like so:

int main() {
  Tree<int> tree1;

  tree1.insert(5);

  int treeMin = tree1.minValue();
  int treeMax = tree1.maxValue();

  tree1.printTree();
}

Right now, in order to call these functions, I am defining both public and private functions so that you don't call function in a redundant manner. for instance:

(what I'm trying to avoid)

int main() {
  Tree<int> tree1;

  tree1.insert(tree1, 5);

  int treeMin = tree1.minValue(tree1);
  int treeMax = tree1.maxValue(tree1);

  tree1.printTree(tree1);
}

In order to do avoid having this redundancy, I am defining a public and private version of the same function. In this way, the public functions call their private counterparts.

template<class T>
class Tree {
private:
  treeNode<T>* root;
  treeNode<T>* newNode(T data);
  void insert(treeNode<T>*& root, T data);
  int minValue(treeNode<T>*& root);
  int maxValue(treeNode<T>*& root);
  void printTree(treeNode<T>*& root);

public:
  Tree();
  ~Tree();
  void insert(T data);
  int minValue();
  int maxValue();
  void printTree();
};

And then, as an example:

template<class T>
int Tree<T>::minValue() { minValue(root); }

template<class T>
int Tree<T>::minValue(treeNode<T>*& root) {
  if (root == NULL) { return 0; }
  if (root->left == NULL) { return root->data; }
  else { minValue(root->left); }
}

So, my question is: If I'm writing my functions recursively, I understand that I need to declare a private function that accepts an argument, but is this considered a bad style? Is this sloppy?

Thanks for your help!

Solution

The private member functions in your code are only a needless complication. I would just move their code to the public member functions: less code, more clean code, less indirection so more directly grokable code, all nice. For some of them you might support reuse by making them free functions in a details namespace, but I think that would be premature generalization, expending effort on possible reuse that probably won't take place.

Example code at end of answer.

---

Re another design issue, declaring

int minValue();
int maxValue();

precludes calling these member functions on a const object. Instead do

int minValue() const;
int maxValue() const;

---

A third issue, it's generally a Really Bad Idea™ to do i/o in a non-i/o class. If you print the tree to standard output, how would you use the class in a GUI program? So, instead of

void printTree();

do e.g.

ostream& operator<<( ostream& stream ) const;

or e.g.

string toString() const;

---

A fourth issue, you need to take charge of copying – read up on the “rule of three” and the “rule of zero”.

The simplest way to do that is to replace

treeNode<T>* root;

with

unique_ptr< treeNode< T > > root;

where unique_ptr is std::unique_ptr.

Alternatively declare at least a copy constructor and a copy assignment operator, or inherit from a “non-copyable” class. To make the class effectively non-copyable, you can make these operators private or protected. To make it copyable, make them public and do the right thing in each (a good default implementation of the copy assignment operator is to express it in terms of copy construction via the copy-and-swap idiom, which means introducing a non-throwing swap function).

---

A fifth issue is that the implementation

template<class T>
int Tree<T>::minValue(treeNode<T>*& root) {
  if (root == NULL) { return 0; }
  if (root->left == NULL) { return root->data; }
  else { minValue(root->left); }
}

strongly suggests that each node stores a value that's implicitly convertible to int. You don't provide the declaration of treeNode. But this looks like a design level bug, that the intent was for minValue to return a T, not an int – and ditto for maxValue.

---

A very small coding issue (not design level): in C++11 and later you should preferentially use nullptr, not NULL.

• nullptr can be freely passed through argument forwarding functions, while NULL then suffers a decay to integral type, since NULL is just a zero-constant of integral type.

• nullptr does not require that you include any header, while NULL is defined by a header, i.e. with nullptr you avoid a header dependency.

---

Finally, regarding

if (root == NULL) { return 0; }

for the minValue, this may of course be the intention, the design. But possibly you want to either signal failure or treat the call as a logic error.

• To treat the call as an error, assert( root != nullptr ); and provide a means for the client code to check for empty tree.

• To signal failure, either return an object with optional value (e.g. like boost::optional or Barton/Nackmann's original Fallible), or throw an exception (the std::runtime_error class is a good general default exception class choice).

• It's also possible to combine the two approaches, to provide both, perhaps with names like minValue and minValueOrX.

More generally it's sometimes possible to reserve some special value as a "no such" indicator. E.g. std::numeric_limits<T>::min(). But this makes for brittle code, since such a value can easily occur naturally in the data, and since client code may easily fail to check for the special value.

---

Example, coded for C++11:

#include <assert.h>
#include <iostream>     // std::cout, std::endl
#include <string>       // std::string

namespace my {
    using std::string;

    template<class T>
    class Tree
    {
    private:
        struct Node
        {
            T       value;
            Node*   p_left;
            Node*   p_right;

            auto to_string() const -> string
            {
                using std::to_string;
                string const left   = (p_left == nullptr? "" : p_left->to_string());
                string const right  = (p_right == nullptr? "" : p_right->to_string());
                return "(" + left + " " + to_string( value ) + " " + right + ")";
            }

            ~Node() { delete p_left; delete p_right; }
        };

        Node*   root_;

        Tree( Tree const&  ) = delete;
        Tree& operator=( Tree const& ) = delete;

    public:
        auto is_empty() const -> bool { return (root_ == nullptr); }

        void insert( T const data )
        {
            Node** pp = &root_;
            while( *pp != nullptr )
            {
                auto const p = *pp;
                pp = (data < p->value? &p->p_left : &p->p_right);
            }
            *pp = new Node{ data, nullptr, nullptr };
        }

        auto minValue() const -> T
        {
            assert( root_ != nullptr );
            Node* p = root_;
            while( p->p_left != nullptr ) { p = p->p_left; }
            return p->value;
        }

        auto maxValue() const -> T
        {
            assert( root_ != nullptr );
            Node* p = root_;
            while( p->p_right != nullptr ) { p = p->p_right; }
            return p->value;
        }

        auto to_string() const -> string
        {
            return (root_ == nullptr? "" : root_->to_string());
        }

        ~Tree() { delete root_; }

        Tree(): root_( nullptr ) {}

        Tree( Tree&& other ): root_( other.root_ ) { other.root_ = nullptr; }
    };

}  // namespace my

auto main() -> int
{
    my::Tree<int> tree;
    for( int const x : {5, 3, 4, 2, 7, 6, 1, 8} )
    {
        tree.insert( x );
    }

    using std::cout; using std::endl;
    cout << tree.to_string() << endl;
    cout << "min = " << tree.minValue() << ", max = " << tree.maxValue() << endl;
}

Output:

(((( 1 ) 2 ) 3 ( 4 )) 5 (( 6 ) 7 ( 8 )))
min = 1, max = 8