Hello,

I was looking for a FIFO stack in std.containers but only found SList and Array which both appear to essentially operate as LIFO stacks. Is there any standard container with which I can push items on to a list, then later pop them off from the bottom of that list? If so, then how?

Thank you,
Dominic Jones

On Wed, 26 Oct 2011 10:58:12 +0200, Dominic Jones <dominic.jones@qmul.ac.uk> wrote:

> Hello,
>
> I was looking for a FIFO stack in std.containers but only found SList
> and Array which both appear to essentially operate as LIFO stacks. Is
> there any standard container with which I can push items on to a list,
> then later pop them off from the bottom of that list? If so, then how?

No such thing, sorry. Though writing one should be no big challenge.

-- 
  Simen

On Wed, 26 Oct 2011 17:15:37 +0200, Simen Kjaeraas <simen.kjaras@gmail.com> wrote:

> On Wed, 26 Oct 2011 10:58:12 +0200, Dominic Jones <dominic.jones@qmul.ac.uk> wrote:
>
>> Hello,
>>
>> I was looking for a FIFO stack in std.containers but only found SList
>> and Array which both appear to essentially operate as LIFO stacks. Is
>> there any standard container with which I can push items on to a list,
>> then later pop them off from the bottom of that list? If so, then how?
>
> No such thing, sorry. Though writing one should be no big challenge.
>

No such thing that is, if you don't want to use dCollections:

http://www.dsource.org/projects/dcollections

-- 
  Simen

Am 26.10.2011, 17:20 Uhr, schrieb Simen Kjaeraas <simen.kjaras@gmail.com>:

> On Wed, 26 Oct 2011 17:15:37 +0200, Simen Kjaeraas <simen.kjaras@gmail.com> wrote:
>
>> On Wed, 26 Oct 2011 10:58:12 +0200, Dominic Jones <dominic.jones@qmul.ac.uk> wrote:
>>
>>> Hello,
>>>
>>> I was looking for a FIFO stack in std.containers but only found SList
>>> and Array which both appear to essentially operate as LIFO stacks. Is
>>> there any standard container with which I can push items on to a list,
>>> then later pop them off from the bottom of that list? If so, then how?
>>
>> No such thing, sorry. Though writing one should be no big challenge.
>>
>
> No such thing that is, if you don't want to use dCollections:
>
> http://www.dsource.org/projects/dcollections

Also an plain array is a good stack. :)

> Also an plain array is a good stack. :)

I'd rather not use a plain array because (I assume) that when I push
or pop using arrays, a swap array is created to resize the original.
If this is not the case, then an array will certainly do.
-Dominic

On Wednesday, October 26, 2011 09:00 Dominic Jones wrote:
> > Also an plain array is a good stack. :)
> 
> I'd rather not use a plain array because (I assume) that when I push
> or pop using arrays, a swap array is created to resize the original.
> If this is not the case, then an array will certainly do.
> -Dominic

Not exactly. If you want to know more about how arrays work, you should read this: http://www.dsource.org/projects/dcollections/wiki/ArrayArticle It's a great read. As for using an array as a stack, you can do it with a wrapper struct, but using it by itself would result in a lot more reallocations than you'd want, as discussed here: https://www.semitwist.com/articles/article/view/don-t-use-arrays-as-stacks

- Jonathan M Davis

On 10/26/11 1:28 PM, Jonathan M Davis wrote:
> On Wednesday, October 26, 2011 09:00 Dominic Jones wrote:
>>> Also an plain array is a good stack. :)
>>
>> I'd rather not use a plain array because (I assume) that when I push
>> or pop using arrays, a swap array is created to resize the original.
>> If this is not the case, then an array will certainly do.
>> -Dominic
>
> Not exactly. If you want to know more about how arrays work, you should read
> this: http://www.dsource.org/projects/dcollections/wiki/ArrayArticle It's a
> great read. As for using an array as a stack, you can do it with a wrapper
> struct, but using it by itself would result in a lot more reallocations than
> you'd want, as discussed here:
> https://www.semitwist.com/articles/article/view/don-t-use-arrays-as-stacks
>
> - Jonathan M Davis

I think that if you have to read an article that long, with all the explanations of the different caveats a programmer can bump to when using them, to understand how arrays and slices work.... something must be wrong.

