alloc/collections/btree/map.rs
1use core::borrow::Borrow;
2use core::cmp::Ordering;
3use core::error::Error;
4use core::fmt::{self, Debug};
5use core::hash::{Hash, Hasher};
6use core::iter::{FusedIterator, TrustedLen};
7use core::marker::PhantomData;
8use core::mem::{self, ManuallyDrop};
9use core::ops::{Bound, Index, RangeBounds};
10use core::ptr;
11
12use super::borrow::DormantMutRef;
13use super::dedup_sorted_iter::DedupSortedIter;
14use super::navigate::{LazyLeafRange, LeafRange};
15use super::node::ForceResult::*;
16use super::node::{self, Handle, NodeRef, Root, marker};
17use super::search::SearchBound;
18use super::search::SearchResult::*;
19use super::set_val::SetValZST;
20use crate::alloc::{AllocatorClone, Global};
21use crate::vec::Vec;
22
23mod entry;
24
25use Entry::*;
26#[stable(feature = "rust1", since = "1.0.0")]
27pub use entry::{Entry, OccupiedEntry, OccupiedError, VacantEntry};
28
29/// Minimum number of elements in a node that is not a root.
30/// We might temporarily have fewer elements during methods.
31pub(super) const MIN_LEN: usize = node::MIN_LEN_AFTER_SPLIT;
32
33// A tree in a `BTreeMap` is a tree in the `node` module with additional invariants:
34// - Keys must appear in ascending order (according to the key's type).
35// - Every non-leaf node contains at least 1 element (has at least 2 children).
36// - Every non-root node contains at least MIN_LEN elements.
37//
38// An empty map is represented either by the absence of a root node or by a
39// root node that is an empty leaf.
40
41/// An ordered map based on a [B-Tree].
42///
43/// Given a key type with a [total order], an ordered map stores its entries in key order.
44/// That means that keys must be of a type that implements the [`Ord`] trait,
45/// such that two keys can always be compared to determine their [`Ordering`].
46/// Examples of keys with a total order are strings with lexicographical order,
47/// and numbers with their natural order.
48///
49/// Iterators obtained from functions such as [`BTreeMap::iter`], [`BTreeMap::into_iter`], [`BTreeMap::values`], or
50/// [`BTreeMap::keys`] produce their items in key order, and take worst-case logarithmic and
51/// amortized constant time per item returned.
52///
53/// It is a logic error for a key to be modified in such a way that the key's ordering relative to
54/// any other key, as determined by the [`Ord`] trait, changes while it is in the map. This is
55/// normally only possible through [`Cell`], [`RefCell`], global state, I/O, or unsafe code.
56/// The behavior resulting from such a logic error is not specified, but will be encapsulated to the
57/// `BTreeMap` that observed the logic error and not result in undefined behavior. This could
58/// include panics, incorrect results, aborts, memory leaks, and non-termination.
59///
60/// # Examples
61///
62/// ```
63/// use std::collections::BTreeMap;
64///
65/// // type inference lets us omit an explicit type signature (which
66/// // would be `BTreeMap<&str, &str>` in this example).
67/// let mut movie_reviews = BTreeMap::new();
68///
69/// // review some movies.
70/// movie_reviews.insert("Office Space", "Deals with real issues in the workplace.");
71/// movie_reviews.insert("Pulp Fiction", "Masterpiece.");
72/// movie_reviews.insert("The Godfather", "Very enjoyable.");
73/// movie_reviews.insert("The Blues Brothers", "Eye lyked it a lot.");
74///
75/// // check for a specific one.
76/// if !movie_reviews.contains_key("Les Misérables") {
77/// println!("We've got {} reviews, but Les Misérables ain't one.",
78/// movie_reviews.len());
79/// }
80///
81/// // oops, this review has a lot of spelling mistakes, let's delete it.
82/// movie_reviews.remove("The Blues Brothers");
83///
84/// // look up the values associated with some keys.
85/// let to_find = ["Up!", "Office Space"];
86/// for movie in &to_find {
87/// match movie_reviews.get(movie) {
88/// Some(review) => println!("{movie}: {review}"),
89/// None => println!("{movie} is unreviewed.")
90/// }
91/// }
92///
93/// // Look up the value for a key (will panic if the key is not found).
94/// println!("Movie review: {}", movie_reviews["Office Space"]);
95///
96/// // iterate over everything.
97/// for (movie, review) in &movie_reviews {
98/// println!("{movie}: \"{review}\"");
99/// }
100/// ```
101///
102/// A `BTreeMap` with a known list of items can be initialized from an array:
103///
104/// ```
105/// use std::collections::BTreeMap;
106///
107/// let solar_distance = BTreeMap::from([
108/// ("Mercury", 0.4),
109/// ("Venus", 0.7),
110/// ("Earth", 1.0),
111/// ("Mars", 1.5),
112/// ]);
113/// ```
114///
115/// ## `Entry` API
116///
117/// `BTreeMap` implements an [`Entry API`], which allows for complex
118/// methods of getting, setting, updating and removing keys and their values:
119///
120/// [`Entry API`]: BTreeMap::entry
121///
122/// ```
123/// use std::collections::BTreeMap;
124///
125/// // type inference lets us omit an explicit type signature (which
126/// // would be `BTreeMap<&str, u8>` in this example).
127/// let mut player_stats = BTreeMap::new();
128///
129/// fn random_stat_buff() -> u8 {
130/// // could actually return some random value here - let's just return
131/// // some fixed value for now
132/// 42
133/// }
134///
135/// // insert a key only if it doesn't already exist
136/// player_stats.entry("health").or_insert(100);
137///
138/// // insert a key using a function that provides a new value only if it
139/// // doesn't already exist
140/// player_stats.entry("defence").or_insert_with(random_stat_buff);
141///
142/// // update a key, guarding against the key possibly not being set
143/// let stat = player_stats.entry("attack").or_insert(100);
144/// *stat += random_stat_buff();
145///
146/// // modify an entry before an insert with in-place mutation
147/// player_stats.entry("mana").and_modify(|mana| *mana += 200).or_insert(100);
148/// ```
149///
150/// # Background
151///
152/// A B-tree is (like) a [binary search tree], but adapted to the natural granularity that modern
153/// machines like to consume data at. This means that each node contains an entire array of elements,
154/// instead of just a single element.
155///
156/// B-Trees represent a fundamental compromise between cache-efficiency and actually minimizing
157/// the amount of work performed in a search. In theory, a binary search tree (BST) is the optimal
158/// choice for a sorted map, as a perfectly balanced BST performs the theoretical minimum number of
159/// comparisons necessary to find an element (log<sub>2</sub>n). However, in practice the way this
160/// is done is *very* inefficient for modern computer architectures. In particular, every element
161/// is stored in its own individually heap-allocated node. This means that every single insertion
162/// triggers a heap-allocation, and every comparison is a potential cache-miss due to the indirection.
163/// Since both heap-allocations and cache-misses are notably expensive in practice, we are forced to,
164/// at the very least, reconsider the BST strategy.
165///
166/// A B-Tree instead makes each node contain B-1 to 2B-1 elements in a contiguous array. By doing
167/// this, we reduce the number of allocations by a factor of B, and improve cache efficiency in
168/// searches. However, this does mean that searches will have to do *more* comparisons on average.
169/// The precise number of comparisons depends on the node search strategy used. For optimal cache
170/// efficiency, one could search the nodes linearly. For optimal comparisons, one could search
171/// the node using binary search. As a compromise, one could also perform a linear search
172/// that initially only checks every i<sup>th</sup> element for some choice of i.
173///
174/// Currently, our implementation simply performs naive linear search. This provides excellent
175/// performance on *small* nodes of elements which are cheap to compare. However in the future we
176/// would like to further explore choosing the optimal search strategy based on the choice of B,
177/// and possibly other factors. Using linear search, searching for a random element is expected
178/// to take B * log(n) comparisons, which is generally worse than a BST. In practice,
179/// however, performance is excellent.
180///
181/// [B-Tree]: https://en.wikipedia.org/wiki/B-tree
182/// [binary search tree]: https://en.wikipedia.org/wiki/Binary_search_tree
183/// [total order]: https://en.wikipedia.org/wiki/Total_order
184/// [`Cell`]: core::cell::Cell
185/// [`RefCell`]: core::cell::RefCell
186#[stable(feature = "rust1", since = "1.0.0")]
187#[cfg_attr(not(test), rustc_diagnostic_item = "BTreeMap")]
188#[rustc_insignificant_dtor]
189pub struct BTreeMap<
190 K,
191 V,
192 #[unstable(feature = "allocator_ext", issue = "163177", implied_by = "allocator_api")] A: AllocatorClone = Global,
193> {
194 root: Option<Root<K, V>>,
195 length: usize,
196 /// `ManuallyDrop` to control drop order (needs to be dropped after all the nodes).
197 // Although some of the accessory types store a copy of the allocator, the nodes do not.
198 // Because allocations will remain live as long as any copy (like this one) of the allocator
199 // is live, it's unnecessary to store the allocator in each node.
200 pub(super) alloc: ManuallyDrop<A>,
201 // For dropck; the `Box` avoids making the `Unpin` impl more strict than before
202 _marker: PhantomData<crate::boxed::Box<(K, V), A>>,
203}
204
205#[stable(feature = "btree_drop", since = "1.7.0")]
206unsafe impl<#[may_dangle] K, #[may_dangle] V, A: AllocatorClone> Drop for BTreeMap<K, V, A> {
207 fn drop(&mut self) {
208 if let Some(root) = self.root.take() {
209 // SAFETY: The tree won't be used after this point.
210 // The allocator has not been moved out and will be moved into `drop_tree`.
211 unsafe { root.into_dying().drop_tree(ManuallyDrop::take(&mut self.alloc)) };
212 } else {
213 // SAFETY: The allocator has not been moved out and won't be used after this point.
214 unsafe { ManuallyDrop::drop(&mut self.alloc) };
215 }
216 }
217}
218
219// FIXME: This implementation is "wrong", but changing it would be a breaking change.
220// (The bounds of the automatic `UnwindSafe` implementation have been like this since Rust 1.50.)
221// Maybe we can fix it nonetheless with a crater run, or if the `UnwindSafe`
222// traits are deprecated, or disarmed (no longer causing hard errors) in the future.
223#[stable(feature = "btree_unwindsafe", since = "1.64.0")]
224impl<K, V, A: AllocatorClone> core::panic::UnwindSafe for BTreeMap<K, V, A>
225where
226 A: core::panic::UnwindSafe,
227 K: core::panic::RefUnwindSafe,
228 V: core::panic::RefUnwindSafe,
229{
230}
231
232#[stable(feature = "rust1", since = "1.0.0")]
233impl<K: Clone, V: Clone, A: AllocatorClone> Clone for BTreeMap<K, V, A> {
234 fn clone(&self) -> BTreeMap<K, V, A> {
235 fn clone_subtree<'a, K: Clone, V: Clone, A: AllocatorClone>(
236 node: NodeRef<marker::Immut<'a>, K, V, marker::LeafOrInternal>,
237 alloc: A,
238 ) -> BTreeMap<K, V, A>
239 where
240 K: 'a,
241 V: 'a,
242 {
243 match node.force() {
244 Leaf(leaf) => {
245 let mut out_tree = BTreeMap {
246 root: Some(Root::new(alloc.clone())),
247 length: 0,
248 alloc: ManuallyDrop::new(alloc),
249 _marker: PhantomData,
250 };
251
252 {
253 let root = out_tree.root.as_mut().unwrap(); // unwrap succeeds because we just wrapped
254 let mut out_node = match root.borrow_mut().force() {
255 Leaf(leaf) => leaf,
256 Internal(_) => unreachable!(),
257 };
258
259 let mut in_edge = leaf.first_edge();
260 while let Ok(kv) = in_edge.right_kv() {
261 let (k, v) = kv.into_kv();
262 in_edge = kv.right_edge();
263
264 out_node.push(k.clone(), v.clone());
265 out_tree.length += 1;
266 }
267 }
268
269 out_tree
270 }
271 Internal(internal) => {
272 let mut out_tree =
273 clone_subtree(internal.first_edge().descend(), alloc.clone());
274
275 {
276 let out_root = out_tree.root.as_mut().unwrap();
277 let mut out_node = out_root.push_internal_level(alloc.clone());
278 let mut in_edge = internal.first_edge();
279 while let Ok(kv) = in_edge.right_kv() {
280 let (k, v) = kv.into_kv();
281 in_edge = kv.right_edge();
282
283 let k = (*k).clone();
284 let v = (*v).clone();
285 let subtree = clone_subtree(in_edge.descend(), alloc.clone());
286
287 // We can't destructure subtree directly
288 // because BTreeMap implements Drop
289 let (subroot, sublength) = {
290 let subtree = ManuallyDrop::new(subtree);
291 // ignore-tidy-undocumented-unsafe
292 let root = unsafe { ptr::read(&subtree.root) };
293 let length = subtree.length;
294 (root, length)
295 };
296
297 out_node.push(
298 k,
299 v,
300 subroot.unwrap_or_else(|| Root::new(alloc.clone())),
301 );
302 out_tree.length += 1 + sublength;
303 }
304 }
305
306 out_tree
307 }
308 }
309 }
310
311 if self.is_empty() {
312 BTreeMap::new_in((*self.alloc).clone())
313 } else {
314 clone_subtree(self.root.as_ref().unwrap().reborrow(), (*self.alloc).clone()) // unwrap succeeds because not empty
315 }
316 }
317}
318
319// Internal functionality for `BTreeSet`.
320impl<K, A: AllocatorClone> BTreeMap<K, SetValZST, A> {
321 pub(super) fn replace(&mut self, key: K) -> Option<K>
322 where
323 K: Ord,
324 {
325 let (map, dormant_map) = DormantMutRef::new(self);
326 let root_node =
327 map.root.get_or_insert_with(|| Root::new((*map.alloc).clone())).borrow_mut();
328 match root_node.search_tree::<K>(&key) {
329 Found(mut kv) => Some(mem::replace(kv.key_mut(), key)),
330 GoDown(handle) => {
331 VacantEntry {
332 key,
333 handle: Some(handle),
334 dormant_map,
335 alloc: (*map.alloc).clone(),
336 _marker: PhantomData,
337 }
338 .insert(SetValZST);
339 None
340 }
341 }
342 }
343
344 pub(super) fn get_or_insert_with<Q: ?Sized, F>(&mut self, q: &Q, f: F) -> &K
345 where
346 K: Borrow<Q> + Ord,
347 Q: Ord,
348 F: FnOnce(&Q) -> K,
349 {
350 let (map, dormant_map) = DormantMutRef::new(self);
351 let root_node =
352 map.root.get_or_insert_with(|| Root::new((*map.alloc).clone())).borrow_mut();
353 match root_node.search_tree(q) {
354 Found(handle) => handle.into_kv_mut().0,
355 GoDown(handle) => {
356 let key = f(q);
357 assert!(*key.borrow() == *q, "new value is not equal");
358 VacantEntry {
359 key,
360 handle: Some(handle),
361 dormant_map,
362 alloc: (*map.alloc).clone(),
363 _marker: PhantomData,
364 }
365 .insert_entry(SetValZST)
366 .into_key()
367 }
368 }
369 }
370}
371
372/// An iterator over the entries of a `BTreeMap`.
373///
374/// This `struct` is created by the [`iter`] method on [`BTreeMap`]. See its
375/// documentation for more.
376///
377/// [`iter`]: BTreeMap::iter
378#[must_use = "iterators are lazy and do nothing unless consumed"]
379#[stable(feature = "rust1", since = "1.0.0")]
380pub struct Iter<'a, K: 'a, V: 'a> {
381 range: LazyLeafRange<marker::Immut<'a>, K, V>,
382 length: usize,
383}
384
385#[stable(feature = "collection_debug", since = "1.17.0")]
386impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Iter<'_, K, V> {
387 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
388 f.debug_list().entries(self.clone()).finish()
389 }
390}
391
392#[stable(feature = "default_iters", since = "1.70.0")]
393impl<'a, K: 'a, V: 'a> Default for Iter<'a, K, V> {
394 /// Creates an empty `btree_map::Iter`.
395 ///
396 /// ```
397 /// # use std::collections::btree_map;
398 /// let iter: btree_map::Iter<'_, u8, u8> = Default::default();
399 /// assert_eq!(iter.len(), 0);
400 /// ```
401 fn default() -> Self {
402 Iter { range: Default::default(), length: 0 }
403 }
404}
405
406/// A mutable iterator over the entries of a `BTreeMap`.
407///
408/// This `struct` is created by the [`iter_mut`] method on [`BTreeMap`]. See its
409/// documentation for more.
410///
411/// [`iter_mut`]: BTreeMap::iter_mut
412#[must_use = "iterators are lazy and do nothing unless consumed"]
413#[stable(feature = "rust1", since = "1.0.0")]
414pub struct IterMut<'a, K: 'a, V: 'a> {
415 range: LazyLeafRange<marker::ValMut<'a>, K, V>,
416 length: usize,
417
418 // Be invariant in `K` and `V`
419 _marker: PhantomData<&'a mut (K, V)>,
420}
421
422#[stable(feature = "collection_debug", since = "1.17.0")]
423impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IterMut<'_, K, V> {
424 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
425 let range = Iter { range: self.range.reborrow(), length: self.length };
426 f.debug_list().entries(range).finish()
427 }
428}
429
430#[stable(feature = "default_iters", since = "1.70.0")]
431impl<'a, K: 'a, V: 'a> Default for IterMut<'a, K, V> {
432 /// Creates an empty `btree_map::IterMut`.
433 ///
434 /// ```
435 /// # use std::collections::btree_map;
436 /// let iter: btree_map::IterMut<'_, u8, u8> = Default::default();
437 /// assert_eq!(iter.len(), 0);
438 /// ```
439 fn default() -> Self {
440 IterMut { range: Default::default(), length: 0, _marker: PhantomData {} }
441 }
442}
443
444/// An owning iterator over the entries of a `BTreeMap`, sorted by key.
445///
446/// This `struct` is created by the [`into_iter`] method on [`BTreeMap`]
447/// (provided by the [`IntoIterator`] trait). See its documentation for more.
448///
449/// [`into_iter`]: IntoIterator::into_iter
450#[stable(feature = "rust1", since = "1.0.0")]
451#[rustc_insignificant_dtor]
452pub struct IntoIter<
453 K,
454 V,
455 #[unstable(feature = "allocator_ext", issue = "163177", implied_by = "allocator_api")] A: AllocatorClone = Global,
456> {
457 range: LazyLeafRange<marker::Dying, K, V>,
458 length: usize,
459 /// The BTreeMap will outlive this IntoIter so we don't care about drop order for `alloc`.
460 alloc: A,
461}
462
463impl<K, V, A: AllocatorClone> IntoIter<K, V, A> {
464 /// Returns an iterator of references over the remaining items.
465 #[inline]
466 pub(super) fn iter(&self) -> Iter<'_, K, V> {
467 Iter { range: self.range.reborrow(), length: self.length }
468 }
469}
470
471#[stable(feature = "collection_debug", since = "1.17.0")]
472impl<K: Debug, V: Debug, A: AllocatorClone> Debug for IntoIter<K, V, A> {
473 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
474 f.debug_list().entries(self.iter()).finish()
475 }
476}
477
478#[stable(feature = "default_iters", since = "1.70.0")]
479impl<K, V, A> Default for IntoIter<K, V, A>
480where
481 A: AllocatorClone + Default,
482{
483 /// Creates an empty `btree_map::IntoIter`.
484 ///
485 /// ```
486 /// # use std::collections::btree_map;
487 /// let iter: btree_map::IntoIter<u8, u8> = Default::default();
488 /// assert_eq!(iter.len(), 0);
489 /// ```
490 fn default() -> Self {
491 IntoIter { range: Default::default(), length: 0, alloc: Default::default() }
492 }
493}
494
495/// An iterator over the keys of a `BTreeMap`.
496///
497/// This `struct` is created by the [`keys`] method on [`BTreeMap`]. See its
498/// documentation for more.
499///
500/// [`keys`]: BTreeMap::keys
501#[must_use = "iterators are lazy and do nothing unless consumed"]
502#[stable(feature = "rust1", since = "1.0.0")]
503pub struct Keys<'a, K, V> {
504 inner: Iter<'a, K, V>,
505}
506
507#[stable(feature = "collection_debug", since = "1.17.0")]
508impl<K: fmt::Debug, V> fmt::Debug for Keys<'_, K, V> {
509 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
510 f.debug_list().entries(self.clone()).finish()
511 }
512}
513
514/// An iterator over the values of a `BTreeMap`.
515///
516/// This `struct` is created by the [`values`] method on [`BTreeMap`]. See its
517/// documentation for more.
518///
519/// [`values`]: BTreeMap::values
520#[must_use = "iterators are lazy and do nothing unless consumed"]
521#[stable(feature = "rust1", since = "1.0.0")]
522pub struct Values<'a, K, V> {
523 inner: Iter<'a, K, V>,
524}
525
526#[stable(feature = "collection_debug", since = "1.17.0")]
527impl<K, V: fmt::Debug> fmt::Debug for Values<'_, K, V> {
528 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
529 f.debug_list().entries(self.clone()).finish()
530 }
531}
532
533/// A mutable iterator over the values of a `BTreeMap`.
534///
535/// This `struct` is created by the [`values_mut`] method on [`BTreeMap`]. See its
536/// documentation for more.
537///
538/// [`values_mut`]: BTreeMap::values_mut
539#[must_use = "iterators are lazy and do nothing unless consumed"]
540#[stable(feature = "map_values_mut", since = "1.10.0")]
541pub struct ValuesMut<'a, K, V> {
542 inner: IterMut<'a, K, V>,
543}
544
545#[stable(feature = "map_values_mut", since = "1.10.0")]
546impl<K, V: fmt::Debug> fmt::Debug for ValuesMut<'_, K, V> {
547 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
548 f.debug_list().entries(self.inner.iter().map(|(_, val)| val)).finish()
549 }
550}
551
552/// An owning iterator over the keys of a `BTreeMap`.
553///
554/// This `struct` is created by the [`into_keys`] method on [`BTreeMap`].
555/// See its documentation for more.
556///
557/// [`into_keys`]: BTreeMap::into_keys
558#[must_use = "iterators are lazy and do nothing unless consumed"]
559#[stable(feature = "map_into_keys_values", since = "1.54.0")]
560pub struct IntoKeys<
561 K,
562 V,
563 #[unstable(feature = "allocator_ext", issue = "163177", implied_by = "allocator_api")] A: AllocatorClone = Global,
564> {
565 inner: IntoIter<K, V, A>,
566}
567
568#[stable(feature = "map_into_keys_values", since = "1.54.0")]
569impl<K: fmt::Debug, V, A: AllocatorClone> fmt::Debug for IntoKeys<K, V, A> {
570 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
571 f.debug_list().entries(self.inner.iter().map(|(key, _)| key)).finish()
572 }
573}
574
575/// An owning iterator over the values of a `BTreeMap`.
576///
577/// This `struct` is created by the [`into_values`] method on [`BTreeMap`].
578/// See its documentation for more.
579///
580/// [`into_values`]: BTreeMap::into_values
581#[must_use = "iterators are lazy and do nothing unless consumed"]
582#[stable(feature = "map_into_keys_values", since = "1.54.0")]
583pub struct IntoValues<
584 K,
585 V,
586 #[unstable(feature = "allocator_ext", issue = "163177", implied_by = "allocator_api")] A: AllocatorClone = Global,
587> {
588 inner: IntoIter<K, V, A>,
589}
590
591#[stable(feature = "map_into_keys_values", since = "1.54.0")]
592impl<K, V: fmt::Debug, A: AllocatorClone> fmt::Debug for IntoValues<K, V, A> {
593 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
594 f.debug_list().entries(self.inner.iter().map(|(_, val)| val)).finish()
595 }
596}
597
598/// An iterator over a sub-range of entries in a `BTreeMap`.
599///
600/// This `struct` is created by the [`range`] method on [`BTreeMap`]. See its
601/// documentation for more.
602///
603/// [`range`]: BTreeMap::range
604#[must_use = "iterators are lazy and do nothing unless consumed"]
605#[stable(feature = "btree_range", since = "1.17.0")]
606pub struct Range<'a, K: 'a, V: 'a> {
607 inner: LeafRange<marker::Immut<'a>, K, V>,
608}
609
610#[stable(feature = "collection_debug", since = "1.17.0")]
611impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Range<'_, K, V> {
612 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
613 f.debug_list().entries(self.clone()).finish()
614 }
615}
616
617/// A mutable iterator over a sub-range of entries in a `BTreeMap`.
618///
619/// This `struct` is created by the [`range_mut`] method on [`BTreeMap`]. See its
620/// documentation for more.
621///
622/// [`range_mut`]: BTreeMap::range_mut
623#[must_use = "iterators are lazy and do nothing unless consumed"]
624#[stable(feature = "btree_range", since = "1.17.0")]
625pub struct RangeMut<'a, K: 'a, V: 'a> {
626 inner: LeafRange<marker::ValMut<'a>, K, V>,
627
628 // Be invariant in `K` and `V`
629 _marker: PhantomData<&'a mut (K, V)>,
630}
631
632#[stable(feature = "collection_debug", since = "1.17.0")]
633impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for RangeMut<'_, K, V> {
634 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
635 let range = Range { inner: self.inner.reborrow() };
636 f.debug_list().entries(range).finish()
637 }
638}
639
640impl<K, V> BTreeMap<K, V> {
641 /// Makes a new, empty `BTreeMap`.
642 ///
643 /// Does not allocate anything on its own.
644 ///
645 /// # Examples
646 ///
647 /// ```
648 /// use std::collections::BTreeMap;
649 ///
650 /// let mut map = BTreeMap::new();
651 ///
652 /// // entries can now be inserted into the empty map
653 /// map.insert(1, "a");
654 /// ```
655 #[stable(feature = "rust1", since = "1.0.0")]
656 #[rustc_const_stable(feature = "const_btree_new", since = "1.66.0")]
657 #[inline]
658 #[must_use]
659 pub const fn new() -> BTreeMap<K, V> {
660 BTreeMap { root: None, length: 0, alloc: ManuallyDrop::new(Global), _marker: PhantomData }
661 }
662}
663
664impl<K, V, A: AllocatorClone> BTreeMap<K, V, A> {
665 /// Clears the map, removing all elements.
666 ///
667 /// # Examples
668 ///
669 /// ```
670 /// use std::collections::BTreeMap;
671 ///
672 /// let mut a = BTreeMap::new();
673 /// a.insert(1, "a");
674 /// a.clear();
675 /// assert!(a.is_empty());
676 /// ```
677 #[stable(feature = "rust1", since = "1.0.0")]
678 pub fn clear(&mut self) {
679 // avoid moving the allocator
680 drop(BTreeMap {
681 root: self.root.take(),
682 length: mem::replace(&mut self.length, 0),
683 alloc: self.alloc.clone(),
684 _marker: PhantomData,
685 });
686 }
687
688 /// Makes a new empty BTreeMap with a reasonable choice for B.
689 ///
690 /// # Examples
691 ///
692 /// ```
693 /// # #![feature(btreemap_alloc)]
694 ///
695 /// use std::collections::BTreeMap;
696 /// use std::alloc::Global;
697 ///
698 /// let map: BTreeMap<i32, i32> = BTreeMap::new_in(Global);
699 /// ```
700 #[unstable(feature = "btreemap_alloc", issue = "163177")]
701 #[must_use]
702 pub const fn new_in(alloc: A) -> BTreeMap<K, V, A> {
703 BTreeMap { root: None, length: 0, alloc: ManuallyDrop::new(alloc), _marker: PhantomData }
704 }
705
706 /// Returns a reference to the underlying allocator.
707 #[unstable(feature = "btreemap_alloc", issue = "163177")]
708 #[inline]
709 pub fn allocator(&self) -> &A {
710 &self.alloc
711 }
712}
713
714impl<K, V, A: AllocatorClone> BTreeMap<K, V, A> {
715 /// Returns a reference to the value corresponding to the key.
716 ///
717 /// The key may be any borrowed form of the map's key type, but the ordering
718 /// on the borrowed form *must* match the ordering on the key type.
719 ///
720 /// # Examples
721 ///
722 /// ```
723 /// use std::collections::BTreeMap;
724 ///
725 /// let mut map = BTreeMap::new();
726 /// map.insert(1, "a");
727 /// assert_eq!(map.get(&1), Some(&"a"));
728 /// assert_eq!(map.get(&2), None);
729 /// ```
730 #[stable(feature = "rust1", since = "1.0.0")]
731 pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V>
732 where
733 K: Borrow<Q> + Ord,
734 Q: Ord,
735 {
736 let root_node = self.root.as_ref()?.reborrow();
737 match root_node.search_tree(key) {
738 Found(handle) => Some(handle.into_kv().1),
739 GoDown(_) => None,
740 }
741 }
742
743 /// Returns the key-value pair corresponding to the supplied key. This is
744 /// potentially useful:
745 /// - for key types where non-identical keys can be considered equal;
746 /// - for getting the `&K` stored key value from a borrowed `&Q` lookup key; or
747 /// - for getting a reference to a key with the same lifetime as the collection.
748 ///
749 /// The supplied key may be any borrowed form of the map's key type, but the ordering
750 /// on the borrowed form *must* match the ordering on the key type.
751 ///
752 /// # Examples
753 ///
754 /// ```
755 /// use std::cmp::Ordering;
756 /// use std::collections::BTreeMap;
757 ///
758 /// #[derive(Clone, Copy, Debug)]
759 /// struct S {
760 /// id: u32,
761 /// # #[allow(unused)] // prevents a "field `name` is never read" error
762 /// name: &'static str, // ignored by equality and ordering operations
763 /// }
764 ///
765 /// impl PartialEq for S {
766 /// fn eq(&self, other: &S) -> bool {
767 /// self.id == other.id
768 /// }
769 /// }
770 ///
771 /// impl Eq for S {}
772 ///
773 /// impl PartialOrd for S {
774 /// fn partial_cmp(&self, other: &S) -> Option<Ordering> {
775 /// self.id.partial_cmp(&other.id)
776 /// }
777 /// }
778 ///
779 /// impl Ord for S {
780 /// fn cmp(&self, other: &S) -> Ordering {
781 /// self.id.cmp(&other.id)
782 /// }
783 /// }
784 ///
785 /// let j_a = S { id: 1, name: "Jessica" };
786 /// let j_b = S { id: 1, name: "Jess" };
787 /// let p = S { id: 2, name: "Paul" };
788 /// assert_eq!(j_a, j_b);
789 ///
790 /// let mut map = BTreeMap::new();
791 /// map.insert(j_a, "Paris");
792 /// assert_eq!(map.get_key_value(&j_a), Some((&j_a, &"Paris")));
793 /// assert_eq!(map.get_key_value(&j_b), Some((&j_a, &"Paris"))); // the notable case
794 /// assert_eq!(map.get_key_value(&p), None);
795 /// ```
796 #[stable(feature = "map_get_key_value", since = "1.40.0")]
797 pub fn get_key_value<Q: ?Sized>(&self, k: &Q) -> Option<(&K, &V)>
798 where
799 K: Borrow<Q> + Ord,
800 Q: Ord,
801 {
802 let root_node = self.root.as_ref()?.reborrow();
803 match root_node.search_tree(k) {
804 Found(handle) => Some(handle.into_kv()),
805 GoDown(_) => None,
806 }
807 }
808
809 /// Returns the first key-value pair in the map.
810 /// The key in this pair is the minimum key in the map.
811 ///
812 /// # Examples
813 ///
814 /// ```
815 /// use std::collections::BTreeMap;
816 ///
817 /// let mut map = BTreeMap::new();
818 /// assert_eq!(map.first_key_value(), None);
819 /// map.insert(1, "b");
820 /// map.insert(2, "a");
821 /// assert_eq!(map.first_key_value(), Some((&1, &"b")));
822 /// ```
823 #[stable(feature = "map_first_last", since = "1.66.0")]
824 pub fn first_key_value(&self) -> Option<(&K, &V)>
825 where
826 K: Ord,
827 {
828 let root_node = self.root.as_ref()?.reborrow();
829 root_node.first_leaf_edge().right_kv().ok().map(Handle::into_kv)
830 }
831
832 /// Returns the first entry in the map for in-place manipulation.
833 /// The key of this entry is the minimum key in the map.
834 ///
835 /// # Examples
836 ///
837 /// ```
838 /// use std::collections::BTreeMap;
839 ///
840 /// let mut map = BTreeMap::new();
841 /// map.insert(1, "a");
842 /// map.insert(2, "b");
843 /// if let Some(mut entry) = map.first_entry() {
844 /// if *entry.key() > 0 {
845 /// entry.insert("first");
846 /// }
847 /// }
848 /// assert_eq!(*map.get(&1).unwrap(), "first");
849 /// assert_eq!(*map.get(&2).unwrap(), "b");
850 /// ```
851 #[stable(feature = "map_first_last", since = "1.66.0")]
852 pub fn first_entry(&mut self) -> Option<OccupiedEntry<'_, K, V, A>>
853 where
854 K: Ord,
855 {
856 let (map, dormant_map) = DormantMutRef::new(self);
857 let root_node = map.root.as_mut()?.borrow_mut();
858 let kv = root_node.first_leaf_edge().right_kv().ok()?;
859 Some(OccupiedEntry {
860 handle: kv.forget_node_type(),
861 dormant_map,
862 alloc: (*map.alloc).clone(),
863 _marker: PhantomData,
864 })
865 }
866
867 /// Removes and returns the first element in the map.
868 /// The key of this element is the minimum key that was in the map.
869 ///
870 /// # Examples
871 ///
872 /// Draining elements in ascending order, while keeping a usable map each iteration.
873 ///
874 /// ```
875 /// use std::collections::BTreeMap;
876 ///
877 /// let mut map = BTreeMap::new();
878 /// map.insert(1, "a");
879 /// map.insert(2, "b");
880 /// while let Some((key, _val)) = map.pop_first() {
881 /// assert!(map.iter().all(|(k, _v)| *k > key));
882 /// }
883 /// assert!(map.is_empty());
884 /// ```
885 #[stable(feature = "map_first_last", since = "1.66.0")]
886 pub fn pop_first(&mut self) -> Option<(K, V)>
887 where
888 K: Ord,
889 {
890 self.first_entry().map(|entry| entry.remove_entry())
891 }
892
893 /// Returns the last key-value pair in the map.
894 /// The key in this pair is the maximum key in the map.
895 ///
896 /// # Examples
897 ///
898 /// ```
899 /// use std::collections::BTreeMap;
900 ///
901 /// let mut map = BTreeMap::new();
902 /// map.insert(1, "b");
903 /// map.insert(2, "a");
904 /// assert_eq!(map.last_key_value(), Some((&2, &"a")));
905 /// ```
906 #[stable(feature = "map_first_last", since = "1.66.0")]
907 pub fn last_key_value(&self) -> Option<(&K, &V)>
908 where
909 K: Ord,
910 {
911 let root_node = self.root.as_ref()?.reborrow();
912 root_node.last_leaf_edge().left_kv().ok().map(Handle::into_kv)
913 }
914
915 /// Returns the last entry in the map for in-place manipulation.
916 /// The key of this entry is the maximum key in the map.
917 ///
918 /// # Examples
919 ///
920 /// ```
921 /// use std::collections::BTreeMap;
922 ///
923 /// let mut map = BTreeMap::new();
924 /// map.insert(1, "a");
925 /// map.insert(2, "b");
926 /// if let Some(mut entry) = map.last_entry() {
927 /// if *entry.key() > 0 {
928 /// entry.insert("last");
929 /// }
930 /// }
931 /// assert_eq!(*map.get(&1).unwrap(), "a");
932 /// assert_eq!(*map.get(&2).unwrap(), "last");
933 /// ```
934 #[stable(feature = "map_first_last", since = "1.66.0")]
935 pub fn last_entry(&mut self) -> Option<OccupiedEntry<'_, K, V, A>>
936 where
937 K: Ord,
938 {
939 let (map, dormant_map) = DormantMutRef::new(self);
940 let root_node = map.root.as_mut()?.borrow_mut();
941 let kv = root_node.last_leaf_edge().left_kv().ok()?;
942 Some(OccupiedEntry {
943 handle: kv.forget_node_type(),
944 dormant_map,
945 alloc: (*map.alloc).clone(),
946 _marker: PhantomData,
947 })
948 }
949
950 /// Removes and returns the last element in the map.
951 /// The key of this element is the maximum key that was in the map.
952 ///
953 /// # Examples
954 ///
955 /// Draining elements in descending order, while keeping a usable map each iteration.
956 ///
957 /// ```
958 /// use std::collections::BTreeMap;
959 ///
960 /// let mut map = BTreeMap::new();
961 /// map.insert(1, "a");
962 /// map.insert(2, "b");
963 /// while let Some((key, _val)) = map.pop_last() {
964 /// assert!(map.iter().all(|(k, _v)| *k < key));
965 /// }
966 /// assert!(map.is_empty());
967 /// ```
968 #[stable(feature = "map_first_last", since = "1.66.0")]
969 pub fn pop_last(&mut self) -> Option<(K, V)>
970 where
971 K: Ord,
972 {
973 self.last_entry().map(|entry| entry.remove_entry())
974 }
975
976 /// Returns `true` if the map contains a value for the specified key.
977 ///
978 /// The key may be any borrowed form of the map's key type, but the ordering
979 /// on the borrowed form *must* match the ordering on the key type.
980 ///
981 /// # Examples
982 ///
983 /// ```
984 /// use std::collections::BTreeMap;
985 ///
986 /// let mut map = BTreeMap::new();
987 /// map.insert(1, "a");
988 /// assert_eq!(map.contains_key(&1), true);
989 /// assert_eq!(map.contains_key(&2), false);
990 /// ```
991 #[stable(feature = "rust1", since = "1.0.0")]
992 #[cfg_attr(not(test), rustc_diagnostic_item = "btreemap_contains_key")]
993 pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool
994 where
995 K: Borrow<Q> + Ord,
996 Q: Ord,
997 {
998 self.get(key).is_some()
999 }
1000
1001 /// Returns a mutable reference to the value corresponding to the key.
1002 ///
1003 /// The key may be any borrowed form of the map's key type, but the ordering
1004 /// on the borrowed form *must* match the ordering on the key type.
1005 ///
1006 /// # Examples
1007 ///
1008 /// ```
1009 /// use std::collections::BTreeMap;
1010 ///
1011 /// let mut map = BTreeMap::new();
1012 /// map.insert(1, "a");
1013 /// if let Some(x) = map.get_mut(&1) {
1014 /// *x = "b";
1015 /// }
1016 /// assert_eq!(map[&1], "b");
1017 /// ```
1018 // See `get` for implementation notes, this is basically a copy-paste with mut's added
1019 #[stable(feature = "rust1", since = "1.0.0")]
1020 pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>
1021 where
1022 K: Borrow<Q> + Ord,
1023 Q: Ord,
1024 {
1025 let root_node = self.root.as_mut()?.borrow_mut();
1026 match root_node.search_tree(key) {
1027 Found(handle) => Some(handle.into_val_mut()),
1028 GoDown(_) => None,
1029 }
1030 }
1031
1032 /// Inserts a key-value pair into the map.
1033 ///
1034 /// If the map did not have this key present, `None` is returned.
1035 ///
1036 /// If the map did have this key present, the value is updated, and the old
1037 /// value is returned. The key is not updated, though; this matters for
1038 /// types that can be `==` without being identical. See the [module-level
1039 /// documentation] for more.
1040 ///
1041 /// [module-level documentation]: index.html#insert-and-complex-keys
1042 ///
1043 /// # Examples
1044 ///
1045 /// ```
1046 /// use std::collections::BTreeMap;
1047 ///
1048 /// let mut map = BTreeMap::new();
1049 /// assert_eq!(map.insert(37, "a"), None);
1050 /// assert_eq!(map.is_empty(), false);
1051 ///
1052 /// map.insert(37, "b");
1053 /// assert_eq!(map.insert(37, "c"), Some("b"));
1054 /// assert_eq!(map[&37], "c");
1055 /// ```
1056 #[stable(feature = "rust1", since = "1.0.0")]
1057 #[rustc_confusables("push", "put", "set")]
1058 #[cfg_attr(not(test), rustc_diagnostic_item = "btreemap_insert")]
1059 pub fn insert(&mut self, key: K, value: V) -> Option<V>
1060 where
1061 K: Ord,
1062 {
1063 match self.entry(key) {
1064 Occupied(mut entry) => Some(entry.insert(value)),
1065 Vacant(entry) => {
1066 entry.insert(value);
1067 None
1068 }
1069 }
1070 }
1071
1072 /// Tries to insert a key-value pair into the map, and returns
1073 /// a mutable reference to the value in the entry.
1074 ///
1075 /// If the map already had this key present, nothing is updated, and
1076 /// an error containing the occupied entry, key, and the value is returned.
1077 ///
1078 /// # Examples
1079 ///
1080 /// ```
1081 /// #![feature(map_try_insert)]
1082 ///
1083 /// use std::collections::BTreeMap;
1084 ///
1085 /// let mut map = BTreeMap::new();
1086 /// assert_eq!(map.try_insert(37, "a").unwrap(), &"a");
1087 ///
1088 /// let err = map.try_insert(37, "b").unwrap_err();
1089 /// assert_eq!(err.entry.key(), &37);
1090 /// assert_eq!(err.entry.get(), &"a");
1091 /// assert_eq!(err.key, 37);
1092 /// assert_eq!(err.value, "b");
1093 /// ```
1094 #[unstable(feature = "map_try_insert", issue = "82766")]
1095 pub fn try_insert(&mut self, key: K, value: V) -> Result<&mut V, OccupiedError<'_, K, V, A>>
1096 where
1097 K: Ord,
1098 {
1099 let (map, dormant_map) = DormantMutRef::new(self);
1100 let handle = match map.root {
1101 Some(ref mut root) => match root.borrow_mut().search_tree(&key) {
1102 Found(handle) => {
1103 let entry = OccupiedEntry {
1104 handle,
1105 dormant_map,
1106 alloc: (*map.alloc).clone(),
1107 _marker: PhantomData,
1108 };
1109 return Err(OccupiedError { entry, key, value });
1110 }
1111 GoDown(handle) => Some(handle),
1112 },
1113 None => None,
1114 };
1115 let entry = VacantEntry {
1116 key,
1117 handle,
1118 dormant_map,
1119 alloc: (*map.alloc).clone(),
1120 _marker: PhantomData,
1121 };
1122 Ok(entry.insert(value))
1123 }
1124
1125 /// Removes a key from the map, returning the value at the key if the key
1126 /// was previously in the map.
1127 ///
1128 /// The key may be any borrowed form of the map's key type, but the ordering
1129 /// on the borrowed form *must* match the ordering on the key type.
1130 ///
1131 /// # Examples
1132 ///
1133 /// ```
1134 /// use std::collections::BTreeMap;
1135 ///
1136 /// let mut map = BTreeMap::new();
1137 /// map.insert(1, "a");
1138 /// assert_eq!(map.remove(&1), Some("a"));
1139 /// assert_eq!(map.remove(&1), None);
1140 /// ```
1141 #[stable(feature = "rust1", since = "1.0.0")]
1142 #[rustc_confusables("delete", "take")]
1143 pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V>
1144 where
1145 K: Borrow<Q> + Ord,
1146 Q: Ord,
1147 {
1148 self.remove_entry(key).map(|(_, v)| v)
1149 }
1150
1151 /// Removes a key from the map, returning the stored key and value if the key
1152 /// was previously in the map.
1153 ///
1154 /// The key may be any borrowed form of the map's key type, but the ordering
1155 /// on the borrowed form *must* match the ordering on the key type.
1156 ///
1157 /// # Examples
1158 ///
1159 /// ```
1160 /// use std::collections::BTreeMap;
1161 ///
1162 /// let mut map = BTreeMap::new();
1163 /// map.insert(1, "a");
1164 /// assert_eq!(map.remove_entry(&1), Some((1, "a")));
1165 /// assert_eq!(map.remove_entry(&1), None);
1166 /// ```
1167 #[stable(feature = "btreemap_remove_entry", since = "1.45.0")]
1168 pub fn remove_entry<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)>
1169 where
1170 K: Borrow<Q> + Ord,
1171 Q: Ord,
1172 {
1173 let (map, dormant_map) = DormantMutRef::new(self);
1174 let root_node = map.root.as_mut()?.borrow_mut();
1175 match root_node.search_tree(key) {
1176 Found(handle) => Some(
1177 OccupiedEntry {
1178 handle,
1179 dormant_map,
1180 alloc: (*map.alloc).clone(),
1181 _marker: PhantomData,
1182 }
1183 .remove_entry(),
1184 ),
1185 GoDown(_) => None,
1186 }
1187 }
1188
1189 /// Retains only the elements specified by the predicate.
1190 ///
1191 /// In other words, remove all pairs `(k, v)` for which `f(&k, &mut v)` returns `false`.
1192 /// The elements are visited in ascending key order.
1193 ///
1194 /// # Examples
1195 ///
1196 /// ```
1197 /// use std::collections::BTreeMap;
1198 ///
1199 /// let mut map: BTreeMap<i32, i32> = (0..8).map(|x| (x, x*10)).collect();
1200 /// // Keep only the elements with even-numbered keys.
1201 /// map.retain(|&k, _| k % 2 == 0);
1202 /// assert!(map.into_iter().eq(vec![(0, 0), (2, 20), (4, 40), (6, 60)]));
1203 /// ```
1204 #[inline]
1205 #[stable(feature = "btree_retain", since = "1.53.0")]
1206 pub fn retain<F>(&mut self, mut f: F)
1207 where
1208 K: Ord,
1209 F: FnMut(&K, &mut V) -> bool,
1210 {
1211 self.extract_if(.., |k, v| !f(k, v)).for_each(drop);
1212 }
1213
1214 /// Moves all elements from `other` into `self`, leaving `other` empty.
1215 ///
1216 /// If a key from `other` is already present in `self`, the respective
1217 /// value from `self` will be overwritten with the respective value from `other`.
1218 /// Similar to [`insert`], though, the key is not overwritten,
1219 /// which matters for types that can be `==` without being identical.
1220 ///
1221 /// [`insert`]: BTreeMap::insert
1222 ///
1223 /// # Examples
1224 ///
1225 /// ```
1226 /// use std::collections::BTreeMap;
1227 ///
1228 /// let mut a = BTreeMap::new();
1229 /// a.insert(1, "a");
1230 /// a.insert(2, "b");
1231 /// a.insert(3, "c"); // Note: Key (3) also present in b.
1232 ///
1233 /// let mut b = BTreeMap::new();
1234 /// b.insert(3, "d"); // Note: Key (3) also present in a.
1235 /// b.insert(4, "e");
1236 /// b.insert(5, "f");
1237 ///
1238 /// a.append(&mut b);
1239 ///
1240 /// assert_eq!(a.len(), 5);
1241 /// assert_eq!(b.len(), 0);
1242 ///
1243 /// assert_eq!(a[&1], "a");
1244 /// assert_eq!(a[&2], "b");
1245 /// assert_eq!(a[&3], "d"); // Note: "c" has been overwritten.
1246 /// assert_eq!(a[&4], "e");
1247 /// assert_eq!(a[&5], "f");
1248 /// ```
1249 #[stable(feature = "btree_append", since = "1.11.0")]
1250 pub fn append(&mut self, other: &mut Self)
1251 where
1252 K: Ord,
1253 A: Clone,
1254 {
1255 let other = mem::replace(other, Self::new_in((*self.alloc).clone()));
1256 self.merge(other, |_key, _self_val, other_val| other_val);
1257 }
1258
1259 /// Moves all elements from `other` into `self`, leaving `other` empty.
1260 ///
1261 /// If a key from `other` is already present in `self`, then the `conflict`
1262 /// closure is used to return a value to `self`. The `conflict`
1263 /// closure takes in a borrow of `self`'s key, `self`'s value, and `other`'s value
1264 /// in that order.
1265 ///
1266 /// An example of why one might use this method over [`append`]
1267 /// is to combine `self`'s value with `other`'s value when their keys conflict.
1268 ///
1269 /// Similar to [`insert`], though, the key is not overwritten,
1270 /// which matters for types that can be `==` without being identical.
1271 ///
1272 /// [`insert`]: BTreeMap::insert
1273 /// [`append`]: BTreeMap::append
1274 ///
1275 /// # Examples
1276 ///
1277 /// ```
1278 /// #![feature(btree_merge)]
1279 /// use std::collections::BTreeMap;
1280 ///
1281 /// let mut a = BTreeMap::new();
1282 /// a.insert(1, String::from("a"));
1283 /// a.insert(2, String::from("b"));
1284 /// a.insert(3, String::from("c")); // Note: Key (3) also present in b.
1285 ///
1286 /// let mut b = BTreeMap::new();
1287 /// b.insert(3, String::from("d")); // Note: Key (3) also present in a.
1288 /// b.insert(4, String::from("e"));
1289 /// b.insert(5, String::from("f"));
1290 ///
1291 /// // concatenate a's value and b's value
1292 /// a.merge(b, |_, a_val, b_val| {
1293 /// format!("{a_val}{b_val}")
1294 /// });
1295 ///
1296 /// assert_eq!(a.len(), 5); // all of b's keys in a
1297 ///
1298 /// assert_eq!(a[&1], "a");
1299 /// assert_eq!(a[&2], "b");
1300 /// assert_eq!(a[&3], "cd"); // Note: "c" has been combined with "d".
1301 /// assert_eq!(a[&4], "e");
1302 /// assert_eq!(a[&5], "f");
1303 /// ```
1304 #[unstable(feature = "btree_merge", issue = "152152")]
1305 pub fn merge(&mut self, mut other: Self, mut conflict: impl FnMut(&K, V, V) -> V)
1306 where
1307 K: Ord,
1308 A: Clone,
1309 {
1310 // Do we have to append anything at all?
1311 if other.is_empty() {
1312 return;
1313 }
1314
1315 // We can just swap `self` and `other` if `self` is empty.
1316 if self.is_empty() {
1317 mem::swap(self, &mut other);
1318 return;
1319 }
1320
1321 let mut other_iter = other.into_iter();
1322 let (first_other_key, first_other_val) = other_iter.next().unwrap();
1323
1324 // find the first gap that has the smallest key greater than or equal to
1325 // the first key from other
1326 let mut self_cursor = self.lower_bound_mut(Bound::Included(&first_other_key));
1327
1328 if let Some((self_key, _)) = self_cursor.peek_next() {
1329 match K::cmp(self_key, &first_other_key) {
1330 Ordering::Equal => {
1331 // if `f` unwinds, the next entry is already removed leaving
1332 // the tree in valid state.
1333 // FIXME: Once `MaybeDangling` is implemented, we can optimize
1334 // this through using a drop handler and transmutating CursorMutKey<K, V>
1335 // to CursorMutKey<ManuallyDrop<K>, ManuallyDrop<V>> (see PR #152418)
1336 if let Some((k, v)) = self_cursor.remove_next() {
1337 let v = conflict(&k, v, first_other_val);
1338 // SAFETY: we remove the K, V out of the next entry,
1339 // apply 'f' to get a new (K, V), and insert it back
1340 // into the next entry that the cursor is pointing at
1341 unsafe { self_cursor.insert_after_unchecked(k, v) };
1342 }
1343 }
1344 Ordering::Greater =>
1345 // SAFETY: we know our other_key's ordering is less than self_key,
1346 // so inserting before will guarantee sorted order
1347 unsafe {
1348 self_cursor.insert_before_unchecked(first_other_key, first_other_val);
1349 },
1350 Ordering::Less => {
1351 unreachable!("Cursor's peek_next should return None.");
1352 }
1353 }
1354 } else {
1355 // SAFETY: reaching here means our cursor is at the end
1356 // self BTreeMap so we just insert other_key here
1357 unsafe {
1358 self_cursor.insert_before_unchecked(first_other_key, first_other_val);
1359 }
1360 }
1361
1362 for (other_key, other_val) in other_iter {
1363 loop {
1364 if let Some((self_key, _)) = self_cursor.peek_next() {
1365 match K::cmp(self_key, &other_key) {
1366 Ordering::Equal => {
1367 // if `f` unwinds, the next entry is already removed leaving
1368 // the tree in valid state.
1369 // FIXME: Once `MaybeDangling` is implemented, we can optimize
1370 // this through using a drop handler and transmutating CursorMutKey<K, V>
1371 // to CursorMutKey<ManuallyDrop<K>, ManuallyDrop<V>> (see PR #152418)
1372 if let Some((k, v)) = self_cursor.remove_next() {
1373 let v = conflict(&k, v, other_val);
1374 // SAFETY: we remove the K, V out of the next entry,
1375 // apply 'f' to get a new (K, V), and insert it back
1376 // into the next entry that the cursor is pointing at
1377 unsafe { self_cursor.insert_after_unchecked(k, v) };
1378 }
1379 break;
1380 }
1381 Ordering::Greater => {
1382 // SAFETY: we know our self_key's ordering is greater than other_key,
1383 // so inserting before will guarantee sorted order
1384 unsafe {
1385 self_cursor.insert_before_unchecked(other_key, other_val);
1386 }
1387 break;
1388 }
1389 Ordering::Less => {
1390 // FIXME: instead of doing a linear search here,
1391 // this can be optimized to search the tree by starting
1392 // from self_cursor and going towards the root and then
1393 // back down to the proper node -- that should probably
1394 // be a new method on Cursor*.
1395 self_cursor.next();
1396 }
1397 }
1398 } else {
1399 // FIXME: If we get here, that means all of other's keys are greater than
1400 // self's keys. For performance, this should really do a bulk insertion of items
1401 // from other_iter into the end of self `BTreeMap`. Maybe this should be
1402 // a method for Cursor*?
1403
1404 // SAFETY: reaching here means our cursor is at the end
1405 // self BTreeMap so we just insert other_key here
1406 unsafe {
1407 self_cursor.insert_before_unchecked(other_key, other_val);
1408 }
1409 break;
1410 }
1411 }
1412 }
1413 }
1414
1415 /// Constructs a double-ended iterator over a sub-range of elements in the map.
1416 /// The simplest way is to use the range syntax `min..max`, thus `range(min..max)` will
1417 /// yield elements from min (inclusive) to max (exclusive).
1418 /// The range may also be entered as `(Bound<T>, Bound<T>)`, so for example
1419 /// `range((Excluded(4), Included(10)))` will yield a left-exclusive, right-inclusive
1420 /// range from 4 to 10.
1421 ///
1422 /// # Panics
1423 ///
1424 /// Panics if range `start > end`.
1425 /// Panics if range `start == end` and both bounds are `Excluded`.
1426 ///
1427 /// # Examples
1428 ///
1429 /// ```
1430 /// use std::collections::BTreeMap;
1431 /// use std::ops::Bound::Included;
1432 ///
1433 /// let mut map = BTreeMap::new();
1434 /// map.insert(3, "a");
1435 /// map.insert(5, "b");
1436 /// map.insert(8, "c");
1437 /// for (&key, &value) in map.range((Included(&4), Included(&8))) {
1438 /// println!("{key}: {value}");
1439 /// }
1440 /// assert_eq!(Some((&5, &"b")), map.range(4..).next());
1441 /// ```
1442 #[stable(feature = "btree_range", since = "1.17.0")]
1443 pub fn range<T: ?Sized, R>(&self, range: R) -> Range<'_, K, V>
1444 where
1445 T: Ord,
1446 K: Borrow<T> + Ord,
1447 R: RangeBounds<T>,
1448 {
1449 if let Some(root) = &self.root {
1450 Range { inner: root.reborrow().range_search(range) }
1451 } else {
1452 Range { inner: LeafRange::none() }
1453 }
1454 }
1455
1456 /// Constructs a mutable double-ended iterator over a sub-range of elements in the map.
1457 /// The simplest way is to use the range syntax `min..max`, thus `range(min..max)` will
1458 /// yield elements from min (inclusive) to max (exclusive).
1459 /// The range may also be entered as `(Bound<T>, Bound<T>)`, so for example
1460 /// `range((Excluded(4), Included(10)))` will yield a left-exclusive, right-inclusive
1461 /// range from 4 to 10.
1462 ///
1463 /// # Panics
1464 ///
1465 /// Panics if range `start > end`.
1466 /// Panics if range `start == end` and both bounds are `Excluded`.
1467 ///
1468 /// # Examples
1469 ///
1470 /// ```
1471 /// use std::collections::BTreeMap;
1472 ///
1473 /// let mut map: BTreeMap<&str, i32> =
1474 /// [("Alice", 0), ("Bob", 0), ("Carol", 0), ("Cheryl", 0)].into();
1475 /// for (_, balance) in map.range_mut("B".."Cheryl") {
1476 /// *balance += 100;
1477 /// }
1478 /// for (name, balance) in &map {
1479 /// println!("{name} => {balance}");
1480 /// }
1481 /// ```
1482 #[stable(feature = "btree_range", since = "1.17.0")]
1483 pub fn range_mut<T: ?Sized, R>(&mut self, range: R) -> RangeMut<'_, K, V>
1484 where
1485 T: Ord,
1486 K: Borrow<T> + Ord,
1487 R: RangeBounds<T>,
1488 {
1489 if let Some(root) = &mut self.root {
1490 RangeMut { inner: root.borrow_valmut().range_search(range), _marker: PhantomData }
1491 } else {
1492 RangeMut { inner: LeafRange::none(), _marker: PhantomData }
1493 }
1494 }
1495
1496 /// Gets the given key's corresponding entry in the map for in-place manipulation.
1497 ///
1498 /// # Examples
1499 ///
1500 /// ```
1501 /// use std::collections::BTreeMap;
1502 ///
1503 /// let mut count: BTreeMap<&str, usize> = BTreeMap::new();
1504 ///
1505 /// // count the number of occurrences of letters in the vec
1506 /// for x in ["a", "b", "a", "c", "a", "b"] {
1507 /// count.entry(x).and_modify(|curr| *curr += 1).or_insert(1);
1508 /// }
1509 ///
1510 /// assert_eq!(count["a"], 3);
1511 /// assert_eq!(count["b"], 2);
1512 /// assert_eq!(count["c"], 1);
1513 /// ```
1514 #[stable(feature = "rust1", since = "1.0.0")]
1515 pub fn entry(&mut self, key: K) -> Entry<'_, K, V, A>
1516 where
1517 K: Ord,
1518 {
1519 let (map, dormant_map) = DormantMutRef::new(self);
1520 match map.root {
1521 None => Vacant(VacantEntry {
1522 key,
1523 handle: None,
1524 dormant_map,
1525 alloc: (*map.alloc).clone(),
1526 _marker: PhantomData,
1527 }),
1528 Some(ref mut root) => match root.borrow_mut().search_tree(&key) {
1529 Found(handle) => Occupied(OccupiedEntry {
1530 handle,
1531 dormant_map,
1532 alloc: (*map.alloc).clone(),
1533 _marker: PhantomData,
1534 }),
1535 GoDown(handle) => Vacant(VacantEntry {
1536 key,
1537 handle: Some(handle),
1538 dormant_map,
1539 alloc: (*map.alloc).clone(),
1540 _marker: PhantomData,
1541 }),
1542 },
1543 }
1544 }
1545
1546 /// Splits the collection into two at the given key. Returns everything after the given key,
1547 /// including the key. If the key is not present, the split will occur at the nearest
1548 /// greater key, or return an empty map if no such key exists.
1549 ///
1550 /// # Examples
1551 ///
1552 /// ```
1553 /// use std::collections::BTreeMap;
1554 ///
1555 /// let mut a = BTreeMap::new();
1556 /// a.insert(1, "a");
1557 /// a.insert(2, "b");
1558 /// a.insert(3, "c");
1559 /// a.insert(17, "d");
1560 /// a.insert(41, "e");
1561 ///
1562 /// let b = a.split_off(&3);
1563 ///
1564 /// assert_eq!(a.len(), 2);
1565 /// assert_eq!(b.len(), 3);
1566 ///
1567 /// assert_eq!(a[&1], "a");
1568 /// assert_eq!(a[&2], "b");
1569 ///
1570 /// assert_eq!(b[&3], "c");
1571 /// assert_eq!(b[&17], "d");
1572 /// assert_eq!(b[&41], "e");
1573 /// ```
1574 #[stable(feature = "btree_split_off", since = "1.11.0")]
1575 pub fn split_off<Q: ?Sized + Ord>(&mut self, key: &Q) -> Self
1576 where
1577 K: Borrow<Q> + Ord,
1578 A: Clone,
1579 {
1580 if self.is_empty() {
1581 return Self::new_in((*self.alloc).clone());
1582 }
1583
1584 let total_num = self.len();
1585 let left_root = self.root.as_mut().unwrap(); // unwrap succeeds because not empty
1586
1587 let right_root = left_root.split_off(key, (*self.alloc).clone());
1588
1589 let (new_left_len, right_len) = Root::calc_split_length(total_num, left_root, &right_root);
1590 self.length = new_left_len;
1591
1592 BTreeMap {
1593 root: Some(right_root),
1594 length: right_len,
1595 alloc: self.alloc.clone(),
1596 _marker: PhantomData,
1597 }
1598 }
1599
1600 /// Creates an iterator that visits elements (key-value pairs) in the specified range in
1601 /// ascending key order and uses a closure to determine if an element
1602 /// should be removed.
1603 ///
1604 /// If the closure returns `true`, the element is removed from the map and
1605 /// yielded. If the closure returns `false`, or panics, the element remains
1606 /// in the map and will not be yielded.
1607 ///
1608 /// The iterator also lets you mutate the value of each element in the
1609 /// closure, regardless of whether you choose to keep or remove it.
1610 ///
1611 /// If the returned `ExtractIf` is not exhausted, e.g. because it is dropped without iterating
1612 /// or the iteration short-circuits, then the remaining elements will be retained.
1613 /// Use `extract_if().for_each(drop)` if you do not need the returned iterator,
1614 /// or [`retain`] with a negated predicate if you also do not need to restrict the range.
1615 ///
1616 /// [`retain`]: BTreeMap::retain
1617 ///
1618 /// # Examples
1619 ///
1620 /// ```
1621 /// use std::collections::BTreeMap;
1622 ///
1623 /// // Splitting a map into even and odd keys, reusing the original map:
1624 /// let mut map: BTreeMap<i32, i32> = (0..8).map(|x| (x, x)).collect();
1625 /// let evens: BTreeMap<_, _> = map.extract_if(.., |k, _v| k % 2 == 0).collect();
1626 /// let odds = map;
1627 /// assert_eq!(evens.keys().copied().collect::<Vec<_>>(), [0, 2, 4, 6]);
1628 /// assert_eq!(odds.keys().copied().collect::<Vec<_>>(), [1, 3, 5, 7]);
1629 ///
1630 /// // Splitting a map into low and high halves, reusing the original map:
1631 /// let mut map: BTreeMap<i32, i32> = (0..8).map(|x| (x, x)).collect();
1632 /// let low: BTreeMap<_, _> = map.extract_if(0..4, |_k, _v| true).collect();
1633 /// let high = map;
1634 /// assert_eq!(low.keys().copied().collect::<Vec<_>>(), [0, 1, 2, 3]);
1635 /// assert_eq!(high.keys().copied().collect::<Vec<_>>(), [4, 5, 6, 7]);
1636 /// ```
1637 #[stable(feature = "btree_extract_if", since = "1.91.0")]
1638 pub fn extract_if<F, R>(&mut self, range: R, pred: F) -> ExtractIf<'_, K, V, R, F, A>
1639 where
1640 K: Ord,
1641 R: RangeBounds<K>,
1642 F: FnMut(&K, &mut V) -> bool,
1643 {
1644 let (inner, alloc) = self.extract_if_inner(range);
1645 ExtractIf { pred, inner, alloc }
1646 }
1647
1648 pub(super) fn extract_if_inner<R>(&mut self, range: R) -> (ExtractIfInner<'_, K, V, R>, A)
1649 where
1650 K: Ord,
1651 R: RangeBounds<K>,
1652 {
1653 if let Some(root) = self.root.as_mut() {
1654 let (root, dormant_root) = DormantMutRef::new(root);
1655 let first = root.borrow_mut().lower_bound(SearchBound::from_range(range.start_bound()));
1656 (
1657 ExtractIfInner {
1658 length: &mut self.length,
1659 dormant_root: Some(dormant_root),
1660 cur_leaf_edge: Some(first),
1661 range,
1662 },
1663 (*self.alloc).clone(),
1664 )
1665 } else {
1666 (
1667 ExtractIfInner {
1668 length: &mut self.length,
1669 dormant_root: None,
1670 cur_leaf_edge: None,
1671 range,
1672 },
1673 (*self.alloc).clone(),
1674 )
1675 }
1676 }
1677
1678 /// Creates a consuming iterator visiting all the keys, in sorted order.
1679 /// The map cannot be used after calling this.
1680 /// The iterator element type is `K`.
1681 ///
1682 /// # Examples
1683 ///
1684 /// ```
1685 /// use std::collections::BTreeMap;
1686 ///
1687 /// let mut a = BTreeMap::new();
1688 /// a.insert(2, "b");
1689 /// a.insert(1, "a");
1690 ///
1691 /// let keys: Vec<i32> = a.into_keys().collect();
1692 /// assert_eq!(keys, [1, 2]);
1693 /// ```
1694 #[inline]
1695 #[stable(feature = "map_into_keys_values", since = "1.54.0")]
1696 pub fn into_keys(self) -> IntoKeys<K, V, A> {
1697 IntoKeys { inner: self.into_iter() }
1698 }
1699
1700 /// Creates a consuming iterator visiting all the values, in order by key.
1701 /// The map cannot be used after calling this.
1702 /// The iterator element type is `V`.
1703 ///
1704 /// # Examples
1705 ///
1706 /// ```
1707 /// use std::collections::BTreeMap;
1708 ///
1709 /// let mut a = BTreeMap::new();
1710 /// a.insert(1, "hello");
1711 /// a.insert(2, "goodbye");
1712 ///
1713 /// let values: Vec<&str> = a.into_values().collect();
1714 /// assert_eq!(values, ["hello", "goodbye"]);
1715 /// ```
1716 #[inline]
1717 #[stable(feature = "map_into_keys_values", since = "1.54.0")]
1718 pub fn into_values(self) -> IntoValues<K, V, A> {
1719 IntoValues { inner: self.into_iter() }
1720 }
1721
1722 /// Makes a `BTreeMap` from a sorted iterator.
1723 pub(crate) fn bulk_build_from_sorted_iter<I>(iter: I, alloc: A) -> Self
1724 where
1725 K: Ord,
1726 I: IntoIterator<Item = (K, V)>,
1727 {
1728 let mut root = Root::new(alloc.clone());
1729 let mut length = 0;
1730 root.bulk_push(DedupSortedIter::new(iter.into_iter()), &mut length, alloc.clone());
1731 BTreeMap { root: Some(root), length, alloc: ManuallyDrop::new(alloc), _marker: PhantomData }
1732 }
1733}
1734
1735#[stable(feature = "rust1", since = "1.0.0")]
1736impl<'a, K, V, A: AllocatorClone> IntoIterator for &'a BTreeMap<K, V, A> {
1737 type Item = (&'a K, &'a V);
1738 type IntoIter = Iter<'a, K, V>;
1739
1740 fn into_iter(self) -> Iter<'a, K, V> {
1741 self.iter()
1742 }
1743}
1744
1745#[stable(feature = "rust1", since = "1.0.0")]
1746impl<'a, K: 'a, V: 'a> Iterator for Iter<'a, K, V> {
1747 type Item = (&'a K, &'a V);
1748
1749 fn next(&mut self) -> Option<(&'a K, &'a V)> {
1750 if self.length == 0 {
1751 None
1752 } else {
1753 self.length -= 1;
1754 // SAFETY: Ensured by check.
1755 Some(unsafe { self.range.next_unchecked() })
1756 }
1757 }
1758
1759 fn size_hint(&self) -> (usize, Option<usize>) {
1760 (self.length, Some(self.length))
1761 }
1762
1763 fn last(mut self) -> Option<(&'a K, &'a V)> {
1764 self.next_back()
1765 }
1766
1767 fn min(mut self) -> Option<(&'a K, &'a V)>
1768 where
1769 (&'a K, &'a V): Ord,
1770 {
1771 self.next()
1772 }
1773
1774 fn max(mut self) -> Option<(&'a K, &'a V)>
1775 where
1776 (&'a K, &'a V): Ord,
1777 {
1778 self.next_back()
1779 }
1780}
1781
1782#[stable(feature = "fused", since = "1.26.0")]
1783impl<K, V> FusedIterator for Iter<'_, K, V> {}
1784
1785#[stable(feature = "rust1", since = "1.0.0")]
1786impl<'a, K: 'a, V: 'a> DoubleEndedIterator for Iter<'a, K, V> {
1787 fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
1788 if self.length == 0 {
1789 None
1790 } else {
1791 self.length -= 1;
1792 // SAFETY: Ensured by check.
1793 Some(unsafe { self.range.next_back_unchecked() })
1794 }
1795 }
1796}
1797
1798#[stable(feature = "rust1", since = "1.0.0")]
1799impl<K, V> ExactSizeIterator for Iter<'_, K, V> {
1800 fn len(&self) -> usize {
1801 self.length
1802 }
1803}
1804
1805#[unstable(feature = "trusted_len", issue = "37572")]
1806unsafe impl<K, V> TrustedLen for Iter<'_, K, V> {}
1807
1808#[stable(feature = "rust1", since = "1.0.0")]
1809impl<K, V> Clone for Iter<'_, K, V> {
1810 fn clone(&self) -> Self {
1811 Iter { range: self.range.clone(), length: self.length }
1812 }
1813}
1814
1815#[stable(feature = "rust1", since = "1.0.0")]
1816impl<'a, K, V, A: AllocatorClone> IntoIterator for &'a mut BTreeMap<K, V, A> {
1817 type Item = (&'a K, &'a mut V);
1818 type IntoIter = IterMut<'a, K, V>;
1819
1820 fn into_iter(self) -> IterMut<'a, K, V> {
1821 self.iter_mut()
1822 }
1823}
1824
1825#[stable(feature = "rust1", since = "1.0.0")]
1826impl<'a, K, V> Iterator for IterMut<'a, K, V> {
1827 type Item = (&'a K, &'a mut V);
1828
1829 fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
1830 if self.length == 0 {
1831 None
1832 } else {
1833 self.length -= 1;
1834 // SAFETY: Ensured by check.
1835 Some(unsafe { self.range.next_unchecked() })
1836 }
1837 }
1838
1839 fn size_hint(&self) -> (usize, Option<usize>) {
1840 (self.length, Some(self.length))
1841 }
1842
1843 fn last(mut self) -> Option<(&'a K, &'a mut V)> {
1844 self.next_back()
1845 }
1846
1847 fn min(mut self) -> Option<(&'a K, &'a mut V)>
1848 where
1849 (&'a K, &'a mut V): Ord,
1850 {
1851 self.next()
1852 }
1853
1854 fn max(mut self) -> Option<(&'a K, &'a mut V)>
1855 where
1856 (&'a K, &'a mut V): Ord,
1857 {
1858 self.next_back()
1859 }
1860}
1861
1862#[stable(feature = "rust1", since = "1.0.0")]
1863impl<'a, K, V> DoubleEndedIterator for IterMut<'a, K, V> {
1864 fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
1865 if self.length == 0 {
1866 None
1867 } else {
1868 self.length -= 1;
1869 // SAFETY: Ensured by check.
1870 Some(unsafe { self.range.next_back_unchecked() })
1871 }
1872 }
1873}
1874
1875#[stable(feature = "rust1", since = "1.0.0")]
1876impl<K, V> ExactSizeIterator for IterMut<'_, K, V> {
1877 fn len(&self) -> usize {
1878 self.length
1879 }
1880}
1881
1882#[unstable(feature = "trusted_len", issue = "37572")]
1883unsafe impl<K, V> TrustedLen for IterMut<'_, K, V> {}
1884
1885#[stable(feature = "fused", since = "1.26.0")]
1886impl<K, V> FusedIterator for IterMut<'_, K, V> {}
1887
1888impl<'a, K, V> IterMut<'a, K, V> {
1889 /// Returns an iterator of references over the remaining items.
1890 #[inline]
1891 pub(super) fn iter(&self) -> Iter<'_, K, V> {
1892 Iter { range: self.range.reborrow(), length: self.length }
1893 }
1894}
1895
1896#[stable(feature = "rust1", since = "1.0.0")]
1897impl<K, V, A: AllocatorClone> IntoIterator for BTreeMap<K, V, A> {
1898 type Item = (K, V);
1899 type IntoIter = IntoIter<K, V, A>;
1900
1901 /// Gets an owning iterator over the entries of the map, sorted by key.
1902 fn into_iter(self) -> IntoIter<K, V, A> {
1903 let mut me = ManuallyDrop::new(self);
1904 if let Some(root) = me.root.take() {
1905 let full_range = root.into_dying().full_range();
1906
1907 IntoIter {
1908 range: full_range,
1909 length: me.length,
1910 // ignore-tidy-undocumented-unsafe
1911 alloc: unsafe { ManuallyDrop::take(&mut me.alloc) },
1912 }
1913 } else {
1914 IntoIter {
1915 range: LazyLeafRange::none(),
1916 length: 0,
1917 // ignore-tidy-undocumented-unsafe
1918 alloc: unsafe { ManuallyDrop::take(&mut me.alloc) },
1919 }
1920 }
1921 }
1922}
1923
1924#[stable(feature = "btree_drop", since = "1.7.0")]
1925impl<K, V, A: AllocatorClone> Drop for IntoIter<K, V, A> {
1926 fn drop(&mut self) {
1927 struct DropGuard<'a, K, V, A: AllocatorClone>(&'a mut IntoIter<K, V, A>);
1928
1929 impl<'a, K, V, A: AllocatorClone> Drop for DropGuard<'a, K, V, A> {
1930 fn drop(&mut self) {
1931 // Continue the same loop we perform below. This only runs when unwinding, so we
1932 // don't have to care about panics this time (they'll abort).
1933 while let Some(kv) = self.0.dying_next() {
1934 // SAFETY: we consume the dying handle immediately.
1935 unsafe { kv.drop_key_val() };
1936 }
1937 }
1938 }
1939
1940 while let Some(kv) = self.dying_next() {
1941 let guard = DropGuard(self);
1942 // SAFETY: we don't touch the tree before consuming the dying handle.
1943 unsafe { kv.drop_key_val() };
1944 mem::forget(guard);
1945 }
1946 }
1947}
1948
1949impl<K, V, A: AllocatorClone> IntoIter<K, V, A> {
1950 /// Core of a `next` method returning a dying KV handle,
1951 /// invalidated by further calls to this function and some others.
1952 fn dying_next(
1953 &mut self,
1954 ) -> Option<Handle<NodeRef<marker::Dying, K, V, marker::LeafOrInternal>, marker::KV>> {
1955 if self.length == 0 {
1956 self.range.deallocating_end(self.alloc.clone());
1957 None
1958 } else {
1959 self.length -= 1;
1960 // ignore-tidy-undocumented-unsafe
1961 Some(unsafe { self.range.deallocating_next_unchecked(self.alloc.clone()) })
1962 }
1963 }
1964
1965 /// Core of a `next_back` method returning a dying KV handle,
1966 /// invalidated by further calls to this function and some others.
1967 fn dying_next_back(
1968 &mut self,
1969 ) -> Option<Handle<NodeRef<marker::Dying, K, V, marker::LeafOrInternal>, marker::KV>> {
1970 if self.length == 0 {
1971 self.range.deallocating_end(self.alloc.clone());
1972 None
1973 } else {
1974 self.length -= 1;
1975 // ignore-tidy-undocumented-unsafe
1976 Some(unsafe { self.range.deallocating_next_back_unchecked(self.alloc.clone()) })
1977 }
1978 }
1979}
1980
1981#[stable(feature = "rust1", since = "1.0.0")]
1982impl<K, V, A: AllocatorClone> Iterator for IntoIter<K, V, A> {
1983 type Item = (K, V);
1984
1985 fn next(&mut self) -> Option<(K, V)> {
1986 // SAFETY: we consume the dying handle immediately.
1987 self.dying_next().map(unsafe { |kv| kv.into_key_val() })
1988 }
1989
1990 fn size_hint(&self) -> (usize, Option<usize>) {
1991 (self.length, Some(self.length))
1992 }
1993}
1994
1995#[stable(feature = "rust1", since = "1.0.0")]
1996impl<K, V, A: AllocatorClone> DoubleEndedIterator for IntoIter<K, V, A> {
1997 fn next_back(&mut self) -> Option<(K, V)> {
1998 // SAFETY: we consume the dying handle immediately.
1999 self.dying_next_back().map(unsafe { |kv| kv.into_key_val() })
2000 }
2001}
2002
2003#[stable(feature = "rust1", since = "1.0.0")]
2004impl<K, V, A: AllocatorClone> ExactSizeIterator for IntoIter<K, V, A> {
2005 fn len(&self) -> usize {
2006 self.length
2007 }
2008}
2009
2010#[unstable(feature = "trusted_len", issue = "37572")]
2011unsafe impl<K, V, A: AllocatorClone> TrustedLen for IntoIter<K, V, A> {}
2012
2013#[stable(feature = "fused", since = "1.26.0")]
2014impl<K, V, A: AllocatorClone> FusedIterator for IntoIter<K, V, A> {}
2015
2016#[stable(feature = "rust1", since = "1.0.0")]
2017impl<'a, K, V> Iterator for Keys<'a, K, V> {
2018 type Item = &'a K;
2019
2020 fn next(&mut self) -> Option<&'a K> {
2021 self.inner.next().map(|(k, _)| k)
2022 }
2023
2024 fn size_hint(&self) -> (usize, Option<usize>) {
2025 self.inner.size_hint()
2026 }
2027
2028 fn last(mut self) -> Option<&'a K> {
2029 self.next_back()
2030 }
2031
2032 fn min(mut self) -> Option<&'a K>
2033 where
2034 &'a K: Ord,
2035 {
2036 self.next()
2037 }
2038
2039 fn max(mut self) -> Option<&'a K>
2040 where
2041 &'a K: Ord,
2042 {
2043 self.next_back()
2044 }
2045}
2046
2047#[stable(feature = "rust1", since = "1.0.0")]
2048impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> {
2049 fn next_back(&mut self) -> Option<&'a K> {
2050 self.inner.next_back().map(|(k, _)| k)
2051 }
2052}
2053
2054#[stable(feature = "rust1", since = "1.0.0")]
2055impl<K, V> ExactSizeIterator for Keys<'_, K, V> {
2056 fn len(&self) -> usize {
2057 self.inner.len()
2058 }
2059}
2060
2061#[unstable(feature = "trusted_len", issue = "37572")]
2062unsafe impl<K, V> TrustedLen for Keys<'_, K, V> {}
2063
2064#[stable(feature = "fused", since = "1.26.0")]
2065impl<K, V> FusedIterator for Keys<'_, K, V> {}
2066
2067#[stable(feature = "rust1", since = "1.0.0")]
2068impl<K, V> Clone for Keys<'_, K, V> {
2069 fn clone(&self) -> Self {
2070 Keys { inner: self.inner.clone() }
2071 }
2072}
2073
2074#[stable(feature = "default_iters", since = "1.70.0")]
2075impl<K, V> Default for Keys<'_, K, V> {
2076 /// Creates an empty `btree_map::Keys`.
2077 ///
2078 /// ```
2079 /// # use std::collections::btree_map;
2080 /// let iter: btree_map::Keys<'_, u8, u8> = Default::default();
2081 /// assert_eq!(iter.len(), 0);
2082 /// ```
2083 fn default() -> Self {
2084 Keys { inner: Default::default() }
2085 }
2086}
2087
2088#[stable(feature = "rust1", since = "1.0.0")]
2089impl<'a, K, V> Iterator for Values<'a, K, V> {
2090 type Item = &'a V;
2091
2092 fn next(&mut self) -> Option<&'a V> {
2093 self.inner.next().map(|(_, v)| v)
2094 }
2095
2096 fn size_hint(&self) -> (usize, Option<usize>) {
2097 self.inner.size_hint()
2098 }
2099
2100 fn last(mut self) -> Option<&'a V> {
2101 self.next_back()
2102 }
2103}
2104
2105#[stable(feature = "rust1", since = "1.0.0")]
2106impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> {
2107 fn next_back(&mut self) -> Option<&'a V> {
2108 self.inner.next_back().map(|(_, v)| v)
2109 }
2110}
2111
2112#[stable(feature = "rust1", since = "1.0.0")]
2113impl<K, V> ExactSizeIterator for Values<'_, K, V> {
2114 fn len(&self) -> usize {
2115 self.inner.len()
2116 }
2117}
2118
2119#[unstable(feature = "trusted_len", issue = "37572")]
2120unsafe impl<K, V> TrustedLen for Values<'_, K, V> {}
2121
2122#[stable(feature = "fused", since = "1.26.0")]
2123impl<K, V> FusedIterator for Values<'_, K, V> {}
2124
2125#[stable(feature = "rust1", since = "1.0.0")]
2126impl<K, V> Clone for Values<'_, K, V> {
2127 fn clone(&self) -> Self {
2128 Values { inner: self.inner.clone() }
2129 }
2130}
2131
2132#[stable(feature = "default_iters", since = "1.70.0")]
2133impl<K, V> Default for Values<'_, K, V> {
2134 /// Creates an empty `btree_map::Values`.
2135 ///
2136 /// ```
2137 /// # use std::collections::btree_map;
2138 /// let iter: btree_map::Values<'_, u8, u8> = Default::default();
2139 /// assert_eq!(iter.len(), 0);
2140 /// ```
2141 fn default() -> Self {
2142 Values { inner: Default::default() }
2143 }
2144}
2145
2146/// This `struct` is created by the [`extract_if`] method on [`BTreeMap`].
2147///
2148/// [`extract_if`]: BTreeMap::extract_if
2149#[stable(feature = "btree_extract_if", since = "1.91.0")]
2150#[must_use = "iterators are lazy and do nothing unless consumed; \
2151 use `retain` or `extract_if().for_each(drop)` to remove and discard elements"]
2152pub struct ExtractIf<
2153 'a,
2154 K,
2155 V,
2156 R,
2157 F,
2158 #[unstable(feature = "allocator_ext", issue = "163177", implied_by = "allocator_api")] A: AllocatorClone = Global,
2159> {
2160 pred: F,
2161 inner: ExtractIfInner<'a, K, V, R>,
2162 /// The BTreeMap will outlive this IntoIter so we don't care about drop order for `alloc`.
2163 alloc: A,
2164}
2165
2166/// Most of the implementation of ExtractIf are generic over the type
2167/// of the predicate, thus also serving for BTreeSet::ExtractIf.
2168pub(super) struct ExtractIfInner<'a, K, V, R> {
2169 /// Reference to the length field in the borrowed map, updated live.
2170 length: &'a mut usize,
2171 /// Buried reference to the root field in the borrowed map.
2172 /// Wrapped in `Option` to allow drop handler to `take` it.
2173 dormant_root: Option<DormantMutRef<'a, Root<K, V>>>,
2174 /// Contains a leaf edge preceding the next element to be returned, or the last leaf edge.
2175 /// Empty if the map has no root, if iteration went beyond the last leaf edge,
2176 /// or if a panic occurred in the predicate.
2177 cur_leaf_edge: Option<Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>>,
2178 /// Range over which iteration was requested. We don't need the left side, but we
2179 /// can't extract the right side without requiring K: Clone.
2180 range: R,
2181}
2182
2183#[stable(feature = "btree_extract_if", since = "1.91.0")]
2184impl<K, V, R, F, A> fmt::Debug for ExtractIf<'_, K, V, R, F, A>
2185where
2186 K: fmt::Debug,
2187 V: fmt::Debug,
2188 A: AllocatorClone,
2189{
2190 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2191 f.debug_struct("ExtractIf").field("peek", &self.inner.peek()).finish_non_exhaustive()
2192 }
2193}
2194
2195#[stable(feature = "btree_extract_if", since = "1.91.0")]
2196impl<K, V, R, F, A: AllocatorClone> Iterator for ExtractIf<'_, K, V, R, F, A>
2197where
2198 K: PartialOrd,
2199 R: RangeBounds<K>,
2200 F: FnMut(&K, &mut V) -> bool,
2201{
2202 type Item = (K, V);
2203
2204 fn next(&mut self) -> Option<(K, V)> {
2205 self.inner.next(&mut self.pred, self.alloc.clone())
2206 }
2207
2208 fn size_hint(&self) -> (usize, Option<usize>) {
2209 self.inner.size_hint()
2210 }
2211}
2212
2213impl<'a, K, V, R> ExtractIfInner<'a, K, V, R> {
2214 /// Allow Debug implementations to predict the next element.
2215 pub(super) fn peek(&self) -> Option<(&K, &V)> {
2216 let edge = self.cur_leaf_edge.as_ref()?;
2217 edge.reborrow().next_kv().ok().map(Handle::into_kv)
2218 }
2219
2220 /// Implementation of a typical `ExtractIf::next` method, given the predicate.
2221 pub(super) fn next<F, A: AllocatorClone>(&mut self, pred: &mut F, alloc: A) -> Option<(K, V)>
2222 where
2223 K: PartialOrd,
2224 R: RangeBounds<K>,
2225 F: FnMut(&K, &mut V) -> bool,
2226 {
2227 while let Ok(mut kv) = self.cur_leaf_edge.take()?.next_kv() {
2228 let (k, v) = kv.kv_mut();
2229
2230 // On creation, we navigated directly to the left bound, so we need only check the
2231 // right bound here to decide whether to stop.
2232 match self.range.end_bound() {
2233 Bound::Included(end) if (*k).le(end) => (),
2234 Bound::Excluded(end) if (*k).lt(end) => (),
2235 Bound::Unbounded => (),
2236 _ => return None,
2237 }
2238
2239 if pred(k, v) {
2240 *self.length -= 1;
2241 let (kv, pos) = kv.remove_kv_tracking(
2242 || {
2243 // SAFETY: we will touch the root in a way that will not
2244 // invalidate the position returned.
2245 let root = unsafe { self.dormant_root.take().unwrap().awaken() };
2246 root.pop_internal_level(alloc.clone());
2247 self.dormant_root = Some(DormantMutRef::new(root).1);
2248 },
2249 alloc.clone(),
2250 );
2251 self.cur_leaf_edge = Some(pos);
2252 return Some(kv);
2253 }
2254 self.cur_leaf_edge = Some(kv.next_leaf_edge());
2255 }
2256 None
2257 }
2258
2259 /// Implementation of a typical `ExtractIf::size_hint` method.
2260 pub(super) fn size_hint(&self) -> (usize, Option<usize>) {
2261 // In most of the btree iterators, `self.length` is the number of elements
2262 // yet to be visited. Here, it includes elements that were visited and that
2263 // the predicate decided not to drain. Making this upper bound more tight
2264 // during iteration would require an extra field.
2265 (0, Some(*self.length))
2266 }
2267}
2268
2269#[stable(feature = "btree_extract_if", since = "1.91.0")]
2270impl<K, V, R, F> FusedIterator for ExtractIf<'_, K, V, R, F>
2271where
2272 K: PartialOrd,
2273 R: RangeBounds<K>,
2274 F: FnMut(&K, &mut V) -> bool,
2275{
2276}
2277
2278#[stable(feature = "btree_range", since = "1.17.0")]
2279impl<'a, K, V> Iterator for Range<'a, K, V> {
2280 type Item = (&'a K, &'a V);
2281
2282 fn next(&mut self) -> Option<(&'a K, &'a V)> {
2283 self.inner.next_checked()
2284 }
2285
2286 fn last(mut self) -> Option<(&'a K, &'a V)> {
2287 self.next_back()
2288 }
2289
2290 fn min(mut self) -> Option<(&'a K, &'a V)>
2291 where
2292 (&'a K, &'a V): Ord,
2293 {
2294 self.next()
2295 }
2296
2297 fn max(mut self) -> Option<(&'a K, &'a V)>
2298 where
2299 (&'a K, &'a V): Ord,
2300 {
2301 self.next_back()
2302 }
2303}
2304
2305#[stable(feature = "default_iters", since = "1.70.0")]
2306impl<K, V> Default for Range<'_, K, V> {
2307 /// Creates an empty `btree_map::Range`.
2308 ///
2309 /// ```
2310 /// # use std::collections::btree_map;
2311 /// let iter: btree_map::Range<'_, u8, u8> = Default::default();
2312 /// assert_eq!(iter.count(), 0);
2313 /// ```
2314 fn default() -> Self {
2315 Range { inner: Default::default() }
2316 }
2317}
2318
2319#[stable(feature = "default_iters_sequel", since = "1.82.0")]
2320impl<K, V> Default for RangeMut<'_, K, V> {
2321 /// Creates an empty `btree_map::RangeMut`.
2322 ///
2323 /// ```
2324 /// # use std::collections::btree_map;
2325 /// let iter: btree_map::RangeMut<'_, u8, u8> = Default::default();
2326 /// assert_eq!(iter.count(), 0);
2327 /// ```
2328 fn default() -> Self {
2329 RangeMut { inner: Default::default(), _marker: PhantomData }
2330 }
2331}
2332
2333#[stable(feature = "map_values_mut", since = "1.10.0")]
2334impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
2335 type Item = &'a mut V;
2336
2337 fn next(&mut self) -> Option<&'a mut V> {
2338 self.inner.next().map(|(_, v)| v)
2339 }
2340
2341 fn size_hint(&self) -> (usize, Option<usize>) {
2342 self.inner.size_hint()
2343 }
2344
2345 fn last(mut self) -> Option<&'a mut V> {
2346 self.next_back()
2347 }
2348}
2349
2350#[stable(feature = "map_values_mut", since = "1.10.0")]
2351impl<'a, K, V> DoubleEndedIterator for ValuesMut<'a, K, V> {
2352 fn next_back(&mut self) -> Option<&'a mut V> {
2353 self.inner.next_back().map(|(_, v)| v)
2354 }
2355}
2356
2357#[stable(feature = "map_values_mut", since = "1.10.0")]
2358impl<K, V> ExactSizeIterator for ValuesMut<'_, K, V> {
2359 fn len(&self) -> usize {
2360 self.inner.len()
2361 }
2362}
2363
2364#[unstable(feature = "trusted_len", issue = "37572")]
2365unsafe impl<K, V> TrustedLen for ValuesMut<'_, K, V> {}
2366
2367#[stable(feature = "fused", since = "1.26.0")]
2368impl<K, V> FusedIterator for ValuesMut<'_, K, V> {}
2369
2370#[stable(feature = "default_iters_sequel", since = "1.82.0")]
2371impl<K, V> Default for ValuesMut<'_, K, V> {
2372 /// Creates an empty `btree_map::ValuesMut`.
2373 ///
2374 /// ```
2375 /// # use std::collections::btree_map;
2376 /// let iter: btree_map::ValuesMut<'_, u8, u8> = Default::default();
2377 /// assert_eq!(iter.count(), 0);
2378 /// ```
2379 fn default() -> Self {
2380 ValuesMut { inner: Default::default() }
2381 }
2382}
2383
2384#[stable(feature = "map_into_keys_values", since = "1.54.0")]
2385impl<K, V, A: AllocatorClone> Iterator for IntoKeys<K, V, A> {
2386 type Item = K;
2387
2388 fn next(&mut self) -> Option<K> {
2389 self.inner.next().map(|(k, _)| k)
2390 }
2391
2392 fn size_hint(&self) -> (usize, Option<usize>) {
2393 self.inner.size_hint()
2394 }
2395
2396 fn last(mut self) -> Option<K> {
2397 self.next_back()
2398 }
2399
2400 fn min(mut self) -> Option<K>
2401 where
2402 K: Ord,
2403 {
2404 self.next()
2405 }
2406
2407 fn max(mut self) -> Option<K>
2408 where
2409 K: Ord,
2410 {
2411 self.next_back()
2412 }
2413}
2414
2415#[stable(feature = "map_into_keys_values", since = "1.54.0")]
2416impl<K, V, A: AllocatorClone> DoubleEndedIterator for IntoKeys<K, V, A> {
2417 fn next_back(&mut self) -> Option<K> {
2418 self.inner.next_back().map(|(k, _)| k)
2419 }
2420}
2421
2422#[stable(feature = "map_into_keys_values", since = "1.54.0")]
2423impl<K, V, A: AllocatorClone> ExactSizeIterator for IntoKeys<K, V, A> {
2424 fn len(&self) -> usize {
2425 self.inner.len()
2426 }
2427}
2428
2429#[unstable(feature = "trusted_len", issue = "37572")]
2430unsafe impl<K, V, A: AllocatorClone> TrustedLen for IntoKeys<K, V, A> {}
2431
2432#[stable(feature = "map_into_keys_values", since = "1.54.0")]
2433impl<K, V, A: AllocatorClone> FusedIterator for IntoKeys<K, V, A> {}
2434
2435#[stable(feature = "default_iters", since = "1.70.0")]
2436impl<K, V, A> Default for IntoKeys<K, V, A>
2437where
2438 A: AllocatorClone + Default,
2439{
2440 /// Creates an empty `btree_map::IntoKeys`.
2441 ///
2442 /// ```
2443 /// # use std::collections::btree_map;
2444 /// let iter: btree_map::IntoKeys<u8, u8> = Default::default();
2445 /// assert_eq!(iter.len(), 0);
2446 /// ```
2447 fn default() -> Self {
2448 IntoKeys { inner: Default::default() }
2449 }
2450}
2451
2452#[stable(feature = "map_into_keys_values", since = "1.54.0")]
2453impl<K, V, A: AllocatorClone> Iterator for IntoValues<K, V, A> {
2454 type Item = V;
2455
2456 fn next(&mut self) -> Option<V> {
2457 self.inner.next().map(|(_, v)| v)
2458 }
2459
2460 fn size_hint(&self) -> (usize, Option<usize>) {
2461 self.inner.size_hint()
2462 }
2463
2464 fn last(mut self) -> Option<V> {
2465 self.next_back()
2466 }
2467}
2468
2469#[stable(feature = "map_into_keys_values", since = "1.54.0")]
2470impl<K, V, A: AllocatorClone> DoubleEndedIterator for IntoValues<K, V, A> {
2471 fn next_back(&mut self) -> Option<V> {
2472 self.inner.next_back().map(|(_, v)| v)
2473 }
2474}
2475
2476#[stable(feature = "map_into_keys_values", since = "1.54.0")]
2477impl<K, V, A: AllocatorClone> ExactSizeIterator for IntoValues<K, V, A> {
2478 fn len(&self) -> usize {
2479 self.inner.len()
2480 }
2481}
2482
2483#[unstable(feature = "trusted_len", issue = "37572")]
2484unsafe impl<K, V, A: AllocatorClone> TrustedLen for IntoValues<K, V, A> {}
2485
2486#[stable(feature = "map_into_keys_values", since = "1.54.0")]
2487impl<K, V, A: AllocatorClone> FusedIterator for IntoValues<K, V, A> {}
2488
2489#[stable(feature = "default_iters", since = "1.70.0")]
2490impl<K, V, A> Default for IntoValues<K, V, A>
2491where
2492 A: AllocatorClone + Default,
2493{
2494 /// Creates an empty `btree_map::IntoValues`.
2495 ///
2496 /// ```
2497 /// # use std::collections::btree_map;
2498 /// let iter: btree_map::IntoValues<u8, u8> = Default::default();
2499 /// assert_eq!(iter.len(), 0);
2500 /// ```
2501 fn default() -> Self {
2502 IntoValues { inner: Default::default() }
2503 }
2504}
2505
2506#[stable(feature = "btree_range", since = "1.17.0")]
2507impl<'a, K, V> DoubleEndedIterator for Range<'a, K, V> {
2508 fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
2509 self.inner.next_back_checked()
2510 }
2511}
2512
2513#[stable(feature = "fused", since = "1.26.0")]
2514impl<K, V> FusedIterator for Range<'_, K, V> {}
2515
2516#[stable(feature = "btree_range", since = "1.17.0")]
2517impl<K, V> Clone for Range<'_, K, V> {
2518 fn clone(&self) -> Self {
2519 Range { inner: self.inner.clone() }
2520 }
2521}
2522
2523#[stable(feature = "btree_range", since = "1.17.0")]
2524impl<'a, K, V> Iterator for RangeMut<'a, K, V> {
2525 type Item = (&'a K, &'a mut V);
2526
2527 fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
2528 self.inner.next_checked()
2529 }
2530
2531 fn last(mut self) -> Option<(&'a K, &'a mut V)> {
2532 self.next_back()
2533 }
2534
2535 fn min(mut self) -> Option<(&'a K, &'a mut V)>
2536 where
2537 (&'a K, &'a mut V): Ord,
2538 {
2539 self.next()
2540 }
2541
2542 fn max(mut self) -> Option<(&'a K, &'a mut V)>
2543 where
2544 (&'a K, &'a mut V): Ord,
2545 {
2546 self.next_back()
2547 }
2548}
2549
2550#[stable(feature = "btree_range", since = "1.17.0")]
2551impl<'a, K, V> DoubleEndedIterator for RangeMut<'a, K, V> {
2552 fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
2553 self.inner.next_back_checked()
2554 }
2555}
2556
2557#[stable(feature = "fused", since = "1.26.0")]
2558impl<K, V> FusedIterator for RangeMut<'_, K, V> {}
2559
2560#[stable(feature = "rust1", since = "1.0.0")]
2561impl<K: Ord, V> FromIterator<(K, V)> for BTreeMap<K, V> {
2562 /// Constructs a `BTreeMap<K, V>` from an iterator of key-value pairs.
2563 ///
2564 /// If the iterator produces any pairs with equal keys,
2565 /// all but one of the corresponding values will be dropped.
2566 fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> BTreeMap<K, V> {
2567 let mut inputs: Vec<_> = iter.into_iter().collect();
2568
2569 if inputs.is_empty() {
2570 return BTreeMap::new();
2571 }
2572
2573 // use stable sort to preserve the insertion order.
2574 inputs.sort_by(|a, b| a.0.cmp(&b.0));
2575 BTreeMap::bulk_build_from_sorted_iter(inputs, Global)
2576 }
2577}
2578
2579#[stable(feature = "rust1", since = "1.0.0")]
2580impl<K: Ord, V, A: AllocatorClone> Extend<(K, V)> for BTreeMap<K, V, A> {
2581 #[inline]
2582 fn extend<I: IntoIterator<Item = (K, V)>>(&mut self, iter: I) {
2583 iter.into_iter().for_each(move |(k, v)| {
2584 self.insert(k, v);
2585 });
2586 }
2587
2588 #[inline]
2589 fn extend_one(&mut self, (k, v): (K, V)) {
2590 self.insert(k, v);
2591 }
2592}
2593
2594#[stable(feature = "extend_ref", since = "1.2.0")]
2595impl<'a, K: Ord + Copy, V: Copy, A: AllocatorClone> Extend<(&'a K, &'a V)> for BTreeMap<K, V, A> {
2596 fn extend<I: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: I) {
2597 self.extend(iter.into_iter().map(|(&key, &value)| (key, value)));
2598 }
2599
2600 #[inline]
2601 fn extend_one(&mut self, (&k, &v): (&'a K, &'a V)) {
2602 self.insert(k, v);
2603 }
2604}
2605
2606#[stable(feature = "rust1", since = "1.0.0")]
2607impl<K: Hash, V: Hash, A: AllocatorClone> Hash for BTreeMap<K, V, A> {
2608 fn hash<H: Hasher>(&self, state: &mut H) {
2609 state.write_length_prefix(self.len());
2610 for elt in self {
2611 elt.hash(state);
2612 }
2613 }
2614}
2615
2616#[stable(feature = "rust1", since = "1.0.0")]
2617#[rustc_const_unstable(feature = "const_default", issue = "143894")]
2618const impl<K, V> Default for BTreeMap<K, V> {
2619 /// Creates an empty `BTreeMap`.
2620 fn default() -> BTreeMap<K, V> {
2621 BTreeMap::new()
2622 }
2623}
2624
2625#[stable(feature = "rust1", since = "1.0.0")]
2626impl<K: PartialEq, V: PartialEq, A: AllocatorClone> PartialEq for BTreeMap<K, V, A> {
2627 fn eq(&self, other: &BTreeMap<K, V, A>) -> bool {
2628 self.len() == other.len() && self.iter().zip(other).all(|(a, b)| a == b)
2629 }
2630}
2631
2632#[stable(feature = "rust1", since = "1.0.0")]
2633impl<K: Eq, V: Eq, A: AllocatorClone> Eq for BTreeMap<K, V, A> {}
2634
2635#[stable(feature = "rust1", since = "1.0.0")]
2636impl<K: PartialOrd, V: PartialOrd, A: AllocatorClone> PartialOrd for BTreeMap<K, V, A> {
2637 #[inline]
2638 fn partial_cmp(&self, other: &BTreeMap<K, V, A>) -> Option<Ordering> {
2639 self.iter().partial_cmp(other.iter())
2640 }
2641}
2642
2643#[stable(feature = "rust1", since = "1.0.0")]
2644impl<K: Ord, V: Ord, A: AllocatorClone> Ord for BTreeMap<K, V, A> {
2645 #[inline]
2646 fn cmp(&self, other: &BTreeMap<K, V, A>) -> Ordering {
2647 self.iter().cmp(other.iter())
2648 }
2649}
2650
2651#[stable(feature = "rust1", since = "1.0.0")]
2652impl<K: Debug, V: Debug, A: AllocatorClone> Debug for BTreeMap<K, V, A> {
2653 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2654 f.debug_map().entries(self.iter()).finish()
2655 }
2656}
2657
2658#[stable(feature = "rust1", since = "1.0.0")]
2659impl<K, Q: ?Sized, V, A: AllocatorClone> Index<&Q> for BTreeMap<K, V, A>
2660where
2661 K: Borrow<Q> + Ord,
2662 Q: Ord,
2663{
2664 type Output = V;
2665
2666 /// Returns a reference to the value corresponding to the supplied key.
2667 ///
2668 /// # Panics
2669 ///
2670 /// Panics if the key is not present in the `BTreeMap`.
2671 #[inline]
2672 fn index(&self, key: &Q) -> &V {
2673 self.get(key).expect("no entry found for key")
2674 }
2675}
2676
2677#[stable(feature = "std_collections_from_array", since = "1.56.0")]
2678impl<K: Ord, V, const N: usize> From<[(K, V); N]> for BTreeMap<K, V> {
2679 /// Converts a `[(K, V); N]` into a `BTreeMap<K, V>`.
2680 ///
2681 /// If any entries in the array have equal keys,
2682 /// all but one of the corresponding values will be dropped.
2683 ///
2684 /// ```
2685 /// use std::collections::BTreeMap;
2686 ///
2687 /// let map1 = BTreeMap::from([(1, 2), (3, 4)]);
2688 /// let map2: BTreeMap<_, _> = [(1, 2), (3, 4)].into();
2689 /// assert_eq!(map1, map2);
2690 /// ```
2691 fn from(mut arr: [(K, V); N]) -> Self {
2692 if N == 0 {
2693 return BTreeMap::new();
2694 }
2695
2696 // use stable sort to preserve the insertion order.
2697 arr.sort_by(|a, b| a.0.cmp(&b.0));
2698 BTreeMap::bulk_build_from_sorted_iter(arr, Global)
2699 }
2700}
2701
2702impl<K, V, A: AllocatorClone> BTreeMap<K, V, A> {
2703 /// Gets an iterator over the entries of the map, sorted by key.
2704 ///
2705 /// # Examples
2706 ///
2707 /// ```
2708 /// use std::collections::BTreeMap;
2709 ///
2710 /// let mut map = BTreeMap::new();
2711 /// map.insert(3, "c");
2712 /// map.insert(2, "b");
2713 /// map.insert(1, "a");
2714 ///
2715 /// for (key, value) in map.iter() {
2716 /// println!("{key}: {value}");
2717 /// }
2718 ///
2719 /// let (first_key, first_value) = map.iter().next().unwrap();
2720 /// assert_eq!((*first_key, *first_value), (1, "a"));
2721 /// ```
2722 #[stable(feature = "rust1", since = "1.0.0")]
2723 pub fn iter(&self) -> Iter<'_, K, V> {
2724 if let Some(root) = &self.root {
2725 let full_range = root.reborrow().full_range();
2726
2727 Iter { range: full_range, length: self.length }
2728 } else {
2729 Iter { range: LazyLeafRange::none(), length: 0 }
2730 }
2731 }
2732
2733 /// Gets a mutable iterator over the entries of the map, sorted by key.
2734 ///
2735 /// # Examples
2736 ///
2737 /// ```
2738 /// use std::collections::BTreeMap;
2739 ///
2740 /// let mut map = BTreeMap::from([
2741 /// ("a", 1),
2742 /// ("b", 2),
2743 /// ("c", 3),
2744 /// ]);
2745 ///
2746 /// // add 10 to the value if the key isn't "a"
2747 /// for (key, value) in map.iter_mut() {
2748 /// if key != &"a" {
2749 /// *value += 10;
2750 /// }
2751 /// }
2752 /// ```
2753 #[stable(feature = "rust1", since = "1.0.0")]
2754 pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
2755 if let Some(root) = &mut self.root {
2756 let full_range = root.borrow_valmut().full_range();
2757
2758 IterMut { range: full_range, length: self.length, _marker: PhantomData }
2759 } else {
2760 IterMut { range: LazyLeafRange::none(), length: 0, _marker: PhantomData }
2761 }
2762 }
2763
2764 /// Gets an iterator over the keys of the map, in sorted order.
2765 ///
2766 /// # Examples
2767 ///
2768 /// ```
2769 /// use std::collections::BTreeMap;
2770 ///
2771 /// let mut a = BTreeMap::new();
2772 /// a.insert(2, "b");
2773 /// a.insert(1, "a");
2774 ///
2775 /// let keys: Vec<_> = a.keys().cloned().collect();
2776 /// assert_eq!(keys, [1, 2]);
2777 /// ```
2778 #[stable(feature = "rust1", since = "1.0.0")]
2779 pub fn keys(&self) -> Keys<'_, K, V> {
2780 Keys { inner: self.iter() }
2781 }
2782
2783 /// Gets an iterator over the values of the map, in order by key.
2784 ///
2785 /// # Examples
2786 ///
2787 /// ```
2788 /// use std::collections::BTreeMap;
2789 ///
2790 /// let mut a = BTreeMap::new();
2791 /// a.insert(1, "hello");
2792 /// a.insert(2, "goodbye");
2793 ///
2794 /// let values: Vec<&str> = a.values().cloned().collect();
2795 /// assert_eq!(values, ["hello", "goodbye"]);
2796 /// ```
2797 #[stable(feature = "rust1", since = "1.0.0")]
2798 pub fn values(&self) -> Values<'_, K, V> {
2799 Values { inner: self.iter() }
2800 }
2801
2802 /// Gets a mutable iterator over the values of the map, in order by key.
2803 ///
2804 /// # Examples
2805 ///
2806 /// ```
2807 /// use std::collections::BTreeMap;
2808 ///
2809 /// let mut a = BTreeMap::new();
2810 /// a.insert(1, String::from("hello"));
2811 /// a.insert(2, String::from("goodbye"));
2812 ///
2813 /// for value in a.values_mut() {
2814 /// value.push_str("!");
2815 /// }
2816 ///
2817 /// let values: Vec<String> = a.values().cloned().collect();
2818 /// assert_eq!(values, [String::from("hello!"),
2819 /// String::from("goodbye!")]);
2820 /// ```
2821 #[stable(feature = "map_values_mut", since = "1.10.0")]
2822 pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {
2823 ValuesMut { inner: self.iter_mut() }
2824 }
2825
2826 /// Returns the number of elements in the map.
2827 ///
2828 /// # Examples
2829 ///
2830 /// ```
2831 /// use std::collections::BTreeMap;
2832 ///
2833 /// let mut a = BTreeMap::new();
2834 /// assert_eq!(a.len(), 0);
2835 /// a.insert(1, "a");
2836 /// assert_eq!(a.len(), 1);
2837 /// ```
2838 #[must_use]
2839 #[stable(feature = "rust1", since = "1.0.0")]
2840 #[rustc_const_stable(feature = "const_btree_len", since = "CURRENT_RUSTC_VERSION")]
2841 #[rustc_confusables("length", "size")]
2842 pub const fn len(&self) -> usize {
2843 self.length
2844 }
2845
2846 /// Returns `true` if the map contains no elements.
2847 ///
2848 /// # Examples
2849 ///
2850 /// ```
2851 /// use std::collections::BTreeMap;
2852 ///
2853 /// let mut a = BTreeMap::new();
2854 /// assert!(a.is_empty());
2855 /// a.insert(1, "a");
2856 /// assert!(!a.is_empty());
2857 /// ```
2858 #[must_use]
2859 #[stable(feature = "rust1", since = "1.0.0")]
2860 #[rustc_const_stable(feature = "const_btree_len", since = "CURRENT_RUSTC_VERSION")]
2861 pub const fn is_empty(&self) -> bool {
2862 self.len() == 0
2863 }
2864
2865 /// Returns a [`Cursor`] pointing at the gap before the smallest key
2866 /// greater than the given bound.
2867 ///
2868 /// Passing `Bound::Included(x)` will return a cursor pointing to the
2869 /// gap before the smallest key greater than or equal to `x`.
2870 ///
2871 /// Passing `Bound::Excluded(x)` will return a cursor pointing to the
2872 /// gap before the smallest key greater than `x`.
2873 ///
2874 /// Passing `Bound::Unbounded` will return a cursor pointing to the
2875 /// gap before the smallest key in the map.
2876 ///
2877 /// # Examples
2878 ///
2879 /// ```
2880 /// #![feature(btree_cursors)]
2881 ///
2882 /// use std::collections::BTreeMap;
2883 /// use std::ops::Bound;
2884 ///
2885 /// let map = BTreeMap::from([
2886 /// (1, "a"),
2887 /// (2, "b"),
2888 /// (3, "c"),
2889 /// (4, "d"),
2890 /// ]);
2891 ///
2892 /// let cursor = map.lower_bound(Bound::Included(&2));
2893 /// assert_eq!(cursor.peek_prev(), Some((&1, &"a")));
2894 /// assert_eq!(cursor.peek_next(), Some((&2, &"b")));
2895 ///
2896 /// let cursor = map.lower_bound(Bound::Excluded(&2));
2897 /// assert_eq!(cursor.peek_prev(), Some((&2, &"b")));
2898 /// assert_eq!(cursor.peek_next(), Some((&3, &"c")));
2899 ///
2900 /// let cursor = map.lower_bound(Bound::Unbounded);
2901 /// assert_eq!(cursor.peek_prev(), None);
2902 /// assert_eq!(cursor.peek_next(), Some((&1, &"a")));
2903 /// ```
2904 #[unstable(feature = "btree_cursors", issue = "107540")]
2905 pub fn lower_bound<Q: ?Sized>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V>
2906 where
2907 K: Borrow<Q> + Ord,
2908 Q: Ord,
2909 {
2910 let root_node = match self.root.as_ref() {
2911 None => return Cursor { current: None, root: None },
2912 Some(root) => root.reborrow(),
2913 };
2914 let edge = root_node.lower_bound(SearchBound::from_range(bound));
2915 Cursor { current: Some(edge), root: self.root.as_ref() }
2916 }
2917
2918 /// Returns a [`CursorMut`] pointing at the gap before the smallest key
2919 /// greater than the given bound.
2920 ///
2921 /// Passing `Bound::Included(x)` will return a cursor pointing to the
2922 /// gap before the smallest key greater than or equal to `x`.
2923 ///
2924 /// Passing `Bound::Excluded(x)` will return a cursor pointing to the
2925 /// gap before the smallest key greater than `x`.
2926 ///
2927 /// Passing `Bound::Unbounded` will return a cursor pointing to the
2928 /// gap before the smallest key in the map.
2929 ///
2930 /// # Examples
2931 ///
2932 /// ```
2933 /// #![feature(btree_cursors)]
2934 ///
2935 /// use std::collections::BTreeMap;
2936 /// use std::ops::Bound;
2937 ///
2938 /// let mut map = BTreeMap::from([
2939 /// (1, "a"),
2940 /// (2, "b"),
2941 /// (3, "c"),
2942 /// (4, "d"),
2943 /// ]);
2944 ///
2945 /// let mut cursor = map.lower_bound_mut(Bound::Included(&2));
2946 /// assert_eq!(cursor.peek_prev(), Some((&1, &mut "a")));
2947 /// assert_eq!(cursor.peek_next(), Some((&2, &mut "b")));
2948 ///
2949 /// let mut cursor = map.lower_bound_mut(Bound::Excluded(&2));
2950 /// assert_eq!(cursor.peek_prev(), Some((&2, &mut "b")));
2951 /// assert_eq!(cursor.peek_next(), Some((&3, &mut "c")));
2952 ///
2953 /// let mut cursor = map.lower_bound_mut(Bound::Unbounded);
2954 /// assert_eq!(cursor.peek_prev(), None);
2955 /// assert_eq!(cursor.peek_next(), Some((&1, &mut "a")));
2956 /// ```
2957 #[unstable(feature = "btree_cursors", issue = "107540")]
2958 pub fn lower_bound_mut<Q: ?Sized>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V, A>
2959 where
2960 K: Borrow<Q> + Ord,
2961 Q: Ord,
2962 {
2963 let (root, dormant_root) = DormantMutRef::new(&mut self.root);
2964 let root_node = match root.as_mut() {
2965 None => {
2966 return CursorMut {
2967 inner: CursorMutKey {
2968 current: None,
2969 root: dormant_root,
2970 length: &mut self.length,
2971 alloc: &mut *self.alloc,
2972 },
2973 };
2974 }
2975 Some(root) => root.borrow_mut(),
2976 };
2977 let edge = root_node.lower_bound(SearchBound::from_range(bound));
2978 CursorMut {
2979 inner: CursorMutKey {
2980 current: Some(edge),
2981 root: dormant_root,
2982 length: &mut self.length,
2983 alloc: &mut *self.alloc,
2984 },
2985 }
2986 }
2987
2988 /// Returns a [`Cursor`] pointing at the gap after the greatest key
2989 /// smaller than the given bound.
2990 ///
2991 /// Passing `Bound::Included(x)` will return a cursor pointing to the
2992 /// gap after the greatest key smaller than or equal to `x`.
2993 ///
2994 /// Passing `Bound::Excluded(x)` will return a cursor pointing to the
2995 /// gap after the greatest key smaller than `x`.
2996 ///
2997 /// Passing `Bound::Unbounded` will return a cursor pointing to the
2998 /// gap after the greatest key in the map.
2999 ///
3000 /// # Examples
3001 ///
3002 /// ```
3003 /// #![feature(btree_cursors)]
3004 ///
3005 /// use std::collections::BTreeMap;
3006 /// use std::ops::Bound;
3007 ///
3008 /// let map = BTreeMap::from([
3009 /// (1, "a"),
3010 /// (2, "b"),
3011 /// (3, "c"),
3012 /// (4, "d"),
3013 /// ]);
3014 ///
3015 /// let cursor = map.upper_bound(Bound::Included(&3));
3016 /// assert_eq!(cursor.peek_prev(), Some((&3, &"c")));
3017 /// assert_eq!(cursor.peek_next(), Some((&4, &"d")));
3018 ///
3019 /// let cursor = map.upper_bound(Bound::Excluded(&3));
3020 /// assert_eq!(cursor.peek_prev(), Some((&2, &"b")));
3021 /// assert_eq!(cursor.peek_next(), Some((&3, &"c")));
3022 ///
3023 /// let cursor = map.upper_bound(Bound::Unbounded);
3024 /// assert_eq!(cursor.peek_prev(), Some((&4, &"d")));
3025 /// assert_eq!(cursor.peek_next(), None);
3026 /// ```
3027 #[unstable(feature = "btree_cursors", issue = "107540")]
3028 pub fn upper_bound<Q: ?Sized>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V>
3029 where
3030 K: Borrow<Q> + Ord,
3031 Q: Ord,
3032 {
3033 let root_node = match self.root.as_ref() {
3034 None => return Cursor { current: None, root: None },
3035 Some(root) => root.reborrow(),
3036 };
3037 let edge = root_node.upper_bound(SearchBound::from_range(bound));
3038 Cursor { current: Some(edge), root: self.root.as_ref() }
3039 }
3040
3041 /// Returns a [`CursorMut`] pointing at the gap after the greatest key
3042 /// smaller than the given bound.
3043 ///
3044 /// Passing `Bound::Included(x)` will return a cursor pointing to the
3045 /// gap after the greatest key smaller than or equal to `x`.
3046 ///
3047 /// Passing `Bound::Excluded(x)` will return a cursor pointing to the
3048 /// gap after the greatest key smaller than `x`.
3049 ///
3050 /// Passing `Bound::Unbounded` will return a cursor pointing to the
3051 /// gap after the greatest key in the map.
3052 ///
3053 /// # Examples
3054 ///
3055 /// ```
3056 /// #![feature(btree_cursors)]
3057 ///
3058 /// use std::collections::BTreeMap;
3059 /// use std::ops::Bound;
3060 ///
3061 /// let mut map = BTreeMap::from([
3062 /// (1, "a"),
3063 /// (2, "b"),
3064 /// (3, "c"),
3065 /// (4, "d"),
3066 /// ]);
3067 ///
3068 /// let mut cursor = map.upper_bound_mut(Bound::Included(&3));
3069 /// assert_eq!(cursor.peek_prev(), Some((&3, &mut "c")));
3070 /// assert_eq!(cursor.peek_next(), Some((&4, &mut "d")));
3071 ///
3072 /// let mut cursor = map.upper_bound_mut(Bound::Excluded(&3));
3073 /// assert_eq!(cursor.peek_prev(), Some((&2, &mut "b")));
3074 /// assert_eq!(cursor.peek_next(), Some((&3, &mut "c")));
3075 ///
3076 /// let mut cursor = map.upper_bound_mut(Bound::Unbounded);
3077 /// assert_eq!(cursor.peek_prev(), Some((&4, &mut "d")));
3078 /// assert_eq!(cursor.peek_next(), None);
3079 /// ```
3080 #[unstable(feature = "btree_cursors", issue = "107540")]
3081 pub fn upper_bound_mut<Q: ?Sized>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V, A>
3082 where
3083 K: Borrow<Q> + Ord,
3084 Q: Ord,
3085 {
3086 let (root, dormant_root) = DormantMutRef::new(&mut self.root);
3087 let root_node = match root.as_mut() {
3088 None => {
3089 return CursorMut {
3090 inner: CursorMutKey {
3091 current: None,
3092 root: dormant_root,
3093 length: &mut self.length,
3094 alloc: &mut *self.alloc,
3095 },
3096 };
3097 }
3098 Some(root) => root.borrow_mut(),
3099 };
3100 let edge = root_node.upper_bound(SearchBound::from_range(bound));
3101 CursorMut {
3102 inner: CursorMutKey {
3103 current: Some(edge),
3104 root: dormant_root,
3105 length: &mut self.length,
3106 alloc: &mut *self.alloc,
3107 },
3108 }
3109 }
3110}
3111
3112/// A cursor over a `BTreeMap`.
3113///
3114/// A `Cursor` is like an iterator, except that it can freely seek back-and-forth.
3115///
3116/// Cursors always point to a gap between two elements in the map, and can
3117/// operate on the two immediately adjacent elements.
3118///
3119/// A `Cursor` is created with the [`BTreeMap::lower_bound`] and [`BTreeMap::upper_bound`] methods.
3120#[unstable(feature = "btree_cursors", issue = "107540")]
3121pub struct Cursor<'a, K: 'a, V: 'a> {
3122 // If current is None then it means the tree has not been allocated yet.
3123 current: Option<Handle<NodeRef<marker::Immut<'a>, K, V, marker::Leaf>, marker::Edge>>,
3124 root: Option<&'a node::Root<K, V>>,
3125}
3126
3127#[unstable(feature = "btree_cursors", issue = "107540")]
3128impl<K, V> Clone for Cursor<'_, K, V> {
3129 fn clone(&self) -> Self {
3130 let Cursor { current, root } = *self;
3131 Cursor { current, root }
3132 }
3133}
3134
3135#[unstable(feature = "btree_cursors", issue = "107540")]
3136impl<K: Debug, V: Debug> Debug for Cursor<'_, K, V> {
3137 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
3138 f.write_str("Cursor")
3139 }
3140}
3141
3142/// A cursor over a `BTreeMap` with editing operations.
3143///
3144/// A `Cursor` is like an iterator, except that it can freely seek back-and-forth, and can
3145/// safely mutate the map during iteration. This is because the lifetime of its yielded
3146/// references is tied to its own lifetime, instead of just the underlying map. This means
3147/// cursors cannot yield multiple elements at once.
3148///
3149/// Cursors always point to a gap between two elements in the map, and can
3150/// operate on the two immediately adjacent elements.
3151///
3152/// A `CursorMut` is created with the [`BTreeMap::lower_bound_mut`] and [`BTreeMap::upper_bound_mut`]
3153/// methods.
3154#[unstable(feature = "btree_cursors", issue = "107540")]
3155pub struct CursorMut<
3156 'a,
3157 K: 'a,
3158 V: 'a,
3159 #[unstable(feature = "allocator_ext", issue = "163177", implied_by = "allocator_api")] A = Global,
3160> {
3161 inner: CursorMutKey<'a, K, V, A>,
3162}
3163
3164#[unstable(feature = "btree_cursors", issue = "107540")]
3165impl<K: Debug, V: Debug, A> Debug for CursorMut<'_, K, V, A> {
3166 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
3167 f.write_str("CursorMut")
3168 }
3169}
3170
3171/// A cursor over a `BTreeMap` with editing operations, and which allows
3172/// mutating the key of elements.
3173///
3174/// A `Cursor` is like an iterator, except that it can freely seek back-and-forth, and can
3175/// safely mutate the map during iteration. This is because the lifetime of its yielded
3176/// references is tied to its own lifetime, instead of just the underlying map. This means
3177/// cursors cannot yield multiple elements at once.
3178///
3179/// Cursors always point to a gap between two elements in the map, and can
3180/// operate on the two immediately adjacent elements.
3181///
3182/// A `CursorMutKey` is created from a [`CursorMut`] with the
3183/// [`CursorMut::with_mutable_key`] method.
3184///
3185/// # Safety
3186///
3187/// Since this cursor allows mutating keys, you must ensure that the `BTreeMap`
3188/// invariants are maintained. Specifically:
3189///
3190/// * The key of the newly inserted element must be unique in the tree.
3191/// * All keys in the tree must remain in sorted order.
3192#[unstable(feature = "btree_cursors", issue = "107540")]
3193pub struct CursorMutKey<
3194 'a,
3195 K: 'a,
3196 V: 'a,
3197 #[unstable(feature = "allocator_ext", issue = "163177", implied_by = "allocator_api")] A = Global,
3198> {
3199 // If current is None then it means the tree has not been allocated yet.
3200 current: Option<Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>>,
3201 root: DormantMutRef<'a, Option<node::Root<K, V>>>,
3202 length: &'a mut usize,
3203 alloc: &'a mut A,
3204}
3205
3206#[unstable(feature = "btree_cursors", issue = "107540")]
3207impl<K: Debug, V: Debug, A> Debug for CursorMutKey<'_, K, V, A> {
3208 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
3209 f.write_str("CursorMutKey")
3210 }
3211}
3212
3213impl<'a, K, V> Cursor<'a, K, V> {
3214 /// Advances the cursor to the next gap, returning the key and value of the
3215 /// element that it moved over.
3216 ///
3217 /// If the cursor is already at the end of the map then `None` is returned
3218 /// and the cursor is not moved.
3219 #[unstable(feature = "btree_cursors", issue = "107540")]
3220 pub fn next(&mut self) -> Option<(&'a K, &'a V)> {
3221 let current = self.current.take()?;
3222 match current.next_kv() {
3223 Ok(kv) => {
3224 let result = kv.into_kv();
3225 self.current = Some(kv.next_leaf_edge());
3226 Some(result)
3227 }
3228 Err(root) => {
3229 self.current = Some(root.last_leaf_edge());
3230 None
3231 }
3232 }
3233 }
3234
3235 /// Advances the cursor to the previous gap, returning the key and value of
3236 /// the element that it moved over.
3237 ///
3238 /// If the cursor is already at the start of the map then `None` is returned
3239 /// and the cursor is not moved.
3240 #[unstable(feature = "btree_cursors", issue = "107540")]
3241 pub fn prev(&mut self) -> Option<(&'a K, &'a V)> {
3242 let current = self.current.take()?;
3243 match current.next_back_kv() {
3244 Ok(kv) => {
3245 let result = kv.into_kv();
3246 self.current = Some(kv.next_back_leaf_edge());
3247 Some(result)
3248 }
3249 Err(root) => {
3250 self.current = Some(root.first_leaf_edge());
3251 None
3252 }
3253 }
3254 }
3255
3256 /// Returns a reference to the key and value of the next element without
3257 /// moving the cursor.
3258 ///
3259 /// If the cursor is at the end of the map then `None` is returned.
3260 #[unstable(feature = "btree_cursors", issue = "107540")]
3261 pub fn peek_next(&self) -> Option<(&'a K, &'a V)> {
3262 self.clone().next()
3263 }
3264
3265 /// Returns a reference to the key and value of the previous element
3266 /// without moving the cursor.
3267 ///
3268 /// If the cursor is at the start of the map then `None` is returned.
3269 #[unstable(feature = "btree_cursors", issue = "107540")]
3270 pub fn peek_prev(&self) -> Option<(&'a K, &'a V)> {
3271 self.clone().prev()
3272 }
3273}
3274
3275impl<'a, K, V, A> CursorMut<'a, K, V, A> {
3276 /// Advances the cursor to the next gap, returning the key and value of the
3277 /// element that it moved over.
3278 ///
3279 /// If the cursor is already at the end of the map then `None` is returned
3280 /// and the cursor is not moved.
3281 #[unstable(feature = "btree_cursors", issue = "107540")]
3282 pub fn next(&mut self) -> Option<(&K, &mut V)> {
3283 let (k, v) = self.inner.next()?;
3284 Some((&*k, v))
3285 }
3286
3287 /// Advances the cursor to the previous gap, returning the key and value of
3288 /// the element that it moved over.
3289 ///
3290 /// If the cursor is already at the start of the map then `None` is returned
3291 /// and the cursor is not moved.
3292 #[unstable(feature = "btree_cursors", issue = "107540")]
3293 pub fn prev(&mut self) -> Option<(&K, &mut V)> {
3294 let (k, v) = self.inner.prev()?;
3295 Some((&*k, v))
3296 }
3297
3298 /// Returns a reference to the key and value of the next element without
3299 /// moving the cursor.
3300 ///
3301 /// If the cursor is at the end of the map then `None` is returned.
3302 #[unstable(feature = "btree_cursors", issue = "107540")]
3303 pub fn peek_next(&mut self) -> Option<(&K, &mut V)> {
3304 let (k, v) = self.inner.peek_next()?;
3305 Some((&*k, v))
3306 }
3307
3308 /// Returns a reference to the key and value of the previous element
3309 /// without moving the cursor.
3310 ///
3311 /// If the cursor is at the start of the map then `None` is returned.
3312 #[unstable(feature = "btree_cursors", issue = "107540")]
3313 pub fn peek_prev(&mut self) -> Option<(&K, &mut V)> {
3314 let (k, v) = self.inner.peek_prev()?;
3315 Some((&*k, v))
3316 }
3317
3318 /// Returns a read-only cursor pointing to the same location as the
3319 /// `CursorMut`.
3320 ///
3321 /// The lifetime of the returned `Cursor` is bound to that of the
3322 /// `CursorMut`, which means it cannot outlive the `CursorMut` and that the
3323 /// `CursorMut` is frozen for the lifetime of the `Cursor`.
3324 #[unstable(feature = "btree_cursors", issue = "107540")]
3325 pub fn as_cursor(&self) -> Cursor<'_, K, V> {
3326 self.inner.as_cursor()
3327 }
3328
3329 /// Converts the cursor into a [`CursorMutKey`], which allows mutating
3330 /// the key of elements in the tree.
3331 ///
3332 /// # Safety
3333 ///
3334 /// Since this cursor allows mutating keys, you must ensure that the `BTreeMap`
3335 /// invariants are maintained. Specifically:
3336 ///
3337 /// * The key of the newly inserted element must be unique in the tree.
3338 /// * All keys in the tree must remain in sorted order.
3339 #[unstable(feature = "btree_cursors", issue = "107540")]
3340 pub unsafe fn with_mutable_key(self) -> CursorMutKey<'a, K, V, A> {
3341 self.inner
3342 }
3343}
3344
3345impl<'a, K, V, A> CursorMutKey<'a, K, V, A> {
3346 /// Advances the cursor to the next gap, returning the key and value of the
3347 /// element that it moved over.
3348 ///
3349 /// If the cursor is already at the end of the map then `None` is returned
3350 /// and the cursor is not moved.
3351 #[unstable(feature = "btree_cursors", issue = "107540")]
3352 pub fn next(&mut self) -> Option<(&mut K, &mut V)> {
3353 let current = self.current.take()?;
3354 match current.next_kv() {
3355 Ok(mut kv) => {
3356 // SAFETY: The key/value pointers remain valid even after the
3357 // cursor is moved forward. The lifetimes then prevent any
3358 // further access to the cursor.
3359 let (k, v) = unsafe { kv.reborrow_mut().into_kv_mut() };
3360 let (k, v) = (k as *mut _, v as *mut _);
3361 self.current = Some(kv.next_leaf_edge());
3362 // ignore-tidy-undocumented-unsafe
3363 Some(unsafe { (&mut *k, &mut *v) })
3364 }
3365 Err(root) => {
3366 self.current = Some(root.last_leaf_edge());
3367 None
3368 }
3369 }
3370 }
3371
3372 /// Advances the cursor to the previous gap, returning the key and value of
3373 /// the element that it moved over.
3374 ///
3375 /// If the cursor is already at the start of the map then `None` is returned
3376 /// and the cursor is not moved.
3377 #[unstable(feature = "btree_cursors", issue = "107540")]
3378 pub fn prev(&mut self) -> Option<(&mut K, &mut V)> {
3379 let current = self.current.take()?;
3380 match current.next_back_kv() {
3381 Ok(mut kv) => {
3382 // SAFETY: The key/value pointers remain valid even after the
3383 // cursor is moved forward. The lifetimes then prevent any
3384 // further access to the cursor.
3385 let (k, v) = unsafe { kv.reborrow_mut().into_kv_mut() };
3386 let (k, v) = (k as *mut _, v as *mut _);
3387 self.current = Some(kv.next_back_leaf_edge());
3388 // ignore-tidy-undocumented-unsafe
3389 Some(unsafe { (&mut *k, &mut *v) })
3390 }
3391 Err(root) => {
3392 self.current = Some(root.first_leaf_edge());
3393 None
3394 }
3395 }
3396 }
3397
3398 /// Returns a reference to the key and value of the next element without
3399 /// moving the cursor.
3400 ///
3401 /// If the cursor is at the end of the map then `None` is returned.
3402 #[unstable(feature = "btree_cursors", issue = "107540")]
3403 pub fn peek_next(&mut self) -> Option<(&mut K, &mut V)> {
3404 let current = self.current.as_mut()?;
3405 // SAFETY: We're not using this to mutate the tree.
3406 let kv = unsafe { current.reborrow_mut() }.next_kv().ok()?.into_kv_mut();
3407 Some(kv)
3408 }
3409
3410 /// Returns a reference to the key and value of the previous element
3411 /// without moving the cursor.
3412 ///
3413 /// If the cursor is at the start of the map then `None` is returned.
3414 #[unstable(feature = "btree_cursors", issue = "107540")]
3415 pub fn peek_prev(&mut self) -> Option<(&mut K, &mut V)> {
3416 let current = self.current.as_mut()?;
3417 // SAFETY: We're not using this to mutate the tree.
3418 let kv = unsafe { current.reborrow_mut() }.next_back_kv().ok()?.into_kv_mut();
3419 Some(kv)
3420 }
3421
3422 /// Returns a read-only cursor pointing to the same location as the
3423 /// `CursorMutKey`.
3424 ///
3425 /// The lifetime of the returned `Cursor` is bound to that of the
3426 /// `CursorMutKey`, which means it cannot outlive the `CursorMutKey` and that the
3427 /// `CursorMutKey` is frozen for the lifetime of the `Cursor`.
3428 #[unstable(feature = "btree_cursors", issue = "107540")]
3429 pub fn as_cursor(&self) -> Cursor<'_, K, V> {
3430 Cursor {
3431 // SAFETY: The tree is immutable while the cursor exists.
3432 root: unsafe { self.root.reborrow_shared().as_ref() },
3433 current: self.current.as_ref().map(|current| current.reborrow()),
3434 }
3435 }
3436}
3437
3438// Now the tree editing operations
3439impl<'a, K: Ord, V, A: AllocatorClone> CursorMutKey<'a, K, V, A> {
3440 /// Inserts a new key-value pair into the map in the gap that the
3441 /// cursor is currently pointing to.
3442 ///
3443 /// After the insertion the cursor will be pointing at the gap before the
3444 /// newly inserted element.
3445 ///
3446 /// # Safety
3447 ///
3448 /// You must ensure that the `BTreeMap` invariants are maintained.
3449 /// Specifically:
3450 ///
3451 /// * The key of the newly inserted element must be unique in the tree.
3452 /// * All keys in the tree must remain in sorted order.
3453 #[unstable(feature = "btree_cursors", issue = "107540")]
3454 pub unsafe fn insert_after_unchecked(&mut self, key: K, value: V) {
3455 let edge = match self.current.take() {
3456 None => {
3457 // Tree is empty, allocate a new root.
3458 // SAFETY: We have no other reference to the tree.
3459 let root = unsafe { self.root.reborrow() };
3460 debug_assert!(root.is_none());
3461 let mut node = NodeRef::new_leaf(self.alloc.clone());
3462 // SAFETY: We don't touch the root while the handle is alive.
3463 let handle = unsafe { node.borrow_mut().push_with_handle(key, value) };
3464 *root = Some(node.forget_type());
3465 *self.length += 1;
3466 self.current = Some(handle.left_edge());
3467 return;
3468 }
3469 Some(current) => current,
3470 };
3471
3472 let handle = edge.insert_recursing(key, value, self.alloc.clone(), |ins| {
3473 drop(ins.left);
3474 // SAFETY: The handle to the newly inserted value is always on a
3475 // leaf node, so adding a new root node doesn't invalidate it.
3476 let root = unsafe { self.root.reborrow().as_mut().unwrap() };
3477 root.push_internal_level(self.alloc.clone()).push(ins.kv.0, ins.kv.1, ins.right)
3478 });
3479 self.current = Some(handle.left_edge());
3480 *self.length += 1;
3481 }
3482
3483 /// Inserts a new key-value pair into the map in the gap that the
3484 /// cursor is currently pointing to.
3485 ///
3486 /// After the insertion the cursor will be pointing at the gap after the
3487 /// newly inserted element.
3488 ///
3489 /// # Safety
3490 ///
3491 /// You must ensure that the `BTreeMap` invariants are maintained.
3492 /// Specifically:
3493 ///
3494 /// * The key of the newly inserted element must be unique in the tree.
3495 /// * All keys in the tree must remain in sorted order.
3496 #[unstable(feature = "btree_cursors", issue = "107540")]
3497 pub unsafe fn insert_before_unchecked(&mut self, key: K, value: V) {
3498 let edge = match self.current.take() {
3499 None => {
3500 // SAFETY: We have no other reference to the tree.
3501 match unsafe { self.root.reborrow() } {
3502 root @ None => {
3503 // Tree is empty, allocate a new root.
3504 let mut node = NodeRef::new_leaf(self.alloc.clone());
3505 // SAFETY: We don't touch the root while the handle is alive.
3506 let handle = unsafe { node.borrow_mut().push_with_handle(key, value) };
3507 *root = Some(node.forget_type());
3508 *self.length += 1;
3509 self.current = Some(handle.right_edge());
3510 return;
3511 }
3512 Some(root) => root.borrow_mut().last_leaf_edge(),
3513 }
3514 }
3515 Some(current) => current,
3516 };
3517
3518 let handle = edge.insert_recursing(key, value, self.alloc.clone(), |ins| {
3519 drop(ins.left);
3520 // SAFETY: The handle to the newly inserted value is always on a
3521 // leaf node, so adding a new root node doesn't invalidate it.
3522 let root = unsafe { self.root.reborrow().as_mut().unwrap() };
3523 root.push_internal_level(self.alloc.clone()).push(ins.kv.0, ins.kv.1, ins.right)
3524 });
3525 self.current = Some(handle.right_edge());
3526 *self.length += 1;
3527 }
3528
3529 /// Inserts a new key-value pair into the map in the gap that the
3530 /// cursor is currently pointing to.
3531 ///
3532 /// After the insertion the cursor will be pointing at the gap before the
3533 /// newly inserted element.
3534 ///
3535 /// If the inserted key is not greater than the key before the cursor
3536 /// (if any), or if it not less than the key after the cursor (if any),
3537 /// then an [`UnorderedKeyError`] is returned since this would
3538 /// invalidate the [`Ord`] invariant between the keys of the map.
3539 #[unstable(feature = "btree_cursors", issue = "107540")]
3540 pub fn insert_after(&mut self, key: K, value: V) -> Result<(), UnorderedKeyError> {
3541 if let Some((prev, _)) = self.peek_prev() {
3542 if &key <= prev {
3543 return Err(UnorderedKeyError {});
3544 }
3545 }
3546 if let Some((next, _)) = self.peek_next() {
3547 if &key >= next {
3548 return Err(UnorderedKeyError {});
3549 }
3550 }
3551 // SAFETY: Ensured by checks above.
3552 unsafe {
3553 self.insert_after_unchecked(key, value);
3554 }
3555 Ok(())
3556 }
3557
3558 /// Inserts a new key-value pair into the map in the gap that the
3559 /// cursor is currently pointing to.
3560 ///
3561 /// After the insertion the cursor will be pointing at the gap after the
3562 /// newly inserted element.
3563 ///
3564 /// If the inserted key is not greater than the key before the cursor
3565 /// (if any), or if it not less than the key after the cursor (if any),
3566 /// then an [`UnorderedKeyError`] is returned since this would
3567 /// invalidate the [`Ord`] invariant between the keys of the map.
3568 #[unstable(feature = "btree_cursors", issue = "107540")]
3569 pub fn insert_before(&mut self, key: K, value: V) -> Result<(), UnorderedKeyError> {
3570 if let Some((prev, _)) = self.peek_prev() {
3571 if &key <= prev {
3572 return Err(UnorderedKeyError {});
3573 }
3574 }
3575 if let Some((next, _)) = self.peek_next() {
3576 if &key >= next {
3577 return Err(UnorderedKeyError {});
3578 }
3579 }
3580 // SAFETY: Ensured by checks above.
3581 unsafe {
3582 self.insert_before_unchecked(key, value);
3583 }
3584 Ok(())
3585 }
3586
3587 /// Removes the next element from the `BTreeMap`.
3588 ///
3589 /// The element that was removed is returned. The cursor position is
3590 /// unchanged (before the removed element).
3591 #[unstable(feature = "btree_cursors", issue = "107540")]
3592 pub fn remove_next(&mut self) -> Option<(K, V)> {
3593 let current = self.current.take()?;
3594 if current.reborrow().next_kv().is_err() {
3595 self.current = Some(current);
3596 return None;
3597 }
3598 let mut emptied_internal_root = false;
3599 let (kv, pos) = current
3600 .next_kv()
3601 // This should be unwrap(), but that doesn't work because NodeRef
3602 // doesn't implement Debug. The condition is checked above.
3603 .ok()?
3604 .remove_kv_tracking(|| emptied_internal_root = true, self.alloc.clone());
3605 self.current = Some(pos);
3606 *self.length -= 1;
3607 if emptied_internal_root {
3608 // SAFETY: This is safe since current does not point within the now
3609 // empty root node.
3610 let root = unsafe { self.root.reborrow().as_mut().unwrap() };
3611 root.pop_internal_level(self.alloc.clone());
3612 }
3613 Some(kv)
3614 }
3615
3616 /// Removes the preceding element from the `BTreeMap`.
3617 ///
3618 /// The element that was removed is returned. The cursor position is
3619 /// unchanged (after the removed element).
3620 #[unstable(feature = "btree_cursors", issue = "107540")]
3621 pub fn remove_prev(&mut self) -> Option<(K, V)> {
3622 let current = self.current.take()?;
3623 if current.reborrow().next_back_kv().is_err() {
3624 self.current = Some(current);
3625 return None;
3626 }
3627 let mut emptied_internal_root = false;
3628 let (kv, pos) = current
3629 .next_back_kv()
3630 // This should be unwrap(), but that doesn't work because NodeRef
3631 // doesn't implement Debug. The condition is checked above.
3632 .ok()?
3633 .remove_kv_tracking(|| emptied_internal_root = true, self.alloc.clone());
3634 self.current = Some(pos);
3635 *self.length -= 1;
3636 if emptied_internal_root {
3637 // SAFETY: This is safe since current does not point within the now
3638 // empty root node.
3639 let root = unsafe { self.root.reborrow().as_mut().unwrap() };
3640 root.pop_internal_level(self.alloc.clone());
3641 }
3642 Some(kv)
3643 }
3644}
3645
3646impl<'a, K: Ord, V, A: AllocatorClone> CursorMut<'a, K, V, A> {
3647 /// Inserts a new key-value pair into the map in the gap that the
3648 /// cursor is currently pointing to.
3649 ///
3650 /// After the insertion the cursor will be pointing at the gap after the
3651 /// newly inserted element.
3652 ///
3653 /// # Safety
3654 ///
3655 /// You must ensure that the `BTreeMap` invariants are maintained.
3656 /// Specifically:
3657 ///
3658 /// * The key of the newly inserted element must be unique in the tree.
3659 /// * All keys in the tree must remain in sorted order.
3660 #[unstable(feature = "btree_cursors", issue = "107540")]
3661 pub unsafe fn insert_after_unchecked(&mut self, key: K, value: V) {
3662 // SAFETY: Upheld by caller.
3663 unsafe { self.inner.insert_after_unchecked(key, value) }
3664 }
3665
3666 /// Inserts a new key-value pair into the map in the gap that the
3667 /// cursor is currently pointing to.
3668 ///
3669 /// After the insertion the cursor will be pointing at the gap after the
3670 /// newly inserted element.
3671 ///
3672 /// # Safety
3673 ///
3674 /// You must ensure that the `BTreeMap` invariants are maintained.
3675 /// Specifically:
3676 ///
3677 /// * The key of the newly inserted element must be unique in the tree.
3678 /// * All keys in the tree must remain in sorted order.
3679 #[unstable(feature = "btree_cursors", issue = "107540")]
3680 pub unsafe fn insert_before_unchecked(&mut self, key: K, value: V) {
3681 // SAFETY: Upheld by caller.
3682 unsafe { self.inner.insert_before_unchecked(key, value) }
3683 }
3684
3685 /// Inserts a new key-value pair into the map in the gap that the
3686 /// cursor is currently pointing to.
3687 ///
3688 /// After the insertion the cursor will be pointing at the gap before the
3689 /// newly inserted element.
3690 ///
3691 /// If the inserted key is not greater than the key before the cursor
3692 /// (if any), or if it not less than the key after the cursor (if any),
3693 /// then an [`UnorderedKeyError`] is returned since this would
3694 /// invalidate the [`Ord`] invariant between the keys of the map.
3695 #[unstable(feature = "btree_cursors", issue = "107540")]
3696 pub fn insert_after(&mut self, key: K, value: V) -> Result<(), UnorderedKeyError> {
3697 self.inner.insert_after(key, value)
3698 }
3699
3700 /// Inserts a new key-value pair into the map in the gap that the
3701 /// cursor is currently pointing to.
3702 ///
3703 /// After the insertion the cursor will be pointing at the gap after the
3704 /// newly inserted element.
3705 ///
3706 /// If the inserted key is not greater than the key before the cursor
3707 /// (if any), or if it not less than the key after the cursor (if any),
3708 /// then an [`UnorderedKeyError`] is returned since this would
3709 /// invalidate the [`Ord`] invariant between the keys of the map.
3710 #[unstable(feature = "btree_cursors", issue = "107540")]
3711 pub fn insert_before(&mut self, key: K, value: V) -> Result<(), UnorderedKeyError> {
3712 self.inner.insert_before(key, value)
3713 }
3714
3715 /// Removes the next element from the `BTreeMap`.
3716 ///
3717 /// The element that was removed is returned. The cursor position is
3718 /// unchanged (before the removed element).
3719 #[unstable(feature = "btree_cursors", issue = "107540")]
3720 pub fn remove_next(&mut self) -> Option<(K, V)> {
3721 self.inner.remove_next()
3722 }
3723
3724 /// Removes the preceding element from the `BTreeMap`.
3725 ///
3726 /// The element that was removed is returned. The cursor position is
3727 /// unchanged (after the removed element).
3728 #[unstable(feature = "btree_cursors", issue = "107540")]
3729 pub fn remove_prev(&mut self) -> Option<(K, V)> {
3730 self.inner.remove_prev()
3731 }
3732}
3733
3734/// Error type returned by [`CursorMut::insert_before`] and
3735/// [`CursorMut::insert_after`] if the key being inserted is not properly
3736/// ordered with regards to adjacent keys.
3737#[derive(Clone, PartialEq, Eq, Debug)]
3738#[unstable(feature = "btree_cursors", issue = "107540")]
3739pub struct UnorderedKeyError {}
3740
3741#[unstable(feature = "btree_cursors", issue = "107540")]
3742impl fmt::Display for UnorderedKeyError {
3743 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
3744 write!(f, "key is not properly ordered relative to neighbors")
3745 }
3746}
3747
3748#[unstable(feature = "btree_cursors", issue = "107540")]
3749impl Error for UnorderedKeyError {}
3750
3751#[cfg(test)]
3752mod tests;