www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Dynamic Arrays as Stack and/or Queue

reply Just Dave <abcdef 1234.com> writes:
I need a stack and a queue and I noticed that the standard 
library doesn't appear to have one. Which is ok. I just need 
something that can logically behave as a stack and queue, which I 
think the dynamic array should be able to do (if I understand 
correctly this is effectively the equivalent of vector<T> in C++ 

the best way to push, pop, enqueue and dequeue using D.

I'm not seeing here: https://dlang.org/spec/arrays.html, anyway 
to remove from the array. What's the correct syntax/method call 
for this? I see you can easily concatenate with '~', but I see no 
corresponding delete.

Sorry for the newbie question, but I'm just unsure where to look 
for this.
Oct 07 2019
next sibling parent mipri <mipri minimaltype.com> writes:
On Monday, 7 October 2019 at 17:11:08 UTC, Just Dave wrote:

 I need a stack and a queue and I noticed that the standard 
 library doesn't appear to have one. Which is ok. I just need 
 something that can logically behave as a stack and queue, which 
 I think the dynamic array should be able to do (if I understand 
 correctly this is effectively the equivalent of vector<T> in 

 out the best way to push, pop, enqueue and dequeue using D.

 I'm not seeing here: https://dlang.org/spec/arrays.html, anyway 
 to remove from the array. What's the correct syntax/method call 
 for this? I see you can easily concatenate with '~', but I see 
 no corresponding delete.

 Sorry for the newbie question, but I'm just unsure where to 
 look for this.


if the top of the stack is the last element, --stack.length works
as a simple pop.
Oct 07 2019
prev sibling next sibling parent reply bachmeier <no spam.net> writes:
On Monday, 7 October 2019 at 17:11:08 UTC, Just Dave wrote:

 I need a stack and a queue and I noticed that the standard 
 library doesn't appear to have one. Which is ok. I just need 
 something that can logically behave as a stack and queue, which 
 I think the dynamic array should be able to do (if I understand 
 correctly this is effectively the equivalent of vector<T> in 

 out the best way to push, pop, enqueue and dequeue using D.

 I'm not seeing here: https://dlang.org/spec/arrays.html, anyway 
 to remove from the array. What's the correct syntax/method call 
 for this? I see you can easily concatenate with '~', but I see 
 no corresponding delete.

 Sorry for the newbie question, but I'm just unsure where to 
 look for this.


Does slicing do what you need?

x[1..$]
Oct 07 2019
parent Just Dave <abcdef 1234.com> writes:
On Monday, 7 October 2019 at 17:18:03 UTC, bachmeier wrote:

 On Monday, 7 October 2019 at 17:11:08 UTC, Just Dave wrote:

 I need a stack and a queue and I noticed that the standard 
 library doesn't appear to have one. Which is ok. I just need 
 something that can logically behave as a stack and queue, 
 which I think the dynamic array should be able to do (if I 
 understand correctly this is effectively the equivalent of 

 time figuring out the best way to push, pop, enqueue and 
 dequeue using D.

 I'm not seeing here: https://dlang.org/spec/arrays.html, 
 anyway to remove from the array. What's the correct 
 syntax/method call for this? I see you can easily concatenate 
 with '~', but I see no corresponding delete.

 Sorry for the newbie question, but I'm just unsure where to 
 look for this.


 Does slicing do what you need?

 x[1..$]


I have no clue. My problem is I need a stack and queue and I'm a 
little unsure the 'd' way to do it.
Oct 07 2019
prev sibling next sibling parent bachmeier <no spam.net> writes:
On Monday, 7 October 2019 at 17:11:08 UTC, Just Dave wrote:

 I need a stack and a queue and I noticed that the standard 
 library doesn't appear to have one. Which is ok. I just need 
 something that can logically behave as a stack and queue, which 
 I think the dynamic array should be able to do (if I understand 
 correctly this is effectively the equivalent of vector<T> in 

 out the best way to push, pop, enqueue and dequeue using D.

 I'm not seeing here: https://dlang.org/spec/arrays.html, anyway 
 to remove from the array. What's the correct syntax/method call 
 for this? I see you can easily concatenate with '~', but I see 
 no corresponding delete.

 Sorry for the newbie question, but I'm just unsure where to 
 look for this.


Also, these may be of interest:
https://dlang.org/phobos/std_array.html
https://dlang.org/phobos/std_range.html
Oct 07 2019
prev sibling next sibling parent reply Ferhat =?UTF-8?B?S3VydHVsbXXFnw==?= <aferust gmail.com> writes:
On Monday, 7 October 2019 at 17:11:08 UTC, Just Dave wrote:

 I need a stack and a queue and I noticed that the standard 
 library doesn't appear to have one. Which is ok. I just need 
 something that can logically behave as a stack and queue, which 
 I think the dynamic array should be able to do (if I understand 
 correctly this is effectively the equivalent of vector<T> in 

 out the best way to push, pop, enqueue and dequeue using D.

 I'm not seeing here: https://dlang.org/spec/arrays.html, anyway 
 to remove from the array. What's the correct syntax/method call 
 for this? I see you can easily concatenate with '~', but I see 
 no corresponding delete.

 Sorry for the newbie question, but I'm just unsure where to 
 look for this.


Built-in D arrays rely on garbage collector, and you don't need 
an explicit delete. For nogc arrays, there are 3rd party libs and 
std.container.array. take a look at
https://dlang.org/phobos/std_container_array.html
Oct 07 2019
parent reply Just Dave <abcdef 1234.com> writes:
On Monday, 7 October 2019 at 17:24:19 UTC, Ferhat Kurtulmuş wrote:

 On Monday, 7 October 2019 at 17:11:08 UTC, Just Dave wrote:

 I need a stack and a queue and I noticed that the standard 
 library doesn't appear to have one. Which is ok. I just need 
 something that can logically behave as a stack and queue, 
 which I think the dynamic array should be able to do (if I 
 understand correctly this is effectively the equivalent of 

 time figuring out the best way to push, pop, enqueue and 
 dequeue using D.

 I'm not seeing here: https://dlang.org/spec/arrays.html, 
 anyway to remove from the array. What's the correct 
 syntax/method call for this? I see you can easily concatenate 
 with '~', but I see no corresponding delete.

 Sorry for the newbie question, but I'm just unsure where to 
 look for this.


 Built-in D arrays rely on garbage collector, and you don't need 
 an explicit delete. For nogc arrays, there are 3rd party libs 
 and std.container.array. take a look at
 https://dlang.org/phobos/std_container_array.html


I'm not talking about memory deletion. I'm talking about push, 
pop, enqueue, and dequeue behavior. I'd assume in a garbage 
collected language letting the reference float off should be 
picked up by the GC.
Oct 07 2019
parent reply Ferhat =?UTF-8?B?S3VydHVsbXXFnw==?= <aferust gmail.com> writes:
On Monday, 7 October 2019 at 17:28:11 UTC, Just Dave wrote:

 On Monday, 7 October 2019 at 17:24:19 UTC, Ferhat Kurtulmuş 
 wrote:

 On Monday, 7 October 2019 at 17:11:08 UTC, Just Dave wrote:

 [...]


 Built-in D arrays rely on garbage collector, and you don't 
 need an explicit delete. For nogc arrays, there are 3rd party 
 libs and std.container.array. take a look at
 https://dlang.org/phobos/std_container_array.html


 I'm not talking about memory deletion. I'm talking about push, 
 pop, enqueue, and dequeue behavior. I'd assume in a garbage 
 collected language letting the reference float off should be 
 picked up by the GC.


I'm sorry. Writing on my mobile phone. Maybe this is what you are 
looking for
https://dlang.org/phobos/std_container_dlist.html
Oct 07 2019
parent reply IGotD- <nise nise.com> writes:
On Monday, 7 October 2019 at 17:36:09 UTC, Ferhat Kurtulmuş wrote:

 I'm not talking about memory deletion. I'm talking about push, 
 pop, enqueue, and dequeue behavior. I'd assume in a garbage 
 collected language letting the reference float off should be 
 picked up by the GC.


 I'm sorry. Writing on my mobile phone. Maybe this is what you 
 are looking for
 https://dlang.org/phobos/std_container_dlist.html


I think what he is looking for are the general pop_front, 
push_front, pop_back and push_back that you would find in 
virtually any C++ STL container algorithms like list, vector or 
map.

I think this is a good question as I don't really see any good 
example in the documentation of the dynamic arrays about this. 
This is very common use case for arrays. Is there any D 
equivalent?
Oct 07 2019
next sibling parent reply mipri <mipri minimaltype.com> writes:
On Monday, 7 October 2019 at 19:16:31 UTC, IGotD- wrote:

 On Monday, 7 October 2019 at 17:36:09 UTC, Ferhat Kurtulmuş 
 wrote:

 I'm not talking about memory deletion. I'm talking about 
 push, pop, enqueue, and dequeue behavior. I'd assume in a 
 garbage collected language letting the reference float off 
 should be picked up by the GC.


 I'm sorry. Writing on my mobile phone. Maybe this is what you 
 are looking for
 https://dlang.org/phobos/std_container_dlist.html


 I think what he is looking for are the general pop_front, 
 push_front, pop_back and push_back that you would find in 
 virtually any C++ STL container algorithms like list, vector or 
 map.

 I think this is a good question as I don't really see any good 
 example in the documentation of the dynamic arrays about this. 
 This is very common use case for arrays. Is there any D 
 equivalent?


With the performance that you'd expect, I believe:


import std.stdio;
import std.algorithm : moveAll;

void push_front(T)(ref T[] xs, T x) {
     ++xs.length;
     moveAll(xs[0 .. $-1], xs[1..$]);
     x[0] = x;
}
T pop_front(T)(ref T[] xs) {
     T x = xs[0];
     moveAll(xs[1 .. $], xs[0 .. $-1]);
     --xs.length;
     return x;
}
void push_back(T)(ref T[] xs, T x) {
     xs ~= x;
}
T pop_back(T)(ref T[] xs) {
     T x = xs[$ - 1];
     --xs.length;
     return x;
}

void main() {
     int[] xs;
     foreach (i; 0 .. 10)
         xs.push_back(i);
     writeln(xs.pop_back());  // output: 9
     writeln(xs.pop_front()); // output: 0
     writeln(xs.pop_front()); // output: 1
     writeln(xs); // output: [2, 3, 4, 5, 6, 7, 8]
}
Oct 07 2019
parent Alex <sascha.orlov gmail.com> writes:
On Monday, 7 October 2019 at 19:38:50 UTC, mipri wrote:

 On Monday, 7 October 2019 at 19:16:31 UTC, IGotD- wrote:

 On Monday, 7 October 2019 at 17:36:09 UTC, Ferhat Kurtulmuş 
 wrote:

 I'm not talking about memory deletion. I'm talking about 
 push, pop, enqueue, and dequeue behavior. I'd assume in a 
 garbage collected language letting the reference float off 
 should be picked up by the GC.


 I'm sorry. Writing on my mobile phone. Maybe this is what you 
 are looking for
 https://dlang.org/phobos/std_container_dlist.html


 I think what he is looking for are the general pop_front, 
 push_front, pop_back and push_back that you would find in 
 virtually any C++ STL container algorithms like list, vector 
 or map.

 I think this is a good question as I don't really see any good 
 example in the documentation of the dynamic arrays about this. 
 This is very common use case for arrays. Is there any D 
 equivalent?


 With the performance that you'd expect, I believe:


 [...]


I assume this is a little bit more complicated:
while popFront and popBack are ubiquitous in ranges in D, the 
push functions can't be unified in terms of memory management. 
For example, you cannot guarantee any performance, while using 
GC. This opposed to complexity, which is, of course, known.

Maybe, this is the reason, why such containers are omitted in 
Phobos (?)

But:
There is a priority queue, named binaryheap:
https://dlang.org/phobos/std_container_binaryheap.html

and there are hints, that for a stack you have to rely e.g., on 
an array or a list implementation
http://www.cplusplus.com/reference/stack/stack/
both exist in phobos:
https://dlang.org/phobos/std_container_array.html
https://dlang.org/phobos/std_container_dlist.html

This gives rise to user implementations like
https://code.dlang.org/packages/queue
https://code.dlang.org/packages/mergearray
etc.

Maybe, there will be more soon? ;)
Oct 07 2019
prev sibling parent reply Jonathan M Davis <newsgroup.d jmdavisprog.com> writes:
On Monday, October 7, 2019 1:16:31 PM MDT IGotD- via Digitalmars-d-learn 
wrote:

 On Monday, 7 October 2019 at 17:36:09 UTC, Ferhat Kurtulmuş wrote:

 I'm not talking about memory deletion. I'm talking about push,
 pop, enqueue, and dequeue behavior. I'd assume in a garbage
 collected language letting the reference float off should be
 picked up by the GC.


 I'm sorry. Writing on my mobile phone. Maybe this is what you
 are looking for
 https://dlang.org/phobos/std_container_dlist.html


 I think what he is looking for are the general pop_front,
 push_front, pop_back and push_back that you would find in
 virtually any C++ STL container algorithms like list, vector or
 map.

 I think this is a good question as I don't really see any good
 example in the documentation of the dynamic arrays about this.
 This is very common use case for arrays. Is there any D
 equivalent?


Pushing and popping like you'd do with a stack or queue can certainly be
done with a dynamic array, but D's dynamic arrays don't work very well that
way without wrapping them. Shrinking them is easy enough. You just slice the
dynamic array to get another dynamic array which is a slice referring just
to the elements that were sliced. e.g.

auto arr2 = arr1[5 .. $];
assert(arr2.length == arr1.length - 5);
assert(arr2 == arr1[5 .. $]);

If you just want to pop off the first element, you can even use popFront
from std.range.primitives. e.g.

auto arr2 = arr1;
arr2.popFront();
assert(arr2 == arr1[1 .. $]);

Similarly, you could use popBack to pop off the last element. e.g.

auto arr2 = arr1;
arr2.popBack();
assert(arr2 == arr1[0 .. $ - 1]);

~= can be used to append to a dynamic array, but then we start getting into
some issues.

When a dynamic array is appended to, the GC determines whether it has the
capacity to put that element one past the end of that dynamic array within
the block of memory that that dynamic array is a slice of. If the dynamic
array is not a slice of GC-allocated memory for dynamic arrays, then the GC
determines that it can't append in place, so it allocates a new block of
memory, copies the elements to that new block of memory (including the
appendend elements), and then mutates that dynamic array to point to the new
block of memory. Similarly, if the dynamic array refers to a GC-allocated
block of memory with no extra space on the end, the GC will allocate a new
block of memory, copy the elements over, and mutate the dynamic array to
point to the new block of memory. On the other hand, if the memory block was
allocated by the GC for dynamic arrays, and it does have space beyond the
end of that dynamic array, then it will just append in place and adjust the
length member of the dynamic array accordingly. However, the real kicker for
this particular use case is what happens when the dynamic array's last
element is not the last element used within the memory block. e.g.

arr2 = arr1[0 .. $ - 1];
arr2 ~= 42;

or even

arr1 = arr1[0 .. $ - 1];
arr1 ~= 42;

Both of those examples will result in a new block of memory being allocated
when the dynamic array is appended to. That's because the GC is written to
avoid appending into another dynamic array which refers to the same block of
memory. In order for a dynamic array to have capacity to expand into, no
other dynamic array can ever have had any elements beyond the end of that
dynamic array (the metadata keeps track of the farthest that any array has
expanded into the block of memory). Even if there are currently no other
dynamic arrays which refer to that element, it doesn't matter. All the GC
cares about is whether any dynamic array has ever expanded that far into the
memory block.

The result of this is that code like

stack.popBack();
stack ~= foo;
stack ~= bar;
stack.popBack();
stack ~= baz;

will end up allocating all over the place. Every time you append to the
array after shrinking it, you're going to end up with the GC allocating a
new block of memory instead of appending in place.

The solution to this problem is to use the function assumeSafeAppend
(it's in object.d, so it's always available). e.g.

stack.popBack();
stack.assumeSafeAppend();
stack ~= foo;
stack ~= bar;
stack.popBack();
stack.assumeSafeAppend();
stack ~= baz;

This tells the GC to reset the metadata for the block of memory that that
dynamic array is a slice of so that however far the last element of that
dynamic array is is considered to be the last element curently used in the
memory block. That way, when you append to it, it won't think that there are
any other dynamic arrays using that memory, and it will expand the array in
place.

The problem with this (and the reason that assumeSafeAppend is  system) is
that if you ever use it when there are still other dynamic arrays in use
which are slices of that same block of memory and which refer to elements
beyond the end of the dynamic array that you call assumeSafeAppend on,
you're going to get some subtle and nasty bugs. Because of that issue, it's
not necessarily a great idea to put a tutorial for beginners somewhere about
how to use a D dynamic array as a stack or queue. It can work quite well to
use a dynamic array in the internal implementation of a stack or queue, but
you probably don't want to do to it with a naked dynamic array.

The problem with queues isn't quite the same as with stacks, but it's also
something that you need to be careful about. If you keep doing something
like appending elements to the end and popping elements off of the front,
that dynamic array is going to be an ever shifting slice of a memory block
until it can't expand in place, and then you'd end up with a new memory
block for that dynamic array being allocated. If the queue never gets very
large, then you're just going to keep getting the underlying memory block
for the dynamic array getting allocated over and over again without it
growing, because when the array is reallocated, I'm pretty sure that the new
size is based on the current size of the dynamic array, not the size of the
underlying memory block.

Using std.algorithm's remove function instead of shrinking the slice at the
front fixes that problem (it moves the elements forward within the dynamic
array and then returns a dynamic array one element shorter), but then you
need assumeSafeAppend, and it means that you're constantly moving the
elements, which probably isn't good. There are of course several ways that
this problem could be tackled to minimize the number of allocations while
still avoiding constantly moving the elements around, but as with a stack,
it's the sort of thing where you'd want to wrap the dynamic array in a
struct or class to manage all of the logic required for pushing and popping
elements instead of using a naked dynamic array.

- Jonathan M Davis
Oct 08 2019
next sibling parent Just Dave <abcdef 1234.com> writes:
Thanks for the advice. I used a quick and dirty range solution as 
was suggested. It allowed me to move on as I really wasn't 
looking to fully implement a queue or stack. Just get something 
that semantically behaved as such. I'll return later and optimize 
it with the later suggestions if it's a major issue.
Oct 08 2019
prev sibling parent reply mipri <mipri minimaltype.com> writes:
On Tuesday, 8 October 2019 at 10:48:45 UTC, Jonathan M Davis 
wrote:

 The result of this is that code like

 stack.popBack();
 stack ~= foo;
 stack ~= bar;
 stack.popBack();
 stack ~= baz;

 will end up allocating all over the place. Every time you
 append to the array after shrinking it, you're going to end up
 with the GC allocating a new block of memory instead of
 appending in place.


Thanks as well! I thought the code I posted would only allocate 
when
the array ran out of capacity. And I see how, even if that's 
worked
around with assumeSafeAppend, it becomes a bad idea to define the
stack functions against `ref T[]` as this makes it too easy for 
other
code to slice the array and cause the bugs that assumeSafeAppend
allows.
Oct 08 2019
next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Tue, Oct 08, 2019 at 08:42:22PM +0000, mipri via Digitalmars-d-learn wrote:

 On Tuesday, 8 October 2019 at 10:48:45 UTC, Jonathan M Davis wrote:

 The result of this is that code like
 
 stack.popBack();
 stack ~= foo;
 stack ~= bar;
 stack.popBack();
 stack ~= baz;
 
 will end up allocating all over the place. Every time you
 append to the array after shrinking it, you're going to end up
 with the GC allocating a new block of memory instead of
 appending in place.
 


 
 Thanks as well! I thought the code I posted would only allocate when
 the array ran out of capacity. And I see how, even if that's worked
 around with assumeSafeAppend, it becomes a bad idea to define the
 stack functions against `ref T[]` as this makes it too easy for other
 code to slice the array and cause the bugs that assumeSafeAppend
 allows.


IMO, the best way to implement a stack using built-in arrays is to wrap
the array inside a struct that separately keeps track of the last
element. Something like this:

	// Warning: untested code
	struct Stack(T) {
		private T[] impl;
		private size_t idx;
		...
		void push(T t) {
			if (impl.length <= idx)
				impl.length = ...; //expand by some amount
			impl[idx++] = t;
		}
		T pop() in(idx > 0) {
			// ... optional: reduce impl.length if idx /
			// .length ratio smalle than some threshold.

			return impl[idx--];
		}
	}


T

-- 
LINUX = Lousy Interface for Nefarious Unix Xenophobes.
Oct 08 2019
prev sibling parent Jonathan M Davis <newsgroup.d jmdavisprog.com> writes:
On Tuesday, October 8, 2019 2:42:22 PM MDT mipri via Digitalmars-d-learn 
wrote:

 On Tuesday, 8 October 2019 at 10:48:45 UTC, Jonathan M Davis

 wrote:

 The result of this is that code like

 stack.popBack();
 stack ~= foo;
 stack ~= bar;
 stack.popBack();
 stack ~= baz;

 will end up allocating all over the place. Every time you
 append to the array after shrinking it, you're going to end up
 with the GC allocating a new block of memory instead of
 appending in place.


 Thanks as well! I thought the code I posted would only allocate
 when
 the array ran out of capacity. And I see how, even if that's
 worked
 around with assumeSafeAppend, it becomes a bad idea to define the
 stack functions against `ref T[]` as this makes it too easy for
 other
 code to slice the array and cause the bugs that assumeSafeAppend
 allows.


Technically, it only does allocate when it runs out of capacity. However, if
you do something like

arr = arr[0 .. $ - 1];

then arr.capacity will either be the length of the array or 0 (I don't
remember which off the top of my head), because the capacity is calculated
based on how much space is available after the end of the dynamic array. How
much space is available at the end of the memory block is irrelevant unless
the dynamic array includes the last element that any dynamic array has ever
had within that memory block. If it's at the end, and the capacity is
greater than the length of the array, then the array can expand in place (up
to the difference between the length and the capacity). But if there is no
extra room on the end, or if the current dynamic array is not at the end,
then the capacity will reflect that. The same goes if the dynamic array is
actually a slice of memory that wasn't allocated by the GC for dynamic
arrays. IIRC, a dynamic array which is a slice of malloc-ed memory will
always give a capacity of 0, but regardless of whether it's actually 0, it's
never more than the length of the dynamic array, because there is no extra
capacity to grow into, since the memory was not allocated by the GC for use
by a dynamic array.

All of the various dynamic array functions work the same regardless of what
kind of memory is backing the dynamic array. It's just that if the memory
wasn't allocated by the GC for dynamic arrays, then when you call the
dynamic array function or property, then the GC treats it the same as it
would treat a dynamic array that referred to the end of the block of memory
(and thus wouldn't have any extra capacity).

You should always be able to call capacity on a dynamic array and see
whether appending to would then result in a reallocation or not.

Either way, because assumeSafeAppend resets the metadata so that the dynamic
array it's given is considered to be the farthest dynamic array within the
block of memory, after calling assumeSafeAppend, capacity will reflect that.

- Jonathan M Davis
Oct 08 2019
prev sibling parent =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 10/07/2019 10:11 AM, Just Dave wrote:

 I need a stack and a queue


There is a DoubleEndedQueue example under "Indexing Operators" here:

 
http://ddili.org/ders/d.en/operator_overloading.html#ix_operator_overloading.opIndexOpAssign

It does not have the pop varieties but it should be trivial to add those 
because it internally uses two slices and the "head" of the whole 
container is the actual "end" of one of those slices. (The elementAt() 
member function takes care of reversed indexing for half of the elements.)

I stole the idea of that example from Chuck Allison after one of his 
DConf presentations.

Ali
Oct 07 2019