Things should be simpler.

On Wednesday, October 26, 2011 10:38 Ary Manzana wrote:
> On 10/26/11 1:28 PM, Jonathan M Davis wrote:
> > On Wednesday, October 26, 2011 09:00 Dominic Jones wrote:
> >>> Also an plain array is a good stack. :)
> >> 
> >> I'd rather not use a plain array because (I assume) that when I push
> >> or pop using arrays, a swap array is created to resize the original.
> >> If this is not the case, then an array will certainly do.
> >> -Dominic
> > 
> > Not exactly. If you want to know more about how arrays work, you should read this: http://www.dsource.org/projects/dcollections/wiki/ArrayArticle It's a great read. As for using an array as a stack, you can do it with a wrapper struct, but using it by itself would result in a lot more reallocations than you'd want, as discussed here: https://www.semitwist.com/articles/article/view/don-t-use-arrays-as-stack s
> > 
> > - Jonathan M Davis
> 
> I think that if you have to read an article that long, with all the explanations of the different caveats a programmer can bump to when using them, to understand how arrays and slices work.... something must be wrong.
> 
> Things should be simpler.

Perhaps. But doing so and still having them be appropriately powerful is not straightforward if it's even possible. What we have works very well overall. It's just that if you start doing stuff that can cause an array to reallocate, and you don't understand enough about how arrays and slices work, you're going to end up reallocating your arrays way too often and harm performance. So, for the most part, you can use arrays just fine without understanding everything in that article, but your code risks being less efficient.

Given how much you gain from D arrays, I think whatever complexity they have is _well_ worth it. It would be nice if the complexity could be reduced without reducing their usefuless or efficiency, but I don't know how possible that is.

- Jonathan M Davis

Ary Manzana Wrote:

> On 10/26/11 1:28 PM, Jonathan M Davis wrote:
> > Not exactly. If you want to know more about how arrays work, you should read this: http://www.dsource.org/projects/dcollections/wiki/ArrayArticle It's a great read. As for using an array as a stack, you can do it with a wrapper struct, but using it by itself would result in a lot more reallocations than you'd want, as discussed here: https://www.semitwist.com/articles/article/view/don-t-use-arrays-as-stacks
> >
> > - Jonathan M Davis
> 
> I think that if you have to read an article that long, with all the explanations of the different caveats a programmer can bump to when using them, to understand how arrays and slices work.... something must be wrong.
> 
> Things should be simpler.

The thing is, it is simple. You can use them as a stack. But if performance matters to you, then you should be aware of how it operates. Or use something already built for performance for that use-case. Now it would be good if Arrays could be used for this, but that would make things more complicated, not less.

On 10/26/2011 07:38 PM, Ary Manzana wrote:
> On 10/26/11 1:28 PM, Jonathan M Davis wrote:
>> On Wednesday, October 26, 2011 09:00 Dominic Jones wrote:
>>>> Also an plain array is a good stack. :)
>>>
>>> I'd rather not use a plain array because (I assume) that when I push
>>> or pop using arrays, a swap array is created to resize the original.
>>> If this is not the case, then an array will certainly do.
>>> -Dominic
>>
>> Not exactly. If you want to know more about how arrays work, you
>> should read
>> this: http://www.dsource.org/projects/dcollections/wiki/ArrayArticle
>> It's a
>> great read. As for using an array as a stack, you can do it with a
>> wrapper
>> struct, but using it by itself would result in a lot more
>> reallocations than
>> you'd want, as discussed here:
>> https://www.semitwist.com/articles/article/view/don-t-use-arrays-as-stacks
>>
>>
>> - Jonathan M Davis
>
> I think that if you have to read an article that long, with all the
> explanations of the different caveats a programmer can bump to when
> using them, to understand how arrays and slices work.... something must
> be wrong.
>
> Things should be simpler.

You exaggerate. The word 'caveat' appears exactly once in that article. The rest are straightforward explanations, mainly about how the runtime implements D array concatenation. After reading Steve's (actually quite short) article, you know about everything described in Nick's.

D arrays and slices are so powerful that they are well worth a tiny little bit of complexity. The behaviour of dynamic arrays is a good trade-off between simplicity and performance imho.