Hello guys,

I'm looking for an implementation of a data structure that allows for fast:

- find insertion point that preserves ordering
- get element after that point
- insertion of a value at that point
- sorted iteration

I thought about the `BTreeSet`

, however the catch here is that my data can have repeated values (as in `Ordering::Equal`

) and I want to keep all occurences. So maybe I'm looking for `BTree`

?

Searching around, I've found this question that asks for BTree but no mention of allowing for repeated values.

Sorry if the question is dumb in its essence. I'll add more context that may help understanding:

I'm implementing a space-efficient quantile algorithm that allows to get an approximation of a desired quantile (like median) of a huge Iterator (inspired by Spark's `approx_percentile`

). The core of the algorithm is to keep an ordered list of some sampled values (around with some metadata) and update it as we go: adding new samples (`insert_one`

), dropping old samples (`compress`

).

Here is some pseudo-rust code that highlights the uses of the data structure I'm searching for (`SomeNiceDataStructure`

):

```
// Relevant structs
struct Sample<T: Ord> {
value: T,
g: u64,
delta: u64
}
impl<T: Ord> Ord for Sample<T> { /* delegates to self.value */ }
pub struct Summary<T: Ord> {
samples: SomeNiceDataStructure<Sample<T>>
}
// Relevant methods
impl<T: Ord> Summary<T> {
pub fn insert_one(&mut self, value: T) {
let insert_before = self.samples.insertion_point(value);
if self.should_insert(value, insert_before) {
self.samples.insert_before(value, insert_before);
}
}
pub fn compress(&mut self) {
let mut new_samples = SomeNiceDataStructure::new();
for sample in self.samples {
if self.should_keep(sample) {
new_samples.push(sample); // we know insertion is ordered here
}
}
self.samples = new_samples;
}
}
```

Do you know what I should use for this? Either inside the std lib or some external crate. Maybe my requirements are too specific and I may have to roll my own? (I'd strongly prefer not to, I'm not versed well enough in Rust for that )

Any suggestion is welcomed!

Thanks a lot