Skip to main content

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;