eliminating std.range.SListRange?

[Steven Schveighoffer]

On Tue, 01 Jun 2010 09:28:28 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail at erdani.org> wrote:

> On 06/01/2010 07:57 AM, 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.
>
> The problem is the original range is still around.
>
> void fun(Range)(Range r) if (isRandomAccessRange!Range)
> {
>      auto heap = BinaryHeap!Range(r);
>      ... use heap, but r is still there ...
> }
>
> This is not memory-unsafe, but may mess up the working of the heap. If  
> the heap takes a copy of the range, that would most often be wasteful.

You can go through lengths to make sure r isn't accessible outside it's  
heap interface, for example, by splitting fun into two functions:

void fun(Range)(Range r) if (isRandomAccessRange!Range)
{
     auto heap = BinaryHeap!Range(r);
     fun2(heap);  // in this function, r is not accessible.
}

And even without this, I can stop using r after the first line.  I have a  
better chance of not using r in a non-heap way in that case.

A heap type also may want to make a copy of the input, most other  
containers do.  This allows it to own the storage for the data.

-Steve