C++: Is It Possible to End a Non-Void Function Without a Return?

Question

This is a fairly general question, but long story short, I'm trying to figure out a way to break out of a function without using return. I've got a function built from a template, so my compiler doesn't like me using "return;" to terminate early as I've seen suggested before. Here is a condensed version of what I'm trying to do:

V & find (K key) {
    TreeNode<K,V> *traverseFind;
    //TreeNode<K,V> * treeNode = new TreeNode<K,V> (key,NULL);
    traverseFind = root;
    unsigned int compareTraverseToHeight = 0;
    //A bunch of stuff happens
    if(keyFinder == 0)  //this is what I have tried to do
        return;
    return traverseFind->value; //This is what I'm working with, the value can be NULL
}

Some background: this is a find function within a binary tree, which contains two parameters key and value. A key is searched for, and then its corresponding value is returned. As part of the project, I've been tasked with throwing an exception which is caught by a tester function if a key is entered which isn't in the tree. This works fine, however, the way the tester program is configured throws me right back into the function after being resolved, in which case I have traverseFind->value = NULL, which crashes my program when I try and return it. I have no control over the tester, so I'd like to break out of the find function before I have to return a value.

Most of this is background for the curious. My real question is: instead of the if(keyFinder ==0) function that I have tried to use (which doesn't compile), is there another option I can use to end the function early? A "break" statement for functions, so to speak?

MORE CODE:

#ifndef __CSC116__BST_H__
#define __CSC116__BST_H__

//
// An implementation of a binary search tree.
//
// This tree stores both keys and values associated with those keys.
//
// More information about binary search trees can be found here:
//
// http://en.wikipedia.org/wiki/Binary_search_tree
//
// Note: Wikipedia is using a different definition of 
//       depth and height than we are using.  Be sure
//       to read the comments in this file for the
//   height function.
//

#include <list>
#include <iostream>
#include <utility>
#include <algorithm>
#include <string>

using namespace std;

unsigned int heightCount = 0;
unsigned int sizeCount = 0;
int keyFinder = 0;



//
// Each node in the tree stores
// both a key and a value
//
template <class K, class V> class TreeNode
{
public:
    TreeNode(K k, V v): key(k), value(v), left(0), right(0) {}

    K       key;
    V       value;
    TreeNode<K,V>   *left;
    TreeNode<K,V>   *right;
    template <class X, class Y> friend std::ostream & operator<< (std::ostream &s, const TreeNode<X,Y> &t);
};

// 
// TreeNodes can output themselves to streams
template <class K, class V> std::ostream & operator << (std::ostream &s, const TreeNode<K,V> &n)
{
    s << "\"" << n.key << ":" << n.value << "\"";
    return s;
}

//
// This exception is thrown if you try to find 
// a key in the tree that isn't present.
//

class key_not_found_exception {

};



template <class K, class V> class BinarySearchTree {
public:
    //
    // Constructor
    //
    BinarySearchTree ()
    {
        sizeCount = 0;
        heightCount = 0;
        root = NULL;
    }


    ~BinarySearchTree()
    {
    }


void insert (K k, V v) {
  TreeNode<K,V> * treeNode = new TreeNode<K,V> (k,v);
  TreeNode<K,V> *temp=NULL;
  TreeNode<K,V> *prev=NULL;
  temp = root;

  while(temp) { 
    prev = temp;
    if (temp->key < treeNode->key)
      temp = temp->right;
    else
      temp = temp->left;
  }

  if (prev==NULL)
    {root = treeNode;heightCount++;}
  else {
    if (prev->key<treeNode->key)
      {
        prev->right = treeNode;  
        if(prev->left ==NULL){heightCount++;}
      }
    else
      {
        prev->left = treeNode;
        if(prev->right ==NULL){heightCount++;}
      }
  } 

  sizeCount++;
  cout << "Height of Tree is:"<<"_" <<heightCount<<endl;
}






    V & find (K key)                     
    {

    TreeNode<K,V> *traverseFind;
    //TreeNode<K,V> * treeNode = new TreeNode<K,V> (key,NULL);

    traverseFind = root; 
    unsigned int compareTraverseToHeight = 0;

    while (compareTraverseToHeight < heightCount) 
    {
        if (traverseFind == NULL)  // We've fallen off the tree without finding item.
        {
            keyFinder = 0;
            cout<<"code1"<<endl;
            cout<<"keyFinder = 0"<<endl;
            break;

        }

        else if ( key == traverseFind->key )// We've found the item. 
        {
            keyFinder = 1;   

            cout<<"code2"<<endl;
            cout<<"keyFinder = 1"<<endl;
            break;
        }       

        else if ( key < traverseFind->key )                   // If the item occurs, it must be in the left subtree,
        {                                                 // So, advance the runner down one level to the left.
            traverseFind = traverseFind->left;

            cout<<"code3";
        }   


        else  // If the item occurs, it must be in the right subtree. // So, advance the runner down one level to the right.
        {
            traverseFind = traverseFind->right;

            cout<<"code4";  
        }  


         compareTraverseToHeight++;      

    }  // end while

    cout<<"At end of loop, keyFinder ="<<keyFinder<<endl;

        try
        {
            if(keyFinder ==0)
            {
                cout<<"Try has found that keyFinder = 0"<<endl;
                throw key_not_found_exception();

            }
            else{cout<<"keyFinder = 1"<<endl;}
        }catch(...){}

        cout<<"RETURNED";
        cout<<traverseFind->value<<endl;

            if(keyFinder == 0)
            {

            }
            return traverseFind->value;



    }

private:

    unsigned int doHeight (TreeNode<K,V> *t)
    {
        return -1;
    }

    void        doDelete (TreeNode<K,V> * n )
    {
    }

    TreeNode<K,V>   *root;
    unsigned int    count;
    unsigned int    sizeCount;

#endif

TESTER FUNCTION

void test_insert_find()
{
    BinarySearchTree<string,string> t;

    t.insert("bob", "bobdata");
    t.insert("joe", "joedata");
    t.insert("jane", "janedata");

    try
    {
        cout<<"Looking for Bob"<<endl;
        string s = t.find("bob");
        if (s != "bobdata")
            throw bst_tester_exception(__func__,__LINE__);
    }
    catch (key_not_found_exception &e)
    {
            throw bst_tester_exception(__func__,__LINE__);
    }

    try
    {
        cout<<"Looking for Sarah"<<endl;
        string s = t.find("sarah");
        throw bst_tester_exception(__func__,__LINE__);

    }


    catch (key_not_found_exception &e)
    {

        cout<<"Successfully caught"<<endl;
        // this is expected.
    }

FULL OUTPUT OF TEST:

Looking for Bob
code2
keyFinder = 1
At end of loop, keyFinder = 1
keyFinder = 1
RETURNEDbobdata
Looking for Sarah
code4code4code1
keyFinder = 0
At end of loop, keyFinder = 0
Try has found that keyFinder = 0, throwing exception
RETURNED /*Program now crashes when it attempts to return NULL*/

Answer 1

In general, to return "failure" from a find-type function, one has two primary choices:

1. Return the element (or reference) that is found, otherwise throw an exception.

2. Return a pointer to the element, if it is found, or nullptr if not.

There are also other ways, such as returning a bool indicating success and returning the element found in an additional reference or pointer parameter.

In your case, returning V & reference, your only reasonable option to end the function without returning a value is to throw an exception.