Feature gate: #![feature(btree_cursors)]
This is a tracking issue for the Cursor and CursorMut types for BTreeMap.
A Cursor is like an iterator, except that it can freely seek back-and-forth, and can safely mutate the tree during iteration. This is because the lifetime of its yielded references is tied to its own lifetime, instead of just the underlying tree. A cursor either points to an element in the tree, or to a "ghost" non-element that is logically located after the last element and before the first element.
Public API
impl<K, V> BTreeMap<K, V> { fn lower_bound<Q>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V> where K: Borrow<Q> + Ord, Q: Ord; fn lower_bound_mut<Q>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V> where K: Borrow<Q> + Ord, Q: Ord; fn upper_bound<Q>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V> where K: Borrow<Q> + Ord, Q: Ord; fn upper_bound_mut<Q>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V> where K: Borrow<Q> + Ord, Q: Ord; } struct Cursor<'a, K: 'a, V: 'a>; impl<'a, K, V> Cursor<'a, K, V> { fn move_next(&mut self); fn move_prev(&mut self); fn key(&self) -> Option<&'a K>; fn value(&self) -> Option<&'a V>; fn key_value(&self) -> Option<(&'a K, &'a V)>; fn peek_next(&self) -> Option<(&'a K, &'a V)>; fn peek_prev(&self) -> Option<(&'a K, &'a V)>; } struct CursorMut<'a, K: 'a, V: 'a>; impl<'a, K, V> CursorMut<'a, K, V> { fn move_next(&mut self); fn move_prev(&mut self); fn key(&self) -> Option<&K>; fn value(&self) -> Option<&V>; fn value_mut(&mut self) -> Option<&mut V>; fn key_value(&self) -> Option<(&K, &V)>; fn key_value_mut(&self) -> Option<(&K, &mut V)>; unsafe fn key_mut_unchecked(&mut self) -> Option<&mut K>; fn peek_next(&self) -> Option<(&K, &V)>; fn peek_prev(&self) -> Option<(&K, &V)>; fn as_cursor(&self) -> Cursor<'_, K, V>; fn insert_after(&mut self, key: K, value: V); fn insert_before(&mut self, key: K, value: V); unsafe fn insert_after_unchecked(&mut self, key: K, value: V); unsafe fn insert_before_unchecked(&mut self, key: K, value: V); fn remove_current(&mut self) -> Option<(K, V)>; fn remove_current_and_move_back(&mut self) -> Option<(K, V)>; }
Steps / History
- Implementation: Implement cursors for BTreeMap #105641
- Final comment period (FCP)1
- Stabilization PR
Unresolved Questions
- None yet.