Vectors, trees, and dynamic memory

Suppose you have a node defined like:
1
2
3
4
5
struct node
{
	string value;
	vector <node *> subnodes;
};	//end node 

that you used to build a tree. Now, let's say that you are done with the tree. From there, I have two questions:
1.) If you started the declaration with something like node tree;, would you still need a deletion function?
2.) If the answer to the first question is "yes", and you decided to make a deletion function that deletes via post-order traversal (child nodes, or leaf nodes, first), and you define your deletion function like:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void deletetree(node * a)
{
    if (a != 0)
    {
        if (a->subnodes.size() == 1)
        {
            deletetree(a->subnodes[0]);
        }   //end if
        else if (a->subnodes.size() > 1)
        {
            for (int pos = 0; pos < (int)(a->subnodes.size()); pos++)
            {
                //delete the node
            }   //end for
        }   //end else if
        else
        {
            delete a;   //delete the node
        }   //end else
    }   //end if
}   //end if 
, does the node pointer disappear from the vector when you delete it?
If you started the declaration with something like node tree;, would you still need a deletion function?

If nodes were allocated with new, yes, they would still need to be deleted, regardless of how the initial node was allocated.

, does the node pointer disappear from the vector when you delete it?

No. To remove an element at an arbitrary position from a vector you use erase (and no, using erase does not cause delete to be called on pointer elements.)
So, you would have to add
1
2
deletetree(a->subnodes[0]);
a->subnodes.erase(a->subnodes.begin());

to the inside of the for loop (so that I am emptying the vector as I am freeing the space)? I wish vectors could have their own destructors (that would also apply to their pointer elements) in cases like this! I would have had my function be declared as
void createtree(node & a, string dir) but then the question would be whether I could traverse the tree by checking for non-null pointer values...
It looks like this works now (as per your advice)! Thanks for the quick response!!
Last edited on
When the node gets out of scope, its destructor will be called.
That destructor will kill the vector and its elements (note that the elements are pointers)

So, put that function in your destructor and don't call `erase()' (inefficient)

> I wish vectors could have their own destructors (that would also apply to their pointer elements) in cases like this!
Either use an especial container or smart pointers.
There are cases where you are not responsible of the lifetime.


Edit: ¿why are is `size=1' a special case?
Last edited on
>Edit: ¿why are is `size=1' a special case?
It is a special case because there should not be a for loop for that condition. (If there was, it would be an infinite one.)
It would not be infinite, it would only execute one time.
Read for (int pos = 0; pos < 1; pos++)

ps: my english is getting worse.
Last edited on
If the idea is to remove the node pointed to by a and all of it's sub-nodes, then the function is wrong.

It only removes a if it has 0 sub-nodes.

I would expect the function to look more like:

1
2
3
4
5
6
7
8
9
10
11
12
13
// There is no good reason to bother erasing elements from the vector here,
// since it will be immediately destroyed anyway.
void directorytree::deletetree(node * a)
{
    if (a)
    {
        for ( unsigned i = 0 ; i < subnodes.size() ; ++i )
            deletetree(a->subnodes[i]) ;

        std::cout << "node for " << a->value << " deleted successfully!\n" ;
        delete a ;
    }
} 


I wish vectors could have their own destructors (that would also apply to their pointer elements) in cases like this!


You could've stored nodes instead of pointers to nodes. Failing that, you could've stored smart pointers instead of raw pointers.


Oh yeah, that would be because we are INCREMENTING pos, so it would automatically terminate. Maybe this is where I should post my full code so we can analyze why only part of the tree is showing up (it will crash on the last statement):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <iostream>
#include <windows.h>
#include <cstring>
#include <new>
#include <vector>
#include <stack>

using namespace std;

struct node
{
    string value;
    vector <node *> subnodes;
};   //end node

class directorytree
{
    private:
        stack <HANDLE> hstack;
        stack <WIN32_FIND_DATA> fdstack;
        HANDLE h;
        WIN32_FIND_DATA fd;
        node thenode;
    public:
        directorytree(node);
        void createtree(node*, string);
        void preorder(node *);
        void deletetree(node *, node*);
};  //end directorytree

directorytree::directorytree(node n)
{
    thenode = n;
}   //end constructor

void directorytree::createtree(node * a, string dir)
{
    if (a != 0)
    {
        a->value = dir;
        h = FindFirstFile((a->value + "/*.").c_str(), &fd);
        while ((((string)fd.cFileName == ".") || ((string)fd.cFileName == "..")) && (FindNextFile(h,&fd)))
        {

        }   //end while
        if (((string)fd.cFileName != ".") && ((string)fd.cFileName != ".."))
        {
            if (fd.dwFileAttributes != 16)
            {
                a->subnodes.push_back(0);
                createtree(a->subnodes[0], dir);
            }   //end if
            else
            {
                hstack.push(h);
                fdstack.push(fd);
                do
                {
                    dir = a->value + '/' + (string)((fdstack.top()).cFileName);
                    a->subnodes.push_back(new(nothrow)node);
                    createtree(a->subnodes.back(), dir);
                }   //end do
                while (FindNextFile(hstack.top(), &(fdstack.top())));
                hstack.pop();
                fdstack.pop();
            }   //end else
        }   //end if
        else
        {
            a->subnodes.push_back(0);
            createtree(a->subnodes[0], dir);
        }   //end else
    }   //end if
}   //end createtree

void directorytree::preorder(node * a)
{
    if (a != 0)
    {
        cout << a->value << endl;
        if (a->subnodes.size() == 1)
        {
            preorder(a->subnodes[0]);
        }   //end if
        else
        {
            for (int pos = 0; pos < (int)(a->subnodes.size()); pos++)
            {
                preorder(a->subnodes[pos]);
            }   //end for
        }   //end else
    }   //end if
}   //end preorder

