"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 ;)

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

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

"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.

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

"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.

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

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

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.

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)