[chrisoverzero]

Does a Vec<u8> with that calculation listed end up smaller than two integers of (presumably) arbitrary length?

When I read about the problem, I imagined using the mediant to calculate “between”. I think that mediant of $value and 1/1 would work for “after” and mediant of $value and 0/1 would work for “before”.

There must be a requirement I’m missing, though!

mediant: https://en.wikipedia.org/wiki/Mediant_(mathematics)

[paulgb]

That would be an interesting thing to test! My first instinct is that the comparison operation (when denominators differ) would be more expensive.

In general some approaches should be better than others depending on how inserts are distributed — I think my approach is optimal when inserts are made at random (I haven’t proved this), but in practice it may be common for a bunch of things to be inserted in sequence for some applications. In those cases, there are more space-optimal approaches.