www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Remove elements without losing capacity

reply Riccardo M <asd asd.asd> writes:
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--
```

Thanks
Oct 04 2022
parent reply Steven Schveighoffer <schveiguy gmail.com> writes:
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`:

```d
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.:

```d
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
Oct 04 2022
parent reply Riccardo M <asd asd.asd> writes:
On Tuesday, 4 October 2022 at 15:42:21 UTC, Steven Schveighoffer 
wrote:

 Yes, you use `assumeSafeAppend`:

 ```d
 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.

 [...]


Thanks! I can use the unstable `remove` and then restore the 
original capacity with `assumeSafeAppend` in case data can be 
safely overwritten.

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?
Oct 04 2022
parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
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
Oct 04 2022
next sibling parent Riccardo M <asd asd.asd> writes:
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,
Oct 04 2022
prev sibling parent Nick Treleaven <nick geany.org> writes:
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
Oct 24 2022