Re: C++ library extensions (was: Re: Garbage Collection - The Trash Begins To Pile Up)
Lourens Veen wrote:
You know, I would use an XML document. Of course, I'm doing an MSc
thesis on exactly that, so I would :-). All the queries above are
easily expressed in XPath or XQuery. And you can also ask things
like "List everyone under 'sales'" or "List everyone under 'sales'
who is a manager, regardless of at which level". Incidentally, nobody
stores XML documents internally as trees (even though conceptually
they are), because querying for ancestor-descendant relationships is
much more efficient when stored in different ways.
Aha!!! You cannot imagine how close this is to a conversation I had
with a colleague a while back. I have been doing my own "XML". The
efficiency thing you mention, I know what it is. I do not have that
problem. All of my operations are O(n). This is what I meant about
fundamental. There are data structures that should exist, because we
use them everyday but do not name them, but they do not exist, because
not everyone has arrived at the conclusion that they are there. So
there is much reinvention. The essence of XML though, if you ignore
the human-readable aspect, is captured in a data structure that should
be in a standard library.
At any rate, XML is a popular subject that seems to be very similar to
what you want, so if you want some terminology perhaps you should
look there. "Semi-structured data" is the general term in use there:
there is some structure, but it's much looser than an SQL table or an
OO database unless you explicitly use schemas to constrain the
possibilities.
No need to look. I already have the structure. I watched the rise of
XML, how people got so excited about it, not really understanding
exactly what it was that made them excited. Some actually thought the
XML file, if made sophisticated enough, would become intelligent and
start walking. ;)
Lookup by what? Do you want to search for nodes with a specific value
for a certain attribute, or do you just want to specify a path from
the root to the node?
Path from root node.
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.
As Mirek said, I don't see the difference. If you have a company
hierarchy with multiple roots at the top that are the CEO, the COO,
the CTO, and the CFO then you might as well model that is a tree with
a single root (the company) with four children (the CxO's). Perhaps
it's useful to make this distinction when modelling, but I think the
distinction is too small to carry it over to the implementation
level.
Right. The concept is more important that the implementation. In fact,
to implement my single-rooted hierarchy, I inherit from the
multi-rooted hierarchy, and tweak the member function set to prevent
adding multiple items in the single-rooted hierarchy. You might still
say that, that might be something that the programmer could have done
himself, but as it turns out, making two separate classes simplify the
member functions of each.
-Le Chaud Lapin-
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]