Invalid initialization of reference

Question

I have a template class that looks like this

namespace binary_search_tree {

template <typename T> 
class binary_tree {

private:
    T d;
    binary_tree<T> *l, *r;

public:
    binary_tree(T d) : d(d), l(nullptr), r(nullptr)
    {}
    
    void insert(T d) {
        binary_tree<T>* branch = new binary_tree<T>(d);
        if(d <= this->d) {
            this->l = branch;           
        } else {
            this->r = branch;
        }
    }
    
    const T data() const {
        return d;
    }
    
    const binary_tree<T>* left() const {
        return l;
    }
    
    const binary_tree<T>* right() const {
        return r;
    }

};

}

And I have a test.cpp file designed for testing my class

#include "binary_search_tree.h"
#include "test/catch.hpp"
#include <vector>

// test data version: 1.0.0

template<typename T>
using tree_ptr = typename std::unique_ptr<binary_search_tree::binary_tree<T>>;

template<typename T>
static void test_leaf(const tree_ptr<T> &tree, 
                      const T& data, bool has_left, bool has_right)
{
    REQUIRE(data == tree->data());                  //        ***************
    REQUIRE((bool) tree->left() == has_left);       // <----  *** problem ***
    REQUIRE((bool) tree->right() == has_right);     //        ***************
}

template<typename T>
static tree_ptr<T> make_tree(const std::vector<T> &data)
{
    if (data.empty())
        return tree_ptr<T>(nullptr);
    
    auto data_iter = data.begin();
    auto tree = tree_ptr<T>(new binary_search_tree::binary_tree<T>(*data_iter));
    ++data_iter;

    for (; data_iter != data.end(); ++data_iter)
    {
        tree->insert(*data_iter);
    }

    return tree;
}

TEST_CASE("data_is_retained")
{
    auto tested = make_tree<uint32_t>({4});
    test_leaf<uint32_t>(tested, 4, false, false);
}


TEST_CASE("smaller_number_at_left_node")
{
    auto tested = make_tree<uint32_t>({4, 2});

    test_leaf<uint32_t>(tested, 4, true, false);
    test_leaf<uint32_t>(tested->left(), 2, false, false);
}

The TEST_CASE() functions come from a separate header file designed for testing.

The problem originates when left() and right() are called in the test_leaf() function.

The compiler says

invalid initialization of reference of type ‘tree_ptr<unsigned int>&’ {aka ‘const 
std::unique_ptr<binary_search_tree::binary_tree<unsigned int>, 
std::default_delete<binary_search_tree::binary_tree<unsigned int> > >&’} from expression of 
type ‘binary_search_tree::binary_tree<unsigned int>*’

I'm not sure how to make these types match. I've tried returning a reference in various ways but that seems to make thing worse. Should I be returning a unique_ptr<>? I'm confused as to what the default_delete<> is. It looks to me That I should be returning some sort of reference instead of a pointer. I'm not sure how to safely do this in my class.

Answer 1

Your issue is on this line:

test_leaf<uint32_t>(tested->left(), 2, false, false);

binary_tree<T>::left returns a raw, non-owning pointer to the tree's left subtree, but test_leaf expects a reference to a std::unique_ptr<binary_tree<T>>.

The solution here is to change test_leaf to accept a raw pointer or a reference instead:

template<typename T>
static void test_leaf(binary_search_tree::binary_tree<T>& tree,
                      const T& data, bool has_left, bool has_right)
{
    REQUIRE(data == tree.data());
    REQUIRE(static_cast<bool>(tree.left()) == has_left);
    REQUIRE(static_cast<bool>(tree.right()) == has_right);
}

(Note the type of tree really should be const qualified, but your binary_tree class template isn't const-correct enough for that to actually work right now)

Then change all of the places where you call test_leaf any type of pointer to pass a reference to the underlying object instead. For example:

test_leaf<uint32_t>(tested, 4, true, false);
test_leaf<uint32_t>(tested->left(), 2, false, false);

Would change to

test_leaf<uint32_t>(*tested, 4, true, false);
test_leaf<uint32_t>(*tested->left(), 2, false, false);

---

In general, functions that do not assume any ownership of the pointed-to object should accept either a reference or a raw pointer to the object owned by a smart pointer. Passing a reference to the smart pointer itself doesn't add any safety and unnecessarily restricts the use of the function to only dynamically-allocated objects owned by a specific type of smart pointer.