Re: Standard iterator model and tree<>
On May 8, 9:50 pm, Seungbeom Kim <musip...@bawi.org> wrote:
Le Chaud Lapin wrote:
What do you mean by the name Rottweiler? A breed of dog, or something
else? I'm afraid your analogy is not working for me, because the name
doesn't mean anything in the context of our discussion.
That was actually my goal - to chose a name so absurd that it would
not invoke any preconceived notions of what an X<> means. I've been
calling X<> tree<>, but that is not what it is. Hierarchy<> might
work, but some people (not you) are stubborn, and when I tried to use
that, they (my colleagues) immediately said, "you mean a tree<>." For
the record, I call my tree<>, Monarchy<>.
There's no problem in defining a specific data structure of your own
that has specific requirements and capabilities. But it doesn't
represent the whole class of things that people expect from the concept
"tree".
Yes, B. L. Whorf would be pleased with our current discussion. ;)
[Names determine what we think about].
So, the tree that a taxonomist use is a specific type of a tree, and
different from a binary tree that a computer scientist might be
interested in, but they both are valid abstractions of trees. So it
doesn't make much sense to have one called "tree" and another not called
"tree". And that's why I argue that it's hard to have one "tree" that
suits all needs.
Ok, so the market has been cornered<> for tree<>.
I must mention that I have a high-performance tree<> in my personal
library that does not conform to STL.
You keep saying that, but can you please give answers to my questions
this time:
- What does it mean to "conform to STL"?
- What in your tree<> class makes it non-conforming to STL?
Again, I never use STL, but it seems that there are expectations on
structures that play roles of containers. In particular, the
iterators are external. In my Monarchy<> class, there is only one
iterator, and it is internal.
In a tree in its most general sense, searching for an element should
take O(n) in the worst case. Making a specific type of search faster
requires some additional requirements, as binary trees do. And wasn't it
you that considered such a requirement as "an inappropriate breach of
abstraction barrier"?
No, this is what I meant by abstract data type (ADT). On one level,
there is the what the user of the library sees, a set<> for example,
and on another level, there is what the designer of the class
concocts, in this case, a red-black "tree". What happens behind the
interface of set<> is acceptable so long as the contract is
satisfied. One of the contracts is O[logn] searching for set<>
What's the idea behind the tree<> class that you have?
How is it represented and what operations does it support?
My class Monarchy<> is what one would imagine, one node at the top,
with any number of children for each node. If the template argument
is of type string, then it is precisely what a taxonomist might
imagine. At a particular level, if one wants to see if a sibling is
present, that can be determined in O[log(n)] time.
Beyond that, there is not much else for Monarchy<> except the usual
constructor, destructor, equivalence, graft, merge, adopt, orphan,
delete, etc...basically all the operations one might imagine for such
a data structure.
Concerning the question, Why would anyone want such a thing...that's a
different matter altogether. ;)
-Le Chaud Lapin-
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]