Comparator for BTree(Map|Set)s

libs
8

To make things simpler we can actually just make any cursor always point to a valid existing element or null for non existent lookups. In addition we simply support 3 operations all of which take a comparator and return a cursor.

  1. lower_bound
  2. upper_bound
  3. get

with the respective mut versions.

Since cursors support insert_after and insert_before then one can use the lower|upper_bound operations to insert new entries without doing multiple lookups or even better, imagine importing a sorted vector into your BTreeMap which would translate to one lower_bound operation and sequence of insert_after.

In that approach perhaps we can keep the builder as a holder for the comparator closure? So we end up with something like that:

pub fn BTreeMap::raw_entry_mut(&mut self, cmp: F) -> RawEntryBuilderMut<'_, K, V, S, OtherK>
where
    for<'b> F: FnMut(&'b K, &OtherK) -> Ordering,


pub fn RawEntryBuilderMut::get(self, &OtherK) -> RawEntryMut<'a, K, V>


pub fn RawEntryBuilderMut::lower_bound(self, &OtherK) -> RawEntryMut<'a, K, V>


pub fn RawEntryBuilderMut::upper_bound(self, &OtherK) -> RawEntryMut<'a, K, V>

enum RawEntryMut
{
Occupied(cursor),
Vacant
}

If K and OtherK are the same types then it is just a different way sorting K from the standard one provided by Ord but of course you get the advantage of having a stateful sorting closure.

This approach is heavily inspired by pretty much what you would do in C++ in a similar situation as I pointed out here

I also stumbled upon those interesting Intrusive Data Structures but the APIs unfortunately don't accept comparator closures.