Simple tree template class using vectors

[alexmbcm]

Hi:

I would like to make a really simple template class using vectors, something like the following:




#include <vector>

using namespace std;


//Class that can use generic types
template <typename T>
class Tree
{
//Pointer that points to vector of children
vector<T> *childrenPointer;

//Class variables
public:
Tree();
~Tree();
makeChildren(int numberOfChildren);

//For example: deleteChildren(4) is like deleting
entry 3 (indexing from 0) out of 6
deleteChildren(int childrenId);

deleteAllChildren();
private:

};


Tree::Tree()
{
this->childrenPointer = NULL;
}

Tree::makeChildren(int numberOfChildren)
{
childrenPointer = new vector<T> [numberOfChildren];
//Not sure if this is right
}

Tree::deleteAllChildren()
{
//Make all children run the deleteAllChildren function
?

//After deleting all children delete children pointer
this->childrenPointer = NULL;
}




The function should work something like this:

To make tree:

Tree<Data> roottree
//Data is another class with some numbers
//(like a structure but I need 2 functions in it)

rootTree.makeChildren(2);
rootTree.children[1].makeChildren(2);
rootTree.children[2].makeChildren(2);

rootTree.children[1].makeChildren.Data.setValue(7);

rootTree.deleteAllChildren;



I just have some issues like how to declare the pointer to a vector of the Tree class in the function makeChildren and how to delete the vectors referenced by the childrenPointer.


Thank you for your time.

Alex.

[kbw]

It gets much easier to code correctly if you replace:
vector<T> *childrenPointer;
with:
vector<T> childrenPointer;

[alexmbcm]

Hi kbw:

Thanks for the prompt reply. What I don't get is the following:
if you declare a vector of tress like you said with vector<T> childrenPointer; this variable is going to be generated
forever. At least that's what I think will happen since I don't want to run it until I'm sure I'm not leaking memory.

What about doing it this way? What do you suggest I should change to make it work?

#include <vector>

using namespace std;


//Class that can use generic types  
template <typename T> 
class Tree 
{
	//No nondynamically allocated class variables 
	
	//Public functions
	public:
		Tree();
		~Tree();
		makeChildren(int numberOfChildren);
		int getChildrenSize();
		deleteChildren(int childrenIndex);
		deleteAllChildren();
	
	//Private functions
	private:
	
};


Tree::makeChildren(int numberOfChildren)
{
	vector<Tree>* children = new vector<Tree>(numberOfChildren);
}

int Tree::getChildrenSize()
{
	return children.size();
}

Tree::deleteChildren(int childrenIndex)
{
	//For erase you need the an iterator 
	//which in this case is children.begin()
	//this line deletes childrenId + 1 position
	//(using 0 indexing for everything)
	children.erase(children.begin() + childrenIndex);
}

Tree::deleteAllChildren()
{
	//Make every children run deleteAllChildren
	for (int i=0; i<children.size(); i++) 
	{
		children[i].deleteAllChildren();
	}
	
	//Delete children vector
	delete children;
}

Thank you for your time.

Alex.

[kbw]

There's too much indirection. Remember, a vector is an array that grows, and so has indirection built into it. There's no need to use a pointer of vectors as unless you're experienced, you'll write code like:

Tree::makeChildren(int numberOfChildren)
{
    childrenPointer = new vector<T> [numberOfChildren];
}

which is clearly wrong. It should be:

Tree::makeChildren(int numberOfChildren)
{
    childrenPointer = new vector<T>(numberOfChildren);
}

or with my suggested declaration:

Tree::makeChildren(int numberOfChildren)
{
    childrenPointer.resize(numberOfChildren);
}

I made a mistake with my declaration. It should be:
vector<T*> childrenPointer;

The idea is that each node has a vector of tree nodes.

Take a step back and think about the methods you need for your Tree class. You'll need to add a node, remove a node and so on. Think about it in that way, then try to implement that interface using your tree. At the moment, the interface looks like you thought about the vector first then the tree second.

[alexmbcm]

Hi kbw:
So what you are saying is that I should forget about using indirection and just declare a vector? So I don't need the function deleteAllNodes then?

I have 2 questions about that:

Isn't the declaration vector<T*> childrenPointer; declaring a vector of type T instead of a vector of trees of type T?

If you declare a vector of trees when you declare a tree then c++ going to keep declaring trees right?

Alex.

[kbw]

I suggested:
vector<T*> childrenPointer;
because each node has an ordered set of pointers to children and a pointer to the parent.

You will still need methods to insert/remove child nodes. And that will involve creating/destroying tree objects (children) and manipulating the entries in the vector.

I still don't think you've thought about the public interface. You really should think about how this is going to be used. You really need to think about that up front. The best way to get started is to write some code that uses the tree. Try writing a little program that creates a tree, adds a node, deletes it, then destroy the tree. Do this on paper without trying to go any further with your tree.

[alexmbcm]

Hi kbw:

After thinking about why I needed the tree in the first place like you mentioned, I implemented what I had to do in a vector of structures. Thanks for the help. Initially the idea was to generate this vector but I found out it can be done directly.