Sorted Array (Container) Type

Siarhei Siamashka siarhei.siamashka at gmail.com
Tue Nov 15 23:27:07 UTC 2022


On Tuesday, 15 November 2022 at 20:09:40 UTC, Per Nordlöw wrote:
> I wanted a sorted array because I want to include it in a 
> benchmark suite and study it's time and space complexity. No 
> application yet.

For doing a fast insert into an already sorted array (and 
avoiding duplicated values) it's probably better to do something 
like this:

```D
bool fast_insert_into_a_sorted_array(alias less = "a < b", T)(ref 
T[] a, T value)
{
   auto pos = a.assumeSorted!(less).lowerBound(value).length;
   if (pos < a.length && a[pos] == value)
     return false; // indicate no insert
   a.insertInPlace(pos, value);
   return true; // indicate insert
}
```


More information about the Digitalmars-d-learn mailing list