tree container

Hello! It is my first post and I've got probably easy question. I can use containers like list, vector. But I think there is no tree container in standard containers of C++. I found this site http://www.gamedev.net/reference/art...rticle2192.asp and I'd like to use it. The problem is that I do not know how to create trees with this tree.h.

This is my listing:

Code:

#include <cstdlib>
#include <iostream>
#include <string>
//source of tree.h:
//http://www.gamedev.net/reference/articles/article2192.asp
#include "tree.h"

using namespace std;

class dir //directory
{
public:
   dir() : itsName("katalog") {} //default constructor
   explicit dir(const string &name) : itsName(name) {} //constructor
   const string &getName() const { return itsName; } //accessor
   bool operator==(const dir &rhs) const
        { return this->getName() == rhs.getName(); }
   bool operator<(const dir &rhs) const
        { return this->getName() < rhs.getName(); }
private:
   string itsName;
};

void temp() //temporary function which creates simple tree of directories
//and shows the result
{
   using namespace core; //namespace from tree.h
   //typedef tree<dir> treeDir;
   tree<dir> leafDir; //it creates tree of dir
   tree<dir>::iterator iter = leafDir.insert(dir("main")); //root of tree
   iter = iter.insert(dir("dir1"));
   //... AND HERE I CAN'T WRITE THE PROPER CODE

   ////////////////////////////////////////////////////
   // output the dir tree
   ////////////////////////////////////////////////////
   for (tree<dir>::const_iterator iter = leafDir.begin(); iter != leafDir.end(); ++iter)
   {
      std::cout << iter.data().getName() << std::endl;
      tree<dir>::const_iterator inner = iter;
      // dir's iterators are containers themselves - use the
      // same iterator to traverse inwards through the dir
      for (inner = inner.in(); inner != inner.end(); inner = inner.in())
      {
         for (int tabs = 1; tabs < inner.level(); ++tabs)
            std::cout << "\t";
         std::cout << (*inner).getName() << std::endl;
      }
   }
}

int main(int argc, char *argv[])
{
   temp();
   system("PAUSE");
   return EXIT_SUCCESS;
}

I'd like to create an examplary tree (so that I can train how to use tree.h):

main
---dir1
------subdir1
---------subdir4
------subdir2
---dir2
------subdir3
---dir3

But I don't know how to create new "levels" of the tree, how to "step back" into lower level, how to create branches/leaves on the same level - please, help me.

Greetings and thanks in advance for your help!

It looks like you've already got it working. Did you write that code or is it from an example?

I'd imagine inserting more nodes would be the same as how glowny and kata were inserted there.

It is my code but based on the code from that site (the link is given in my first post).

