Having class X, how to pass X as a template argument to itself?

Question

I'm trying to implement a Red-Black Tree that inherits from a BS Tree. BST uses BSNode as its nodes while RBT (Red-Black Tree) uses RBNode which in turn inherits from BSNode. The code looks like this, the problems arise in the code:

#include <iostream>

#define _BST BST<K, T, RBNode<K, T>>

// attempt 1
//template <typename K, typename T, typename NODE>
//class BSNode
//{
//
//public:
//
//  K key;
//  T value;
//
//  NODE* left;
//  NODE* right;
//
//  // ...
//};

// attempt 2
template <typename K, typename T, template<typename, typename> typename NODE>
class BSNode
{

public:

    K key;
    T value;

    NODE<K, T>* left;
    NODE<K, T>* right;

    // ...
};

template <typename K, typename T>
class RBNode : public BSNode<K, T, RBNode>
{

public:

    bool color;

    // ...
};

template <typename K, typename T, typename NODE>
class BST
{

public:

    NODE* root = nullptr;

    // ...
};

template <typename K, typename T>
class RBT : public _BST
{
    // ...
};

int main()
{
    RBT<int, int> rbt;

    // attempt 1
    // recursive and can't be done.
    // BST<int, int, BSNode<int, int, BSNode<int, int, BSNode<int.....

    // attempt 2
    // template arguments list for NODE takes
    // 2 arguments while BSNode takes 3. Not compatible.
    // BST<int, int, BSNode<int, int, BSNode>>
}

questions:

1 - how to implement it so that BSTs are just written as BST<int, int> while still having it accept different types of nodes for left and right such as RBNode?

2 - how to let RBNode inherit from BSNode while being able to create BSTs and RBTs?

3 - in attempt 2, in the macro #define _BST BST<K, T, RBNode<K, T>>, why do I get an error when writing it as #define _BST BST<K, T, RBNode>? in the class BSNode, left and right are defined as NODE<K, T>*. this means substituting NODE by BSNode<K, T> would result in left and right being equal to BSNode<K, T><K, T>*. why is this the right way?

Is there something wrong with the design or if can it be improved?

I am afraid you're missing an additional level of indirection. The idiomatic way is to use a CRTP I think. — πάντα ῥεῖ, Oct 01 '20 at 09:32
Sure: https://stackoverflow.com/questions/4173254/what-is-the-curiously-recurring-template-pattern-crtp `RBNode` should be passed as a class type deriving from `BST`. — πάντα ῥεῖ, Oct 01 '20 at 10:15
The problem with the title is that `X` is either a class or a class template. Unrelated: `_BST` is a name that's reserved for the implementation. — MSalters, Oct 01 '20 at 10:37

Flaviu · Answer 1 · 2020-10-01T11:23:18.020

1

The issue resides in node definitions. For simplicity it would be better using node as tree itself and therefore removing BST and RBT classes.

The node classes could be defined as:

template <typename K, typename T, template<typename, typename> typename Node>
class GenericNode
{

public:
    K key;
    T value;

    Node<K, T>* left = nullptr;
    Node<K, T>* right = nullptr;

    // common code
};

template <typename K, typename T>
class BSNode : public GenericNode<K, T, BSNode>
{
    // specific code if exists
};

template <typename K, typename T>
class RBNode : public GenericNode<K, T, RBNode>
{

public:
    bool color;

    // specific code
};

int main()
{
    {
        BSNode<int, float> n1, n2, n3;
        n1.left = &n2;
        n1.right = &n3;
    }

    {
        RBNode<int, float> n1, n2, n3;
        n1.left = &n2;
        n1.right = &n3;
        n1.color = true;
    }
}

Reply 3. NODE<T,K>, as template parameter of BSNode class, allows using pointers to derived classes. Otherwise, BSNode can used for left and right pointers but it may be necessary making static casts to derived classes (eg. static_cast<RBNode*>(left)) in many cases. This is the reason using NODE<T,K>.

edited Oct 01 '20 at 11:23

answered Oct 01 '20 at 10:16

Flaviu

931
11
16

1

Thanks for the answer, but this does not answer question 3, plus, trees and nodes are different things. For example, trees will contain the root node while nodes don't. – StackExchange123 Oct 01 '20 at 10:54
I added reply 3. What are the main differences between tree node and tree? A "std::unique_ptr my_tree" could be a perfectly defined tree. It depends how node details are exposed. IMO the node should expose methods and not raw fields. – Flaviu Oct 01 '20 at 11:34
Well, in Red Black trees for example, roots have special conditions for them. For example, if the root is red, it can be changed to black with no problem. this applies only to the root. Also, if the tree is empty, that means that the root is null, but the tree isn't null yet. I want to be able to use the tree and empty it up and fill it again with having no problem and for that I would need a wrapper for the nodes (the trees). As of for the question 3, I'm not quite sure what do you mean. I've updated the question so that it's more clearer. Thanks! – StackExchange123 Oct 01 '20 at 11:43
Welcome. About reply 3, Node struct can have only K and T parameters and left and right pointers to Node and it works. Then deriving from Node, you will still have pointers to Node (not pointers to descendant classes). For accessing derived objects (eg. RBNode) from left and right members, static casts would be needed. – Flaviu Oct 01 '20 at 12:48

score 1 · Accepted Answer · answered Oct 01 '20 at 11:27

1

You need to separate both Node and Tree from the specific BSNode, RBNode, BSTree and RBTree types

template <typename K, typename T, template<typename, typename> typename NODE>
struct Node
{
    K key;
    T value;

    NODE<K, T>* left;
    NODE<K, T>* right;

    // ...
};

template <typename K, typename T>
struct BSNode : Node<K, T, BSNode>
{};

template <typename K, typename T>
struct RBNode : Node<K, T, RBNode>
{
    bool color;

    // ...
};

template <typename NODE>
struct Tree
{
    NODE* root = nullptr;

    // ...
};

template <typename K, typename T>
struct BSTree : Tree<BSNode<K, T>>
{
    // ...
};

template <typename K, typename T>
struct RBTree : Tree<RBNode<K, T>>
{
    // ...
};

Aside: if you are making everything public, you may as well use struct over class. The only difference is public by default.

answered Oct 01 '20 at 11:27

Caleth

52,200
2
44
75

Well, I've thought of this way but I'm not sure would this be a good solution or not.. now instead of BSNode being a parent for RBNode, they are siblings and an RBNode can't be substituted in place of BSNode. Also, I'd be thankful if you're able to provide an answer for question 3. Thanks! – StackExchange123 Oct 01 '20 at 11:50
@StackExchange123 they aren't the same type, so it's good that you can't mix them. #3 is because you define `NODE` as a type, not a template. Nowhere in `BST` do you write `NODE` – Caleth Oct 01 '20 at 12:32
Thanks for the reply. I believe RBNode is just a BSNode with the boolean color added to it. Why you're saying that they're not the same type? – StackExchange123 Oct 01 '20 at 12:54
because you shoudn't put an `RBNode` in a `BSTree` – Caleth Oct 01 '20 at 13:47
You can still write functions that don't care if you pass a `BSTree` or a `RBTree` without inheritance – Caleth Oct 01 '20 at 13:49

Having class X, how to pass X as a template argument to itself?

2 Answers2