feature request: delete entries of a map (TreeMap, BTreeMap, etc) while iterating over it

[haberman]

I was writing an algorithm the other day where I wanted to be able to delete items from a map as I was iterating over it.

My desired algorithm, in pseudo-code, is basically:

iter = map.find(x)
while (true) {
  item = iter.next()
  max = item.foo
  iter.delete();  // Delete current item.
  if (max > y) {  // This could be any application-level predicate.
    break;
  }
}

A slight variant that is often important also is: I want to iterate over the whole map, but delete some items and not others based on a user predicate.

After asking on IRC it doesn't appear that there is any way to mutate a map in Rust while iterating over it.

• iterating over the map borrows it, preventing map.remove() calls while iterating.
• the iterator itself offers no deleting functionality.
• while the BTreeMap Entry type allows some amount of mutating directly from OccupiedEntry to VacantEntry, there is nothing that offers iteration over Entry types. The iterators offered only expose (key, value) tuples, not Entrys.

The only workaround I can see for this is: while iterating, build a Vec of keys I want to delete, and after iteration, delete them. But this turns a constant-space algorithm in to an O(n) space algorithm.

C++ offers deleting while iterating via this (admittedly subtle) pattern: http://stackoverflow.com/a/2874533/77070

Possible solutions to the problem in Rust that I can think of:

1. Offer an iterator that can add/delete entries during iteration. There is currently an iterator that exposes mut entries, but none AFAICS that is mut with respect to the container.
2. Offer an iterator over Entry types. But this solution is less satisfying because it is very BTreeMap-specific.
3. Offer a version of map.remove() that takes an iterator instead of a key... but I guess you'd run into the same problem where you can't call the method because iterating has already borrowed the map.
4. Others? Someone on IRC said something about cursors being a possible solution to this problem?

[Gankra]

So this is just straight up a hard problem to solve in Rust.

The first issue is that the lifetime of the iterator is seperate from the references it yields. So you can't do anything that could possibly invalidate old references while iterating. So doing this on BTreeMap is out of the question due to its complex structure. However you could potentially do this on TreeMap, and maybe our current HashMap if you were careful. VecMap would be easy.

However if we use the idea of cursors we've been kicking around, this issue goes away. A cursor would be an iterator whose references are tied to its own lifetime. However this would have to be iterated manually as it wouldn't be a proper iterator. Probably fine since you want to have control over what's going on at every step anyway. However you still have the tricky situation of deleting stuff and keeping the cursor at the right place. For HashMap and VecMap this is probably fine. For TreeMap and BTreeMap this is a bit tricky. Cursor-based APIs also let us support bi-directionality. I think this is something we'd like to explore eventually, but don't have the resources to do. Or rather, it's lower priority right now.

Doing this via entries seems like a non-starter due to their current design (note that Entry is impl'd on BTreeMap, HashMap, and TrieMap now).

[haberman]

pcwalton thinks it should be possible to add deleting methods on the iterator itself -- that would be really nice: http://www.reddit.com/r/rust/comments/2mkra1/impressions_after_writing_a_little_rust/cm55xah

[Stebalien]

An alternative is #1338.

[Centril]

Closing in favor of #1338.