[Issue 17094] std.container.binaryheap doesn't manage store length consistently when inserting

[d-bugmail at puremagic.com]

https://issues.dlang.org/show_bug.cgi?id=17094

Simen Kjaeraas <simen.kjaras at gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
                 CC|                            |simen.kjaras at gmail.com
         Resolution|---                         |INVALID

--- Comment #2 from Simen Kjaeraas <simen.kjaras at gmail.com> ---
Sorry to disappoint you, but this is not actually a bug.

According to the documentation for heapify: "initialized with s" (s being the
array).
And from BinaryHeap: "If Store is a container that supports insertBack, the
BinaryHeap may grow by adding elements to the container."

That is, the passed array is used simply to create the initial heap, and the
heap will keep using it until it needs to reallocate. Since you gave it an
empty array, that's going to happen immediately.

Basically, what you're doing is equivalent to this code:

int[] a = [];
int[] b = a;
a ~= 2;
assert(b == [2]); // Will fail since b == [].

Supposing the heap kept a reference to the exact slice that was used to
initialize it, this would cause problems:

auto foo() {
    int[] a = [1,2,3,4];
    return heapify(a);
}

Once the scope is exited, the reference to a would no longer be valid (but the
array holding the elements would).

Another part of the explanation is that slices are weird. They behave a bit
like ranges and a bit like containers, and in this case that duality is
tripping you up.

--