www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Does D have a Queue and Stack container?

reply "Damian" <damianday hotmail.co.uk> writes:
As per title, it would be awesome if someone could link me to 
these. I'm quite suprised that D does not already contain these.. 
are there any plans for them joining Phobos?
Jan 13 2013
next sibling parent "Peter Alexander" <peter.alexander.au gmail.com> writes:
On Sunday, 13 January 2013 at 19:55:28 UTC, Damian wrote:
 As per title, it would be awesome if someone could link me to 
 these. I'm quite suprised that D does not already contain 
 these.. are there any plans for them joining Phobos?

Well, a stack is just an array. int[] stack; stack ~= 1; stack ~= 2; assert(stack.back == 2); stack.popBack(); assert(stack.back == 1); stack.popBack(); assert(stack.empty); If you want strict stack semantics (i.e. *only* allow access to the top/back) then you could trivially write a wrapper around an array that does this. For queues, you could use DList, which is a doubly-linked list. Use .front to get the front of the queue, and .insertBack(x) to add to the back of the queue. In C++, std::stack and std::queue are just wrappers around the other standard containers.
Jan 13 2013
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Damian:

 As per title, it would be awesome if someone could link me to 
 these. I'm quite suprised that D does not already contain 
 these.. are there any plans for them joining Phobos?

Currently Phobos doesn't have deque, queue and stack data structures. I hope it will eventually have them. In the meantime around you find some implementations of queues and stacks. There are packages of data structures in D code repositories. This is a growable circular queue, useful in some situations: http://rosettacode.org/wiki/Queue/Usage#Faster_Version Bye, bearophile
Jan 13 2013
prev sibling next sibling parent "Robik" <szadows gmail.com> writes:
On Sunday, 13 January 2013 at 19:55:28 UTC, Damian wrote:
 As per title, it would be awesome if someone could link me to 
 these. I'm quite suprised that D does not already contain 
 these.. are there any plans for them joining Phobos?

Here's one I am using: https://gist.github.com/4525926 You can use LinkedList as DeQueue.
Jan 13 2013
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Peter Alexander:

 Well, a stack is just an array.

 int[] stack;
 stack ~= 1;
 stack ~= 2;
 assert(stack.back == 2);
 stack.popBack();
 assert(stack.back == 1);
 stack.popBack();
 assert(stack.empty);

 If you want strict stack semantics (i.e. *only* allow access to 
 the top/back) then you could trivially write a wrapper around 
 an array that does this.

That's very slow.
 For queues, you could use DList, which is a doubly-linked list. 
 Use .front to get the front of the queue, and .insertBack(x) to 
 add to the back of the queue.

Linked list are very slow, unless you have to add and delete many items in the middle of the sequence.
 In C++, std::stack and std::queue are just wrappers around the 
 other standard containers.

The standard container you refer to is deque, sometimes implemented as a dynamic array of fixed-sized arrays, and this data structure is not present in Phobos. Bye, bearophile
Jan 13 2013
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
 The standard container you refer to is deque, sometimes 
 implemented as a dynamic array of fixed-sized arrays,

Sorry, I meant to say, a dynamic array of pointers to fixed-sized arrays. Bye, bearophile
Jan 13 2013
prev sibling next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Sun, Jan 13, 2013 at 09:02:38PM +0100, Peter Alexander wrote:
 On Sunday, 13 January 2013 at 19:55:28 UTC, Damian wrote:
As per title, it would be awesome if someone could link me to
these. I'm quite suprised that D does not already contain these..
are there any plans for them joining Phobos?

Well, a stack is just an array. int[] stack; stack ~= 1; stack ~= 2; assert(stack.back == 2); stack.popBack(); assert(stack.back == 1); stack.popBack(); assert(stack.empty); If you want strict stack semantics (i.e. *only* allow access to the top/back) then you could trivially write a wrapper around an array that does this.

One does have to be careful about performance though: once you pop the back of an array, appending to the array again will reallocate the entire array (because the runtime can't tell if something else is referencing the slice beyond the end of the array). So if you have a sequence of pop, push, pop, push, ..., it will reallocate the array every time you push, which is pretty disastrous performance-wise. The workaround is to use assumeSafeAppend before pushing to the end of the array -- and make sure there aren't any other slices referencing it, 'cos otherwise other parts of your program may suddenly get unexpected results. :) T -- Живёшь только однажды.
Jan 13 2013
prev sibling next sibling parent "ponce" <contact gamesfrommars.fr> writes:
On Sunday, 13 January 2013 at 19:55:28 UTC, Damian wrote:
 As per title, it would be awesome if someone could link me to 
 these. I'm quite suprised that D does not already contain 
 these.. are there any plans for them joining Phobos?

I wrote a Queue/RingBuffer here: https://github.com/p0nce/gfm/blob/master/common/queue.d Not sure how it would fare with structs.
Jan 13 2013
prev sibling next sibling parent "Andrey" <andr-sar yandex.ru> writes:
D's containers are disappointment. I'm currently writing custom 
module of data structures to be as fast, economic and close to 
hardware as possible. I'm almost at the beginning stage, so no 
clear timeline.

Thanks creators, D allows to work with low level stuff and mix it 
rather effectively with high level.
Jan 13 2013
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
ponce:

 I wrote a Queue/RingBuffer here:
 https://github.com/p0nce/gfm/blob/master/common/queue.d

You have code like: return _data[(_first + _count - 1) % _data.length]; Take a look here: http://rosettacode.org/wiki/Queue/Usage#Faster_Version It keeps another instance field: private uint power2 = 0; And instead of the modulus uses an And, that is supposed to be faster: tail = (tail + 1) & ((cast(size_t)1 << power2) - 1); This is usable if the growth rate is 2. This is almost true in your code: size_t newCapacity = capacity * 2; if (newCapacity < 8) newCapacity = 8; Bye, bearophile
Jan 13 2013
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Andrey:

 D's containers are disappointment.

They will get better because I think D is slowly getting all the machinery to implement them well, finishing the implementation of const/immutable, shared and memory allocators. Bye, bearophile
Jan 13 2013
prev sibling next sibling parent Jacob Carlborg <doob me.com> writes:
On 2013-01-13 20:55, Damian wrote:
 As per title, it would be awesome if someone could link me to these. I'm
 quite suprised that D does not already contain these.. are there any
 plans for them joining Phobos?

Tango has a stack, at least: https://github.com/SiegeLord/Tango-D2 http://www.dsource.org/projects/tango/docs/current/ -- /Jacob Carlborg
Jan 13 2013
prev sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
 Sorry, I meant to say, a dynamic array of pointers to 
 fixed-sized arrays.

That's for a stack. For a queue a nice implementation is a power-of-2 growable circular queue of pointers to fixed-sized arrays (chunks); plus a ("intrusive", no more memory needed) linked list of some of the last free blocks (that need to be cleared if they contain indirections). For a deque the implementation is similar, just a bit more complex. (In theory there is a small queue optimization, a union on the dynamic array that implements the circular queue, to remove one indirection level when the queue needs only one chunk of memory, but then you have to add one test to tell apart the two configurations every time you add or remove an item, so probably it's not worth it). Bye, bearophile
Jan 14 2013