• Dominic Jones (7/7) Oct 26 2011 Hello,
• Simen Kjaeraas (5/10) Oct 26 2011 No such thing, sorry. Though writing one should be no big challenge.
• Simen Kjaeraas (6/15) Oct 26 2011 No such thing that is, if you don't want to use dCollections:
• Marco Leise (2/18) Oct 26 2011 Also an plain array is a good stack. :)
• Dominic Jones (4/5) Oct 26 2011 I'd rather not use a plain array because (I assume) that when I push
• Jonathan M Davis (8/14) Oct 26 2011 Not exactly. If you want to know more about how arrays work, you should ...
• Ary Manzana (6/20) Oct 26 2011 I think that if you have to read an article that long, with all the
• Jonathan M Davis (13/39) Oct 26 2011 Perhaps. But doing so and still having them be appropriately powerful is...
• Jesse Phillips (2/18) Oct 26 2011 The thing is, it is simple. You can use them as a stack. But if performa...
• Timon Gehr (8/35) Oct 26 2011 You exaggerate. The word 'caveat' appears exactly once in that article.
• Nick Sabalausky (8/34) Oct 27 2011 FWIW, my article can be summarized with a line that's [poorly] located r...
• Ary Manzana (3/39) Oct 27 2011 Nah, I liked your article, it assumes I know nothing and I like that.
• Nick Sabalausky (6/51) Oct 27 2011 Thanks. But you did have a good point, in fact it had already been naggi...
• Dominic Jones (10/10) Oct 28 2011 To conclude the matter regarding the absence of a FIFO stack in the
• Jonathan M Davis (5/15) Oct 28 2011 Pretty much any container that you would expect to be in a standard libr...
• Nick Sabalausky (13/18) Oct 27 2011 The matter of using D's arrays as a LIFO is discussed the other branch o...
• Steven Schveighoffer (8/31) Oct 27 2011 No, the granularity is on memory blocks. Once you slice off those first...
• travert phare.normalesup.org (Christophe) (10/33) Oct 27 2011 As far as I understand, if there is a pointer to an allocated memory
• Marco Leise (6/11) Nov 05 2011 Someone could have told me that the topic wasn't FILO stacks ^^. A "FILO...
• Dejan Lekic (2/11) Nov 04 2011 The Array can be used as both LIFO and FIFO structure.

Dominic Jones <dominic.jones qmul.ac.uk> writes:

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

"Simen Kjaeraas" <simen.kjaras gmail.com> writes:

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

"Simen Kjaeraas" <simen.kjaras gmail.com> writes:

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

"Marco Leise" <Marco.Leise gmx.de> writes:

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. :)

Dominic Jones <dominic.jones qmul.ac.uk> writes:

 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

"Jonathan M Davis" <jmdavisProg gmx.com> writes:

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

Ary Manzana <ary esperanto.org.ar> writes:

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.

"Jonathan M Davis" <jmdavisProg gmx.com> writes:

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

Jesse Phillips <jessekphillips+D gmail.com> writes:

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.

Timon Gehr <timon.gehr gmx.ch> writes:

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.

"Nick Sabalausky" <a a.a> writes:

"Ary Manzana" <ary esperanto.org.ar> wrote in message 
news:j89gle$9nn$1 digitalmars.com...
 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.

FWIW, my article can be summarized with a line that's [poorly] located right 
around the middle (annotations added):

"Slicing an array is fast [no allocation or copying], and appending is 
usually fast  [usually no allocation or copying], but slicing the end off 
and then appending is slow [does an allocate and copy]."

I guess I have a habit of making things longer than they need to be ;)

Ary Manzana <ary esperanto.org.ar> writes:

On 10/27/11 8:38 AM, Nick Sabalausky wrote:
 "Ary Manzana"<ary esperanto.org.ar>  wrote in message
 news:j89gle$9nn$1 digitalmars.com...
 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.

 FWIW, my article can be summarized with a line that's [poorly] located right
 around the middle (annotations added):

 "Slicing an array is fast [no allocation or copying], and appending is
 usually fast  [usually no allocation or copying], but slicing the end off
 and then appending is slow [does an allocate and copy]."

 I guess I have a habit of making things longer than they need to be ;)

Nah, I liked your article, it assumes I know nothing and I like that. 
Maybe I did was exaggerating...

"Nick Sabalausky" <a a.a> writes:

"Ary Manzana" <ary esperanto.org.ar> wrote in message 
news:j8buhd$1s80$1 digitalmars.com...
 On 10/27/11 8:38 AM, Nick Sabalausky wrote:
 "Ary Manzana"<ary esperanto.org.ar>  wrote in message
 news:j89gle$9nn$1 digitalmars.com...
 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.

 FWIW, my article can be summarized with a line that's [poorly] located 
 right
 around the middle (annotations added):

 "Slicing an array is fast [no allocation or copying], and appending is
 usually fast  [usually no allocation or copying], but slicing the end off
 and then appending is slow [does an allocate and copy]."

 I guess I have a habit of making things longer than they need to be ;)

 Nah, I liked your article, it assumes I know nothing and I like that. 
 Maybe I did was exaggerating...

Thanks. But you did have a good point, in fact it had already been nagging 
at me a little bit anyway: There's a very simple summary of the matter, but 
I didn't get around to spitting it out until halfway through. I've added a 
little thing to the top and feel a lot better about it now.

Dominic Jones <dominic.jones qmul.ac.uk> writes:

