I have read doc for std.range and std.algorithm, but I have not found how I could add new value to SortedRange. What I want is to sort some array of structs by one of it's fields using custom predicate and save this SortedRange somewhere. But also I need to be able to append new elements into array and keep it sorted and using advantages of sorted data structure to for doing it quick.

Is it possible to do it in current implementation of SortedRange. If not what workarounds would you advise?

On Saturday, 15 February 2014 at 09:51:57 UTC, Uranuz wrote:
> I have read doc for std.range and std.algorithm, but I have not found how I could add new value to SortedRange. What I want is to sort some array of structs by one of it's fields using custom predicate and save this SortedRange somewhere. But also I need to be able to append new elements into array and keep it sorted and using advantages of sorted data structure to for doing it quick.
>
> Is it possible to do it in current implementation of SortedRange. If not what workarounds would you advise?

The range concept does not include any notion of growing. It's kind of messy, you have to grow the original:

---
T x = ...; // Insert x into...
T[] c = ...; // ...this sorted slice

auto pivot = c.assumeSorted().lowerBound(x).length;
c.insertInPlace(pivot, x);
---

For non-slice containers, use the `insertBefore` primitive (see std.container).

Use a container adequate for the task at hand, e.g. red-black tree.

Artem Tarasov:

> Use a container adequate for the task at hand, e.g. red-black tree.

If you have a limited number of small values (like 30 ints) using a sorted array is quite efficient, and keeps low the binary size and the pressure on the code L1 cache :-)

Arrays are awesome on modern CPUs.

Bye,
bearophile

On Sunday, 16 February 2014 at 12:41:45 UTC, Artem Tarasov wrote:
> Use a container adequate for the task at hand, e.g. red-black tree.

Very often a sorted array is the most adequate set implementation and we should have support for it in phobos.

On Sunday, 16 February 2014 at 12:51:10 UTC, bearophile wrote:
>
> If you have a limited number of small values (like 30 ints) using a sorted array is quite efficient, and keeps low the binary size and the pressure on the code L1 cache :-)

Yup, I admit I over-generalized.
But this sorted array should also be encapsulated into a convenient interface. At times, I really miss things like llvm::SmallVector/SmallSet/etc.