I changed this listing from previous message - now there is also possibility to see the results of creating a tree. Yes, inserting more nodes would be ALMOST the same as those previous ones. But there is one difference and I don't know how to do it - I don't want it to move into deeper branch every 'insert' commend. I'd like it to stay on the same level for some branches or to go to the previous branch for some of them - I don't know how to maintain this navigation. It may be something like lower_bound or upper_bound (http://www.cplusplus.com/reference/stl/set/) but how to use it? And what should I use to stay on the same level (lower and upper are for changing the level)?
Thanks for your help

My guess is that you should save the iterator for the node that is the parent and add nodes to that instead of adding them to the child each time. Your problem appears to be that you are saving the iterator returned by insert into the iter variable every time, which overwrites the previous parent with the new node. You need a separate iterator variable for the parent of the objects and one for the newly inserted one.

Sorry for the stupid question but how to do it (how to write the proper code)? I was trying to do it and I don't know how. Thanks for help .

We generally don't just write code here. If you've tried, go ahead and post your attempt and I'm sure somebody will be able to guide you.

It's a pretty simple concept. You need another tree<dir>::iterator variable besides iter. One to hold the current parent, and the other to save the result of insert.

Code:

   //typedef tree<dir> treeDir;
   tree<dir> leafDir; //it creates tree of dir
   //I need two variables
   //"One to hold the current parent, and the other to save the result of insert".
   //Is this one below for saving the result of insert??
   tree<dir>::iterator iter = leafDir.insert(dir("main"));
   //And how to create the other one?
   tree<dir>::iterator parent = leafDir.??? //how to do it?
   iter = iter.insert(dir("dir1"));

I have read everything on the website http://www.gamedev.net/reference/art...rticle2192.asp and there was nothing about navigating in the tree in this way (creating branches on the same level, changing the level to the previous one and so on) so this is why I'm asking you on this forum. Thanks for help.
I'd like to create the tree with more than one branch on the same level, as it is shown on the bottom of my first post (main - dir1 - subdir1 and so on).

>> //how to do it?

You have to think about what the variable is holding.

Code:

tree<dir>::iterator iter = leafDir.insert(dir("main"));

In that code, iter is pointing to "main" in the tree.

Code:

iter = iter.insert(dir("dir1"));

After that, iter refers to the "dir1" subdirectory.

What you need to do is assign iter to parent when you want to save what it points to. For example, if you want to have multiple children of "main", then you should save a copy of iter to parent after you create "main" and before you create "dir1". Does that make sense?

Please note that this will become more complicated the more levels you need. I'd suggest you start by getting this to work:

Code:

main
---dir1
---dir2

This is what I've got - main and then dir1, dir2 on the same level. I saved a copy of iter to parent after creating "main" and before "dir1". But I guess there is a problem with "output the dir tree" - or maybe other kind of mistake? I can compile and run it but it doesn't show dir2.

Code:

void temp() //temporary function which creates simple tree of directories
//and shows the result
{
   using namespace core; //namespace from tree.h
   typedef tree<dir> treeDir;
   treeDir leafDir; //it creates tree of dir
   treeDir::iterator iter = leafDir.insert(dir("main")); //root of tree
   treeDir::iterator iter2 = iter;
   iter = iter.insert(dir("dir1"));
   iter2 = iter2.insert(dir("dir2"));

   ////////////////////////////////////////////////////
   // output the dir tree
   ////////////////////////////////////////////////////
   for (tree<dir>::const_iterator iter = leafDir.begin(); iter != leafDir.end(); ++iter)
   {
      std::cout << iter.data().getName() << std::endl;
      tree<dir>::const_iterator inner = iter;
      // dir's iterators are containers themselves - use the
      // same iterator to traverse inwards through the dir
      for (inner = inner.in(); inner != inner.end(); inner = inner.in())
      {
         for (int tabs = 1; tabs < inner.level(); ++tabs)
            std::cout << "\t";
         std::cout << (*inner).getName() << std::endl;
      }
   }
}

OK, now I've got the other idea and the other code. But I don't know 1) where I've got memory outflow (what kind of situation can cause this memory outflow), 2) how to avoid it/ improve the code
Thanks for help, greetings!

Structure which represents directory - directory, obviously, has got its name and subdirectories (and constructor is to simplify the code).

Code:

struct Directory {
 std::string name;
 std::vector<Directory*> children;

 Directory(std::string name_) : name(name_) { };
};

The simplest recurrence function shows the tree. (std::for_each is in <algorithm>):

Code:

void print(Directory *dir) {
 std::cout << dir->name << " : " << std::endl;
 std::for_each(dir->children.begin(), dir->children.end(), print);
}

This code shows the tree in the better way.

Code:

int nesting = 0;

void print(Directory *dir) {
 for (int i = 0; i < nesting; ++i) std::cout << ' ';
 std::cout << dir->name << " => (" << std::endl;
 ++nesting;
 std::for_each(dir->children.begin(), dir->children.end(), print);
 --nesting;
 for (int i = 0; i < nesting; ++i) std::cout << ' ';
 std::cout << ")" << std::endl;
}

And exemplary tree:

Code:

