Jump to page: 1 2
Thread overview
Dynamic Arrays as Stack and/or Queue
Oct 07
Just Dave
Oct 07
mipri
Oct 07
bachmeier
Oct 07
Just Dave
Oct 07
bachmeier
Oct 07
Just Dave
Oct 07
IGotD-
Oct 07
mipri
Oct 07
Alex
Oct 08
Just Dave
Oct 08
mipri
October 07
I need a stack and a queue and I noticed that the standard library doesn't appear to have one. Which is ok. I just need something that can logically behave as a stack and queue, which I think the dynamic array should be able to do (if I understand correctly this is effectively the equivalent of vector<T> in C++ or List<T> in C#). However, I'm having a hard time figuring out the best way to push, pop, enqueue and dequeue using D.

I'm not seeing here: https://dlang.org/spec/arrays.html, anyway to remove from the array. What's the correct syntax/method call for this? I see you can easily concatenate with '~', but I see no corresponding delete.

Sorry for the newbie question, but I'm just unsure where to look for this.
October 07
On Monday, 7 October 2019 at 17:11:08 UTC, Just Dave wrote:
> I need a stack and a queue and I noticed that the standard library doesn't appear to have one. Which is ok. I just need something that can logically behave as a stack and queue, which I think the dynamic array should be able to do (if I understand correctly this is effectively the equivalent of vector<T> in C++ or List<T> in C#). However, I'm having a hard time figuring out the best way to push, pop, enqueue and dequeue using D.
>
> I'm not seeing here: https://dlang.org/spec/arrays.html, anyway to remove from the array. What's the correct syntax/method call for this? I see you can easily concatenate with '~', but I see no corresponding delete.
>
> Sorry for the newbie question, but I'm just unsure where to look for this.

if the top of the stack is the last element, --stack.length works
as a simple pop.
October 07
On Monday, 7 October 2019 at 17:11:08 UTC, Just Dave wrote:
> I need a stack and a queue and I noticed that the standard library doesn't appear to have one. Which is ok. I just need something that can logically behave as a stack and queue, which I think the dynamic array should be able to do (if I understand correctly this is effectively the equivalent of vector<T> in C++ or List<T> in C#). However, I'm having a hard time figuring out the best way to push, pop, enqueue and dequeue using D.
>
> I'm not seeing here: https://dlang.org/spec/arrays.html, anyway to remove from the array. What's the correct syntax/method call for this? I see you can easily concatenate with '~', but I see no corresponding delete.
>
> Sorry for the newbie question, but I'm just unsure where to look for this.

Does slicing do what you need?

x[1..$]
October 07
On Monday, 7 October 2019 at 17:11:08 UTC, Just Dave wrote:
> I need a stack and a queue and I noticed that the standard library doesn't appear to have one. Which is ok. I just need something that can logically behave as a stack and queue, which I think the dynamic array should be able to do (if I understand correctly this is effectively the equivalent of vector<T> in C++ or List<T> in C#). However, I'm having a hard time figuring out the best way to push, pop, enqueue and dequeue using D.
>
> I'm not seeing here: https://dlang.org/spec/arrays.html, anyway to remove from the array. What's the correct syntax/method call for this? I see you can easily concatenate with '~', but I see no corresponding delete.
>
> Sorry for the newbie question, but I'm just unsure where to look for this.

Also, these may be of interest:
https://dlang.org/phobos/std_array.html
https://dlang.org/phobos/std_range.html
October 07
On Monday, 7 October 2019 at 17:18:03 UTC, bachmeier wrote:
> On Monday, 7 October 2019 at 17:11:08 UTC, Just Dave wrote:
>> I need a stack and a queue and I noticed that the standard library doesn't appear to have one. Which is ok. I just need something that can logically behave as a stack and queue, which I think the dynamic array should be able to do (if I understand correctly this is effectively the equivalent of vector<T> in C++ or List<T> in C#). However, I'm having a hard time figuring out the best way to push, pop, enqueue and dequeue using D.
>>
>> I'm not seeing here: https://dlang.org/spec/arrays.html, anyway to remove from the array. What's the correct syntax/method call for this? I see you can easily concatenate with '~', but I see no corresponding delete.
>>
>> Sorry for the newbie question, but I'm just unsure where to look for this.
>
> Does slicing do what you need?
>
> x[1..$]

I have no clue. My problem is I need a stack and queue and I'm a little unsure the 'd' way to do it.
October 07
On Monday, 7 October 2019 at 17:11:08 UTC, Just Dave wrote:
> I need a stack and a queue and I noticed that the standard library doesn't appear to have one. Which is ok. I just need something that can logically behave as a stack and queue, which I think the dynamic array should be able to do (if I understand correctly this is effectively the equivalent of vector<T> in C++ or List<T> in C#). However, I'm having a hard time figuring out the best way to push, pop, enqueue and dequeue using D.
>
> I'm not seeing here: https://dlang.org/spec/arrays.html, anyway to remove from the array. What's the correct syntax/method call for this? I see you can easily concatenate with '~', but I see no corresponding delete.
>
> Sorry for the newbie question, but I'm just unsure where to look for this.

