[Home] [Groups] - Message: [Prev in Group] [Next in Group]
20420: Re: TECH: STL / Heaps, etc. (was: [MUD-Dev] TECH DGN: a few mud server design questions (long))
[Full Header] [Plain Text]
From: Sean K <sean@hoth.ffwd.cx>
Newsgroups: nu.kanga.list.mud-dev
Date: Thu, 2 Aug 2001 16:10:48 -0700
References: [1] [2] [3] [4] [5] [6] [7] [8] <-newest
Organization: Kanga.Nu
On Thu, Aug 02, 2001 at 10:50:21AM -0500, Eli Stevens wrote:
> ----- Original Message -----
> From: "Caliban Tiresias Darklock" <caliban@darklock.com>
>> On Tue, 31 Jul 2001 13:46:09 +0100, "Adam Martin"
>> <ya_hoo_com@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@kanga.nu
https://www.kanga.nu/lists/listinfo/mud-dev