Containers

[BBasile via Digitalmars-d]

On Thursday, 3 September 2015 at 19:45:48 UTC, bitwise wrote:
> Any interest in having these in Phobos?
>
> https://github.com/bitwise-github/d-containers
>
> Phobos doesn't currently have a Queue(T), and Array(T) leaves 
> much to be desired. The containers I've built are very full 
> featured, fast, and are unittested fairly thoroughly. I intend 
> to add range checking to both containers as well. Inspiration 
> was taken from C++'s vector and queue, C#'s generic List and 
> Queue, and D's Array.
>
> I'm not sure how the container's I've built would be integrated 
> though. They do go against the current container spec, but for 
> good reason.
>
> The container spec says containers should be reference types, 
> but I guess this clashed with the idea of Phobos being @nogc so 
> someone tried to make Array(T) ref counted. The result is 
> std.container.Array being a struct with an instance of 
> RefCounted inside it, which is bad for performance, but also 
> inflexible. Innocent looking code like the following will do 2 
> separate allocations: One for the RefCounted payload, and one 
> for the Array's data. On top of being a performance hit, it 
> doesn't allow the user to choose how they want to manage memory.
>
> Array!int a = Array!int(1, 2, 3);    //  2 allocations, or 
> else!  >:D
>
> The containers I've built are simple value types with a 
> postblit. Using this as a base, one can simply use the 
> container as-is if they like(which I do), but it's also trivial 
> to make either a ref-counted version, or GC version.
>
> See here for example:
> https://github.com/bitwise-github/d-containers/blob/master/main.d
>
>     Bit

I think that std.allocators is a prerequisite to implement the 
some new std containers.

Examples:
- library array: gc_allocator for a "single shot" program is fine.
- library array: aligned_allocator if the array content has to be 
used with several SSE instructions.
- linked list: could use malloctor to automatically manage its 
payloads life-time, but the final choice will be a parameter of 
the template instance. Inside the template, some 'static if' 
branches to adapt the code to the allocator used to make new 
payloads.
Also a the free list to get available payloads instead of 
allocationg...etc.

New containers without std.mallocators would be an error. In this 
sense, EMSI allocators are a bit more compliant (they already use 
them, not exactly as required but   templates have an optional 
param to indicate if the structures are GC-free or not).