Re: std::string bad design????
John G Harris wrote:
Have you never had to help someone who's discovered he needs two
concurrent iterators into the same data structure? How would you put an
unlimited number of iterators inside a container?
Yes, myself. I have multiple options. In cases where I have indexing
on my containers (List, Set, etc.), I use unsigned int index;
Red_Black::Set<Foo> rbs;
rbs[i]... // yields element with index i beginning at 0 by const
reference.
If I have a map<> like structure, I can use indexing, or I can keep a
key on the outside of the map and use that.
Red_Black::Associative_Set<unsigned int, Foo> rbas;
rbas.mapping(3) // Returns RHE of rbs that '3' maps to.
In cases where the programmer is really picky and wants to avoid
duplication of keys, one inside the container and one outside the
container, there is nothing to stop him/her from simply taking the
address of the returned element and using that element in another
search. This quickly leads to a discussion on multi-threading. My
solution to keep multi-threading and C++ containers completely
functionally orthogonal. As far as I am concerned, mutual exclusion is
a problem that applicable far beyonds someone want that their map<> be
protected. I think one reason why programmers are so quick to quip that
C++ lacks multi-threading protection is:
1. They want it, cleanly, easily, and right now.
2. They don't have it.
Those two reasons are not, IMO, sufficient, to justify integrating it
directly with STL, even if that were possible to do in a portable
fashion (portable for library writer).
is the notion
that all containers are linear, in the "movement" of the iterator is 1
dimensional.
When you visit every element in a container most computers force you to
visit elements one at a time - in a sequence. Certainly your normal
desktop PC does. Even if the order is different next time you visit,
it's still a sequence.
I don't think I meant linear.
But trees are containers, very useful containers, and we
do not have a tree<> template in STL.
Trees are just a special case of a general structure (acyclic, multiple
links between nodes). I want the general case. I doubt if you would want
the overheads.
Hmm..I do not think so. While reading books on data structures, I
realized that one has to be very careful in classifying these
structures. There is simply too much opportunity for mistakes. The
two biggest mistakes I have found is that computer scientist defined
depth of binary tree with 1-node to be 0 (I think it should be 1). The
other is that "Dijstra's algorithm can be implemented using priority
queues (It can't. It requires a data structure that does not even have
a name).
Do you have a tree class template that lots of other people will want?
I have one. Not sure anyone would want to use it. It is does not
follow the STL pattern, among other things.
What will you say to those who want something different?
What I always say: "I have no idea why you want to use that. It's
buggy, and there's a 10% chance it will crash." :)
I suspect that the reason we
don't is because it would illuminate the fact
algorithms-are-universally-applicable model is not so universal,
The algorithm for multiplying two integers is not so universal, but
no-one thinks that that lack is illuminating.
Programmers want good primitives. So if you have
Integer i = 9293920392002; Integer j = 2376283; Integer k = i % j
A lot of people, cryptographers especially, would like that.
The word "universal" is often abused but the idea that sort, etc., don't
need to know how the data is reached covers a lot of ground.
Well, I do not either. My map<> is called Associative_Set. My list<>
is called List<>.
If I do a search of one of my AS's, i have no idea how the data is
reached either. I only know it is fast. I do allow the programmer to
pick a specific algorithm, because it turns out that the underlying
algorithm does matter for performance.
Calling a parse tree a "container" is unwise. It, also, doesn't make
sense.
So what does one call the data structure that represents a parse tree
in a compiler, assuming that all nodes are homogeneous?
Better yet, if you were to make a taxonomy of flora or fauna using
Latin names, what data structure would you use?
-Le Chaud Lapin-
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]