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