Hello all,

The documentation describes ~= as (dynamic) array concatenation.
I've noticed that it can also add an element to a dynamic
array, as e.g. in:
int[] a;
int t;
..
a ~= t;
which makes a beautiful generic push operation for stacks.
But, then, what about the pop operation?  As far as I know,
it is not directly supported in D, or am I missing something?
Currently, I use the following:

template Pop(T)  {
T pop(inout T[] arr)  {
uint n = arr.length;
assert(n>0);
T t = arr[--n];
arr.length = n;
return t;
}
}

but it seems too clunky.  I would much prefer to have
a single operation built in the language, which pops an
element or throws an exception if the array is empty.
In view of D having dynamic arrays anyway, this seems
a reasonable expectation,.

I would be glad to know other people's opinions on the above.

Regards,
Boyko

In article <e1b0dn$28vl$1@digitaldaemon.com>, Boyko Bantchev says...
>
>int[] a;
>int t;
>..
>a ~= t;
>which makes a beautiful generic push operation for stacks.

Maybe beautifully generic, but horrendously inefficient. It gives you linear complexity for each push, which is really not what you're looking for in a Stack implementation.

cheers
Mike

Boyko Bantchev wrote:

> Hello all,
> 
> The documentation describes ~= as (dynamic) array concatenation.
> I've noticed that it can also add an element to a dynamic
> array, as e.g. in:
> int[] a;
> int t;
> ..
> a ~= t;
> which makes a beautiful generic push operation for stacks.
> But, then, what about the pop operation?  As far as I know,
> it is not directly supported in D, or am I missing something?
> Currently, I use the following:
> 
> template Pop(T)  {
> T pop(inout T[] arr)  {
> uint n = arr.length;
> assert(n>0);
> T t = arr[--n];
> arr.length = n;
> return t;
> }
> }
> 
> but it seems too clunky.  I would much prefer to have
> a single operation built in the language, which pops an
> element or throws an exception if the array is empty.
> In view of D having dynamic arrays anyway, this seems
> a reasonable expectation,.
> 
> I would be glad to know other people's opinions on the above.
> 
> Regards,
> Boyko

You can use array slicing to do it:
int[] a;
int t;
...
a ~= t;
...
t = a[$-1]; //Get the last element
a = a[0..$-1]; //Slice off the last element

But Mike Capp is right: in terms of efficiency, this is a horrible way to do it.  For a stack, you're better off with a linked list.

~John Demme

In article <e1bbeq$2o6o$1@digitaldaemon.com>, Mike Capp says...
>
>In article <e1b0dn$28vl$1@digitaldaemon.com>, Boyko Bantchev says...
>>
>>int[] a;
>>int t;
>>..
>>a ~= t;
>>which makes a beautiful generic push operation for stacks.
>
>Maybe beautifully generic, but horrendously inefficient. It gives you linear complexity for each push, which is really not what you're looking for in a Stack implementation.
>
>cheers
>Mike

Does it really have to be so?  E.g., the stack might be based on a slice
of some other (sufficiently large) array, so that it can be resized without
actually reallocating and copying.  Should a push not be performed in
constant time then?
And should a `pop' operation (which was what I have been proposing in my
previous post) not cause even less trouble in terms of efficiency?

My point is, stack is too important a structure not to support it
smoothly in a language that already has the necessary instrumentation for that.

Cheers,
Boyko

John Demme wrote:
> 
> You can use array slicing to do it:
> int[] a;
> int t;
> ...
> a ~= t;
> ...
> t = a[$-1]; //Get the last element
> a = a[0..$-1]; //Slice off the last element
> 
> But Mike Capp is right: in terms of efficiency, this is a horrible way to do
> it.  For a stack, you're better off with a linked list.

Interestingly, a dynamic array that doubles capacity on allocations is typically better than a linked-list implementation these days.  Linked lists tend to have poor locality, which can result in cache problems and page faults.


Sean

Mike Capp wrote:
> In article <e1b0dn$28vl$1@digitaldaemon.com>, Boyko Bantchev says...
>> int[] a;
>> int t;
>> ..
>> a ~= t;
>> which makes a beautiful generic push operation for stacks.
> 
> Maybe beautifully generic, but horrendously inefficient. It gives you linear
> complexity for each push, which is really not what you're looking for in a Stack
> implementation.

No, it is rather efficient. It does't realloc/copy for each push, as it uses a power of 2 algorithm to resize the array.

On Sun, 09 Apr 2006 17:32:20 -0700, Walter Bright wrote:

> Mike Capp wrote:
>> In article <e1b0dn$28vl$1@digitaldaemon.com>, Boyko Bantchev says...
>>> int[] a;
>>> int t;
>>> ..
>>> a ~= t;
>>> which makes a beautiful generic push operation for stacks.
>> 
>> Maybe beautifully generic, but horrendously inefficient. It gives you linear complexity for each push, which is really not what you're looking for in a Stack implementation.
> 
> No, it is rather efficient. It does't realloc/copy for each push, as it uses a power of 2 algorithm to resize the array.

And also, I believe, that popping an element does not involve a memory reallocation either. The empty space is not reclaimed and is available for the next 'push' operation.

For example ...

   int Pop(int[] pStack)
   {
       int l_Item;
       if (pStack.length > 0)
       {
           // Grab last item
           l_Item = a[$-1];
           // Remove it from the stack list.
           pStack.length = pStack.length - 1;
       }
       else
       {
           throw new Exception("Pop: Stack is empty");
       }

       return l_Item;
   }



-- 
Derek
(skype: derek.j.parnell)
Melbourne, Australia
"Down with mediocracy!"
10/04/2006 12:01:04 PM

But in the posted code, for every pop() operation, the length is set

> arr.length = n;

doesn't this do a realloc the memory every time it is called ? if pop is done many times, this should definitly make it inefficient.

does't it ?

Thanks
Sai


In article <e1c92h$o2s$1@digitaldaemon.com>, Walter Bright says...
>
>Mike Capp wrote:
>> In article <e1b0dn$28vl$1@digitaldaemon.com>, Boyko Bantchev says...
>>> int[] a;
>>> int t;
>>> ..
>>> a ~= t;
>>> which makes a beautiful generic push operation for stacks.
>> 
>> Maybe beautifully generic, but horrendously inefficient. It gives you linear complexity for each push, which is really not what you're looking for in a Stack implementation.
>
>No, it is rather efficient. It does't realloc/copy for each push, as it uses a power of 2 algorithm to resize the array.

Never mind ....
Derek's post made it clear.

Sai


In article <e1cjvk$18rf$1@digitaldaemon.com>, sai says...
>
>But in the posted code, for every pop() operation, the length is set
>
>> arr.length = n;
>
>doesn't this do a realloc the memory every time it is called ? if pop is done many times, this should definitly make it inefficient.
>
>does't it ?
>
>Thanks
>Sai
>
>
>In article <e1c92h$o2s$1@digitaldaemon.com>, Walter Bright says...
>>
>>Mike Capp wrote:
>>> In article <e1b0dn$28vl$1@digitaldaemon.com>, Boyko Bantchev says...
>>>> int[] a;
>>>> int t;
>>>> ..
>>>> a ~= t;
>>>> which makes a beautiful generic push operation for stacks.
>>> 
>>> Maybe beautifully generic, but horrendously inefficient. It gives you linear complexity for each push, which is really not what you're looking for in a Stack implementation.
>>
>>No, it is rather efficient. It does't realloc/copy for each push, as it uses a power of 2 algorithm to resize the array.
>
>