www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - implementing stacks using dynamic arrays

reply Boyko Bantchev <Boyko_member pathlink.com> writes:
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
Apr 09 2006
next sibling parent reply Mike Capp <mike.capp gmail.com> writes:
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
Apr 09 2006
next sibling parent Boyko Bantchev <Boyko_member pathlink.com> writes:
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
Apr 09 2006
prev sibling parent reply Walter Bright <newshound digitalmars.com> writes:
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.
Apr 09 2006
next sibling parent Derek Parnell <derek psych.ward> writes:
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
Apr 09 2006
prev sibling parent reply sai <sai_member pathlink.com> writes:
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.
Apr 09 2006
parent sai <sai_member pathlink.com> writes:
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.
Apr 09 2006
prev sibling parent reply John Demme <me teqdruid.com> writes:
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
Apr 09 2006
parent Sean Kelly <sean f4.ca> writes:
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
Apr 09 2006