Reputation: 173
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.
Upvotes: 2
Views: 720
Reputation: 30879
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.
Upvotes: 3