TECH: STL / Heaps, etc. (was: [MUD-Dev] TECH DGN: a few mud server design questions (long))
sean at hoth.ffwd.cx
Thu Aug 2 16:10:48 New Zealand Standard Time 2001
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.
MUD-Dev mailing list
MUD-Dev at kanga.nu
More information about the MUD-Dev