To conclude the matter regarding the absence of a FIFO stack in the
standard library and the not so good alternative of arrays (in
particular where there are a significant number of push-pops and the
maximum length is not initially known):

Does anyone in-the-know know if something like "DList" (a doubly
linked list) will be added to "std.containers" in the near future?

I, for one, would very much appreciate its implementation in the
standard library.

Regards,
Dominic

Jonathan M Davis <jmdavisProg gmx.com> writes:

On Friday, October 28, 2011 13:24:58 Dominic Jones wrote:
 To conclude the matter regarding the absence of a FIFO stack in the
 standard library and the not so good alternative of arrays (in
 particular where there are a significant number of push-pops and the
 maximum length is not initially known):
 
 Does anyone in-the-know know if something like "DList" (a doubly
 linked list) will be added to "std.containers" in the near future?
 
 I, for one, would very much appreciate its implementation in the
 standard library.

Pretty much any container that you would expect to be in a standard library 
will be in std.container eventually. But the custom allocator scheme has to be 
sorted out before that happens.

- Jonathan M Davis

"Nick Sabalausky" <a a.a> writes:

"Dominic Jones" <dominic.jones qmul.ac.uk> wrote in message 
news:j89arh$2ua3$1 digitalmars.com...
 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

The matter of using D's arrays as a LIFO is discussed the other branch of 
this thread (ie, you can do it, but it's slow because a "pop then push" will 
reallocate and copy), but as far as a FIFO: That may actually be reasonable 
to do as an array:

Decreasing the length of an array (from either end) is a trivial matter that 
never allocates or copies. Appending to the end *usually* doesn't involve 
allocating. So the only issue I see it that the FIFO will "march" across 
memory. I guess that's probably not a problem as long as the GC knows it can 
reclaim the stuff you've popped off (Does it do that? Ie, if you do "x = 
x[10..$];" and there's no other references, is the GC smart enough to 
reclaim those first ten spots? I guess I would assume so.) 

"Steven Schveighoffer" <schveiguy yahoo.com> writes:

On Thu, 27 Oct 2011 08:00:31 -0400, Nick Sabalausky <a a.a> wrote:

 "Dominic Jones" <dominic.jones qmul.ac.uk> wrote in message
 news:j89arh$2ua3$1 digitalmars.com...
 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

 The matter of using D's arrays as a LIFO is discussed the other branch of
 this thread (ie, you can do it, but it's slow because a "pop then push"  
 will
 reallocate and copy), but as far as a FIFO: That may actually be  
 reasonable
 to do as an array:

 Decreasing the length of an array (from either end) is a trivial matter  
 that
 never allocates or copies. Appending to the end *usually* doesn't involve
 allocating. So the only issue I see it that the FIFO will "march" across
 memory. I guess that's probably not a problem as long as the GC knows it  
 can
 reclaim the stuff you've popped off (Does it do that? Ie, if you do "x =
 x[10..$];" and there's no other references, is the GC smart enough to
 reclaim those first ten spots? I guess I would assume so.)

No, the granularity is on memory blocks.  Once you slice off those first  
10 elements, and you have no references to them, they become dead weight.

But, as you append to the end, it will eventually outgrow its block, and  
the dead weight is *not* carried to the new block, so it will then be  
reclaimed.  There are exceptions (such as when a block tacks on more  
pages).

-Steve

travert phare.normalesup.org (Christophe) writes:

"Nick Sabalausky" , dans le message (digitalmars.D.learn:30309), a
 écrit :
 "Dominic Jones" <dominic.jones qmul.ac.uk> wrote in message 
 news:j89arh$2ua3$1 digitalmars.com...
 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

 
 The matter of using D's arrays as a LIFO is discussed the other branch of 
 this thread (ie, you can do it, but it's slow because a "pop then push" will 
 reallocate and copy), but as far as a FIFO: That may actually be reasonable 
 to do as an array:
 
 Decreasing the length of an array (from either end) is a trivial matter that 
 never allocates or copies. Appending to the end *usually* doesn't involve 
 allocating. So the only issue I see it that the FIFO will "march" across 
 memory. I guess that's probably not a problem as long as the GC knows it can 
 reclaim the stuff you've popped off (Does it do that? Ie, if you do "x = 
 x[10..$];" and there's no other references, is the GC smart enough to 
 reclaim those first ten spots? I guess I would assume so.) 
 
 

As far as I understand, if there is a pointer to an allocated memory 
block, the GC keeps the whole memory block. So the data at the beginning 
of x will be kept as long as x is not reallocated (but x will be 
reallocated at some point, because it can't walk across memory 
indefinitely, unless the GC is particularly efficient at avoiding 
reallocation).

AFAIC, if I had to design a FIFO, I would use a circular array to avoid 
constant growing and reallocation of the array.

"Marco Leise" <Marco.Leise gmx.de> writes:

Am 26.10.2011, 18:00 Uhr, schrieb Dominic Jones <dominic.jones qmul.ac.uk>:

 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

Someone could have told me that the topic wasn't FILO stacks ^^. A "FILO"  
stack can use a dynamic array with assumeSafeAppend, which avoids the copy  
by telling the runtime that I definitely wont overwrite anything valuable  
in the array when I write pop(); push(...); (There are no other array  
slices operating on the same data block)

Dejan Lekic <dejan.lekic gmail.com> writes:

Dominic Jones 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?
 
 Thank you,
 Dominic Jones

The Array can be used as both LIFO and FIFO structure.