Creating a Priority Queue: An Adventure

John Colvin via Digitalmars-d-learn digitalmars-d-learn at puremagic.com
Wed Aug 5 11:20:40 PDT 2015


On Wednesday, 5 August 2015 at 15:29:39 UTC, Nordlöw wrote:
> On Wednesday, 5 August 2015 at 13:37:19 UTC, John Colvin wrote:
>> On Wednesday, 5 August 2015 at 11:09:29 UTC, Per Nordlöw wrote:
>>> On Wednesday, 5 August 2015 at 09:04:54 UTC, Nordlöw wrote:
>>>> This will however duplicate the underlying array aswell, 
>>>> which is probably not what we want. How do we avoid this?
>>>
>>> Correction: the underlying storage array *must* be duplicated 
>>> whenever we want to iterate over it without side effects in 
>>> the original instance. That's just the way binary heaps work.
>>
>> Crazy idea: what about a range that lazily copies as it needs 
>> to? I.e. copy-on-write
>
> I guess you mean that popFront should copy on demand then. We 
> then an extra bool to keep track of whether the copying has 
> been done then. One problem though:
>
> auto x = PQ;
> x.insert(...); // one element
> auto y = x; // no copying of underlying storage
> x.popFront; // modified both x and y!
> y.popFront; // copied on demands, but underlying storage is 
> already empty. oops!
>
> I don't think this is a desired behaviour.

in my vision, either x.popFront would also create a copy or you 
would have to go "auto y = x.nonModifyingView" or similar. What I 
don't want is something that copies 10000 elements just to use 
x.take(6)


More information about the Digitalmars-d-learn mailing list