Re: Sequence container with fast random access and fast insertion/removal (wherever)
comocomocomo wrote:
I've written an STL-like sequence container for those cases where list
and vector/deque are slow due to intensive use of _both_ random access
and insertion/removal (at ends or wherever):
Is this anti-STL-spirit?
No.
Do you think it is useful?
Yes.
Don't you think there's a complexity gap between vector/deque and list?
Apparently there is. :)
Two quick notes about your code. :
1. Do you really need a dummy node for root? If you use just a plain
pointer to act as the anchor, it is conceptually more regular.
2. Unless you have another reason to keep the heights, I would make
insert and delete recursive to eliminate this extra field.
On a related note, I'm sure many people will disagree, but my gut
feeling is that the height of a binary tree with 1 node should have
been defined as 1. Most algorithms books define it as 0. This
introduces irregularities that manifest in the implementation. It's
almost as if the implementation tries to give you a hint that 1 node
should mean height 1.
One can also see this by exercising a little discipline when speaking
about binary trees. For example, instead of calling the left or right
pointer to a node "the child node", call it what it is, a pointer to
the child node. [Not maintaining parity between names and what they
refer to is a *HUGE* source of conceptual inconsistencies in C++ design
in general]. Saying that the height of binary tree is the number of
links that must be traversed from the root node to the object node
implies that there is at least one node from which to traverse. But if
there is a such thing as a population of the tree, and 0 is a valid
population, there are trees with no nodes. Then what? Does a
zero-population tree have any nodes? Does it still have a dummy node to
assist with linkage to no nodes?
The height of a binary tree should have been defined as the number of
links that must be traversed to get to a node [STOP]. Then, one could
say, "Nodes are reachable by traversing pointers. Then one could say,
if there is a 1-node tree, then there must be a pointer to it somewhere
- the anchor." So implicit in the structure of binary trees, there is
always an anchor, a pointer to start things off. If that pointer is
null, the tree is empty, and contains no node. If not, then it points
to 1 node of potentially many, but if there is one node, then one link
has been traversed - the height is 1.
Therefore the height of a binary tree should have been defined as the
number of *levels* present in the tree.
For amusement, I went back through my data structures book, "Data
Structures & Their Algorithms" by Harry R. Lewis and Larry Denenberg
and started redoing some of the formulas to see what they would look
like with this change, and not only do some of the formulas come out
slightly simpler (yes this is my subective opinion), but certain
definitions like "extended binary trees" become moot in certain
situations.
Naturally, no one is going to go back and redress this definition. All
the formulas would have change, including the bound on maximum height
of AVL tree as function of its population (currently 1.44 log(n) IIRC)
-Le Chaud Lapin-
http://en.wikipedia.org/wiki/Occam's_razor
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]