Re: C++ library extensions (was: Re: Garbage Collection - The Trash Begins To Pile Up)
Lourens Veen wrote:
Le Chaud Lapin wrote:
I've tried to find a data structure named "hierarchy", but I couldn't
find any. So I still don't know what you are talking about.
Imagine that you are president of a large corporation, and that your
administrative assistant is asked to produce a (very large) document
showing the command structure among all 500,000 employees. Then
suppose you use that document to ask questions such as:
1. "Who is the boss of E1?"
2. "What is the salary of E2?"
3. "Is E3 in the same group as E4?"
4. "How many direct subordinates does E5 have?"
5. "Doese the group of subordinates of E35 include E117?"
5. ...(many, many questions like this)
A good representation of the structure is a hierarchy. Alternatively,
you could use an Oracle Database with tables, a massive spreadsheet
with redundancy everywhere, but a hierarchy simply makes sense (and is
intuitively optimal in terms of memory consumption).
Perhaps you could describe the data structure. What data elements are
in it and how are they related? Can you traverse the data structure
and if so, how? How do you insert elements? How do you delete them?
The visual imagery of the structure would be a DAG, but conceptually,
it is not. It could be considered a graph, but conceptually, it is
not, not any more than a binary tree could be considered a graph just
because it looks like a graph. You wold not, for example, be using any
of the least-cost algorithms on a binary tree. You *could* do that,
but all the researchers who are trying to do work on fast lookup using
binary trees would fail to see the point.
I'm getting the feeling that you are proposing a very
general "hierarchical data structure" concept, but even such a
general thing would have to have an interface which can be described.
Yes, I am. Actually not proposing. I simply mentioned that it is
something that is missing from STL, and therefore I had to make my own.
The operations would be things like looking up a node in the tree, and
asking specific information about it.
If you are Unix, imagine representing the entire file system in a C++
RAM object. That would be a single-rooted hierarchy where / is the
root.
If you are on Windows, imagine representing the entire file system of
the C:\ drive as a C++ RAM object. Excluding the name of the drive
itself (C:\), that would be a multi-rooted hierarchy where the files
and directories at the root of C:\ are the roots of the hierarchy.
Now all operations that an OS designer would be expected to provide for
a file system could be applied to the C++ structure:
1. Does a file exist?
2. What is size of a file?
3. When was file created
4. Enumerate the children of a given directory.
etc.
All operations would have to be fast.
-Le Chaud Lapin-
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]