Built-in D arrays rely on garbage collector, and you don't need an explicit delete. For nogc arrays, there are 3rd party libs and std.container.array. take a look at
https://dlang.org/phobos/std_container_array.html
October 07
On Monday, 7 October 2019 at 17:24:19 UTC, Ferhat Kurtulmuş wrote:
> On Monday, 7 October 2019 at 17:11:08 UTC, Just Dave wrote:
>> I need a stack and a queue and I noticed that the standard library doesn't appear to have one. Which is ok. I just need something that can logically behave as a stack and queue, which I think the dynamic array should be able to do (if I understand correctly this is effectively the equivalent of vector<T> in C++ or List<T> in C#). However, I'm having a hard time figuring out the best way to push, pop, enqueue and dequeue using D.
>>
>> I'm not seeing here: https://dlang.org/spec/arrays.html, anyway to remove from the array. What's the correct syntax/method call for this? I see you can easily concatenate with '~', but I see no corresponding delete.
>>
>> Sorry for the newbie question, but I'm just unsure where to look for this.
>
> Built-in D arrays rely on garbage collector, and you don't need an explicit delete. For nogc arrays, there are 3rd party libs and std.container.array. take a look at
> https://dlang.org/phobos/std_container_array.html

I'm not talking about memory deletion. I'm talking about push, pop, enqueue, and dequeue behavior. I'd assume in a garbage collected language letting the reference float off should be picked up by the GC.
October 07
On Monday, 7 October 2019 at 17:28:11 UTC, Just Dave wrote:
> On Monday, 7 October 2019 at 17:24:19 UTC, Ferhat Kurtulmuş wrote:
>> On Monday, 7 October 2019 at 17:11:08 UTC, Just Dave wrote:
>>> [...]
>>
>> Built-in D arrays rely on garbage collector, and you don't need an explicit delete. For nogc arrays, there are 3rd party libs and std.container.array. take a look at
>> https://dlang.org/phobos/std_container_array.html
>
> I'm not talking about memory deletion. I'm talking about push, pop, enqueue, and dequeue behavior. I'd assume in a garbage collected language letting the reference float off should be picked up by the GC.
I'm sorry. Writing on my mobile phone. Maybe this is what you are looking for
https://dlang.org/phobos/std_container_dlist.html
October 07
On Monday, 7 October 2019 at 17:36:09 UTC, Ferhat Kurtulmuş wrote:
>>
>> I'm not talking about memory deletion. I'm talking about push, pop, enqueue, and dequeue behavior. I'd assume in a garbage collected language letting the reference float off should be picked up by the GC.
> I'm sorry. Writing on my mobile phone. Maybe this is what you are looking for
> https://dlang.org/phobos/std_container_dlist.html

I think what he is looking for are the general pop_front, push_front, pop_back and push_back that you would find in virtually any C++ STL container algorithms like list, vector or map.

I think this is a good question as I don't really see any good example in the documentation of the dynamic arrays about this. This is very common use case for arrays. Is there any D equivalent?
October 07
On Monday, 7 October 2019 at 19:16:31 UTC, IGotD- wrote:
> On Monday, 7 October 2019 at 17:36:09 UTC, Ferhat Kurtulmuş wrote:
>>>
>>> I'm not talking about memory deletion. I'm talking about push, pop, enqueue, and dequeue behavior. I'd assume in a garbage collected language letting the reference float off should be picked up by the GC.
>> I'm sorry. Writing on my mobile phone. Maybe this is what you are looking for
>> https://dlang.org/phobos/std_container_dlist.html
>
> I think what he is looking for are the general pop_front, push_front, pop_back and push_back that you would find in virtually any C++ STL container algorithms like list, vector or map.
>
> I think this is a good question as I don't really see any good example in the documentation of the dynamic arrays about this. This is very common use case for arrays. Is there any D equivalent?

With the performance that you'd expect, I believe:

#! /usr/bin/env rdmd
import std.stdio;
import std.algorithm : moveAll;

void push_front(T)(ref T[] xs, T x) {
    ++xs.length;
    moveAll(xs[0 .. $-1], xs[1..$]);
    x[0] = x;
}
T pop_front(T)(ref T[] xs) {
    T x = xs[0];
    moveAll(xs[1 .. $], xs[0 .. $-1]);
    --xs.length;
    return x;
}
void push_back(T)(ref T[] xs, T x) {
    xs ~= x;
}
T pop_back(T)(ref T[] xs) {
    T x = xs[$ - 1];
    --xs.length;
    return x;
}

void main() {
    int[] xs;
    foreach (i; 0 .. 10)
        xs.push_back(i);
    writeln(xs.pop_back());  // output: 9
    writeln(xs.pop_front()); // output: 0
    writeln(xs.pop_front()); // output: 1
    writeln(xs); // output: [2, 3, 4, 5, 6, 7, 8]
}

« First   ‹ Prev
1 2