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?

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.

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

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.

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

> 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

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

-- 
Живёшь только однажды.

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.

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.

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