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 reply "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
next sibling parent reply "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
parent reply "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
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
prev 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 "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 reply "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
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 reply "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
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 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