[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

--- Comment #3 from Jon Degenhardt <jrdemail2000-dlang at yahoo.com> ---
(In reply to Simen Kjaeraas from comment #2)
> 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.

Reserve is used to preallocate the necessary space. It is not necessary to
reallocate.

--