Using std.container.BinaryHeap like C++

Paulo Pinto via Digitalmars-d-learn digitalmars-d-learn at puremagic.com
Mon Aug 18 10:22:17 PDT 2014


Am 18.08.2014 14:49, schrieb monarch_dodra:
> On Monday, 18 August 2014 at 06:50:08 UTC, Paulo Pinto wrote:
>> On Sunday, 17 August 2014 at 21:09:04 UTC, monarch_dodra wrote:
>>> On Sunday, 17 August 2014 at 18:54:27 UTC, Paulo Pinto wrote:
>>>> Hi,
>>>>
>>>> I was wondering if it is possible to use the BinaryHeap store like
>>>> the C++'s make_heap/pop_heap/push_heap functions.
>>>>
>>>> I would like to port to D some A* C++ code I have which rearranges
>>>> the priorities on the underlying store, followed by another
>>>> make_heap() call on the vector used as store.
>>>>
>>>> Doing the same in D by calling again heapify() does not seem to
>>>> provide similar behavior.
>>>>
>>>> Just curious about it, as I don't plan to invest too much time on it.
>>>>
>>>> Thanks,
>>>> Paulo
>>>
>>> AFAIK, D's BinaryHeap works just like C++'s
>>> make_heap/pop_heap/push_heap, except that it provides an actual
>>> object you can interface with, which has font, removeFront, removeAny
>>> and insert.
>>>
>>> What exactly is the difference in behavior you are seeing? Just
>>> different results that can be attributed to implementation details,
>>> or fundamental differences?
>>
>> It doesn't seem to like I change the store contents directly under its
>> feet
>> and recalling heapify again on the same store, like I am doing in
>> C++'s heap.
>>
>> Sometimes I get a different sequence of data or just a crash.
>>
>> I still need to make the D code reflect my latest C++ changes, as the
>> C++ code is what really matters in this hobby project, there is where
>> my focus has been lately.
>>
>> The D version is more of a "playing around" thing.
>>
>> As I said, I curious what the behavior is supposed to be.
>>
>> Thanks,
>> Paulo
>
> Weird. The behavior should be the same as C++'s. As I said, the
> difference is that D gives you a "handle" object. This object assumes
> you *don't* modify it's store under the hood, but as long as you don't
> use the heap after a store modification, you should be fine. Do you have
> a minimal test case?

Actually, that is exactly what I am doing. :)

The store contains the open list of nodes to visit, and when new paths 
are found, I re-parent the nodes which leads to a different cost, thus
I re-generate the heap.

The D code is still not up to date with what I am doing on C++ and the 
code I had before lost it somehow while jumping around computers. But 
both projects are on Github.

C++
https://github.com/pjmlp/AStarDemoCpp/blob/master/AStarDemo/AStarSolver.cpp

D
https://github.com/pjmlp/AStarDemoD/blob/master/src/solver.d


--
Paulo


More information about the Digitalmars-d-learn mailing list