My template Binary Search Tree class gives error "Node: no appropriate default constructor available," how can this be fixed?

Question

When trying to run my codebase, I am having an error that says:

'Node': no appropriate default constructor available BST

I have an idea that this could be caused by BST.h:

#ifndef BST_H
#define BST_H

// using namespace std;

template <typename T>
class Node {
    public:
        Node(T n) : data(n), rlink(nullptr), llink(nullptr) {}
        ~Node() {}
    private:
        T data;
        Node *rlink, *llink;

};

template <typename T>
class BST {
public:
    BST();
    void insert(T &p);
private:
    Node<T> * root; 
};

#endif

Or if not that then caused by this function which is part of BST.cpp:

template <typename T>
void BST<T>::insert(T &p) {
    if (root != nullptr) {

    }
    else {
        Node<T> *newNode = new Node<T>;
        cout << "UPD" << endl;
    }
}

The cout is there for test purposes. I am aware of the usage of namespace std; that is just there for quick-testing-purposes. That's not my priority, but this is. Please:

Help me fix this very problem
May I get your assistance and guidance as an answer on how I can fix this problem? I'm not sure how to fix it!

My intention is to do something like this:

Node *newNode = new Node;
newNode->data = new Packet(p);

but in a template version. How can I achieve this? I used to have the error "No default constructor for Packet" but that was fixed w/an edition of this:

Node(T n) : data(n), rlink(nullptr), llink(nullptr) {}

in BST.h. It used to be:

Node() : rlink(nullptr), llink(nullptr) {}

But then it introduced this error.

For reference purposes:

BST.cpp

#include "BST.h"
#include <iostream>

template <typename T>
BST<T>::BST() : root(nullptr) {}

template <typename T>
void BST<T>::insert(T &p) {
    if (root != nullptr) {

    }
    else {
        Node<T> *newNode = new Node<T>;
        cout << "UPD" << endl;
    }
}

Packet.h

#ifndef PACKET_H
#define PACKET_H

#include <string>

// using namespace std;

class Packet {
public:
    Packet(int partId, string description, double price, int partCount) :
        partId(partId), description(description), price(price), partCount(partCount) {}
    int getPartId() const { return partId; }
    string getDescription() const { return description; }
    double getPrice() const { return price; }
    int getPartCount() const { return partCount; }
private:
    int partId;
    string description;
    double price;
    int partCount;
};

#endif

Main.cpp

// using namespace std;

#include <iostream>

#include "BST.h"
#include "BST.cpp"
#include "Packet.h"

int main()
{
    BST<Packet> test;
    Packet one(1, "testPacket", 1, 1);
    test.insert(one);
    system("Pause");
}

Note: Commented out namespace std; but if you want to run the program, just uncomment. I just did it for testing purposes...

Which constructor are you expecting to be invoked by the expression `new Node`? — JaMiT, Jul 25 '19 at 22:31
What I'm trying to do is this: Node *newNode = new Node; newNode->data = new Packet(p);...but in a template version. How can I achieve this??? And yes, I used to have "No default constructor for Packet" but I fixed that by added the T parameter into the Node()... — ii69outof247, Jul 25 '19 at 22:38
[Rethink `#include "BST.cpp"``](https://stackoverflow.com/questions/1686204/why-should-i-not-include-cpp-files-and-instead-use-a-header) — user4581301, Jul 25 '19 at 23:00
I don't believe #include is the problem of this error. How can I get this working the way I want??? What can I do? I just need to get over this hurdle and then the program should start working. It's this that seems to throw the program off. — ii69outof247, Jul 25 '19 at 23:09
The proper way to reduce our attention on `using namespace std;` is to remove it. — L. F., Jul 26 '19 at 00:04
I don't think that will fix my glaring problem. I've commented out using namespace std; though. Any idea on how to fix my problem that it won't even allow the program to execute? — ii69outof247, Jul 26 '19 at 00:12

Scheff's Cat · Answer 1 · 2019-07-26T08:39:45.683

First, I would like to reduce OPs sample to an MCVE:

template <typename T>
struct Node {
  Node(T n) : data(n), rlink(nullptr), llink(nullptr) {}
  ~Node() {}

  T data;
  Node *rlink, *llink;
};

int main()
{
#if 1 // Enough to reproduce the issue:
  Node<int> node;
#else // but this would do as well
  Node<int> *pNode = new Node<int>;
#endif // 1
}

Output:

main.cpp: In function 'int main()':
main.cpp:15:13: error: no matching function for call to 'Node<int>::Node()'
   Node<int> node;
             ^~~~
main.cpp:5:3: note: candidate: 'Node<T>::Node(T) [with T = int]'
   Node(T n) : data(n), rlink(nullptr), llink(nullptr) {}
   ^~~~
main.cpp:5:3: note:   candidate expects 1 argument, 0 provided
main.cpp:4:8: note: candidate: 'constexpr Node<int>::Node(const Node<int>&)'
 struct Node {
        ^~~~
main.cpp:4:8: note:   candidate expects 1 argument, 0 provided

Live Demo on coliru

From gcc, it sounds a bit different. (Not sure which C++ compiler is used by OP.) However, Node<int>::Node() is just the default constructor which is missed.

The thing about default constructors is that:

Default constructors might be generated by compiler
if there isn't any reason preventing this, e.g. a custom defined constructor.

template <typename T>
struct Node {
  //Node(T n) : data(n), rlink(nullptr), llink(nullptr) {}
  ~Node() {}

  T data;
  Node *rlink, *llink;
};

int main()
{
#if 1 // Enough to reproduce the issue:
  Node<int> node;
#else // but this would do as well
  Node<int> *pNode = new Node<int>;
#endif // 1
}

compiles fine. Now, the compiler made a default constructor by itself.

Too bad – it is somehow illformed: rlink and llink are left uninitialized!

Just adding a read access to node.rlink or node.llink makes this obvious:

  Node<int> node;
  std::cout << "node.rlink: " << node.rlink << '\n';
  std::cout << "node.rlink: " << node.llink << '\n';

Warnings:

main.cpp: In function 'int main()':
main.cpp:16:39: warning: 'node.Node<int>::rlink' may be used uninitialized in this function [-Wmaybe-uninitialized]
   std::cout << "node.rlink: " << node.rlink << '\n';
                                  ~~~~~^~~~~
main.cpp:17:39: warning: 'node.Node<int>::llink' may be used uninitialized in this function [-Wmaybe-uninitialized]
   std::cout << "node.rlink: " << node.llink << '\n';
                                  ~~~~~^~~~~

Output:

node.rlink: 0x4007d0
node.rlink: 0x7ffdd1e7e250

Live Demo on coliru

I must admit I'm quite sure that reading unitialized members is U.B..

To summarize:

A default constructor is generated only if there are no user provided constructors.
A generated default constructor relies on that every class member is default constructable.
A generated default constructor might be a bad choice (e.g. for POD member types like raw pointers).

There are two possible fixes:

First: Define a default constructor (additional to the already existing):

  Node(): data(), rlink(nullptr), llink(nullptr) {}

Live Demo on coliru

Second: Modify the constructor that it can be used as default constructor by applying default values to arguments:

  Node(T n = T()) : data(n), rlink(nullptr), llink(nullptr) {}

Live Demo on coliru

Recommended reading: Default constructors on cppreference.com

IMHO, worth to be mentioned: Rule of three.

(I would recommend to delete default copy constructor and assignment in template class Node.)

My template Binary Search Tree class gives error "Node: no appropriate default constructor available," how can this be fixed?

1 Answers1