• Seb (31/31) Feb 24 2016 Hey all,
• bitwise (11/42) Feb 24 2016 Andrei is working on containers, but struggling with trying to
• Steven Schveighoffer (4/10) Feb 24 2016 FYI, dcollections has a deque that is based on 2 arrays:

Seb <seb wilzba.ch> writes:

Hey all,

this is yet another post about phobos (missing) data structures 
;-)
I know this has been discussed quite a bit - [1,2,3] to name a 
few.

While it would be nice to have those "trivially to implement" 
wrappers for some common use cases (map, unordered map, set, 
multiset, ...) [1], this question focuses solely on dequeues.

It is great that we have DList, so having a circular buffer (aka 
constrained queue) should be easy.

I do understand that baking this into DList  (as e.g. Python 
does) might (a) make things more complex or (b) add overhead that 
isn't needed for every user.

However my question is: why is there not a neat wrapper around 
DList with a capacity constraint?

Unfortunately we don't have inheritance for structs, but proxying 
most methods should work too (see e.g [4]).

1) Has anyone else missed deque with capacity constraints?
2) Would such a wrapper fit into phobos?
3) Would you prefer (a) a wrapper around DList [4], (b) around 
arrays [5] or (c) a "vanilla" circular queue?
(b is slower, but allows indexing)

Best wishes,

[1] 
https://stackoverflow.com/questions/7162274/why-is-d-missing-container-classes
[2] 
http://forum.dlang.org/thread/mailman.852.1359488662.22503.digitalmars-d puremagic.com
[3] 
http://forum.dlang.org/post/mailman.394.1358112013.22503.digitalmars-d puremagic.com
[4] http://dpaste.dzfl.pl/d8de9325e9a3
[5] http://rosettacode.org/wiki/Queue/Usage#Faster_Version

bitwise <bitwise.pvt gmail.com> writes:

On Wednesday, 24 February 2016 at 14:46:12 UTC, Seb wrote:
 Hey all,

 this is yet another post about phobos (missing) data structures 
 ;-)
 I know this has been discussed quite a bit - [1,2,3] to name a 
 few.

 While it would be nice to have those "trivially to implement" 
 wrappers for some common use cases (map, unordered map, set, 
 multiset, ...) [1], this question focuses solely on dequeues.

 It is great that we have DList, so having a circular buffer 
 (aka constrained queue) should be easy.

 I do understand that baking this into DList  (as e.g. Python 
 does) might (a) make things more complex or (b) add overhead 
 that isn't needed for every user.

 However my question is: why is there not a neat wrapper around 
 DList with a capacity constraint?

 Unfortunately we don't have inheritance for structs, but 
 proxying most methods should work too (see e.g [4]).

 1) Has anyone else missed deque with capacity constraints?
 2) Would such a wrapper fit into phobos?
 3) Would you prefer (a) a wrapper around DList [4], (b) around 
 arrays [5] or (c) a "vanilla" circular queue?
 (b is slower, but allows indexing)

 Best wishes,

 [1] 
 https://stackoverflow.com/questions/7162274/why-is-d-missing-container-classes
 [2] 
 http://forum.dlang.org/thread/mailman.852.1359488662.22503.digitalmars-d puremagic.com
 [3] 
 http://forum.dlang.org/post/mailman.394.1358112013.22503.digitalmars-d puremagic.com
 [4] http://dpaste.dzfl.pl/d8de9325e9a3
 [5] http://rosettacode.org/wiki/Queue/Usage#Faster_Version

Andrei is working on containers, but struggling with trying to 
make them  safe without comprimising efficiency or utility, 
AFAIK. Getting the containers done to his liking may require the 
work on lifetimes(language supported ref counting) to be 
complete. IIRC, there was a circular buffer on code.dlang.org 
somewhere. I've been planning on adding one to my container 
set(not on code.dlang.org yet) which would be implemented on a 
contiguous array, with the contents wrapping around as items are 
added/removed. I believe it's the most efficient approach.

    Bit

Steven Schveighoffer <schveiguy yahoo.com> writes:

On 2/24/16 9:46 AM, Seb wrote:
 Hey all,

 this is yet another post about phobos (missing) data structures ;-)
 I know this has been discussed quite a bit - [1,2,3] to name a few.

 While it would be nice to have those "trivially to implement" wrappers
 for some common use cases (map, unordered map, set, multiset, ...) [1],
 this question focuses solely on dequeues.

FYI, dcollections has a deque that is based on 2 arrays:

https://github.com/schveiguy/dcollections/blob/master/dcollections/Deque.d

-Steve