Implementation of BST using templates but error no default constructor available, help???

[H3YW0R1Ddispos]

1. Const correctness.
* If you have BST<int>, can you insert(42) ?
void BST<T>::insert(T &p) would create a non-const reference, but you can't do that to literal constant.

* If the 'p' in insert() is a reference, then does the by value 'p' in Node(T p) gain you something?
You apparently have to copy-construct the Node<T>.data, but where and how many copy operations?

I have it now so that it's
void BST<T>::insert(const T &p)

If the 'p' in insert() is a reference, then does the by value 'p' in Node(T p) gain you something?

I'm not sure what this means. I'm using a reference because the Packet object already exists, so I can just pull the existing object. Can't I?

You apparently have to copy-construct the Node<T>.data, but where and how many copy operations?

As many nodes as the BST needs?

Which translation unit will use the BST<T>::insert()?
C++ compiler (at least used to) has to see whole templates where it instantiates a template.

My IDE/C++ compiler know where to look and it knows that this is a template. I don't have any issues so far? Or am I misunderstanding you?

Lets say that you have BST.cpp and main.cpp. They are compiled separately.
When you compile BST.cpp, you don't know what types of BST there will be.
When you compile main.cpp, you don't have the template to create implementation for void BST<std::map<std::string,std::vector<double>>>::insert.

I don't right now. I'm targeting Packets and objects like Packets for now. But isn't it possible for me to add this in in the future by modifying my code, is it not? Templates make it so that you can extend your codebase to accommodate other objects in the future (that's the flexibility of templates) or did I misunderstand somewhere???

3. Who does delete the Nodes?

The BST will. It's the parent of all nodes. I just haven't implemented it yet.

Much thanks.

[keskiverto]

Your Node's constructor takes parameter by value, just like the following Node:

#include <iostream>

template <typename T>
struct Node {
    T y;
    Node( T x ) : y( x ) {}
};

template <typename U>
void test( const U& z ) {
    Node<U> w( z );
    std::cout << "c\n";
}

struct Two {
    int bb;
    Two( int x ) : bb(x) { std::cout << "Two ctor\n"; }
    Two( const Two& rhs ) : bb(rhs.bb) { std::cout << "Two copy ctor\n"; }
    ~Two() { std::cout << "Two dtor\n"; }
};

int main()
{
    Two answer( 42 );
    std::cout << "a\n";
    test( answer );
    std::cout << "b\n";
}

Two ctor
a
Two copy ctor
Two copy ctor
Two dtor
c
Two dtor
b
Two dtor

If we change that constructor to take parameter by reference, the output changes:

template <typename T>
struct Node {
    T y;
    Node( const T& x ) : y( x ) {}
};

Two ctor
a
Two copy ctor
c
Two dtor
b
Two dtor

One less Node was created and destroyed.

My IDE/C++ compiler know where to look and it knows that this is a template.

C++11 does have extern template declaration.
See https://arne-mertz.de/2019/02/extern-template-reduce-compile-times/

That does reduce duplication of effort during compilation, but it does not, nor any other language feature that I know of, allow the compiler to see contents of other cpp-files while it compiles one.

[Niccolo]

My IDE/C++ compiler know where to look and it knows that this is a template.

This is likely a side effect of using only Packet. This tends to cause you to think in terms of Packet instead of T, where T could be just about anything.

We encountered this when, in some function I don't recall now, a member of the template should have instantiated a new T() actually instantiated a new Packet(), and you were resistant to changing it because, as you put it, you were only going to implement Packet. If that were extended to the entire class, "T" wouldn't be required and the class wouldn't even have to be a template, because it only consumes T as Packet and never anything else.

However, it is a template class and that is the exercise.

The IDE has no real knowledge of templates, that is the domain of the compiler (and its associated tools, if any). Template code is compiled slightly differently than non-template code. Template code is instantiated only when a type is known. It can't compile template code without knowing "T" (in your case), because without that type known, code can't be generated that uses "T". So, the code is parsed, but not emitted.

Until the template is instantiated. That happens when it is first declared, like this:

BST< Packet > b;

Here, BST is instantiated as b, on the type Packet. Now that a type is known, the compiler generates all of the template code based on the type "Packet". In order to do that, it must know all of the code in the template. Since C++ is a single pass compiler design, that means the code must already have been parsed, completely. There can be no missing parts (at least none that are used by b, an actual instance).

