# 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:** 10\
**Page:** 1

<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 14, 2022, 1:38pm UTC](https://internals.rust-lang.org/t/comparator-for-btree-map-set-s/17011/1 "2022-07-14T13:38:36Z")

</div>

Hi,

I was wondering if it is possible to have a custom comparator for the ordered collections (BtreeMap|Set) where one can pass closures. I have exactly the same use case described in the question below in which I have some dictionary (essentially a vector of strings) where all my strings are stored and I want to establish an order (using a `BtreeMap`) over that vector using the vector indices. So I want to lookup those integer values only for comparison. To me the current available options are really non appealing

1. Having the dictionary global and having to deal with all the hassle that comes from that.
2. Making my key carry an additional pointer to the dictionary seems like an overkill memory wise.

Perhaps another alternative can be adding a `raw_entry` API to the BTreeMaps similar to that in the `HashMap` where one can have access to the handle where the Entry is supposed to be inserted and it is up to the caller to find that entry with some closure.

[How can I implement Ord when the comparison depends on data not part of the compared items?](https://stackoverflow.com/questions/35786878/how-can-i-implement-ord-when-the-comparison-depends-on-data-not-part-of-the-comp)

---

<div class="post-metadata">

**Author:** ![CAD97](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/cad97/32/3460_2.png) [@CAD97](https://internals.rust-lang.org/u/CAD97)\
**Post date:** [July 14, 2022, 4:35pm UTC](https://internals.rust-lang.org/t/comparator-for-btree-map-set-s/17011/2 "2022-07-14T16:35:02Z")

</div>

As I said the previous time this came up

> [@Interface improvements for BTreeMap](https://internals.rust-lang.org/t/interface-improvements-for-btreemap/16957/3):
>
> Rather than storing a comparator, the more likely choice is probably something like the [hashmap raw\_entry API](https://docs.rs/hashbrown/latest/hashbrown/struct.HashMap.html#method.raw_entry), where you [provide the hash and an equality check callback](https://docs.rs/hashbrown/latest/hashbrown/hash_map/struct.RawEntryBuilder.html#method.from_hash), and [insertion takes a hashing function](https://docs.rs/hashbrown/latest/hashbrown/hash_map/struct.RawVacantEntryMut.html#method.insert_with_hasher).
> 
> For `BTreeMap` IIUC you'd just need `impl Fn(&Key) -> Ordering` for lookup and `Key, Value, impl Fn(&Key, &Key) -> Ordering` for insertion.
> 
> A stored comparator object is certainly more _convenient_, but providing one only when it's needed is more general and Rust has already biased for intrinsic ordering (e.g. `cmp::Reverse<T>`) rather than comparators.

> [@Interface improvements for BTreeMap](https://internals.rust-lang.org/t/interface-improvements-for-btreemap/16957/6):
>
> I'd be up to mentoring a `raw_cursor` implementation. [Open](https://github.com/rust-lang/libs-team/issues/new?assignees=&labels=api-change-proposal%2C+T-libs-api&template=api-change-proposal.md&title=BTreeMap%20Cursor%20API) an [API Change Proposal](https://std-dev-guide.rust-lang.org/feature-lifecycle/api-change-proposals.html) and ping me as a willing mentor (though note I don't have authority to second the proposal).

Though I've heard thought the grapevine that the std hashmap unstable raw\_entry API might be slated for removal? I think a btree raw\_cursor might be slightly easier to support, though, due to the more common use case of using a custom comparison, raw lookup in the btree being simpler than in the hashmap, and being able to provide cursor functionality through the raw API not available in the standard API.

---

<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 14, 2022, 8:47pm UTC](https://internals.rust-lang.org/t/comparator-for-btree-map-set-s/17011/3 "2022-07-14T20:47:24Z")

</div>

In fact I prefer a `raw_entry/cursor` API addition to the BTrees over a stored comparator. I already find the hashmap counterpart very useful and allows for various optimisations and it would be sad to not have it as part of the stable std finally and also surprising at the same time because it is already part of the stable `hashbrown` used by the standard. How can we raise some attention to the topic?

---

<div class="post-metadata">

**Author:** ![CAD97](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/cad97/32/3460_2.png) [@CAD97](https://internals.rust-lang.org/u/CAD97)\
**Post date:** [July 14, 2022, 9:39pm UTC](https://internals.rust-lang.org/t/comparator-for-btree-map-set-s/17011/4 "2022-07-14T21:39:49Z")

</div>

Note that hashbrown still has the freedom of API breaking changes, whereas std never gets those. Additionally, hashbrown actually has a second raw\_entry API used by std which is separate from the one available to crates-io consumers.

---

<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 14, 2022, 10:07pm UTC](https://internals.rust-lang.org/t/comparator-for-btree-map-set-s/17011/5 "2022-07-14T22:07:48Z")

</div>

Sure you are right about breaking changes. But honestly I do not see any reason to remove that API in the future if it becomes stable. One can utilize it for very good optimizations and from comments on the topic there are very common use cases for it. The only counter argument is that one might mistakenly break the invariants of the maps but this is already apparently possible as mentioned by the implementer of the hashmap's API in that [Comment](https://github.com/rust-lang/rust/pull/54043#issuecomment-421600398)

Anyway, at least if it's removed, one has the option to use the hashbrown crate. We don't have any options currently for the Btrees.

---

<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 15, 2022, 6:51am UTC](https://internals.rust-lang.org/t/comparator-for-btree-map-set-s/17011/6 "2022-07-15T06:51:55Z")

</div>

Now that I think about it, I believe the `raw_entry` API will be a "safer" option than a comparator. In the use case I described in the original post, I would need to capture some reference to the dictionary in the comparator closure which will be stored inside the `BTree` eventually for its entire lifetime. On the other hand with the raw entry API I can just do the comparison using the dictionary only right before insertion.

I imagine the API can look like this (obviously stolen from the HashMap counterpart)

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

---

<div class="post-metadata">

**Author:** ![CAD97](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/cad97/32/3460_2.png) [@CAD97](https://internals.rust-lang.org/u/CAD97)\
**Post date:** [July 16, 2022, 2:43am UTC](https://internals.rust-lang.org/t/comparator-for-btree-map-set-s/17011/7 "2022-07-16T02:43:36Z")

</div>

I would skip the builder, personally, and only offer the fully raw API. That is,

```rust
pub fn BTreeMap::raw_entry_mut<F>(&self, cmp: F) -> RawEntryMut<'_, K, V>
where F: FnMut(&K) -> Ordering;

```

The problem is of course defining a proper `Cursor` API, which is... [interesting](https://rust-unofficial.github.io/too-many-lists/sixth-cursors-intro.html) to say the least. Where does the cursor point? At an element? Between elements? Best proposal: `RawEntryMut` is an enum of a "not found" which semantically points between elements, and a cursor, which points at an entry in the btree.

---

<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.

---

<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 18, 2022, 12:59pm UTC](https://internals.rust-lang.org/t/comparator-for-btree-map-set-s/17011/9 "2022-07-18T12:59:46Z")

</div>

FYI, a first attempt: [BTreeMap Raw Entry API · Issue #73 · rust-lang/libs-team · GitHub](https://github.com/rust-lang/libs-team/issues/73)

---

<div class="post-metadata">

**Author:** ![system](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/system/32/14092_2.png) [@system](https://internals.rust-lang.org/u/system)\
**Post date:** [October 16, 2022, 1:00pm UTC](https://internals.rust-lang.org/t/comparator-for-btree-map-set-s/17011/10 "2022-10-16T13:00:28Z")

</div>

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.