Here is a new container class called the hat, developed using a new form of
tree (male-female tree) for random objects.

It provides a user interface of put(), peek() and pull(), all of which
perform in O(log n) time.

http://home.comcast.net/~anglewyrm/hat.html

--
AngleWyrm

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

no_spam_anglewyrm@hotmail.com ("AngleWyrm") wrote in message news:<caaAc.35988$Hg2.1932@attbi_s04>...
> Here is a new container class called the hat, developed using a new form of
> tree (male-female tree) for random objects.
>
> It provides a user interface of put(), peek() and pull(), all of which
> perform in O(log n) time.
>
> http://home.comcast.net/~anglewyrm/hat.html

It looks like an interesting component. The following is mostly some
general comments on the proposal, as well as some specifics about the
interface.

I think it could help if your article had a motivation part, as well
as comparing and contrasting to existing facilities for this (if any).

The article dives straight into what the container does, as well as
details of its implementation, but nothing on _why_ you'd want such a
container in the first place, which left me wondering what would be
the use of it (and I don't think I was alone), and therefore why one
would want to read the rest. This may also account for the lack of
responses in the thread. It took me a while to understand that the
name probably alludes to drawing numbers out of a hat (it says in a
comment in the example code, but that's after the description of the
implementation). "hat", by itself, is not very descriptive.

You have some examples in the example code, but these should be
motivating examples at the start.

Having described what it's for, you should then compare and contrast
it with existing ways of doing the same thing (if they exist), and
what your container does better.

For starters, "hat" works similarly to std::priority_queue, except
that the element selection is random, rather than giving the largest
element, so like priority queue, it's a kind of sequence adaptor.

_Then_ you can go into the specifics of how it's defined, and possibly
how it may be implemented (keep in mind that the components of the
standard library have no mandated implementation, only defined syntax,
semantics and complexity requirements. Thus, my use of "may" in the
first line was deliberate).

Regarding the interface, you may want to separate query from
modification, to enable it to be exception safe. It has been shown
that simultaneously modifying and returning a value cannot be made
exception safe (see Item 10 in "Exceptional C++"). Thus, the standard
library has separate functions top() (your peek()) and pop() (your
pull(), but pop() doesn't return anything) for std::priority_queue. In
other words, make pull() return nothing, possibly changing the names.

As a deeper issue, hat's pull() has two different responsibilities:
removing an element, and returning it. You already have top(), which
returns a reference, so you avoid returning a copy, so pull()
returning an object appears unnecessary.

When it comes to the implementation, why write "node<T>::node(...)" in
the class definition, when "node(...)" is sufficient? I guess it's a
matter of style, but I'm reminded of Kevlin Henney's "Omit Needless
Code".

By the way, when you post to both comp.lang.c++.moderated and
comp.std.c++, you should cross-post (add both in the header). This
ensures that any reply also ends up on the other group. Now, you risk
parallell discussions, where points being restated in the separate
threads.

As this is a proposal to the standard library, I reply in the
comp.std.c++ thread.

Regards,

Terje

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]