# Comparator for BTree(Map|Set)s

**URL:** <https://internals.rust-lang.org/t/comparator-for-btree-map-set-s/17011>\
**Category:** libs\
**Created:** [July 14, 2022, 1:38pm UTC](https://internals.rust-lang.org/t/comparator-for-btree-map-set-s/17011 "2022-07-14T13:38:36Z")\
**Posts on this page:** 1\
**Showing post:** 8

<div class="post-metadata">

**Author:** ![mokhaled](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/mokhaled/32/9607_2.png) [@mokhaled](https://internals.rust-lang.org/u/mokhaled)\
**Post date:** [July 16, 2022, 5:35am UTC](https://internals.rust-lang.org/t/comparator-for-btree-map-set-s/17011/8 "2022-07-16T05:35:01Z")

</div>

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:

```rust
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](https://internals.rust-lang.org/t/interface-improvements-for-btreemap/16957/7)

I also stumbled upon those interesting [Intrusive Data Structures](https://docs.rs/intrusive-collections/latest/intrusive_collections/rbtree/struct.RBTree.html#method.lower_bound_mut) but the APIs unfortunately don't accept comparator closures.

---

_[View the full topic](https://internals.rust-lang.org/t/comparator-for-btree-map-set-s/17011)._