What's the policy on using GC or not in std.container.* ?

- std.container.Array uses malloc for its allocation but
- RedBlackTree.allocate() returns a: new RBNode!Elem*

Is this because RBNode* should be reachable outside of RedBlackTree or is this a todo?

On 2/20/15 4:26 PM, "Nordlöw" wrote:
> What's the policy on using GC or not in std.container.* ?
>
> - std.container.Array uses malloc for its allocation but
> - RedBlackTree.allocate() returns a: new RBNode!Elem*
>
> Is this because RBNode* should be reachable outside of RedBlackTree or
> is this a todo?

RedBlackTree was ported from dcollections, which has an allocator hierarchy.

The code in dcollections looked like this originally:

https://github.com/schveiguy/dcollections/blob/master/dcollections/RBTree.d#L1244

return alloc.allocate();

where alloc is the allocator for the tree.

In answer to your question, RBNode should not be accessible direction outside of RedBlackTree. But we don't have allocators inside of Phobos, so I used the easiest thing I could for portability.

-Steve

On Monday, 23 February 2015 at 19:24:32 UTC, Steven Schveighoffer wrote:
> In answer to your question, RBNode should not be accessible direction outside of RedBlackTree. But we don't have allocators inside of Phobos, so I used the easiest thing I could for portability.
>
> -Steve

Does this mean that in the long run RBTree should allocate its RBNodes using a non-GC allocator (such as std.allocator) instead?

On 2/23/15 3:16 PM, "Nordlöw" wrote:
> On Monday, 23 February 2015 at 19:24:32 UTC, Steven Schveighoffer wrote:
>> In answer to your question, RBNode should not be accessible direction
>> outside of RedBlackTree. But we don't have allocators inside of
>> Phobos, so I used the easiest thing I could for portability.
>
> Does this mean that in the long run RBTree should allocate its RBNodes
> using a non-GC allocator (such as std.allocator) instead?

It means that it can do that, and does do that in dcollections. std.container does not have all the code to do it, dcollections.RBTree has some extra calls that would probably help. However, the allocation is done in one spot so the code can easily use an allocator.

-Steve

On Monday, 23 February 2015 at 21:33:35 UTC, Steven Schveighoffer wrote:
> It means that it can do that, and does do that in dcollections. std.container does not have all the code to do it, dcollections.RBTree has some extra calls that would probably help. However, the allocation is done in one spot so the code can easily use an allocator.

Have anybody done any benchmarks on which allocators are suitable for which containers? I'm especially interested in optimizing RBTree because I want a fast Dikjstra implementation in D:

http://rosettacode.org/wiki/Dijkstra%27s_algorithm#D