Conditional removal for Btree and HashMap: remove_if()

language design
1

As I store Arc types in a BTree, I wondered why there is no conditional removal function for this type. My use case is the following:

let value: Arc<_> = btree.get(key);
if value.unwrap().strong_count() < 2 {
    btree.remove(key);
}

This means the tree will be traversed (or the hash calculated) twice: first with the get() and later on with the remove() function, while a conditional removal could just only traverse the tree once. The function signature would then report the value if an item was removed:

fn remove_if<Q,F>(&mut self, key: &Q, pred: F) -> Option<V>

Furthermore:

  • Mind that this is a request for conditional removal of only a single key, not a conditional removal for all keys (like extract_if()).
  • It seems it had been proposed earlier, but I can't find a reference why it is not implemented, see this comment drain_where() instead of remove_if().
  • Optionally if can fail with different causes, so instead of Option<V> an enum like TryRecvError would be useful too.
2

You could just use .entry(), as in

match btree.entry(key) {
    Entry::Occupied(e) if pred(e.get()) => Some(e.remove()),
    _ => None,
}

Rust Playground

The only issue: this unnecessarily requires an owned key. A means of constructing an OccupiedEntry from a &Q reference (where K: Borrow<Q> + Ord, Q: Ord + ?Sized) seems to be missing from BTreeMap API.

11 Likes
3

Thanks! This answers my original request sufficiently, as I use u64 as keys. As you mention it as an issue, does it make sense to request an implementation with a borrowed key somewhere?

4

I do believe this makes sense. I think it's a non-trivial design space though, one could argue for many extensions of the kind... like (just off the top of my head) entry APIs for set types, an API for constructing occupied entries for hash maps, and API that can also create vacant entries but only conditionally - somehow - upgrades the borrowed version to an owned one on demand... (and for hash maps, their "raw entry" APIs [not stable, and maybe some parts only exist in the hashbrown crate] allow some ways of creating an "entry" from a non-owned key, too, which should already enable most use cases)

5

Could you have (something like) a raw entry api for btree maps/sets too? Then you could build more user friendly abstractions on top.

If I'm understanding this correctly it would basically need the ability to store a cursor to where something either is or would be inserted. Though tree rebalancing, node splitting etc would complicate this of course.

6

The raw APIs for hash maps allow - in their most low-level form – you to supply a custom hash value and custom equality comparison. The key is not even an object anymore, just a callback that asks „is it equal?“ The equivalent for btree structure should be a “how does it compare?” callback returning an Ordering. Through this, one can of course easily build up API on top that needs owned keys only when absolutely necessary. (E.g. a raw entry API means a vacant entry doesn’t own a key yet, unlike the standard entry API, so consequently, the insert method then needs to ultimately accept the owned key after all.)

I don’t know if (and if yes where) raw entry APIs for btree maps (/sets) have been discussed prior.

Given an ordinary entry API already exists (and glancing at its implementation, seems to be implemented by storing some kind of cursor, not unnecessarily re-traversing the tree for inserts/removals), I would conjecture that there shouldn’t be any further complications.

1 Like
7

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