eliminating std.range.SListRange?

[Andrei Alexandrescu]

On 06/01/2010 08:43 AM, Steven Schveighoffer wrote:
> 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.

Good points. Let me just mention that I wrote BinaryHeap for a number of 
practical necessities. Without exception, _all_ would be killed if 
copying would be required. IMHO requiring copying is out of the question.

I see two possibilities:

(a) Move BinaryHeap as it is to std.container. That means you can build 
a heap around any given random-access range, but it also means that the 
heap can't grow beyond the original range's size. Incidentally this is 
often the case, but I'm sure not always.

(b) Have BinaryHeap require a container, then define a method 
Array!(T).acquire(T[]) that assumes ownership of a given buffer. In such 
cases, you can define a growable BinaryHeap on top of an array that has 
just acquired a given range. Other random-access ranges, however, would 
not be supported.

Not sure what to do.


Andrei