Templating a List in C++

Question

I'm writing a program that needs a SkipList that I wrote a while back, but now I need it templated because it needs to use a custom class that I created. The problem I have is with creating the node in the List class. I use template <class t> on all my methods but I think that since both the node and the SkipList class use template <class t>, the same class ts interfere with each other or something.

In my SkipList.h, I have the method saying

Node <t>* createnode<t>(t,int);

And in the SkipList.cpp, the method says

template <class t>
Node<t>* SkipList<t>::createnode(t value, int level) {
    Node<t> *n = new Node<t>(value, level);
    return n;
}

This gives me an error in the .h file that says Template specialization requires 'template<>', and when I add it in, it replaces the code to say

template<> Node<t>* createnode<t>(t,int);

But then my .cpp file says that there is no function definition anymore.

Does anyone know where I'm going wrong or what I'm missing? Thanks a ton for the help. My GitHub is here if anyone needs it for clarification

Seems you are trying to declare a template in a `.cpp` file. That will not work. This is not your issue here but important nevertheless See: https://stackoverflow.com/questions/115703/storing-c-template-function-definitions-in-a-cpp-file — Lala5th, Aug 14 '21 at 18:28
Two other nuggets of info: https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice, one for `bits/stdc++` and one for `using namespace std;` — Lala5th, Aug 14 '21 at 18:31

score 1 · Answer 1 · answered Aug 14 '21 at 19:04

Few things to note:

You can't define templates in .cpp files use headers.
using namespace std; can and will lead to nasty things especially when included in a header like this.
You shouldn't include bits/stdc++.h.

Now to address some things in the code. I am not sure if template <class t, class t> is valid, but at best it is useless in this case. Addressing your question: Yes the two class ts interfere with each other, but you don't need two different ts. You can't create a Node<t> with a t not matching the type of the List can you? Now even if you have a case where that is needed you can just use template <class T1, class T2>.

Now the fixed implementation would look like this:

template <class T>
class SkipList {
    int MAX_LEVEL;
    float p;
    Node<t>* header;
    int level;
public:
    SkipList<T>(int,float) { /* Include definition here */}
    int randomlevel() { /* Include definition here */}
    void insert(T) { /* Include definition here */}
    void remove(T) { /* Include definition here */}
    bool find(T) { /* Include definition here */}
    void print() { /* Include definition here */}
    Node<T>* createnode(T, int) { /* Include definition here */}
};

Similarly Node should be fixed as well (include the definition of the constructor).

An other thing you mentioned in your post is template specialisation. You can read about it here.

You also have a memory leak somewhere between your Node/SkipList classes. Consider moving to smart pointers.

Finally I strongly encourage that you go through the basics of C++ before you continue. You can't run before you can walk.

Templating a List in C++

1 Answers1