Passing arguments in templates

Question

I am implementing a Red black Tree where the insert function should have two templates, one for the item and the other for the key. I am passing the parameters in the insert function this way:

template <class Item, class Key>
void RedBlackTreeNode<Item, Key>::InsertKey(const Item *&T, const Key *&z)

I tried to pass an array(made up of random elements) in the second parameter, this way:

const int* pointer = &arr[i];
t1.InsertKey(//something else here// , pointer); //insert the tree and the node

However, I can't figure out what to pass as the first parameter in order to insert elements in the red black tree. What is the first parameter representing? I tried to pass the root of the tree, this way:

Node<int, int> n1;
t1.InsertKey(n1->root, pointer);

Unfortunately, this is not working.Any help please?

Thanks in advance.

If you're implementing a dictionary (also known as an associative array, or a map) then Item is probably the type of the values stored in the map. — user253751, Dec 29 '13 at 10:04
I am getting three errors: Invalid arguments Candidates are: void InsertKey(const int * &, const int * &), Field 'root' could not be resolved and base operand of ‘->’ has non-pointer type ‘Node’ — user3136756, Dec 29 '13 at 10:07
I don't know another method of how I can implement the red black tree and I have the restriction of using two templates. — user3136756, Dec 29 '13 at 10:14
Why do you pass the parameters to InsertKey with "*&"? Do you want to pass a pointer, a reference, or does *& have a special meaning that I'm not aware of? — MB-F, Dec 29 '13 at 10:16
Pass by reference: http://stackoverflow.com/questions/5789806/meaning-of-and-in-c — user3136756, Dec 29 '13 at 10:20
Ah, thank you for the link. Are you sure that is what you want? *& declares a reference to a pointer. Maybe you want to pass references to an Item and a Key like that: InsertKey(const Item &T, const Key &z) — MB-F, Dec 29 '13 at 10:24
But still, I can't figure out what to pass for 'const Item &T' — user3136756, Dec 29 '13 at 10:28

Johan · Answer 1 · 2013-12-29T10:36:53.573

If you're implementing a red black tree (or just even just a binary tree), you're insertion method just take the element to insert as parameter. You're inserting one Item that can be compared to another item, there is no notion of Key. If you want to create Key/Value container, you can just take an std::pair<Key, Value> item and compare on item.first, or something like this.

Here is a mock up of the code for the binary search tree insertion. You can start with that to add the properties that have to be kept for [red black tree insertion(http://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Insertion):

template <class Item>
void BinarySearchTreeNode<Item>::Insert(Item item)
{
   if (item < this->item)
   {
     if (this->leftChild == nullptr)
        this->leftChild = new BinarySearchTreeNode(item);
     else
        insert(this->leftChild, item);
   } 
   else 
   {
     if (this->rightChild == nullptr)
        this->rightChild = new BinarySearchTreeNode(item);
     else
        insert(this->rightChild, item);
   }
}

And here a example usage (assuming the rest of the implementation has been done):

BinarySearchTree<int> tree;


tree.Insert(1); // Call insert on root node

@user3136756 It is not that it **cannot** take two parameters, but what would be the second one ? If you have a explanation/justification for the usage of the second parameter, go on :) But basic red black tree (or binary tree) take only one value or item to insert in the node. — Johan, Dec 29 '13 at 11:23
Well, that was my question, I don't know what to pass for the second parameter. I was given this question to implement and there was stated that when adding an item both the key and the item should be both generic types(templates in C++). Therefore, I thought that I had to use two templates, but I am coming to conclusions that using two templates does not make any sense! — user3136756, Dec 29 '13 at 11:41

Passing arguments in templates

1 Answers1