Creating a Priority Queue: An Adventure

["Nordlöw" via Digitalmars-d-learn]

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.