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