int main(void) {
 /*
  - root
   - sub1
    - sub1.1
   - sub2
   - sub3
    - sub3.1
     - sub3.1.1
  */
 Directory *root   = new Directory("root");
 Directory *sub1   = new Directory("sub1");
 Directory *sub11  = new Directory("sub1.1");
 Directory *sub2   = new Directory("sub2");
 Directory *sub3   = new Directory("sub3");
 Directory *sub31  = new Directory("sub3.1");
 Directory *sub311 = new Directory("sub3.1.1");
 
 root->children.push_back(sub1);
 sub1->children.push_back(sub11);
 root->children.push_back(sub2);
 root->children.push_back(sub3);
 sub3->children.push_back(sub31);
 sub31->children.push_back(sub311);
 
 print(root);
 return 0;
}

I see no reason to use pointers or dynamic memory here. Change this:

Code:

Directory *root   = new Directory("root");

to this:

Code:

Directory root("root");

Do the same for the rest of your Directory variables. Change your children to be a std::vector<Directory> instead of holding pointers. Then of course you'll have to use . instead of -> everywhere.

If you make that change, then you won't be using dynamic memory, and you won't have to clean up the memory you allocated with new. That means no memory leaks.

You might also consider changing the print function to take a reference to const so you don't copy the root when you pass it in. Otherwise, nice work.

Thanks! Now I've got two questions:
1) how can I create copying constructor (and do I really need it? - line print(root); couldn't be compiled so I thought it may be caused by the lack of copying constructor).
2) is the way how I use 'const' the proper way?

Code:

#include <iostream>
#include <vector>
using namespace std;

class Directory
{
 public:
    string name;
    vector<Directory> children; //I erased * in this line

    Directory(string name_) : name(name_) { };
    Directory(Directory *dir)
    {
       //First question:
       //I guess I should create here copying constructor
       //but I don't know how to do it
    }
};

int nesting = 0;

//void print(Directory *dir) {
                                   //Second question:
void print(const Directory *dir) { //do i use the word 'const' properly?
 for (int i = 0; i < nesting; ++i) cout << ' ';
 cout << dir->name << endl;
 ++nesting;
 for_each(dir->children.begin(), dir->children.end(), print);
 --nesting;
 //for (int i = 0; i < nesting; ++i) cout << ' ';
 //cout << endl;
}

int main(void) {
 /*
  - root
   - sub1
    - sub1.1
   - sub2
   - sub3
    - sub3.1
     - sub3.1.1
  */
 Directory root("root");
 Directory sub1("sub1");
 Directory sub11("sub1.1");
 Directory sub2("sub2");
 Directory sub3("sub3");
 Directory sub31("sub31");
 Directory sub311("sub311");
/*
 Directory *root   = new Directory("root");
 Directory *sub1   = new Directory("sub1");
 Directory *sub11  = new Directory("sub1.1");
 Directory *sub2   = new Directory("sub2");
 Directory *sub3   = new Directory("sub3");
 Directory *sub31  = new Directory("sub3.1");
 Directory *sub311 = new Directory("sub3.1.1");
*/ 
 root.children.push_back(sub1);
 sub1.children.push_back(sub11);
 root.children.push_back(sub2);
 root.children.push_back(sub3);
 sub3.children.push_back(sub31);
 sub31.children.push_back(sub311);
 
 print(root);
 system("pause");
 return 0;
}

No need for a copy constructor. Your class holds a string and a vector, both of which copy themselves correctly, so the compiler generated copy will be what you want.

