Re: C++ library extensions (was: Re: Garbage Collection - The Trash Begins To Pile Up)
Lourens Veen wrote:
Le Chaud Lapin wrote:
Kevin Hall wrote:
Le Chaud Lapin wrote:
OK, I'll bite. What are these dozen or so classes?
2. Monarchy<> (what you would call a single-rooted tree)
There are about a gazillion different kinds of trees though. Would
there be different implementations possible, or do you want a library
with all sorts of trees? What would the interface look like?
3. Polyarchy<> (what you wold call a multi-rooted tree)
A Directed Acyclic Graph? But why not other types of graphs then? Or
do I completely misunderstand?
I do have a Graph<> class. It was one of the most frustrating classes
I had to write, not because it difficult (though it was), but because I
tried to implement Dijkstra's and other algorithms using
priority_queues according to computer science books, which turns out to
be wrong. It is not possible to implement Dijkstra's algorithm using
priority queues. What is required is a data structure that did not
even have a name, so I called it Priorititized_Associative_Set, which,
in STL language, would be a map<> where the elements are also
accessible via priority that is specified upon insertion. This
structure could conceivable be made using maps<> and sets<> and some
fancy cross-references. But I wanted something that was implemented
the structure in the raw, just beneath the abstraction barrier of the
interface provided.
But back to your point, this is precisely the reason that I avoided
using the word "tree". What I want to convey with a name of the the
data structure is very clear in my head. But if I open my mouth and
utter "tree", there is strong possibility of miscommunication, because
that word immediately evokes decades-old preconceived notions and
definitions of what a tree is. So I had to pick something else.
Some would say the data structure is a DAG. Some would say, "Oh it is
a binary tree." Some will say, "No, no, a binary tree is an
implementation of a set. He means a hierarchy." Programmers who never
had the luxury of using a templated hierarchy might say, "No, he
certainly can't mean that. STL does not have that, and if it did, it
would be slow."
I do mean a hierarchy. And it is not slow at all. And it is very
liberating to have such a thing. Imagine representing any kind of
taxonomy, for instance.
-Le Chaud Lapin-
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]