# Interface improvements for BTreeMap **URL:** \ **Category:** libs\ **Created:** [July 6, 2022, 8:20pm UTC](https://internals.rust-lang.org/t/interface-improvements-for-btreemap/16957 "2022-07-06T20:20:23Z")\ **Posts on this page:** 9\ **Page:** 1
**Author:** ![lvella](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/lvella/32/9399_2.png) [@lvella](https://internals.rust-lang.org/u/lvella)\ **Post date:** [July 6, 2022, 8:20pm UTC](https://internals.rust-lang.org/t/interface-improvements-for-btreemap/16957/1 "2022-07-06T20:20:23Z")
In the last months, when implementing some algebra algorithms in rust, I stumbled upon a few shortcomings of the BTreeMap interface. I will list here the issues I had and the proposed solution. - I need a key in order to be able to search the `BTreeMap`, when it might be expensive to build one. This issue has already been brought up in [this post](https://internals.rust-lang.org/t/btreemap-searching-with-a-predicate/8476), and I think the author's proposed solution is quite feasible, and we already have a similar solution with `slice`'s [`binary_search_by`](https://doc.rust-lang.org/std/primitive.slice.html#method.binary_search_by). - Sometimes I want the key order to depend on some external data. There is no way to use this external data from `Ord::cmp` unless I store an extra reference on every key element. This issue is easily solvable by taking a comparator object in the constructor, like C++ `std::map`. I saw this issue already came up [on this StackOverflow question](https://stackoverflow.com/questions/35786878/how-can-i-implement-ord-when-the-comparison-depends-on-data-not-part-of-the-comp). - Once you search for an entry in the BTree\*, you should be able to iterate from that point in both ways, and still be able to insert a new element in the found entry. My specific problem is that I needed to retrieve an element, and if not found, create the value from the previous and next value and insert it into the BTreeMap. Using BTreeMap interface, the only way to do it was with 3 independent searches with the same key: `map.range(key..)`, `map.range(..key)` and `map.insert(key, new_value)`. In comparison, with C++ `std::map`, I can do it with a single `map.lower_bound(key)` search, and from the returned iterator I can get both the lower and higher values, and insert back in O(1) by using the `hint` argument of `map.insert()`. On rust, I am not sure what would be a good interface for this, but maybe `btree_map::Entry` should have two methods: `iter_forward()` and `iter_backwards()`, returning iterators in both directions from the entry. Maybe the entry itself is a pointer that can be advanced. I don't know. I would like to see your ideas about such interface that is idiomatic, fits well existing interface, and is as flexible as C++ `std::map`. - Finally, on a more general side, I missed some form of unsafe interface for the `std::collections`. In particular, coming from C++, I missed the ability to hold an iterator for a `map` and change the `map` while the iterator still remained valid (i.e. the ability to iterate and mutate simultaneously). This may be impossible or much harder in a B-tree, because each entry is not an independently allocated node, but the general feeling is that the `std::collections` are not meant to be used in potentially unsafe operations, and they lack an interface for those that need to do it. But being in `std` and all, maybe they should. ---
**Author:** ![jjpe](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/jjpe/32/9779_2.png) [@jjpe](https://internals.rust-lang.org/u/jjpe)\ **Post date:** [July 6, 2022, 9:07pm UTC](https://internals.rust-lang.org/t/interface-improvements-for-btreemap/16957/2 "2022-07-06T21:07:02Z")
> [@lvella](#): > > In particular, coming from C++, I missed the ability to hold an iterator for a `map` and change the `map` while the iterator still remained valid I don't believe this will ever change as doing that is kind of asking for race conditions. In addition, creating an iterator either takes the collection by value (i.e. `.into_iter()`), in which case it consumes the collection, or it takes an shared borrow (i.e. `&collection`), in which case it's immutable¹, or it takes a mutable borrow (i.e. `&mut`), in which case it can't be shared to both iterate and mutate the collection at the same time. In essence, when using iterators that access pattern is quite problematic. However, an alternative for it is to just use a loop: ```rust for i in start..end { collection[I].mutate(); } ``` ¹Not counting interior mutability, which is very unlikely to be desirable for iterators in general. ---
**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 7, 2022, 4:26am UTC](https://internals.rust-lang.org/t/interface-improvements-for-btreemap/16957/3 "2022-07-07T04:26:18Z")
> [@lvella](#): > > Sometimes I want the key order to depend on some external data. There is no way to use this external data from `Ord::cmp` unless I store an extra reference on every key element. This issue is easily solvable by taking a comparator object in the constructor, like C++ `std::map`. 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`) rather than comparators. ---
**Author:** ![the8472](https://avatars.discourse-cdn.com/v4/letter/t/0ea827/32.png) [@the8472](https://internals.rust-lang.org/u/the8472)\ **Post date:** [July 7, 2022, 1:47pm UTC](https://internals.rust-lang.org/t/interface-improvements-for-btreemap/16957/4 "2022-07-07T13:47:33Z")
Regarding mutation-during-iteration: With lending iterators it would be possible for the iterator itself to provide mutation methods that update both the map and adjust the iterator state after the map update. With the current iterator trait that seems difficult because the iterator hands out references that must remain valid for the lifetime of the iterator so the map can't be modified in a way that moves around values. A [cursor](https://doc.rust-lang.org/std/collections/linked_list/struct.CursorMut.html) API would be needed instead. ---
**Author:** ![lvella](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/lvella/32/9399_2.png) [@lvella](https://internals.rust-lang.org/u/lvella)\ **Post date:** [July 7, 2022, 4:08pm UTC](https://internals.rust-lang.org/t/interface-improvements-for-btreemap/16957/5 "2022-07-07T16:08:59Z")
A cursor would also solve the problem of multiple searches with the same key, specially if it can be used as a hint for insertion. Something like `map.entry_from_cursor(cursor, key)`, that would linear search starting from the cursor position, instead of doing a tree search. ---
**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 7, 2022, 5:46pm UTC](https://internals.rust-lang.org/t/interface-improvements-for-btreemap/16957/6 "2022-07-07T17:46:48Z")
> [@the8472](#): > > A [cursor](https://doc.rust-lang.org/std/collections/linked_list/struct.CursorMut.html) API would be needed instead. 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). ---
**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:55pm UTC](https://internals.rust-lang.org/t/interface-improvements-for-btreemap/16957/7 "2022-07-14T20:55:06Z")
Hi @lvella I come from `C++` and I share pretty much your concerns, which I summarized in my somewhat similar post today > [@Comparator for BTree(Map|Set)s](https://internals.rust-lang.org/t/comparator-for-btree-map-set-s/17011): > > 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 r… 1. I dislike that I have to pass the key by value to the `entry` API. 2. I dislike that cannot make my comparator rely on what you call external data. Actually I stumbled upon the exact same stackoverflow question because I was building the same kind of thing. 3. I also would find it better to avoid searching multiple times if I'm trying to perform a "fetch or add" key in one shot. In C++ one can simply combine the following to achieve that: `hint=lower_bound(k)` and then use the hint to insert in the right location if the key is not found `insert(kv,hint)` I believe having a `raw_entry|cursor` API similar to the one in the ` HashMap` ([HashMap::raw\_entry\_mut](https://doc.rust-lang.org/stable/std/collections/struct.HashMap.html#method.raw_entry_mut)) can actually be the answer to all 3 problems. ---
**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, 1:03pm UTC](https://internals.rust-lang.org/t/interface-improvements-for-btreemap/16957/8 "2022-07-18T13:03:45Z")
> > > \# Proposal > > \## Problem statement > We need an API that will allow the users to > … > 1. Fetch or insert entries without doing double lookups. Currently this is only possible with a sequence of get and insert so two lookups. > 2. Implement custom generic comparators without the need to store the comparator function in the BTreeMap itself. Those custom comparators would allow the users to store entries in an order that can rely on some external contexts. > > \## Motivation, use-cases > > Imagine implementing a dictionary where the data is stored contiguously in some vector and a you want to establish some sorted lightweight index on that vector. The index would be a \`BTreeMap\` of \`usize\` keys which are an index into the vector. Obviously the sorting order would then have to be different from the natural sorting order of the \`usize\` and it will need to rely on the actual string vector. By making the raw entry API take a closure where the second parameter is a generic key we achieve two things: enabling mixed type comparisons, and enabling comparators to consider external contexts during comparions and only during comparisons. In fact this is even better than the \`C++\` alternative where the comparator has to be passed to the constructor and keep whatever references it needs throughout the whole lifetime of the \`map\`. > > Furthermore, the raw entry API would enable the users to efficiently tackle the very common case of "get or insert", in which the caller wants to get a reference to the value if it exists or insert a new value immediately at the right position without having to do the lookup twice; once to check for existence and another to insert. > > Below is a basic user code that summarizes the use case that was described above > > \`\`\` > use std::collections::BTreeMap; > > > // holds all strings contiguously > // maintains a lightweight sorted index > // on such strings. > struct Storage { > dict: Vec\, > index: BTreeMap\, > } > > impl Storage { > fn get\_or\_insert(& mut self, input: &str) -\> usize { > match self.index.raw\_entry\_mut(input, |k1, k2: &str| -\> Ordering { > dict\[k1\].cmp(&k2) > }) > { > RawEntryMut::Occupied(o) =\> o.key(), > RawEntryMut::Vacant(c) =\> { > self.dict.push(input); > c.insert(self.dict.len() - 1); > self.dict.len() - 1 > } > } > } > } > \`\`\` > > \## Solution sketches > The proposed API looks like this > > \`\`\` > pub fn BTreeMap::raw\_entry\_mut\(&self, u: &U, cmp: F) -\> RawEntryMut\<'\_, K, V\> > where F: FnMut(&K, &U) -\> Ordering; > \`\`\` > > \`RawEntryMut\` can be an enum \`Vacant\`/\`Occupied\` where the \`Vacant\` variant points to the where that key would be inserted, or using \`C++\` terms: > > \`\`\` > iterator to the position before which the new element will be inserted > \`\`\` > > Finally, I'm aware of the cursor APIs discussions. I believe future work can extend the methods of \`RawEntryMut\` to add things like \`insert\_before|after\` and so on. > > > \## Links and related work > > I gathered some links showing the demand for such a feature > > 1. \[BTreeSet sorted by dynamically generated keys\](https://users.rust-lang.org/t/btreeset-sorted-by-dynamically-generated-keys/38857) > 2. \[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) > 3. \[Interface improvements for BTreeMap\](https://internals.rust-lang.org/t/interface-improvements-for-btreemap/16957) > 4. \[Comparator for BTree(Map|Set)s \](https://internals.rust-lang.org/t/comparator-for-btree-map-set-s/17011) > > Furthermore, > > This use case is fully achievable in \`C++\` \[(C++ Use case code snippet)\](https://godbolt.org/z/MaaYo5WGb) as shown in this implementation below. > > \`\`\` > \#include \ > \#include \ > \#include \ > \#include \ > > struct Comparator { > using is\_transparent = std::true\_type; > > bool operator()(const std::size\_t lhs, const std::size\_t rhs) const > { > return dict\[lhs\] \< dict\[rhs\]; > } > > bool operator()(const std::string & lhs, const std::size\_t rhs) const { > return lhs \< dict\[rhs\]; > } > > bool operator()(const std::size\_t lhs, const std::string & rhs) const { > return dict\[lhs\] \< rhs; > } > > Comparator(const std::vector\ & dict) : dict(dict) {} > const std::vector\ & dict; > }; > > struct Storage > { > std::vector\ dict; > std::set\ index; > > Storage() : index(Comparator(dict)) {} > > std::size\_t get\_or\_insert(const std::string& s) { > const auto it = index.lower\_bound(s); > if(it == index.end() || dict\[\*it\] != s) { > dict.push\_back(s); > index.emplace\_hint(it, dict.size() - 1); > return dict.size() - 1; > } > > return \*it; > } > }; > > > int main(int argc, const char \*\* argv) { > Storage s; > > std::cout \<\< s.get\_or\_insert("HelloWorld") \<\< std::endl; > std::cout \<\< s.get\_or\_insert("HelloWorld") \<\< std::endl; > std::cout \<\< s.get\_or\_insert("C++") \<\< std::endl; > std::cout \<\< s.get\_or\_insert("Rust") \<\< std::endl; > std::cout \<\< s.get\_or\_insert("C++") \<\< std::endl; > std::cout \<\< s.get\_or\_insert("C++") \<\< std::endl; > std::cout \<\< s.get\_or\_insert("Rust") \<\< std::endl; > std::cout \<\< s.get\_or\_insert("C++") \<\< std::endl; > std::cout \<\< s.get\_or\_insert("C++") \<\< std::endl; > > return 0; > } > \`\`\` > > \## What happens now? > > This issue is part of the libs-api team \[API change proposal process\]. Once this issue is filed the libs-api team will review open proposals in its weekly meeting. You should receive feedback within a week or two. > > \[API change proposal process\]: https://std-dev-guide.rust-lang.org/feature-lifecycle/api-change-proposals.html ---
**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:04pm UTC](https://internals.rust-lang.org/t/interface-improvements-for-btreemap/16957/9 "2022-10-16T13:04:29Z")
This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.