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)