For example, let's say there are 3 functions:

template <typename T >
class A
{
 public:

 void f1() {}
 void f2();
 void f3();
};

Now let's assume an instantiation and usage like this:

A< int > a;

a.f1();

Here, f1 was called, and the body of f1 exists before it in the code. The compiler parsed the entire body of f1, so it "knew" this function, and emitted code for it mutated to work with an int ("T").

However, if this was all the compiler "saw" in this compilation, had I called f2 or f3, the linker would have issued an error. The function body is not defined, and so the code can't be emitted for the instantiation "a".

This could be the situation you're creating by putting functions for BST in "bst.cpp". The compilation unit (the CPP file) bst.cpp might not know what a Packet is, and may not have been told to instantiate code for a "Packet" type. The function(s) in "bst.cpp" may not be instantiated for a "Packet", and thus the linker may issue errors, that this has no function body (undefined reference to the function).

That leads me to think you are compiling, but not linking. If so, you may be assuming that the link stage can't yet be processed because your code is not yet complete, but if the situation that @keskiverto has identified (and I agree with) does exist, the linker is where the complaint comes from. It will be an undefined reference to the "Bst::insert" function for a Packet type.

The "extern template" notion isn't going to help. It merely tells the compiler that some functions may not be available in any particular translation unit, or that there will be duplicates.

Duplicates are a common "non-issue" when templates are used. If we use a template class (or function) on behalf of the same type in multiple translation units, each translation unit will compile the same template code repeatedly. This wastes time, but causes no errors because the template code is considered "inline", such that the linker will not complain about the duplicates. It is "aware" that these duplicates are expected, and resolves to emit just one of the duplicates in the final executable when that is built as a function call (instead of inline code).

However, the "extern template" identifies candidate templates such that the code is not emitted in every consuming translation unit, avoiding duplicates from reaching the linker and saving some compilation time.

That doesn't solve the problem we see with "BST::insert". That function is in bst.cpp, it's own translation unit. If that CPP happens to also instantiate any BST for a "Packet", the code for that BST on behalf of a Packet would be emitted in that translation unit, and the linker would find it. There wouldn't be a problem.

However, this can't be done for most template code. "T" makes the template applicable to any type. That should be more firmly ingrained in your thinking, but we already know it isn't.

Where another user invokes BST for some other type, bst.cpp would not be re-written to know that type, would not generate that code, and the linker would naturally have no code for BST::insert on behalf of that new (unknown) type. I find "class scenario" code to be a disservice to student because of the way it causes students to think about what they write. I can't help fix that here, it would require every college and every teacher to modify their courses with real world development in mind, and that won't happen for a long while.

The code for template function bodies should not be in a CPP file. They are not actually translation unit candidates. They are header code. They must be included as header code, with one exception.

This was applicable back in the days when 32 Mbytes of RAM was $2,000. That's not a typo. That's megabytes, not gigabytes. When templates were new, and that was the cost of RAM, there was no room for compilers to breathe. Templates were a disaster to compile. They'd consume all RAM, and start thrashing virtual memory until the disk was full (disks, in those days, topped out around 2 Gbytes...smaller than most keychain flash drives).

What we were forced to do, back then, was to use explicit template instantiation. The function bodies were still written outside the template class declaration, but placed in ".inl" files, as opposed to ".h" or ".cpp" files. This typified them as "inline" code - though it isn't really one of the "formal" file types like ".hpp" or ".cpp" files.

We then prepared separate translation units with no other code than to include the appropriate headers, including the .h for the template and .inl for it's functions, then explicitly instantiated templates for every type used elsewhere in the application ( up to RAM limits...sometimes we had to create several of these modules with just a few types in each).

This generated code for the linker to find, built for each type used by the application. I've not seen this in many years, because since the era of 1 Gbyte PC's, it really isn't all that important.

It would apply to your design here, where BST.cpp would have to include explicit instantiations for every type user code consumed, but it is just more work.

Instead, you should rename the bst.cpp file to a .h or .inl, include it with your template declaration code, and allow the simpler "inline template instantiation" you're already using do the work.

To be clear, if you're not linking, you're not going to see the error.

If you're compiling, you'll see no "missing functions" message, because compilers naturally assume that non-inline functions (which these are when they're not inside the class declaration) will be found by the linker in some translation unit of the project.

In your case, there may not be one. It is at link time, then, that you'd get an error. Not at compile time.