STL tree implementation -directory structure

[shane]

From searching around, Ive seen this question asked numerous times, but
havent seen a usable answer unfortuantly.

What Im trying to do is something I would have thought would be quite
common, but there just seems to be no information on the topic that I can
find. Basically I need to store a directory structure in memory, from a flat
list of files and paths. ie given:

C:\dir\dir1\abc.txt
C:\dir\toop.txt
C:\temp\acd\test.txt

etc I need to create a directory structure, and represent this in a
tree-view control and give it basic 'explorer' style functionality. I think
I would need to use either map or hash_map, which itself contains a link to
another map. I have started with the following:

typedef stdex::hash_map<std::string, hm> hm;

Obviously thats not really possible, so instead I have:

typedef stdex::hash_map<std::string, void*> hm;

And just use NULL if there are no children, or create a "new" hm if there
are children. The std::string is the full path. I havent really tried this
fully, but I would suspect it would work. For holding the files, I would
probably just use a pair instead, which has both a std::list and a void* to
another hash_map/list.

While I think this would probably work, I get the feeling I am reinventing
the wheel here, yet I havent seen anything like this anywhere else. Which
gives me the impression I am probably doing something wrong :) Surely there
is an example for holding a hierarchial file directory type structure in
memory somewhere around? All Ive seen is overly complex amateur
implementations of fully fledged tree templates. Can someone give me a hand
with this please ?

Cheers,
Shane

[Donovan Rebbechi]

On 2005-03-20, shane <in*****@hotmail.com> wrote:

From searching around, Ive seen this question asked numerous times, but
havent seen a usable answer unfortuantly.

What Im trying to do is something I would have thought would be quite
common, but there just seems to be no information on the topic that I can
find. Basically I need to store a directory structure in memory, from a flat
list of files and paths. ie given:

C:\dir\dir1\abc.txt
C:\dir\toop.txt
C:\temp\acd\test.txt

etc I need to create a directory structure, and represent this in a
tree-view control and give it basic 'explorer' style functionality. I think
I would need to use either map or hash_map, which itself contains a link to
another map. I have started with the following:

typedef stdex::hash_map<std::string, hm> hm;

Obviously thats not really possible, so instead I have:

typedef stdex::hash_map<std::string, void*> hm;

So you're trying to get around the "infinite recursion" issue, but you have
another problem also -- managing those pointers. As is, you don't have a
class that manages your memory.

Both these problems really call for a wrapper class you can make the
template parameter a pointer to your wrapper (you would need a wrapper to
make the class interface typesafe anyway), so the layer of indirection
takes out the self reference.

But since you can put type information in that pointer, you can make it
a smart pointer instead, so you can get around memory management problems.

class X {
typedef stdex::map<std::string, some_smart_pointer<X> > hm;
hm themap;
public:
// put some wrappers for your member functions here
};

depending on the details it might be convenient to use private inheritance.

Cheers,
--
Donovan Rebbechi
http://pegasus.rutgers.edu/~elflord/

[shane]

>>

typedef stdex::hash_map<std::string, hm> hm;

Obviously thats not really possible, so instead I have:

typedef stdex::hash_map<std::string, void*> hm;

So you're trying to get around the "infinite recursion" issue, but you
have
another problem also -- managing those pointers. As is, you don't have a
class that manages your memory.

Both these problems really call for a wrapper class you can make the
template parameter a pointer to your wrapper (you would need a wrapper to
make the class interface typesafe anyway), so the layer of indirection
takes out the self reference.

But since you can put type information in that pointer, you can make it
a smart pointer instead, so you can get around memory management problems.

class X {
typedef stdex::map<std::string, some_smart_pointer<X> > hm;
hm themap;
public:
// put some wrappers for your member functions here
};

depending on the details it might be convenient to use private
inheritance.

Thanks for the info. Theres a possibility I may not even need to use the
tree structure, I still havent finalised the implementation details.

What I found was the following code would compile and run ok:

