Remove elements without losing capacity

Oct 04, 2022

Riccardo M

Oct 04, 2022

Steven Schveighoffer

Oct 04, 2022

Oct 04, 2022

Oct 04, 2022

Oct 24, 2022

void main() { import std.algorithm.mutation : remove, SwapStrategy; import std.stdio : writeln; int[] arr = [1, 2, 3, 2, 4, 2, 5, 2]; assert(arr.length == 8); assert(arr.capacity == 11); arr = arr.remove!(SwapStrategy.unstable)(0); assert(arr.length == 7); assert(arr.capacity == 0); }

October 04, 2022

Re: Remove elements without losing capacity

Posted by Steven Schveighoffer
in reply to Riccardo M

Permalink

Steven Schveighoffer

Posted in reply to Riccardo M

Permalink

On 10/4/22 11:22 AM, Riccardo M wrote:

Is it possible to remove elements from a range without losing its capacity?

void main()
{
     import std.algorithm.mutation : remove, SwapStrategy;
     import std.stdio : writeln;

     int[] arr = [1, 2, 3, 2, 4, 2, 5, 2];

     assert(arr.length == 8);
     assert(arr.capacity == 11);

     arr = arr.remove!(SwapStrategy.unstable)(0);

     assert(arr.length == 7);
     assert(arr.capacity == 0);
}

Here capacity goes to 0. I wish to prevent future reallocations.

This loses the reserved capacity as well:

arr.length--

Yes, you use assumeSafeAppend:

arr.length--;
arr.assumeSafeAppend;
assert(arr.capacity != 0);

Now, I want to clarify that you should only use this if you are sure you are done with the data you removed at the end, as it will get overwritten upon more appends to the array.

e.g.:

auto arr = [1, 2, 3];
auto arr2 = arr;
arr.length--;
arr.assumeSafeAppend;
arr ~= 42;
assert(arr2[2] == 42); // overwritten!

This leads to undefined behavior if the array is immutable (e.g. a string).

-Steve

On 10/4/22 10:59, Riccardo M wrote: > The inherent reason for `remove` to cancel previous capacity and > requiring new allocations is exactly to prevent overwriting data that > could be owned by something else? Yes. A related topic is how the "end slice" never loses that capacity: void main() { auto a = [ 1, 2 ]; auto b = a; assert(a.capacity != 0); assert(b.capacity != 0); b.length--; assert(b.capacity == 0); assert(a.capacity != 0); // <-- Preserved } Aside: .capacity is an expensive operation that requires some levels of table lookups in the druntime. A data structure would benefit a lot if it kept its own capacity as a member variable. Ali

On Tuesday, 4 October 2022 at 18:18:41 UTC, Ali Çehreli wrote: > On 10/4/22 10:59, Riccardo M wrote: > > > The inherent reason for `remove` to cancel previous capacity > and > > requiring new allocations is exactly to prevent overwriting > data that > > could be owned by something else? > > Yes. > > A related topic is how the "end slice" never loses that capacity: > > void main() { > auto a = [ 1, 2 ]; > auto b = a; > > assert(a.capacity != 0); > assert(b.capacity != 0); > > b.length--; > assert(b.capacity == 0); > assert(a.capacity != 0); // <-- Preserved > } > > Aside: .capacity is an expensive operation that requires some levels of table lookups in the druntime. A data structure would benefit a lot if it kept its own capacity as a member variable. > > Ali Wonderful. Thanks for the insight,

On Tuesday, 4 October 2022 at 18:18:41 UTC, Ali Çehreli wrote: > A related topic is how the "end slice" never loses that capacity: > > void main() { > auto a = [ 1, 2 ]; > auto b = a; > > assert(a.capacity != 0); > assert(b.capacity != 0); > > b.length--; > assert(b.capacity == 0); > assert(a.capacity != 0); // <-- Preserved > } > > Aside: .capacity is an expensive operation that requires some levels of table lookups in the druntime. A data structure would benefit a lot if it kept its own capacity as a member variable. I've now made a pull to document this: https://github.com/dlang/dlang.org/pull/3445

Forums