Your print function needs to take a reference, not a pointer. (That's a C++ reference indicated with the & symbol instead of the * symbol.)

There might be an issue with your current implementation. You are pushing a copy of the Directories on to the children vectors. So when you do this:

Code:

 root.children.push_back(sub1);
 sub1.children.push_back(sub11);

A copy of sub1 is added to root, but sub11 is added to the original. This means when you get your print function working, sub11 won't be listed. This happens because of the switch to using objects instead of pointers. Now copies are being made, whereas before you were just storing pointers.

There are a couple potential solutions:

1. Go back to using pointers and new (sorry!). This means you'll have to manage the memory yourself, which can be dangerous. However, I have several tree type structures like this in my code and this first option is how I manage them. If you use this method it is important to understand what is going on.
   
   First, you'd want to leave root as an object, since there is no need to make it a pointer. Then, you'd make each subdirectory a pointer and allocate it with new like you did in post #10. You would make the children vector hold pointers again and push_back the subdirectory pointers like you did in that post. But you'd still have to solve the memory leak problem.
   
   To do that, I'd take advantage of the fact that Directory is a class. Let the destructor delete the pointers. Basically, in the Directory destructor loop through the vector and delete each pointer. This will cause the destructor of each child to be called which will then delete all its children and so on until the entire tree is destroyed. So whenever root is destroyed the whole tree will be cleaned up properly.
   
   You'd also have to disable copying. This is because if you hold pointers in your vector, if you make a copy then both copies will hold the pointers and both will try to delete them leading to double delete errors. To disable copying add a private section to your class and declare the two copy functions there. That way the compiler will complain if you try to copy accidentally:
   Code:

   private:
       Directory(const Directory& dir);
       void operator=(const Directory& dir);

2. Similar to #1, but use boost's ptr_vector or a vector<shared_ptr<Directory> >. These more advanced tools handle memory management for you. They are much better than raw pointers, but I know that in some cases you can't easily use non-standard library tools. Also, this might be a little too much learning required for a simple task.
   
   
3. Keep your code as is (post #12), but add the directories from the bottom up. This is a simple solution that only works if you remember to add all children to a Directory before adding it to its parent. If you don't, then you might be missing some directories.
   
   
4. Don't create all the directories at first, just create root. Then use a reference to the object in the vector. For example:
   Code:

    Directory root("root");
    root.children.push_back("sub1");
    Directory& sub1 = root.children.back();
    sub1.children.push_back("sub11");
    Directory& sub11 = sub1.children.back();
    // ...

5. Use a map instead of vector. Then you can just use the name of the directory to access it (remember to #include <map>):
   Code:

       // inside Directory
       map<string, Directory> children;
   
   // ...
   
    root.children["sub1"] = Directory("sub1");
    root.children["sub1"].children["sub11"] = Directory("sub11");

Like I said, I use option #1 for my tree structures, but I'd probably use option #5 if I could (my objects don't have names to allow them to fit into a map easily). Option #3 is the easiest and simplest if you want it to work quickly, but it gets harder to make sure it's right if you add stuff later. Option #2 is better than option #1 if you have the time to learn those libraries (it doesn't take that long, but if you're struggling with this it might be best to hold off on that). Finally, option #4 is a compromise between option #3 and #5.

Thanks! Which of these solutions will be the best for storing directories? I want to read directories from file which is created in this way "dir /s > myfile.txt" and creating process will be finished after reading it - I won't be changing directories structure. Then (after reading tree from the file) I want to create something like Norton Commander which uses this tree from RAM memory and allows me to navigate (so I need to extend my class Directory and use other variables like int size). And that's all - it is my project on Computer Programming .

Program of navigating the directory tree, displaying subdirectories and files in current directory. The program uses output of the dir/s command. It calculates total space occupied by files in subdirectories of selected directory and calculates estimated disk space occupied by the files considering the cluster size. The configuration data permitting the program to determine the format of dir/s output (dos and windows, a few versions) is stored in an external text file. The program should keep in RAM the directory structure and the file names of files in current directory.

And this is what I've got now:

Code:

#include <iostream>
#include <vector>
#include <fstream>
using namespace std;

class Directory
{
 public:
    string name;
    vector<Directory*> children;

    Directory(string name_) : name(name_) { };
};

int nesting = 0;

void print(Directory *dir) {
 for (int i = 0; i < nesting; ++i) cout << ' ';
 cout << dir->name << endl;
 ++nesting;
 for_each(dir->children.begin(), dir->children.end(), print);
 --nesting;
 //for (int i = 0; i < nesting; ++i) cout << ' ';
 //cout << endl;
}

int main(void) {
 /*
  - root
   - sub1
    - sub1.1
   - sub2
   - sub3
    - sub3.1
     - sub3.1.1
  */
/* Directory *root   = new Directory("root");
 Directory *sub1   = new Directory("sub1");
 Directory *sub11  = new Directory("sub1.1");
 Directory *sub2   = new Directory("sub2");
 Directory *sub3   = new Directory("sub3");
 Directory *sub31  = new Directory("sub3.1");
 Directory *sub311 = new Directory("sub3.1.1");
 
 root->children.push_back(sub1);
 sub1->children.push_back(sub11);
 root->children.push_back(sub2);
 root->children.push_back(sub3);
 sub3->children.push_back(sub31);
 sub31->children.push_back(sub311);
 
 print(root);
*/ 

   ifstream fin("myfile.txt");
   string line;
   int counter=0;

   string nameMainDir; //it contains line " Directory: C:\root"
   //where 'Directory' is word dependent on language version of dir/s
   //and 'myRoot' is the name of main directory in our tree
   size_t lengthOfNameMainDir; //I use it during next iterations
   string myRoot; //it contains only name 'root'
   vector<string> nameUpperChildren; //we've got root and its children UpperChildren
   int isntItNewBlock=0; //inside the file there are blocks
   //(every block begins with " Directory: " C:\root[...]")
   //0 - it is new block, 1 - first line of new block, 2 - second,
   //3 - third, 4 - it is inside this block, 5 - last line
   string rhsDir; //name of the most RHS directory in the line

   //don't read first three lines
   for (int i=0; i<3; i++) {getline(fin,line);}
    
   while(getline(fin, line))
   { 
      //-----------------------------------------------------------------------
      //first iteration - it checks version of dir/s and reads name of main dir
      //-----------------------------------------------------------------------   

      if (counter==0) //if it is first iteration, it reads nameMainDir
      {
         nameMainDir = line; //it reads first line
         lengthOfNameMainDir=line.size(); //here I check size of the line
         int i=lengthOfNameMainDir;
         do { i--; } while (line[i]!=(char)92); //it counts from end of line
                                                //to first use of symbol char(92)=='\'
         myRoot=line.substr((i+1),(lengthOfNameMainDir-i)); //if writes name of root 

directory                                      
         counter++; //it disables entering this if any more
         
         Directory *root = new Directory(myRoot); //it creates root
         cout<<"[[["<<myRoot<<"|||"<<nameMainDir<<"]]]"<<endl;
      }
      
      //----------------------------------------------------
      //main part of this while - it reads tree of directory
      //----------------------------------------------------
  
      //if the line begins with nameDir, then it contains name of new directory

      if (counter != 0) //I don't use else because it won't work for the very first line
      {  
         switch (isntItNewBlock)
         { //I haven't designed this switch yet :)
            case 0: //it reads name of the RHS directory
               break;
            case 1: break; //empty line
            case 2: break; //line with .
            //I need to continue writing code from this line
         }
      }
   }
   
   cout<<"::End of file::";
   fin.close();
 
   system("pause");
   return 0;
}

Greetings!

Since you build the tree dynamically based on the dir /s text, #3 is out. I don't see a need for a map here (#5), since you won't really ever need to look up a directory by its name. #4 doesn't seem like a good idea either.

So I'd go with #1 or #2. You're already working on #1 now, so that's good. I'd write your destructor and declare the private copy functions as I mentioned in my previous post. I'd do that now, then use some simpler code to make sure you have no memory leaks like you did earlier.

I'd still separate out the code that reads in the dir /s text until you get the tree working with the simple code. You're pretty close, it shouldn't be too much more.

Once the destructor is working, you'll have to so some more work on your file reading code. The first thing I notice is that you have "Directory *root = new Directory(myRoot); //it creates root" inside your if block. That root pointer will go out of scope when the if block is done, so you won't be able to access it later. Declare root above the if block (and probably above the while block).

Another very minor point is from the line while (line[i]!=(char)92). Use '\\' instead of (char)92.

Obviously you still have a way to go, but you seem to be getting close to having your tree structure setup.

You might want to consider using a function like print for reading in your directories. Notice how it recursively handles everything cleanly. I would make the nesting a parameter of the function instead of a global variable, but otherwise that code is a good example. For reading in, you'd have to pass the current directory, the filestream, and probably the current nesting level as well. You can then load up all child directories and exit the function when there are no more.