void directorytree::deletetree(node * a, node * parent)
{
    if (a != 0)
    {
        for(int pos = 0; pos < (int)a->subnodes.size(); pos++)
        {
            deletetree(a->subnodes[0], parent);
            a->subnodes.erase(a->subnodes.begin());
        }   //end for
        if (a != parent)
        {
            cout << "The node for "<<a->value << " got deleted."<<endl;
            delete a;
        }   //end if
    }   //end if
}   //end deletetree

int main()
{
    node tree;
    directorytree dirtree(tree);
    dirtree.createtree(&tree, "C:/Users/owner/Desktop");
    dirtree.preorder(&tree);
    dirtree.deletetree(&tree,&tree);
    return 0;
}   //end main 

EDIT: Nevermind! cire solved the problem; I wish his message could have appeared earlier (when I was sending mine)!!
Last edited on
There are some pretty glaring design flaws here.

Honestly, I would begin by starting over. Trying to stick a tree implementation into this class is a mistake.

Actually checking to see if operations have been successful would also be recommended.

What exactly are you trying to accomplish?

The code works as per your suggestion. (Did you not read where I said that your suggestion solved my problem?) As for what I am trying to do, I am trying to make a directory tree to be searched for files that look like this:
this+file%2Bneeds%20renaming.docx
. Those files will have the undesired characters (and strings) replaced with ' '. That would mean that my class that has the renaming action would just be friends with this one so that it could access the tree. I could just bring the struct contents into the class and re-work the class so that the entire tree is private. Of course, this wouldn't do much except deter hackers from figuring out my tree-making method. As for testing what I had, which is slightly different from my code on here, I tested it numerous times, especially my createtree(). I tested my createtree() before I threw it in a class.

I could just go Java-style and give this class its own "main()"....

I would've gone with something more like the following. Notice that none of the internals of FileIterator are exposed to the code in main.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <Windows.h>
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>

const std::string currentDirectory(".") ;
const std::string previousDirectory("..") ;

class FileIterator
{
public:
    struct FileInfo
    {
        std::string fileName ;
        std::string path ;
    };

    FileIterator( const std::string& path, const std::string& wildcard, const std::vector<std::string>& filters )
        : _filters(filters), _directories(1,path), _wildcard(wildcard), _directoryIndex(0), _startingDirectory(true) 
    {
    }

    bool getNext( FileInfo & f )
    {
        WIN32_FIND_DATA ffd ;
        for ( ; ; )
        {
            if ( _startingDirectory )
            {
                while  (_directoryIndex < _directories.size() && 
                       (_findHandle = FindFirstFile((_directories[_directoryIndex]+_wildcard).c_str(), &ffd)) == INVALID_HANDLE_VALUE )
                {
                    ++_directoryIndex ;
                }

                if ( _findHandle == INVALID_HANDLE_VALUE || _directoryIndex == _directories.size() )
                    return false ;

                _startingDirectory = false ; 

                if ( _shouldReturnFile( ffd ) )
                {
                    f.fileName = ffd.cFileName ;
                    f.path = _directories[_directoryIndex] ;
                    return true ;
                }
            }
            else
            {
                if ( !FindNextFile(_findHandle, &ffd) )
                {
                    _startingDirectory = true ;
                    ++_directoryIndex ;
                }
                else if ( _shouldReturnFile(ffd) )
                {
                    f.fileName = ffd.cFileName ;
                    f.path = _directories[_directoryIndex] ;
                    return true ;
                }
            }
        }
    }


private:

    bool _shouldReturnFile( const WIN32_FIND_DATA& f )
    {
        if ( f.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY )
        {
            if ( !(f.cFileName == currentDirectory || f.cFileName == previousDirectory) )
                _directories.push_back( _directories[_directoryIndex] + f.cFileName + '/' ) ;
            
            return false ;
        }

        return  _matchesFilters(f.cFileName) ;
    }

    bool _matchesFilters( const std::string & s )
    {
        for ( auto& filter : _filters )
        {
            if ( std::string::npos != s.find(filter) )
                return true ;
        }
        return false ;
    }

    std::vector<std::string> _filters ;
    std::vector<std::string> _directories ;
    std::string _wildcard ;

    HANDLE _findHandle ;
    unsigned _directoryIndex ;
    bool _startingDirectory ;
};


int main()
{
    char const* path = "C:/Projects/TestDir/" ;
    char const* wildcard = "*" ;

    char const* filterArray[] = { "+", "%20", "%2b" } ;
    const unsigned filterArraySize = sizeof(filterArray) / sizeof(filterArray[0]) ;

    std::vector<std::string> filters(filterArray, filterArray + filterArraySize);

    FileIterator fileIterator( path, wildcard, filters) ;
    std::unordered_map<std::string, std::vector<std::string>> fileMap ;

    FileIterator::FileInfo fi ;

    while ( fileIterator.getNext(fi) )
        fileMap[fi.path].push_back(fi.fileName) ;

    for ( auto& dir : fileMap )
    {
        std::cout << "Directory: \"" << dir.first << "\"\n" ;
        for ( auto & file : dir.second )
            std::cout << "\t\"" << file << "\"\n" ;
    }
}




Directory: "C:/Projects/TestDir/"
        "New+text+document.txt"
        "Old%2bTest+document.txt"

Directory: "C:/Projects/TestDir/SubDir/"
        "Ab+ra+cad.txt"


Topic archived. No new replies allowed.