extern class treeitemsx;
typedef std::map<std::string, treeitemsx> mtypex;
class treeitemsx {
public:
mtypex mtree;
} mbase;
typedef std::pair<std::string, treeitemsx> Map_Pair;

Note the lack of a *. This seems like it shouldnt run at all. ie, as soon as
you insert a value into the mtree, it should run out of stack space.
However, the map object doesnt try and create a treeitemsx object until you
do an insertion so it should be ok. I dont explcitly set the map_pair.second
value when I do an insertion, but I guess it gets created anyway. ie

Map_Pair x;
x.first="string";
mbase.mtree.insert(x);

Would this kind of code be dangerous? Im thinking about putting a bool in
the class to indicate whether there are children or not, but I guess I could
just check if mtree is empty. I suppose the disadvantage of using this over
a pointer is it has a child class with a map object even if its not
necessary (ie in the case of no children). Whereas with a pointer scheme you
can just use NULL.

However, would this scheme manage memory ok? if mbase went out of scope,
would all the nested mtree's be freed?

[Donovan Rebbechi]

On 2005-03-20, shane <in*****@hotmail.com> wrote:

Thanks for the info. Theres a possibility I may not even need to use the
tree structure, I still havent finalised the implementation details.

What I found was the following code would compile and run ok:

extern class treeitemsx;
typedef std::map<std::string, treeitemsx> mtypex;
class treeitemsx {
public:
mtypex mtree;
} mbase;
typedef std::pair<std::string, treeitemsx> Map_Pair;

Note the lack of a *. This seems like it shouldnt run at all. ie, as soon as
you insert a value into the mtree, it should run out of stack space.
However, the map object doesnt try and create a treeitemsx object until you
do an insertion so it should be ok.
I think it works for the same reason as my solution. It doesn't run out of
stack space because the map doesn't really contain an item of type treeitemsx,
it allocates them dynamically. To put it another way, it contains pointers to
the free store where more maps may be created. So you get a similar indirection
to what you have in my solution.
Would this kind of code be dangerous? Im thinking about putting a bool in
the class to indicate whether there are children or not, but I guess I could
just check if mtree is empty.
First, the fact that you want to be able to check whether the tree is empty
or not suggests that you should make a member function that does that.

bool empty () const { return mtree.empty(); }

When you have a choice between a member function and a data member, it's
good practice to put a member function in regardless (perhaps make it an
accessor)

Generally, it's good practice to avoid having redundant members in a class,
because it makes class invariants more complicated. For example, in this
case, any function that adds to or erases from mtree would need to check
whether mtree was empty and update the data member. In this instance, it
doesn't really help much to add the data member (if the computation were
very expensive, that would be an argument for having the data member).
I suppose the disadvantage of using this over
a pointer is it has a child class with a map object even if its not
necessary (ie in the case of no children). Whereas with a pointer scheme you
can just use NULL.
I worked out what you mean ... but your usage of "child class" in this
context is incorrect.
However, would this scheme manage memory ok? if mbase went out of scope,
would all the nested mtree's be freed?

Yes, it does what you want it to do.

Cheers,
--
Donovan Rebbechi
http://pegasus.rutgers.edu/~elflord/

[Phil Staite]

shane wrote:

From searching around, Ive seen this question asked numerous times, but
havent seen a usable answer unfortuantly.

What Im trying to do is something I would have thought would be quite
common, but there just seems to be no information on the topic that I can
find. Basically I need to store a directory structure in memory, from a flat
list of files and paths. ie given:

C:\dir\dir1\abc.txt
C:\dir\toop.txt
C:\temp\acd\test.txt

I think what you have is structurally a tree. But what you may want to
look at to represent it is a "composite" pattern. That is, a
directory-entry object may contain file entries (eg. names, paths, other
file stats) and other directory entries. (eg. subdirectories)

As such, the directory entry objects will build up their own N-way tree,
and internally you can use one or more STL data structures (eg. vector
or list) to maintain the contents.