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
