TECH: STL / Heaps, etc. (was: [MUD-Dev] TECH DGN: a few mud server design questions (long))

[Sean K]

On Thu, Aug 02, 2001 at 10:50:21AM -0500, Eli Stevens wrote: 
> ----- Original Message -----
> From: "Caliban Tiresias Darklock" <caliban at darklock.com>
>> On Tue, 31 Jul 2001 13:46:09 +0100, "Adam Martin"
>> <ya_hoo_com at yahoo.com> wrote:
 
>>> A heap would be faster, but AFAICS they both have the desired (
>>> log(n) ) time complexity - a heap just has a lower constant
>>> factor (and isn't in the standard libraries. Yet).
 
>> But there are so many easily available implementations...

> *cough*STL*cough* Ahem.  Excuse me.

I believe JCL already mentioned std::priority_queue as the STL
method of addressing this need.  The threading thread inspired me to
do a bit of research and I ran across a windows-specific means of
scheduling: CreateTimerQueue and its bretheren.  Turns out you can
specify that a callback function be executed at a pre-specified
time.  I expect that it would be more efficient than any
priority-queue mechanism, provided you're running a windows system.

> everything looks like a nail :).  I think the STL is a Good Thing,
> but my practical/real world experience is limited.  Are there
> problems with the STL lurking under the surface?

Not with its design, though some older implementations may have
subtle problems of their own.

> One aspect that concerned me was that while it specifies the
> complexity of a given operation, you don't have any control over
> the coefficients involved.  Would it be a bad idea to rely on it
> too much?

Actually (if this is what you mean), STL containers all have to mean
complexity gurantees, based on operation.  For example, ransom
access in a vector must be O(1), insertions O(n) at worst, list
insertions O(1), etc.

The outstanding issues with the STL and C++ in general are
sufficiently esoteric that the average programmer won't encounter
them.  One that came up recently is that there's no direct
conversion between a const_iterator and a plain iterator, requiring
an O(n) operation in order to be portable, and that operations that
allow iterators should also allow cost_iterators (since what you
really want is for the container to be const, not its contents).
See the comp.lang.c++ usenet groups for detailed discussion of C++
and the STL.


Sean
_______________________________________________
MUD-Dev mailing list
MUD-Dev at kanga.nu
https://www.kanga.nu/lists/listinfo/mud-dev