View mode: basic / threaded / horizontal-split · Log in · Help
January 13, 2013
Does D have a Queue and Stack container?
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?
January 13, 2013
Re: Does D have a Queue and Stack container?
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.
January 13, 2013
Re: Does D have a Queue and Stack container?
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
January 13, 2013
Re: Does D have a Queue and Stack container?
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.
January 13, 2013
Re: Does D have a Queue and Stack container?
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
January 13, 2013
Re: Does D have a Queue and Stack container?
> 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
January 13, 2013
Re: Does D have a Queue and Stack container?
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

-- 
Живёшь только однажды.
January 13, 2013
Re: Does D have a Queue and Stack container?
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.
January 14, 2013
Re: Does D have a Queue and Stack container?
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.
January 14, 2013
Re: Does D have a Queue and Stack container?
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
« First   ‹ Prev
1 2
Top | Discussion index | About this forum | D home