eliminating std.range.SListRange?

Steven Schveighoffer schveiguy at yahoo.com
Tue Jun 1 06:31:12 PDT 2010


On Tue, 01 Jun 2010 09:17:15 -0400, Don <nospam at nospam.com> wrote:

> Steven Schveighoffer wrote:
>> On Sun, 30 May 2010 18:33:22 -0400, Andrei Alexandrescu  
>> <SeeWebsiteForEmail at erdani.org> wrote:
>>
>>> The heap is a tad difficult to tackle. Most of the time you don't want  
>>> to create a heap, but instead to organize an existing range as a heap.  
>>> As such, the heap is not always obvious to think of as a container.  
>>> I'm undecided on how to approach this.
>>  It's easier to think of a heap as a single entity with operations on  
>> it.  At least for me anyway.
>>  Most of the time, once you make a range a heap, you want to continue  
>> to use it as a heap.  Restricting operations on that range by defining  
>> a heap type around it can do this.  Otherwise, you could accidentally  
>> do something foolish like sort the range.
>>  -Steve
>
> But for several graph algorithms, (eg, A* pathfinding), you have {key1,  
> key2} pairs, forming a heap based on key1, but you also need to able to  
> search for key2.
> The container is a hybrid, consisting of heap on {key1} + AA on {key2}.
> It uses the heap operations, but it's not exactly a heap.

And such a container would be not a heap.  I don't think it should be  
impossible to define such a construct if a vanilla heap type is also  
defined.

My recommendation: keep the heap functions in std.algorithm and create a  
std.container based off them.

-Steve


More information about the Digitalmars-d mailing list