library/alloc/src/collections/btree/map.rs

   1 use crate::vec::Vec;
   2 use core::borrow::Borrow;
   3 use core::cmp::Ordering;
   4 use core::fmt::{self, Debug};
   5 use core::hash::{Hash, Hasher};
   6 use core::iter::{FromIterator, FusedIterator};
   7 use core::marker::PhantomData;
   8 use core::mem::{self, ManuallyDrop};
   9 use core::ops::{Index, RangeBounds};
  10 use core::ptr;
  11
  12 use super::borrow::DormantMutRef;
  13 use super::dedup_sorted_iter::DedupSortedIter;
  14 use super::navigate::{LazyLeafRange, LeafRange};
  15 use super::node::{self, marker, ForceResult::*, Handle, NodeRef, Root};
  16 use super::search::SearchResult::*;
  17
  18 mod entry;
  19
  20 #[stable(feature = "rust1", since = "1.0.0")]
  21 pub use entry::{Entry, OccupiedEntry, OccupiedError, VacantEntry};
  22
  23 use Entry::*;
  24
  25 /// Minimum number of elements in a node that is not a root.
  26 /// We might temporarily have fewer elements during methods.
  27 pub(super) const MIN_LEN: usize = node::MIN_LEN_AFTER_SPLIT;
  28
  29 // A tree in a `BTreeMap` is a tree in the `node` module with additional invariants:
  30 // - Keys must appear in ascending order (according to the key's type).
  31 // - Every non-leaf node contains at least 1 element (has at least 2 children).
  32 // - Every non-root node contains at least MIN_LEN elements.
  33 //
  34 // An empty map is represented either by the absence of a root node or by a
  35 // root node that is an empty leaf.
  36
  37 /// An ordered map based on a [B-Tree].
  38 ///
  39 /// B-Trees represent a fundamental compromise between cache-efficiency and actually minimizing
  40 /// the amount of work performed in a search. In theory, a binary search tree (BST) is the optimal
  41 /// choice for a sorted map, as a perfectly balanced BST performs the theoretical minimum amount of
  42 /// comparisons necessary to find an element (log<sub>2</sub>n). However, in practice the way this
  43 /// is done is *very* inefficient for modern computer architectures. In particular, every element
  44 /// is stored in its own individually heap-allocated node. This means that every single insertion
  45 /// triggers a heap-allocation, and every single comparison should be a cache-miss. Since these
  46 /// are both notably expensive things to do in practice, we are forced to at very least reconsider
  47 /// the BST strategy.
  48 ///
  49 /// A B-Tree instead makes each node contain B-1 to 2B-1 elements in a contiguous array. By doing
  50 /// this, we reduce the number of allocations by a factor of B, and improve cache efficiency in
  51 /// searches. However, this does mean that searches will have to do *more* comparisons on average.
  52 /// The precise number of comparisons depends on the node search strategy used. For optimal cache
  53 /// efficiency, one could search the nodes linearly. For optimal comparisons, one could search
  54 /// the node using binary search. As a compromise, one could also perform a linear search
  55 /// that initially only checks every i<sup>th</sup> element for some choice of i.
  56 ///
  57 /// Currently, our implementation simply performs naive linear search. This provides excellent
  58 /// performance on *small* nodes of elements which are cheap to compare. However in the future we
  59 /// would like to further explore choosing the optimal search strategy based on the choice of B,
  60 /// and possibly other factors. Using linear search, searching for a random element is expected
  61 /// to take B * log(n) comparisons, which is generally worse than a BST. In practice,
  62 /// however, performance is excellent.
  63 ///
  64 /// It is a logic error for a key to be modified in such a way that the key's ordering relative to
  65 /// any other key, as determined by the [`Ord`] trait, changes while it is in the map. This is
  66 /// normally only possible through [`Cell`], [`RefCell`], global state, I/O, or unsafe code.
  67 /// The behavior resulting from such a logic error is not specified (it could include panics,
  68 /// incorrect results, aborts, memory leaks, or non-termination) but will not be undefined
  69 /// behavior.
  70 ///
  71 /// Iterators obtained from functions such as [`BTreeMap::iter`], [`BTreeMap::values`], or
  72 /// [`BTreeMap::keys`] produce their items in order by key, and take worst-case logarithmic and
  73 /// amortized constant time per item returned.
  74 ///
  75 /// [B-Tree]: https://en.wikipedia.org/wiki/B-tree
  76 /// [`Cell`]: core::cell::Cell
  77 /// [`RefCell`]: core::cell::RefCell
  78 ///
  79 /// # Examples
  80 ///
  81 /// ```
  82 /// use std::collections::BTreeMap;
  83 ///
  84 /// // type inference lets us omit an explicit type signature (which
  85 /// // would be `BTreeMap<&str, &str>` in this example).
  86 /// let mut movie_reviews = BTreeMap::new();
  87 ///
  88 /// // review some movies.
  89 /// movie_reviews.insert("Office Space",       "Deals with real issues in the workplace.");
  90 /// movie_reviews.insert("Pulp Fiction",       "Masterpiece.");
  91 /// movie_reviews.insert("The Godfather",      "Very enjoyable.");
  92 /// movie_reviews.insert("The Blues Brothers", "Eye lyked it a lot.");
  93 ///
  94 /// // check for a specific one.
  95 /// if !movie_reviews.contains_key("Les Misérables") {
  96 ///     println!("We've got {} reviews, but Les Misérables ain't one.",
  97 ///              movie_reviews.len());
  98 /// }
  99 ///
 100 /// // oops, this review has a lot of spelling mistakes, let's delete it.
 101 /// movie_reviews.remove("The Blues Brothers");
 102 ///
 103 /// // look up the values associated with some keys.
 104 /// let to_find = ["Up!", "Office Space"];
 105 /// for movie in &to_find {
 106 ///     match movie_reviews.get(movie) {
 107 ///        Some(review) => println!("{}: {}", movie, review),
 108 ///        None => println!("{} is unreviewed.", movie)
 109 ///     }
 110 /// }
 111 ///
 112 /// // Look up the value for a key (will panic if the key is not found).
 113 /// println!("Movie review: {}", movie_reviews["Office Space"]);
 114 ///
 115 /// // iterate over everything.
 116 /// for (movie, review) in &movie_reviews {
 117 ///     println!("{}: \"{}\"", movie, review);
 118 /// }
 119 /// ```
 120 ///
 121 /// A `BTreeMap` with a known list of items can be initialized from an array:
 122 ///
 123 /// ```
 124 /// use std::collections::BTreeMap;
 125 ///
 126 /// let solar_distance = BTreeMap::from([
 127 ///     ("Mercury", 0.4),
 128 ///     ("Venus", 0.7),
 129 ///     ("Earth", 1.0),
 130 ///     ("Mars", 1.5),
 131 /// ]);
 132 /// ```
 133 ///
 134 /// `BTreeMap` implements an [`Entry API`], which allows for complex
 135 /// methods of getting, setting, updating and removing keys and their values:
 136 ///
 137 /// [`Entry API`]: BTreeMap::entry
 138 ///
 139 /// ```
 140 /// use std::collections::BTreeMap;
 141 ///
 142 /// // type inference lets us omit an explicit type signature (which
 143 /// // would be `BTreeMap<&str, u8>` in this example).
 144 /// let mut player_stats = BTreeMap::new();
 145 ///
 146 /// fn random_stat_buff() -> u8 {
 147 ///     // could actually return some random value here - let's just return
 148 ///     // some fixed value for now
 149 ///     42
 150 /// }
 151 ///
 152 /// // insert a key only if it doesn't already exist
 153 /// player_stats.entry("health").or_insert(100);
 154 ///
 155 /// // insert a key using a function that provides a new value only if it
 156 /// // doesn't already exist
 157 /// player_stats.entry("defence").or_insert_with(random_stat_buff);
 158 ///
 159 /// // update a key, guarding against the key possibly not being set
 160 /// let stat = player_stats.entry("attack").or_insert(100);
 161 /// *stat += random_stat_buff();
 162 /// ```
 163 #[stable(feature = "rust1", since = "1.0.0")]
 164 #[cfg_attr(not(test), rustc_diagnostic_item = "BTreeMap")]
 165 #[rustc_insignificant_dtor]
 166 pub struct BTreeMap<K, V> {
 167     root: Option<Root<K, V>>,
 168     length: usize,
 169 }
 170
 171 #[stable(feature = "btree_drop", since = "1.7.0")]
 172 unsafe impl<#[may_dangle] K, #[may_dangle] V> Drop for BTreeMap<K, V> {
 173     fn drop(&mut self) {
 174         drop(unsafe { ptr::read(self) }.into_iter())
 175     }
 176 }
 177
 178 #[stable(feature = "rust1", since = "1.0.0")]
 179 impl<K: Clone, V: Clone> Clone for BTreeMap<K, V> {
 180     fn clone(&self) -> BTreeMap<K, V> {
 181         fn clone_subtree<'a, K: Clone, V: Clone>(
 182             node: NodeRef<marker::Immut<'a>, K, V, marker::LeafOrInternal>,
 183         ) -> BTreeMap<K, V>
 184         where
 185             K: 'a,
 186             V: 'a,
 187         {
 188             match node.force() {
 189                 Leaf(leaf) => {
 190                     let mut out_tree = BTreeMap { root: Some(Root::new()), length: 0 };
 191
 192                     {
 193                         let root = out_tree.root.as_mut().unwrap(); // unwrap succeeds because we just wrapped
 194                         let mut out_node = match root.borrow_mut().force() {
 195                             Leaf(leaf) => leaf,
 196                             Internal(_) => unreachable!(),
 197                         };
 198
 199                         let mut in_edge = leaf.first_edge();
 200                         while let Ok(kv) = in_edge.right_kv() {
 201                             let (k, v) = kv.into_kv();
 202                             in_edge = kv.right_edge();
 203
 204                             out_node.push(k.clone(), v.clone());
 205                             out_tree.length += 1;
 206                         }
 207                     }
 208
 209                     out_tree
 210                 }
 211                 Internal(internal) => {
 212                     let mut out_tree = clone_subtree(internal.first_edge().descend());
 213
 214                     {
 215                         let out_root = BTreeMap::ensure_is_owned(&mut out_tree.root);
 216                         let mut out_node = out_root.push_internal_level();
 217                         let mut in_edge = internal.first_edge();
 218                         while let Ok(kv) = in_edge.right_kv() {
 219                             let (k, v) = kv.into_kv();
 220                             in_edge = kv.right_edge();
 221
 222                             let k = (*k).clone();
 223                             let v = (*v).clone();
 224                             let subtree = clone_subtree(in_edge.descend());
 225
 226                             // We can't destructure subtree directly
 227                             // because BTreeMap implements Drop
 228                             let (subroot, sublength) = unsafe {
 229                                 let subtree = ManuallyDrop::new(subtree);
 230                                 let root = ptr::read(&subtree.root);
 231                                 let length = subtree.length;
 232                                 (root, length)
 233                             };
 234
 235                             out_node.push(k, v, subroot.unwrap_or_else(Root::new));
 236                             out_tree.length += 1 + sublength;
 237                         }
 238                     }
 239
 240                     out_tree
 241                 }
 242             }
 243         }
 244
 245         if self.is_empty() {
 246             BTreeMap::new()
 247         } else {
 248             clone_subtree(self.root.as_ref().unwrap().reborrow()) // unwrap succeeds because not empty
 249         }
 250     }
 251 }
 252
 253 impl<K, Q: ?Sized> super::Recover<Q> for BTreeMap<K, ()>
 254 where
 255     K: Borrow<Q> + Ord,
 256     Q: Ord,
 257 {
 258     type Key = K;
 259
 260     fn get(&self, key: &Q) -> Option<&K> {
 261         let root_node = self.root.as_ref()?.reborrow();
 262         match root_node.search_tree(key) {
 263             Found(handle) => Some(handle.into_kv().0),
 264             GoDown(_) => None,
 265         }
 266     }
 267
 268     fn take(&mut self, key: &Q) -> Option<K> {
 269         let (map, dormant_map) = DormantMutRef::new(self);
 270         let root_node = map.root.as_mut()?.borrow_mut();
 271         match root_node.search_tree(key) {
 272             Found(handle) => {
 273                 Some(OccupiedEntry { handle, dormant_map, _marker: PhantomData }.remove_kv().0)
 274             }
 275             GoDown(_) => None,
 276         }
 277     }
 278
 279     fn replace(&mut self, key: K) -> Option<K> {
 280         let (map, dormant_map) = DormantMutRef::new(self);
 281         let root_node = Self::ensure_is_owned(&mut map.root).borrow_mut();
 282         match root_node.search_tree::<K>(&key) {
 283             Found(mut kv) => Some(mem::replace(kv.key_mut(), key)),
 284             GoDown(handle) => {
 285                 VacantEntry { key, handle, dormant_map, _marker: PhantomData }.insert(());
 286                 None
 287             }
 288         }
 289     }
 290 }
 291
 292 /// An iterator over the entries of a `BTreeMap`.
 293 ///
 294 /// This `struct` is created by the [`iter`] method on [`BTreeMap`]. See its
 295 /// documentation for more.
 296 ///
 297 /// [`iter`]: BTreeMap::iter
 298 #[must_use = "iterators are lazy and do nothing unless consumed"]
 299 #[stable(feature = "rust1", since = "1.0.0")]
 300 pub struct Iter<'a, K: 'a, V: 'a> {
 301     range: LazyLeafRange<marker::Immut<'a>, K, V>,
 302     length: usize,
 303 }
 304
 305 #[stable(feature = "collection_debug", since = "1.17.0")]
 306 impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Iter<'_, K, V> {
 307     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 308         f.debug_list().entries(self.clone()).finish()
 309     }
 310 }
 311
 312 /// A mutable iterator over the entries of a `BTreeMap`.
 313 ///
 314 /// This `struct` is created by the [`iter_mut`] method on [`BTreeMap`]. See its
 315 /// documentation for more.
 316 ///
 317 /// [`iter_mut`]: BTreeMap::iter_mut
 318 #[stable(feature = "rust1", since = "1.0.0")]
 319 pub struct IterMut<'a, K: 'a, V: 'a> {
 320     range: LazyLeafRange<marker::ValMut<'a>, K, V>,
 321     length: usize,
 322
 323     // Be invariant in `K` and `V`
 324     _marker: PhantomData<&'a mut (K, V)>,
 325 }
 326
 327 #[must_use = "iterators are lazy and do nothing unless consumed"]
 328 #[stable(feature = "collection_debug", since = "1.17.0")]
 329 impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IterMut<'_, K, V> {
 330     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 331         let range = Iter { range: self.range.reborrow(), length: self.length };
 332         f.debug_list().entries(range).finish()
 333     }
 334 }
 335
 336 /// An owning iterator over the entries of a `BTreeMap`.
 337 ///
 338 /// This `struct` is created by the [`into_iter`] method on [`BTreeMap`]
 339 /// (provided by the [`IntoIterator`] trait). See its documentation for more.
 340 ///
 341 /// [`into_iter`]: IntoIterator::into_iter
 342 /// [`IntoIterator`]: core::iter::IntoIterator
 343 #[stable(feature = "rust1", since = "1.0.0")]
 344 #[rustc_insignificant_dtor]
 345 pub struct IntoIter<K, V> {
 346     range: LazyLeafRange<marker::Dying, K, V>,
 347     length: usize,
 348 }
 349
 350 impl<K, V> IntoIter<K, V> {
 351     /// Returns an iterator of references over the remaining items.
 352     #[inline]
 353     pub(super) fn iter(&self) -> Iter<'_, K, V> {
 354         Iter { range: self.range.reborrow(), length: self.length }
 355     }
 356 }
 357
 358 #[stable(feature = "collection_debug", since = "1.17.0")]
 359 impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IntoIter<K, V> {
 360     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 361         f.debug_list().entries(self.iter()).finish()
 362     }
 363 }
 364
 365 /// An iterator over the keys of a `BTreeMap`.
 366 ///
 367 /// This `struct` is created by the [`keys`] method on [`BTreeMap`]. See its
 368 /// documentation for more.
 369 ///
 370 /// [`keys`]: BTreeMap::keys
 371 #[must_use = "iterators are lazy and do nothing unless consumed"]
 372 #[stable(feature = "rust1", since = "1.0.0")]
 373 pub struct Keys<'a, K: 'a, V: 'a> {
 374     inner: Iter<'a, K, V>,
 375 }
 376
 377 #[stable(feature = "collection_debug", since = "1.17.0")]
 378 impl<K: fmt::Debug, V> fmt::Debug for Keys<'_, K, V> {
 379     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 380         f.debug_list().entries(self.clone()).finish()
 381     }
 382 }
 383
 384 /// An iterator over the values of a `BTreeMap`.
 385 ///
 386 /// This `struct` is created by the [`values`] method on [`BTreeMap`]. See its
 387 /// documentation for more.
 388 ///
 389 /// [`values`]: BTreeMap::values
 390 #[must_use = "iterators are lazy and do nothing unless consumed"]
 391 #[stable(feature = "rust1", since = "1.0.0")]
 392 pub struct Values<'a, K: 'a, V: 'a> {
 393     inner: Iter<'a, K, V>,
 394 }
 395
 396 #[stable(feature = "collection_debug", since = "1.17.0")]
 397 impl<K, V: fmt::Debug> fmt::Debug for Values<'_, K, V> {
 398     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 399         f.debug_list().entries(self.clone()).finish()
 400     }
 401 }
 402
 403 /// A mutable iterator over the values of a `BTreeMap`.
 404 ///
 405 /// This `struct` is created by the [`values_mut`] method on [`BTreeMap`]. See its
 406 /// documentation for more.
 407 ///
 408 /// [`values_mut`]: BTreeMap::values_mut
 409 #[must_use = "iterators are lazy and do nothing unless consumed"]
 410 #[stable(feature = "map_values_mut", since = "1.10.0")]
 411 pub struct ValuesMut<'a, K: 'a, V: 'a> {
 412     inner: IterMut<'a, K, V>,
 413 }
 414
 415 #[stable(feature = "map_values_mut", since = "1.10.0")]
 416 impl<K, V: fmt::Debug> fmt::Debug for ValuesMut<'_, K, V> {
 417     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 418         f.debug_list().entries(self.inner.iter().map(|(_, val)| val)).finish()
 419     }
 420 }
 421
 422 /// An owning iterator over the keys of a `BTreeMap`.
 423 ///
 424 /// This `struct` is created by the [`into_keys`] method on [`BTreeMap`].
 425 /// See its documentation for more.
 426 ///
 427 /// [`into_keys`]: BTreeMap::into_keys
 428 #[must_use = "iterators are lazy and do nothing unless consumed"]
 429 #[stable(feature = "map_into_keys_values", since = "1.54.0")]
 430 pub struct IntoKeys<K, V> {
 431     inner: IntoIter<K, V>,
 432 }
 433
 434 #[stable(feature = "map_into_keys_values", since = "1.54.0")]
 435 impl<K: fmt::Debug, V> fmt::Debug for IntoKeys<K, V> {
 436     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 437         f.debug_list().entries(self.inner.iter().map(|(key, _)| key)).finish()
 438     }
 439 }
 440
 441 /// An owning iterator over the values of a `BTreeMap`.
 442 ///
 443 /// This `struct` is created by the [`into_values`] method on [`BTreeMap`].
 444 /// See its documentation for more.
 445 ///
 446 /// [`into_values`]: BTreeMap::into_values
 447 #[must_use = "iterators are lazy and do nothing unless consumed"]
 448 #[stable(feature = "map_into_keys_values", since = "1.54.0")]
 449 pub struct IntoValues<K, V> {
 450     inner: IntoIter<K, V>,
 451 }
 452
 453 #[stable(feature = "map_into_keys_values", since = "1.54.0")]
 454 impl<K, V: fmt::Debug> fmt::Debug for IntoValues<K, V> {
 455     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 456         f.debug_list().entries(self.inner.iter().map(|(_, val)| val)).finish()
 457     }
 458 }
 459
 460 /// An iterator over a sub-range of entries in a `BTreeMap`.
 461 ///
 462 /// This `struct` is created by the [`range`] method on [`BTreeMap`]. See its
 463 /// documentation for more.
 464 ///
 465 /// [`range`]: BTreeMap::range
 466 #[must_use = "iterators are lazy and do nothing unless consumed"]
 467 #[stable(feature = "btree_range", since = "1.17.0")]
 468 pub struct Range<'a, K: 'a, V: 'a> {
 469     inner: LeafRange<marker::Immut<'a>, K, V>,
 470 }
 471
 472 #[stable(feature = "collection_debug", since = "1.17.0")]
 473 impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Range<'_, K, V> {
 474     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 475         f.debug_list().entries(self.clone()).finish()
 476     }
 477 }
 478
 479 /// A mutable iterator over a sub-range of entries in a `BTreeMap`.
 480 ///
 481 /// This `struct` is created by the [`range_mut`] method on [`BTreeMap`]. See its
 482 /// documentation for more.
 483 ///
 484 /// [`range_mut`]: BTreeMap::range_mut
 485 #[must_use = "iterators are lazy and do nothing unless consumed"]
 486 #[stable(feature = "btree_range", since = "1.17.0")]
 487 pub struct RangeMut<'a, K: 'a, V: 'a> {
 488     inner: LeafRange<marker::ValMut<'a>, K, V>,
 489
 490     // Be invariant in `K` and `V`
 491     _marker: PhantomData<&'a mut (K, V)>,
 492 }
 493
 494 #[stable(feature = "collection_debug", since = "1.17.0")]
 495 impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for RangeMut<'_, K, V> {
 496     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 497         let range = Range { inner: self.inner.reborrow() };
 498         f.debug_list().entries(range).finish()
 499     }
 500 }
 501
 502 impl<K, V> BTreeMap<K, V> {
 503     /// Makes a new, empty `BTreeMap`.
 504     ///
 505     /// Does not allocate anything on its own.
 506     ///
 507     /// # Examples
 508     ///
 509     /// Basic usage:
 510     ///
 511     /// ```
 512     /// use std::collections::BTreeMap;
 513     ///
 514     /// let mut map = BTreeMap::new();
 515     ///
 516     /// // entries can now be inserted into the empty map
 517     /// map.insert(1, "a");
 518     /// ```
 519     #[stable(feature = "rust1", since = "1.0.0")]
 520     #[rustc_const_unstable(feature = "const_btree_new", issue = "71835")]
 521     #[must_use]
 522     pub const fn new() -> BTreeMap<K, V> {
 523         BTreeMap { root: None, length: 0 }
 524     }
 525
 526     /// Clears the map, removing all elements.
 527     ///
 528     /// # Examples
 529     ///
 530     /// Basic usage:
 531     ///
 532     /// ```
 533     /// use std::collections::BTreeMap;
 534     ///
 535     /// let mut a = BTreeMap::new();
 536     /// a.insert(1, "a");
 537     /// a.clear();
 538     /// assert!(a.is_empty());
 539     /// ```
 540     #[stable(feature = "rust1", since = "1.0.0")]
 541     pub fn clear(&mut self) {
 542         *self = BTreeMap::new();
 543     }
 544
 545     /// Returns a reference to the value corresponding to the key.
 546     ///
 547     /// The key may be any borrowed form of the map's key type, but the ordering
 548     /// on the borrowed form *must* match the ordering on the key type.
 549     ///
 550     /// # Examples
 551     ///
 552     /// Basic usage:
 553     ///
 554     /// ```
 555     /// use std::collections::BTreeMap;
 556     ///
 557     /// let mut map = BTreeMap::new();
 558     /// map.insert(1, "a");
 559     /// assert_eq!(map.get(&1), Some(&"a"));
 560     /// assert_eq!(map.get(&2), None);
 561     /// ```
 562     #[stable(feature = "rust1", since = "1.0.0")]
 563     pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V>
 564     where
 565         K: Borrow<Q> + Ord,
 566         Q: Ord,
 567     {
 568         let root_node = self.root.as_ref()?.reborrow();
 569         match root_node.search_tree(key) {
 570             Found(handle) => Some(handle.into_kv().1),
 571             GoDown(_) => None,
 572         }
 573     }
 574
 575     /// Returns the key-value pair corresponding to the supplied key.
 576     ///
 577     /// The supplied key may be any borrowed form of the map's key type, but the ordering
 578     /// on the borrowed form *must* match the ordering on the key type.
 579     ///
 580     /// # Examples
 581     ///
 582     /// ```
 583     /// use std::collections::BTreeMap;
 584     ///
 585     /// let mut map = BTreeMap::new();
 586     /// map.insert(1, "a");
 587     /// assert_eq!(map.get_key_value(&1), Some((&1, &"a")));
 588     /// assert_eq!(map.get_key_value(&2), None);
 589     /// ```
 590     #[stable(feature = "map_get_key_value", since = "1.40.0")]
 591     pub fn get_key_value<Q: ?Sized>(&self, k: &Q) -> Option<(&K, &V)>
 592     where
 593         K: Borrow<Q> + Ord,
 594         Q: Ord,
 595     {
 596         let root_node = self.root.as_ref()?.reborrow();
 597         match root_node.search_tree(k) {
 598             Found(handle) => Some(handle.into_kv()),
 599             GoDown(_) => None,
 600         }
 601     }
 602
 603     /// Returns the first key-value pair in the map.
 604     /// The key in this pair is the minimum key in the map.
 605     ///
 606     /// # Examples
 607     ///
 608     /// Basic usage:
 609     ///
 610     /// ```
 611     /// #![feature(map_first_last)]
 612     /// use std::collections::BTreeMap;
 613     ///
 614     /// let mut map = BTreeMap::new();
 615     /// assert_eq!(map.first_key_value(), None);
 616     /// map.insert(1, "b");
 617     /// map.insert(2, "a");
 618     /// assert_eq!(map.first_key_value(), Some((&1, &"b")));
 619     /// ```
 620     #[unstable(feature = "map_first_last", issue = "62924")]
 621     pub fn first_key_value(&self) -> Option<(&K, &V)>
 622     where
 623         K: Ord,
 624     {
 625         let root_node = self.root.as_ref()?.reborrow();
 626         root_node.first_leaf_edge().right_kv().ok().map(Handle::into_kv)
 627     }
 628
 629     /// Returns the first entry in the map for in-place manipulation.
 630     /// The key of this entry is the minimum key in the map.
 631     ///
 632     /// # Examples
 633     ///
 634     /// ```
 635     /// #![feature(map_first_last)]
 636     /// use std::collections::BTreeMap;
 637     ///
 638     /// let mut map = BTreeMap::new();
 639     /// map.insert(1, "a");
 640     /// map.insert(2, "b");
 641     /// if let Some(mut entry) = map.first_entry() {
 642     ///     if *entry.key() > 0 {
 643     ///         entry.insert("first");
 644     ///     }
 645     /// }
 646     /// assert_eq!(*map.get(&1).unwrap(), "first");
 647     /// assert_eq!(*map.get(&2).unwrap(), "b");
 648     /// ```
 649     #[unstable(feature = "map_first_last", issue = "62924")]
 650     pub fn first_entry(&mut self) -> Option<OccupiedEntry<'_, K, V>>
 651     where
 652         K: Ord,
 653     {
 654         let (map, dormant_map) = DormantMutRef::new(self);
 655         let root_node = map.root.as_mut()?.borrow_mut();
 656         let kv = root_node.first_leaf_edge().right_kv().ok()?;
 657         Some(OccupiedEntry { handle: kv.forget_node_type(), dormant_map, _marker: PhantomData })
 658     }
 659
 660     /// Removes and returns the first element in the map.
 661     /// The key of this element is the minimum key that was in the map.
 662     ///
 663     /// # Examples
 664     ///
 665     /// Draining elements in ascending order, while keeping a usable map each iteration.
 666     ///
 667     /// ```
 668     /// #![feature(map_first_last)]
 669     /// use std::collections::BTreeMap;
 670     ///
 671     /// let mut map = BTreeMap::new();
 672     /// map.insert(1, "a");
 673     /// map.insert(2, "b");
 674     /// while let Some((key, _val)) = map.pop_first() {
 675     ///     assert!(map.iter().all(|(k, _v)| *k > key));
 676     /// }
 677     /// assert!(map.is_empty());
 678     /// ```
 679     #[unstable(feature = "map_first_last", issue = "62924")]
 680     pub fn pop_first(&mut self) -> Option<(K, V)>
 681     where
 682         K: Ord,
 683     {
 684         self.first_entry().map(|entry| entry.remove_entry())
 685     }
 686
 687     /// Returns the last key-value pair in the map.
 688     /// The key in this pair is the maximum key in the map.
 689     ///
 690     /// # Examples
 691     ///
 692     /// Basic usage:
 693     ///
 694     /// ```
 695     /// #![feature(map_first_last)]
 696     /// use std::collections::BTreeMap;
 697     ///
 698     /// let mut map = BTreeMap::new();
 699     /// map.insert(1, "b");
 700     /// map.insert(2, "a");
 701     /// assert_eq!(map.last_key_value(), Some((&2, &"a")));
 702     /// ```
 703     #[unstable(feature = "map_first_last", issue = "62924")]
 704     pub fn last_key_value(&self) -> Option<(&K, &V)>
 705     where
 706         K: Ord,
 707     {
 708         let root_node = self.root.as_ref()?.reborrow();
 709         root_node.last_leaf_edge().left_kv().ok().map(Handle::into_kv)
 710     }
 711
 712     /// Returns the last entry in the map for in-place manipulation.
 713     /// The key of this entry is the maximum key in the map.
 714     ///
 715     /// # Examples
 716     ///
 717     /// ```
 718     /// #![feature(map_first_last)]
 719     /// use std::collections::BTreeMap;
 720     ///
 721     /// let mut map = BTreeMap::new();
 722     /// map.insert(1, "a");
 723     /// map.insert(2, "b");
 724     /// if let Some(mut entry) = map.last_entry() {
 725     ///     if *entry.key() > 0 {
 726     ///         entry.insert("last");
 727     ///     }
 728     /// }
 729     /// assert_eq!(*map.get(&1).unwrap(), "a");
 730     /// assert_eq!(*map.get(&2).unwrap(), "last");
 731     /// ```
 732     #[unstable(feature = "map_first_last", issue = "62924")]
 733     pub fn last_entry(&mut self) -> Option<OccupiedEntry<'_, K, V>>
 734     where
 735         K: Ord,
 736     {
 737         let (map, dormant_map) = DormantMutRef::new(self);
 738         let root_node = map.root.as_mut()?.borrow_mut();
 739         let kv = root_node.last_leaf_edge().left_kv().ok()?;
 740         Some(OccupiedEntry { handle: kv.forget_node_type(), dormant_map, _marker: PhantomData })
 741     }
 742
 743     /// Removes and returns the last element in the map.
 744     /// The key of this element is the maximum key that was in the map.
 745     ///
 746     /// # Examples
 747     ///
 748     /// Draining elements in descending order, while keeping a usable map each iteration.
 749     ///
 750     /// ```
 751     /// #![feature(map_first_last)]
 752     /// use std::collections::BTreeMap;
 753     ///
 754     /// let mut map = BTreeMap::new();
 755     /// map.insert(1, "a");
 756     /// map.insert(2, "b");
 757     /// while let Some((key, _val)) = map.pop_last() {
 758     ///     assert!(map.iter().all(|(k, _v)| *k < key));
 759     /// }
 760     /// assert!(map.is_empty());
 761     /// ```
 762     #[unstable(feature = "map_first_last", issue = "62924")]
 763     pub fn pop_last(&mut self) -> Option<(K, V)>
 764     where
 765         K: Ord,
 766     {
 767         self.last_entry().map(|entry| entry.remove_entry())
 768     }
 769
 770     /// Returns `true` if the map contains a value for the specified key.
 771     ///
 772     /// The key may be any borrowed form of the map's key type, but the ordering
 773     /// on the borrowed form *must* match the ordering on the key type.
 774     ///
 775     /// # Examples
 776     ///
 777     /// Basic usage:
 778     ///
 779     /// ```
 780     /// use std::collections::BTreeMap;
 781     ///
 782     /// let mut map = BTreeMap::new();
 783     /// map.insert(1, "a");
 784     /// assert_eq!(map.contains_key(&1), true);
 785     /// assert_eq!(map.contains_key(&2), false);
 786     /// ```
 787     #[stable(feature = "rust1", since = "1.0.0")]
 788     pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool
 789     where
 790         K: Borrow<Q> + Ord,
 791         Q: Ord,
 792     {
 793         self.get(key).is_some()
 794     }
 795
 796     /// Returns a mutable reference to the value corresponding to the key.
 797     ///
 798     /// The key may be any borrowed form of the map's key type, but the ordering
 799     /// on the borrowed form *must* match the ordering on the key type.
 800     ///
 801     /// # Examples
 802     ///
 803     /// Basic usage:
 804     ///
 805     /// ```
 806     /// use std::collections::BTreeMap;
 807     ///
 808     /// let mut map = BTreeMap::new();
 809     /// map.insert(1, "a");
 810     /// if let Some(x) = map.get_mut(&1) {
 811     ///     *x = "b";
 812     /// }
 813     /// assert_eq!(map[&1], "b");
 814     /// ```
 815     // See `get` for implementation notes, this is basically a copy-paste with mut's added
 816     #[stable(feature = "rust1", since = "1.0.0")]
 817     pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>
 818     where
 819         K: Borrow<Q> + Ord,
 820         Q: Ord,
 821     {
 822         let root_node = self.root.as_mut()?.borrow_mut();
 823         match root_node.search_tree(key) {
 824             Found(handle) => Some(handle.into_val_mut()),
 825             GoDown(_) => None,
 826         }
 827     }
 828
 829     /// Inserts a key-value pair into the map.
 830     ///
 831     /// If the map did not have this key present, `None` is returned.
 832     ///
 833     /// If the map did have this key present, the value is updated, and the old
 834     /// value is returned. The key is not updated, though; this matters for
 835     /// types that can be `==` without being identical. See the [module-level
 836     /// documentation] for more.
 837     ///
 838     /// [module-level documentation]: index.html#insert-and-complex-keys
 839     ///
 840     /// # Examples
 841     ///
 842     /// Basic usage:
 843     ///
 844     /// ```
 845     /// use std::collections::BTreeMap;
 846     ///
 847     /// let mut map = BTreeMap::new();
 848     /// assert_eq!(map.insert(37, "a"), None);
 849     /// assert_eq!(map.is_empty(), false);
 850     ///
 851     /// map.insert(37, "b");
 852     /// assert_eq!(map.insert(37, "c"), Some("b"));
 853     /// assert_eq!(map[&37], "c");
 854     /// ```
 855     #[stable(feature = "rust1", since = "1.0.0")]
 856     pub fn insert(&mut self, key: K, value: V) -> Option<V>
 857     where
 858         K: Ord,
 859     {
 860         match self.entry(key) {
 861             Occupied(mut entry) => Some(entry.insert(value)),
 862             Vacant(entry) => {
 863                 entry.insert(value);
 864                 None
 865             }
 866         }
 867     }
 868
 869     /// Tries to insert a key-value pair into the map, and returns
 870     /// a mutable reference to the value in the entry.
 871     ///
 872     /// If the map already had this key present, nothing is updated, and
 873     /// an error containing the occupied entry and the value is returned.
 874     ///
 875     /// # Examples
 876     ///
 877     /// Basic usage:
 878     ///
 879     /// ```
 880     /// #![feature(map_try_insert)]
 881     ///
 882     /// use std::collections::BTreeMap;
 883     ///
 884     /// let mut map = BTreeMap::new();
 885     /// assert_eq!(map.try_insert(37, "a").unwrap(), &"a");
 886     ///
 887     /// let err = map.try_insert(37, "b").unwrap_err();
 888     /// assert_eq!(err.entry.key(), &37);
 889     /// assert_eq!(err.entry.get(), &"a");
 890     /// assert_eq!(err.value, "b");
 891     /// ```
 892     #[unstable(feature = "map_try_insert", issue = "82766")]
 893     pub fn try_insert(&mut self, key: K, value: V) -> Result<&mut V, OccupiedError<'_, K, V>>
 894     where
 895         K: Ord,
 896     {
 897         match self.entry(key) {
 898             Occupied(entry) => Err(OccupiedError { entry, value }),
 899             Vacant(entry) => Ok(entry.insert(value)),
 900         }
 901     }
 902
 903     /// Removes a key from the map, returning the value at the key if the key
 904     /// was previously in the map.
 905     ///
 906     /// The key may be any borrowed form of the map's key type, but the ordering
 907     /// on the borrowed form *must* match the ordering on the key type.
 908     ///
 909     /// # Examples
 910     ///
 911     /// Basic usage:
 912     ///
 913     /// ```
 914     /// use std::collections::BTreeMap;
 915     ///
 916     /// let mut map = BTreeMap::new();
 917     /// map.insert(1, "a");
 918     /// assert_eq!(map.remove(&1), Some("a"));
 919     /// assert_eq!(map.remove(&1), None);
 920     /// ```
 921     #[stable(feature = "rust1", since = "1.0.0")]
 922     pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V>
 923     where
 924         K: Borrow<Q> + Ord,
 925         Q: Ord,
 926     {
 927         self.remove_entry(key).map(|(_, v)| v)
 928     }
 929
 930     /// Removes a key from the map, returning the stored key and value if the key
 931     /// was previously in the map.
 932     ///
 933     /// The key may be any borrowed form of the map's key type, but the ordering
 934     /// on the borrowed form *must* match the ordering on the key type.
 935     ///
 936     /// # Examples
 937     ///
 938     /// Basic usage:
 939     ///
 940     /// ```
 941     /// use std::collections::BTreeMap;
 942     ///
 943     /// let mut map = BTreeMap::new();
 944     /// map.insert(1, "a");
 945     /// assert_eq!(map.remove_entry(&1), Some((1, "a")));
 946     /// assert_eq!(map.remove_entry(&1), None);
 947     /// ```
 948     #[stable(feature = "btreemap_remove_entry", since = "1.45.0")]
 949     pub fn remove_entry<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)>
 950     where
 951         K: Borrow<Q> + Ord,
 952         Q: Ord,
 953     {
 954         let (map, dormant_map) = DormantMutRef::new(self);
 955         let root_node = map.root.as_mut()?.borrow_mut();
 956         match root_node.search_tree(key) {
 957             Found(handle) => {
 958                 Some(OccupiedEntry { handle, dormant_map, _marker: PhantomData }.remove_entry())
 959             }
 960             GoDown(_) => None,
 961         }
 962     }
 963
 964     /// Retains only the elements specified by the predicate.
 965     ///
 966     /// In other words, remove all pairs `(k, v)` such that `f(&k, &mut v)` returns `false`.
 967     /// The elements are visited in ascending key order.
 968     ///
 969     /// # Examples
 970     ///
 971     /// ```
 972     /// use std::collections::BTreeMap;
 973     ///
 974     /// let mut map: BTreeMap<i32, i32> = (0..8).map(|x| (x, x*10)).collect();
 975     /// // Keep only the elements with even-numbered keys.
 976     /// map.retain(|&k, _| k % 2 == 0);
 977     /// assert!(map.into_iter().eq(vec![(0, 0), (2, 20), (4, 40), (6, 60)]));
 978     /// ```
 979     #[inline]
 980     #[stable(feature = "btree_retain", since = "1.53.0")]
 981     pub fn retain<F>(&mut self, mut f: F)
 982     where
 983         K: Ord,
 984         F: FnMut(&K, &mut V) -> bool,
 985     {
 986         self.drain_filter(|k, v| !f(k, v));
 987     }
 988
 989     /// Moves all elements from `other` into `Self`, leaving `other` empty.
 990     ///
 991     /// # Examples
 992     ///
 993     /// ```
 994     /// use std::collections::BTreeMap;
 995     ///
 996     /// let mut a = BTreeMap::new();
 997     /// a.insert(1, "a");
 998     /// a.insert(2, "b");
 999     /// a.insert(3, "c");
1000     ///
1001     /// let mut b = BTreeMap::new();
1002     /// b.insert(3, "d");
1003     /// b.insert(4, "e");
1004     /// b.insert(5, "f");
1005     ///
1006     /// a.append(&mut b);
1007     ///
1008     /// assert_eq!(a.len(), 5);
1009     /// assert_eq!(b.len(), 0);
1010     ///
1011     /// assert_eq!(a[&1], "a");
1012     /// assert_eq!(a[&2], "b");
1013     /// assert_eq!(a[&3], "d");
1014     /// assert_eq!(a[&4], "e");
1015     /// assert_eq!(a[&5], "f");
1016     /// ```
1017     #[stable(feature = "btree_append", since = "1.11.0")]
1018     pub fn append(&mut self, other: &mut Self)
1019     where
1020         K: Ord,
1021     {
1022         // Do we have to append anything at all?
1023         if other.is_empty() {
1024             return;
1025         }
1026
1027         // We can just swap `self` and `other` if `self` is empty.
1028         if self.is_empty() {
1029             mem::swap(self, other);
1030             return;
1031         }
1032
1033         let self_iter = mem::take(self).into_iter();
1034         let other_iter = mem::take(other).into_iter();
1035         let root = BTreeMap::ensure_is_owned(&mut self.root);
1036         root.append_from_sorted_iters(self_iter, other_iter, &mut self.length)
1037     }
1038
1039     /// Constructs a double-ended iterator over a sub-range of elements in the map.
1040     /// The simplest way is to use the range syntax `min..max`, thus `range(min..max)` will
1041     /// yield elements from min (inclusive) to max (exclusive).
1042     /// The range may also be entered as `(Bound<T>, Bound<T>)`, so for example
1043     /// `range((Excluded(4), Included(10)))` will yield a left-exclusive, right-inclusive
1044     /// range from 4 to 10.
1045     ///
1046     /// # Panics
1047     ///
1048     /// Panics if range `start > end`.
1049     /// Panics if range `start == end` and both bounds are `Excluded`.
1050     ///
1051     /// # Examples
1052     ///
1053     /// Basic usage:
1054     ///
1055     /// ```
1056     /// use std::collections::BTreeMap;
1057     /// use std::ops::Bound::Included;
1058     ///
1059     /// let mut map = BTreeMap::new();
1060     /// map.insert(3, "a");
1061     /// map.insert(5, "b");
1062     /// map.insert(8, "c");
1063     /// for (&key, &value) in map.range((Included(&4), Included(&8))) {
1064     ///     println!("{}: {}", key, value);
1065     /// }
1066     /// assert_eq!(Some((&5, &"b")), map.range(4..).next());
1067     /// ```
1068     #[stable(feature = "btree_range", since = "1.17.0")]
1069     pub fn range<T: ?Sized, R>(&self, range: R) -> Range<'_, K, V>
1070     where
1071         T: Ord,
1072         K: Borrow<T> + Ord,
1073         R: RangeBounds<T>,
1074     {
1075         if let Some(root) = &self.root {
1076             Range { inner: root.reborrow().range_search(range) }
1077         } else {
1078             Range { inner: LeafRange::none() }
1079         }
1080     }
1081
1082     /// Constructs a mutable double-ended iterator over a sub-range of elements in the map.
1083     /// The simplest way is to use the range syntax `min..max`, thus `range(min..max)` will
1084     /// yield elements from min (inclusive) to max (exclusive).
1085     /// The range may also be entered as `(Bound<T>, Bound<T>)`, so for example
1086     /// `range((Excluded(4), Included(10)))` will yield a left-exclusive, right-inclusive
1087     /// range from 4 to 10.
1088     ///
1089     /// # Panics
1090     ///
1091     /// Panics if range `start > end`.
1092     /// Panics if range `start == end` and both bounds are `Excluded`.
1093     ///
1094     /// # Examples
1095     ///
1096     /// Basic usage:
1097     ///
1098     /// ```
1099     /// use std::collections::BTreeMap;
1100     ///
1101     /// let mut map: BTreeMap<&str, i32> =
1102     ///     [("Alice", 0), ("Bob", 0), ("Carol", 0), ("Cheryl", 0)].into();
1103     /// for (_, balance) in map.range_mut("B".."Cheryl") {
1104     ///     *balance += 100;
1105     /// }
1106     /// for (name, balance) in &map {
1107     ///     println!("{} => {}", name, balance);
1108     /// }
1109     /// ```
1110     #[stable(feature = "btree_range", since = "1.17.0")]
1111     pub fn range_mut<T: ?Sized, R>(&mut self, range: R) -> RangeMut<'_, K, V>
1112     where
1113         T: Ord,
1114         K: Borrow<T> + Ord,
1115         R: RangeBounds<T>,
1116     {
1117         if let Some(root) = &mut self.root {
1118             RangeMut { inner: root.borrow_valmut().range_search(range), _marker: PhantomData }
1119         } else {
1120             RangeMut { inner: LeafRange::none(), _marker: PhantomData }
1121         }
1122     }
1123
1124     /// Gets the given key's corresponding entry in the map for in-place manipulation.
1125     ///
1126     /// # Examples
1127     ///
1128     /// Basic usage:
1129     ///
1130     /// ```
1131     /// use std::collections::BTreeMap;
1132     ///
1133     /// let mut count: BTreeMap<&str, usize> = BTreeMap::new();
1134     ///
1135     /// // count the number of occurrences of letters in the vec
1136     /// for x in ["a", "b", "a", "c", "a", "b"] {
1137     ///     *count.entry(x).or_insert(0) += 1;
1138     /// }
1139     ///
1140     /// assert_eq!(count["a"], 3);
1141     /// ```
1142     #[stable(feature = "rust1", since = "1.0.0")]
1143     pub fn entry(&mut self, key: K) -> Entry<'_, K, V>
1144     where
1145         K: Ord,
1146     {
1147         // FIXME(@porglezomp) Avoid allocating if we don't insert
1148         let (map, dormant_map) = DormantMutRef::new(self);
1149         let root_node = Self::ensure_is_owned(&mut map.root).borrow_mut();
1150         match root_node.search_tree(&key) {
1151             Found(handle) => Occupied(OccupiedEntry { handle, dormant_map, _marker: PhantomData }),
1152             GoDown(handle) => {
1153                 Vacant(VacantEntry { key, handle, dormant_map, _marker: PhantomData })
1154             }
1155         }
1156     }
1157
1158     /// Splits the collection into two at the given key. Returns everything after the given key,
1159     /// including the key.
1160     ///
1161     /// # Examples
1162     ///
1163     /// Basic usage:
1164     ///
1165     /// ```
1166     /// use std::collections::BTreeMap;
1167     ///
1168     /// let mut a = BTreeMap::new();
1169     /// a.insert(1, "a");
1170     /// a.insert(2, "b");
1171     /// a.insert(3, "c");
1172     /// a.insert(17, "d");
1173     /// a.insert(41, "e");
1174     ///
1175     /// let b = a.split_off(&3);
1176     ///
1177     /// assert_eq!(a.len(), 2);
1178     /// assert_eq!(b.len(), 3);
1179     ///
1180     /// assert_eq!(a[&1], "a");
1181     /// assert_eq!(a[&2], "b");
1182     ///
1183     /// assert_eq!(b[&3], "c");
1184     /// assert_eq!(b[&17], "d");
1185     /// assert_eq!(b[&41], "e");
1186     /// ```
1187     #[stable(feature = "btree_split_off", since = "1.11.0")]
1188     pub fn split_off<Q: ?Sized + Ord>(&mut self, key: &Q) -> Self
1189     where
1190         K: Borrow<Q> + Ord,
1191     {
1192         if self.is_empty() {
1193             return Self::new();
1194         }
1195
1196         let total_num = self.len();
1197         let left_root = self.root.as_mut().unwrap(); // unwrap succeeds because not empty
1198
1199         let right_root = left_root.split_off(key);
1200
1201         let (new_left_len, right_len) = Root::calc_split_length(total_num, &left_root, &right_root);
1202         self.length = new_left_len;
1203
1204         BTreeMap { root: Some(right_root), length: right_len }
1205     }
1206
1207     /// Creates an iterator that visits all elements (key-value pairs) in
1208     /// ascending key order and uses a closure to determine if an element should
1209     /// be removed. If the closure returns `true`, the element is removed from
1210     /// the map and yielded. If the closure returns `false`, or panics, the
1211     /// element remains in the map and will not be yielded.
1212     ///
1213     /// The iterator also lets you mutate the value of each element in the
1214     /// closure, regardless of whether you choose to keep or remove it.
1215     ///
1216     /// If the iterator is only partially consumed or not consumed at all, each
1217     /// of the remaining elements is still subjected to the closure, which may
1218     /// change its value and, by returning `true`, have the element removed and
1219     /// dropped.
1220     ///
1221     /// It is unspecified how many more elements will be subjected to the
1222     /// closure if a panic occurs in the closure, or a panic occurs while
1223     /// dropping an element, or if the `DrainFilter` value is leaked.
1224     ///
1225     /// # Examples
1226     ///
1227     /// Splitting a map into even and odd keys, reusing the original map:
1228     ///
1229     /// ```
1230     /// #![feature(btree_drain_filter)]
1231     /// use std::collections::BTreeMap;
1232     ///
1233     /// let mut map: BTreeMap<i32, i32> = (0..8).map(|x| (x, x)).collect();
1234     /// let evens: BTreeMap<_, _> = map.drain_filter(|k, _v| k % 2 == 0).collect();
1235     /// let odds = map;
1236     /// assert_eq!(evens.keys().copied().collect::<Vec<_>>(), [0, 2, 4, 6]);
1237     /// assert_eq!(odds.keys().copied().collect::<Vec<_>>(), [1, 3, 5, 7]);
1238     /// ```
1239     #[unstable(feature = "btree_drain_filter", issue = "70530")]
1240     pub fn drain_filter<F>(&mut self, pred: F) -> DrainFilter<'_, K, V, F>
1241     where
1242         K: Ord,
1243         F: FnMut(&K, &mut V) -> bool,
1244     {
1245         DrainFilter { pred, inner: self.drain_filter_inner() }
1246     }
1247
1248     pub(super) fn drain_filter_inner(&mut self) -> DrainFilterInner<'_, K, V>
1249     where
1250         K: Ord,
1251     {
1252         if let Some(root) = self.root.as_mut() {
1253             let (root, dormant_root) = DormantMutRef::new(root);
1254             let front = root.borrow_mut().first_leaf_edge();
1255             DrainFilterInner {
1256                 length: &mut self.length,
1257                 dormant_root: Some(dormant_root),
1258                 cur_leaf_edge: Some(front),
1259             }
1260         } else {
1261             DrainFilterInner { length: &mut self.length, dormant_root: None, cur_leaf_edge: None }
1262         }
1263     }
1264
1265     /// Creates a consuming iterator visiting all the keys, in sorted order.
1266     /// The map cannot be used after calling this.
1267     /// The iterator element type is `K`.
1268     ///
1269     /// # Examples
1270     ///
1271     /// ```
1272     /// use std::collections::BTreeMap;
1273     ///
1274     /// let mut a = BTreeMap::new();
1275     /// a.insert(2, "b");
1276     /// a.insert(1, "a");
1277     ///
1278     /// let keys: Vec<i32> = a.into_keys().collect();
1279     /// assert_eq!(keys, [1, 2]);
1280     /// ```
1281     #[inline]
1282     #[stable(feature = "map_into_keys_values", since = "1.54.0")]
1283     pub fn into_keys(self) -> IntoKeys<K, V> {
1284         IntoKeys { inner: self.into_iter() }
1285     }
1286
1287     /// Creates a consuming iterator visiting all the values, in order by key.
1288     /// The map cannot be used after calling this.
1289     /// The iterator element type is `V`.
1290     ///
1291     /// # Examples
1292     ///
1293     /// ```
1294     /// use std::collections::BTreeMap;
1295     ///
1296     /// let mut a = BTreeMap::new();
1297     /// a.insert(1, "hello");
1298     /// a.insert(2, "goodbye");
1299     ///
1300     /// let values: Vec<&str> = a.into_values().collect();
1301     /// assert_eq!(values, ["hello", "goodbye"]);
1302     /// ```
1303     #[inline]
1304     #[stable(feature = "map_into_keys_values", since = "1.54.0")]
1305     pub fn into_values(self) -> IntoValues<K, V> {
1306         IntoValues { inner: self.into_iter() }
1307     }
1308
1309     /// Makes a `BTreeMap` from a sorted iterator.
1310     pub(crate) fn bulk_build_from_sorted_iter<I>(iter: I) -> Self
1311     where
1312         K: Ord,
1313         I: IntoIterator<Item = (K, V)>,
1314     {
1315         let mut root = Root::new();
1316         let mut length = 0;
1317         root.bulk_push(DedupSortedIter::new(iter.into_iter()), &mut length);
1318         BTreeMap { root: Some(root), length }
1319     }
1320 }
1321
1322 #[stable(feature = "rust1", since = "1.0.0")]
1323 impl<'a, K, V> IntoIterator for &'a BTreeMap<K, V> {
1324     type Item = (&'a K, &'a V);
1325     type IntoIter = Iter<'a, K, V>;
1326
1327     fn into_iter(self) -> Iter<'a, K, V> {
1328         self.iter()
1329     }
1330 }
1331
1332 #[stable(feature = "rust1", since = "1.0.0")]
1333 impl<'a, K: 'a, V: 'a> Iterator for Iter<'a, K, V> {
1334     type Item = (&'a K, &'a V);
1335
1336     fn next(&mut self) -> Option<(&'a K, &'a V)> {
1337         if self.length == 0 {
1338             None
1339         } else {
1340             self.length -= 1;
1341             Some(unsafe { self.range.next_unchecked() })
1342         }
1343     }
1344
1345     fn size_hint(&self) -> (usize, Option<usize>) {
1346         (self.length, Some(self.length))
1347     }
1348
1349     fn last(mut self) -> Option<(&'a K, &'a V)> {
1350         self.next_back()
1351     }
1352
1353     fn min(mut self) -> Option<(&'a K, &'a V)> {
1354         self.next()
1355     }
1356
1357     fn max(mut self) -> Option<(&'a K, &'a V)> {
1358         self.next_back()
1359     }
1360 }
1361
1362 #[stable(feature = "fused", since = "1.26.0")]
1363 impl<K, V> FusedIterator for Iter<'_, K, V> {}
1364
1365 #[stable(feature = "rust1", since = "1.0.0")]
1366 impl<'a, K: 'a, V: 'a> DoubleEndedIterator for Iter<'a, K, V> {
1367     fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
1368         if self.length == 0 {
1369             None
1370         } else {
1371             self.length -= 1;
1372             Some(unsafe { self.range.next_back_unchecked() })
1373         }
1374     }
1375 }
1376
1377 #[stable(feature = "rust1", since = "1.0.0")]
1378 impl<K, V> ExactSizeIterator for Iter<'_, K, V> {
1379     fn len(&self) -> usize {
1380         self.length
1381     }
1382 }
1383
1384 #[stable(feature = "rust1", since = "1.0.0")]
1385 impl<K, V> Clone for Iter<'_, K, V> {
1386     fn clone(&self) -> Self {
1387         Iter { range: self.range.clone(), length: self.length }
1388     }
1389 }
1390
1391 #[stable(feature = "rust1", since = "1.0.0")]
1392 impl<'a, K, V> IntoIterator for &'a mut BTreeMap<K, V> {
1393     type Item = (&'a K, &'a mut V);
1394     type IntoIter = IterMut<'a, K, V>;
1395
1396     fn into_iter(self) -> IterMut<'a, K, V> {
1397         self.iter_mut()
1398     }
1399 }
1400
1401 #[stable(feature = "rust1", since = "1.0.0")]
1402 impl<'a, K: 'a, V: 'a> Iterator for IterMut<'a, K, V> {
1403     type Item = (&'a K, &'a mut V);
1404
1405     fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
1406         if self.length == 0 {
1407             None
1408         } else {
1409             self.length -= 1;
1410             Some(unsafe { self.range.next_unchecked() })
1411         }
1412     }
1413
1414     fn size_hint(&self) -> (usize, Option<usize>) {
1415         (self.length, Some(self.length))
1416     }
1417
1418     fn last(mut self) -> Option<(&'a K, &'a mut V)> {
1419         self.next_back()
1420     }
1421
1422     fn min(mut self) -> Option<(&'a K, &'a mut V)> {
1423         self.next()
1424     }
1425
1426     fn max(mut self) -> Option<(&'a K, &'a mut V)> {
1427         self.next_back()
1428     }
1429 }
1430
1431 #[stable(feature = "rust1", since = "1.0.0")]
1432 impl<'a, K: 'a, V: 'a> DoubleEndedIterator for IterMut<'a, K, V> {
1433     fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
1434         if self.length == 0 {
1435             None
1436         } else {
1437             self.length -= 1;
1438             Some(unsafe { self.range.next_back_unchecked() })
1439         }
1440     }
1441 }
1442
1443 #[stable(feature = "rust1", since = "1.0.0")]
1444 impl<K, V> ExactSizeIterator for IterMut<'_, K, V> {
1445     fn len(&self) -> usize {
1446         self.length
1447     }
1448 }
1449
1450 #[stable(feature = "fused", since = "1.26.0")]
1451 impl<K, V> FusedIterator for IterMut<'_, K, V> {}
1452
1453 impl<'a, K, V> IterMut<'a, K, V> {
1454     /// Returns an iterator of references over the remaining items.
1455     #[inline]
1456     pub(super) fn iter(&self) -> Iter<'_, K, V> {
1457         Iter { range: self.range.reborrow(), length: self.length }
1458     }
1459 }
1460
1461 #[stable(feature = "rust1", since = "1.0.0")]
1462 impl<K, V> IntoIterator for BTreeMap<K, V> {
1463     type Item = (K, V);
1464     type IntoIter = IntoIter<K, V>;
1465
1466     fn into_iter(self) -> IntoIter<K, V> {
1467         let mut me = ManuallyDrop::new(self);
1468         if let Some(root) = me.root.take() {
1469             let full_range = root.into_dying().full_range();
1470
1471             IntoIter { range: full_range, length: me.length }
1472         } else {
1473             IntoIter { range: LazyLeafRange::none(), length: 0 }
1474         }
1475     }
1476 }
1477
1478 #[stable(feature = "btree_drop", since = "1.7.0")]
1479 impl<K, V> Drop for IntoIter<K, V> {
1480     fn drop(&mut self) {
1481         struct DropGuard<'a, K, V>(&'a mut IntoIter<K, V>);
1482
1483         impl<'a, K, V> Drop for DropGuard<'a, K, V> {
1484             fn drop(&mut self) {
1485                 // Continue the same loop we perform below. This only runs when unwinding, so we
1486                 // don't have to care about panics this time (they'll abort).
1487                 while let Some(kv) = self.0.dying_next() {
1488                     // SAFETY: we consume the dying handle immediately.
1489                     unsafe { kv.drop_key_val() };
1490                 }
1491             }
1492         }
1493
1494         while let Some(kv) = self.dying_next() {
1495             let guard = DropGuard(self);
1496             // SAFETY: we don't touch the tree before consuming the dying handle.
1497             unsafe { kv.drop_key_val() };
1498             mem::forget(guard);
1499         }
1500     }
1501 }
1502
1503 impl<K, V> IntoIter<K, V> {
1504     /// Core of a `next` method returning a dying KV handle,
1505     /// invalidated by further calls to this function and some others.
1506     fn dying_next(
1507         &mut self,
1508     ) -> Option<Handle<NodeRef<marker::Dying, K, V, marker::LeafOrInternal>, marker::KV>> {
1509         if self.length == 0 {
1510             self.range.deallocating_end();
1511             None
1512         } else {
1513             self.length -= 1;
1514             Some(unsafe { self.range.deallocating_next_unchecked() })
1515         }
1516     }
1517
1518     /// Core of a `next_back` method returning a dying KV handle,
1519     /// invalidated by further calls to this function and some others.
1520     fn dying_next_back(
1521         &mut self,
1522     ) -> Option<Handle<NodeRef<marker::Dying, K, V, marker::LeafOrInternal>, marker::KV>> {
1523         if self.length == 0 {
1524             self.range.deallocating_end();
1525             None
1526         } else {
1527             self.length -= 1;
1528             Some(unsafe { self.range.deallocating_next_back_unchecked() })
1529         }
1530     }
1531 }
1532
1533 #[stable(feature = "rust1", since = "1.0.0")]
1534 impl<K, V> Iterator for IntoIter<K, V> {
1535     type Item = (K, V);
1536
1537     fn next(&mut self) -> Option<(K, V)> {
1538         // SAFETY: we consume the dying handle immediately.
1539         self.dying_next().map(unsafe { |kv| kv.into_key_val() })
1540     }
1541
1542     fn size_hint(&self) -> (usize, Option<usize>) {
1543         (self.length, Some(self.length))
1544     }
1545 }
1546
1547 #[stable(feature = "rust1", since = "1.0.0")]
1548 impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
1549     fn next_back(&mut self) -> Option<(K, V)> {
1550         // SAFETY: we consume the dying handle immediately.
1551         self.dying_next_back().map(unsafe { |kv| kv.into_key_val() })
1552     }
1553 }
1554
1555 #[stable(feature = "rust1", since = "1.0.0")]
1556 impl<K, V> ExactSizeIterator for IntoIter<K, V> {
1557     fn len(&self) -> usize {
1558         self.length
1559     }
1560 }
1561
1562 #[stable(feature = "fused", since = "1.26.0")]
1563 impl<K, V> FusedIterator for IntoIter<K, V> {}
1564
1565 #[stable(feature = "rust1", since = "1.0.0")]
1566 impl<'a, K, V> Iterator for Keys<'a, K, V> {
1567     type Item = &'a K;
1568
1569     fn next(&mut self) -> Option<&'a K> {
1570         self.inner.next().map(|(k, _)| k)
1571     }
1572
1573     fn size_hint(&self) -> (usize, Option<usize>) {
1574         self.inner.size_hint()
1575     }
1576
1577     fn last(mut self) -> Option<&'a K> {
1578         self.next_back()
1579     }
1580
1581     fn min(mut self) -> Option<&'a K> {
1582         self.next()
1583     }
1584
1585     fn max(mut self) -> Option<&'a K> {
1586         self.next_back()
1587     }
1588 }
1589
1590 #[stable(feature = "rust1", since = "1.0.0")]
1591 impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> {
1592     fn next_back(&mut self) -> Option<&'a K> {
1593         self.inner.next_back().map(|(k, _)| k)
1594     }
1595 }
1596
1597 #[stable(feature = "rust1", since = "1.0.0")]
1598 impl<K, V> ExactSizeIterator for Keys<'_, K, V> {
1599     fn len(&self) -> usize {
1600         self.inner.len()
1601     }
1602 }
1603
1604 #[stable(feature = "fused", since = "1.26.0")]
1605 impl<K, V> FusedIterator for Keys<'_, K, V> {}
1606
1607 #[stable(feature = "rust1", since = "1.0.0")]
1608 impl<K, V> Clone for Keys<'_, K, V> {
1609     fn clone(&self) -> Self {
1610         Keys { inner: self.inner.clone() }
1611     }
1612 }
1613
1614 #[stable(feature = "rust1", since = "1.0.0")]
1615 impl<'a, K, V> Iterator for Values<'a, K, V> {
1616     type Item = &'a V;
1617
1618     fn next(&mut self) -> Option<&'a V> {
1619         self.inner.next().map(|(_, v)| v)
1620     }
1621
1622     fn size_hint(&self) -> (usize, Option<usize>) {
1623         self.inner.size_hint()
1624     }
1625
1626     fn last(mut self) -> Option<&'a V> {
1627         self.next_back()
1628     }
1629 }
1630
1631 #[stable(feature = "rust1", since = "1.0.0")]
1632 impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> {
1633     fn next_back(&mut self) -> Option<&'a V> {
1634         self.inner.next_back().map(|(_, v)| v)
1635     }
1636 }
1637
1638 #[stable(feature = "rust1", since = "1.0.0")]
1639 impl<K, V> ExactSizeIterator for Values<'_, K, V> {
1640     fn len(&self) -> usize {
1641         self.inner.len()
1642     }
1643 }
1644
1645 #[stable(feature = "fused", since = "1.26.0")]
1646 impl<K, V> FusedIterator for Values<'_, K, V> {}
1647
1648 #[stable(feature = "rust1", since = "1.0.0")]
1649 impl<K, V> Clone for Values<'_, K, V> {
1650     fn clone(&self) -> Self {
1651         Values { inner: self.inner.clone() }
1652     }
1653 }
1654
1655 /// An iterator produced by calling `drain_filter` on BTreeMap.
1656 #[unstable(feature = "btree_drain_filter", issue = "70530")]
1657 pub struct DrainFilter<'a, K, V, F>
1658 where
1659     K: 'a,
1660     V: 'a,
1661     F: 'a + FnMut(&K, &mut V) -> bool,
1662 {
1663     pred: F,
1664     inner: DrainFilterInner<'a, K, V>,
1665 }
1666 /// Most of the implementation of DrainFilter are generic over the type
1667 /// of the predicate, thus also serving for BTreeSet::DrainFilter.
1668 pub(super) struct DrainFilterInner<'a, K: 'a, V: 'a> {
1669     /// Reference to the length field in the borrowed map, updated live.
1670     length: &'a mut usize,
1671     /// Buried reference to the root field in the borrowed map.
1672     /// Wrapped in `Option` to allow drop handler to `take` it.
1673     dormant_root: Option<DormantMutRef<'a, Root<K, V>>>,
1674     /// Contains a leaf edge preceding the next element to be returned, or the last leaf edge.
1675     /// Empty if the map has no root, if iteration went beyond the last leaf edge,
1676     /// or if a panic occurred in the predicate.
1677     cur_leaf_edge: Option<Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>>,
1678 }
1679
1680 #[unstable(feature = "btree_drain_filter", issue = "70530")]
1681 impl<K, V, F> Drop for DrainFilter<'_, K, V, F>
1682 where
1683     F: FnMut(&K, &mut V) -> bool,
1684 {
1685     fn drop(&mut self) {
1686         self.for_each(drop);
1687     }
1688 }
1689
1690 #[unstable(feature = "btree_drain_filter", issue = "70530")]
1691 impl<K, V, F> fmt::Debug for DrainFilter<'_, K, V, F>
1692 where
1693     K: fmt::Debug,
1694     V: fmt::Debug,
1695     F: FnMut(&K, &mut V) -> bool,
1696 {
1697     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1698         f.debug_tuple("DrainFilter").field(&self.inner.peek()).finish()
1699     }
1700 }
1701
1702 #[unstable(feature = "btree_drain_filter", issue = "70530")]
1703 impl<K, V, F> Iterator for DrainFilter<'_, K, V, F>
1704 where
1705     F: FnMut(&K, &mut V) -> bool,
1706 {
1707     type Item = (K, V);
1708
1709     fn next(&mut self) -> Option<(K, V)> {
1710         self.inner.next(&mut self.pred)
1711     }
1712
1713     fn size_hint(&self) -> (usize, Option<usize>) {
1714         self.inner.size_hint()
1715     }
1716 }
1717
1718 impl<'a, K: 'a, V: 'a> DrainFilterInner<'a, K, V> {
1719     /// Allow Debug implementations to predict the next element.
1720     pub(super) fn peek(&self) -> Option<(&K, &V)> {
1721         let edge = self.cur_leaf_edge.as_ref()?;
1722         edge.reborrow().next_kv().ok().map(Handle::into_kv)
1723     }
1724
1725     /// Implementation of a typical `DrainFilter::next` method, given the predicate.
1726     pub(super) fn next<F>(&mut self, pred: &mut F) -> Option<(K, V)>
1727     where
1728         F: FnMut(&K, &mut V) -> bool,
1729     {
1730         while let Ok(mut kv) = self.cur_leaf_edge.take()?.next_kv() {
1731             let (k, v) = kv.kv_mut();
1732             if pred(k, v) {
1733                 *self.length -= 1;
1734                 let (kv, pos) = kv.remove_kv_tracking(|| {
1735                     // SAFETY: we will touch the root in a way that will not
1736                     // invalidate the position returned.
1737                     let root = unsafe { self.dormant_root.take().unwrap().awaken() };
1738                     root.pop_internal_level();
1739                     self.dormant_root = Some(DormantMutRef::new(root).1);
1740                 });
1741                 self.cur_leaf_edge = Some(pos);
1742                 return Some(kv);
1743             }
1744             self.cur_leaf_edge = Some(kv.next_leaf_edge());
1745         }
1746         None
1747     }
1748
1749     /// Implementation of a typical `DrainFilter::size_hint` method.
1750     pub(super) fn size_hint(&self) -> (usize, Option<usize>) {
1751         // In most of the btree iterators, `self.length` is the number of elements
1752         // yet to be visited. Here, it includes elements that were visited and that
1753         // the predicate decided not to drain. Making this upper bound more tight
1754         // during iteration would require an extra field.
1755         (0, Some(*self.length))
1756     }
1757 }
1758
1759 #[unstable(feature = "btree_drain_filter", issue = "70530")]
1760 impl<K, V, F> FusedIterator for DrainFilter<'_, K, V, F> where F: FnMut(&K, &mut V) -> bool {}
1761
1762 #[stable(feature = "btree_range", since = "1.17.0")]
1763 impl<'a, K, V> Iterator for Range<'a, K, V> {
1764     type Item = (&'a K, &'a V);
1765
1766     fn next(&mut self) -> Option<(&'a K, &'a V)> {
1767         self.inner.next_checked()
1768     }
1769
1770     fn last(mut self) -> Option<(&'a K, &'a V)> {
1771         self.next_back()
1772     }
1773
1774     fn min(mut self) -> Option<(&'a K, &'a V)> {
1775         self.next()
1776     }
1777
1778     fn max(mut self) -> Option<(&'a K, &'a V)> {
1779         self.next_back()
1780     }
1781 }
1782
1783 #[stable(feature = "map_values_mut", since = "1.10.0")]
1784 impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
1785     type Item = &'a mut V;
1786
1787     fn next(&mut self) -> Option<&'a mut V> {
1788         self.inner.next().map(|(_, v)| v)
1789     }
1790
1791     fn size_hint(&self) -> (usize, Option<usize>) {
1792         self.inner.size_hint()
1793     }
1794
1795     fn last(mut self) -> Option<&'a mut V> {
1796         self.next_back()
1797     }
1798 }
1799
1800 #[stable(feature = "map_values_mut", since = "1.10.0")]
1801 impl<'a, K, V> DoubleEndedIterator for ValuesMut<'a, K, V> {
1802     fn next_back(&mut self) -> Option<&'a mut V> {
1803         self.inner.next_back().map(|(_, v)| v)
1804     }
1805 }
1806
1807 #[stable(feature = "map_values_mut", since = "1.10.0")]
1808 impl<K, V> ExactSizeIterator for ValuesMut<'_, K, V> {
1809     fn len(&self) -> usize {
1810         self.inner.len()
1811     }
1812 }
1813
1814 #[stable(feature = "fused", since = "1.26.0")]
1815 impl<K, V> FusedIterator for ValuesMut<'_, K, V> {}
1816
1817 #[stable(feature = "map_into_keys_values", since = "1.54.0")]
1818 impl<K, V> Iterator for IntoKeys<K, V> {
1819     type Item = K;
1820
1821     fn next(&mut self) -> Option<K> {
1822         self.inner.next().map(|(k, _)| k)
1823     }
1824
1825     fn size_hint(&self) -> (usize, Option<usize>) {
1826         self.inner.size_hint()
1827     }
1828
1829     fn last(mut self) -> Option<K> {
1830         self.next_back()
1831     }
1832
1833     fn min(mut self) -> Option<K> {
1834         self.next()
1835     }
1836
1837     fn max(mut self) -> Option<K> {
1838         self.next_back()
1839     }
1840 }
1841
1842 #[stable(feature = "map_into_keys_values", since = "1.54.0")]
1843 impl<K, V> DoubleEndedIterator for IntoKeys<K, V> {
1844     fn next_back(&mut self) -> Option<K> {
1845         self.inner.next_back().map(|(k, _)| k)
1846     }
1847 }
1848
1849 #[stable(feature = "map_into_keys_values", since = "1.54.0")]
1850 impl<K, V> ExactSizeIterator for IntoKeys<K, V> {
1851     fn len(&self) -> usize {
1852         self.inner.len()
1853     }
1854 }
1855
1856 #[stable(feature = "map_into_keys_values", since = "1.54.0")]
1857 impl<K, V> FusedIterator for IntoKeys<K, V> {}
1858
1859 #[stable(feature = "map_into_keys_values", since = "1.54.0")]
1860 impl<K, V> Iterator for IntoValues<K, V> {
1861     type Item = V;
1862
1863     fn next(&mut self) -> Option<V> {
1864         self.inner.next().map(|(_, v)| v)
1865     }
1866
1867     fn size_hint(&self) -> (usize, Option<usize>) {
1868         self.inner.size_hint()
1869     }
1870
1871     fn last(mut self) -> Option<V> {
1872         self.next_back()
1873     }
1874 }
1875
1876 #[stable(feature = "map_into_keys_values", since = "1.54.0")]
1877 impl<K, V> DoubleEndedIterator for IntoValues<K, V> {
1878     fn next_back(&mut self) -> Option<V> {
1879         self.inner.next_back().map(|(_, v)| v)
1880     }
1881 }
1882
1883 #[stable(feature = "map_into_keys_values", since = "1.54.0")]
1884 impl<K, V> ExactSizeIterator for IntoValues<K, V> {
1885     fn len(&self) -> usize {
1886         self.inner.len()
1887     }
1888 }
1889
1890 #[stable(feature = "map_into_keys_values", since = "1.54.0")]
1891 impl<K, V> FusedIterator for IntoValues<K, V> {}
1892
1893 #[stable(feature = "btree_range", since = "1.17.0")]
1894 impl<'a, K, V> DoubleEndedIterator for Range<'a, K, V> {
1895     fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
1896         self.inner.next_back_checked()
1897     }
1898 }
1899
1900 #[stable(feature = "fused", since = "1.26.0")]
1901 impl<K, V> FusedIterator for Range<'_, K, V> {}
1902
1903 #[stable(feature = "btree_range", since = "1.17.0")]
1904 impl<K, V> Clone for Range<'_, K, V> {
1905     fn clone(&self) -> Self {
1906         Range { inner: self.inner.clone() }
1907     }
1908 }
1909
1910 #[stable(feature = "btree_range", since = "1.17.0")]
1911 impl<'a, K, V> Iterator for RangeMut<'a, K, V> {
1912     type Item = (&'a K, &'a mut V);
1913
1914     fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
1915         self.inner.next_checked()
1916     }
1917
1918     fn last(mut self) -> Option<(&'a K, &'a mut V)> {
1919         self.next_back()
1920     }
1921
1922     fn min(mut self) -> Option<(&'a K, &'a mut V)> {
1923         self.next()
1924     }
1925
1926     fn max(mut self) -> Option<(&'a K, &'a mut V)> {
1927         self.next_back()
1928     }
1929 }
1930
1931 #[stable(feature = "btree_range", since = "1.17.0")]
1932 impl<'a, K, V> DoubleEndedIterator for RangeMut<'a, K, V> {
1933     fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
1934         self.inner.next_back_checked()
1935     }
1936 }
1937
1938 #[stable(feature = "fused", since = "1.26.0")]
1939 impl<K, V> FusedIterator for RangeMut<'_, K, V> {}
1940
1941 #[stable(feature = "rust1", since = "1.0.0")]
1942 impl<K: Ord, V> FromIterator<(K, V)> for BTreeMap<K, V> {
1943     fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> BTreeMap<K, V> {
1944         let mut inputs: Vec<_> = iter.into_iter().collect();
1945
1946         if inputs.is_empty() {
1947             return BTreeMap::new();
1948         }
1949
1950         // use stable sort to preserve the insertion order.
1951         inputs.sort_by(|a, b| a.0.cmp(&b.0));
1952         BTreeMap::bulk_build_from_sorted_iter(inputs)
1953     }
1954 }
1955
1956 #[stable(feature = "rust1", since = "1.0.0")]
1957 impl<K: Ord, V> Extend<(K, V)> for BTreeMap<K, V> {
1958     #[inline]
1959     fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
1960         iter.into_iter().for_each(move |(k, v)| {
1961             self.insert(k, v);
1962         });
1963     }
1964
1965     #[inline]
1966     fn extend_one(&mut self, (k, v): (K, V)) {
1967         self.insert(k, v);
1968     }
1969 }
1970
1971 #[stable(feature = "extend_ref", since = "1.2.0")]
1972 impl<'a, K: Ord + Copy, V: Copy> Extend<(&'a K, &'a V)> for BTreeMap<K, V> {
1973     fn extend<I: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: I) {
1974         self.extend(iter.into_iter().map(|(&key, &value)| (key, value)));
1975     }
1976
1977     #[inline]
1978     fn extend_one(&mut self, (&k, &v): (&'a K, &'a V)) {
1979         self.insert(k, v);
1980     }
1981 }
1982
1983 #[stable(feature = "rust1", since = "1.0.0")]
1984 impl<K: Hash, V: Hash> Hash for BTreeMap<K, V> {
1985     fn hash<H: Hasher>(&self, state: &mut H) {
1986         self.len().hash(state);
1987         for elt in self {
1988             elt.hash(state);
1989         }
1990     }
1991 }
1992
1993 #[stable(feature = "rust1", since = "1.0.0")]
1994 impl<K, V> Default for BTreeMap<K, V> {
1995     /// Creates an empty `BTreeMap`.
1996     fn default() -> BTreeMap<K, V> {
1997         BTreeMap::new()
1998     }
1999 }
2000
2001 #[stable(feature = "rust1", since = "1.0.0")]
2002 impl<K: PartialEq, V: PartialEq> PartialEq for BTreeMap<K, V> {
2003     fn eq(&self, other: &BTreeMap<K, V>) -> bool {
2004         self.len() == other.len() && self.iter().zip(other).all(|(a, b)| a == b)
2005     }
2006 }
2007
2008 #[stable(feature = "rust1", since = "1.0.0")]
2009 impl<K: Eq, V: Eq> Eq for BTreeMap<K, V> {}
2010
2011 #[stable(feature = "rust1", since = "1.0.0")]
2012 impl<K: PartialOrd, V: PartialOrd> PartialOrd for BTreeMap<K, V> {
2013     #[inline]
2014     fn partial_cmp(&self, other: &BTreeMap<K, V>) -> Option<Ordering> {
2015         self.iter().partial_cmp(other.iter())
2016     }
2017 }
2018
2019 #[stable(feature = "rust1", since = "1.0.0")]
2020 impl<K: Ord, V: Ord> Ord for BTreeMap<K, V> {
2021     #[inline]
2022     fn cmp(&self, other: &BTreeMap<K, V>) -> Ordering {
2023         self.iter().cmp(other.iter())
2024     }
2025 }
2026
2027 #[stable(feature = "rust1", since = "1.0.0")]
2028 impl<K: Debug, V: Debug> Debug for BTreeMap<K, V> {
2029     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2030         f.debug_map().entries(self.iter()).finish()
2031     }
2032 }
2033
2034 #[stable(feature = "rust1", since = "1.0.0")]
2035 impl<K, Q: ?Sized, V> Index<&Q> for BTreeMap<K, V>
2036 where
2037     K: Borrow<Q> + Ord,
2038     Q: Ord,
2039 {
2040     type Output = V;
2041
2042     /// Returns a reference to the value corresponding to the supplied key.
2043     ///
2044     /// # Panics
2045     ///
2046     /// Panics if the key is not present in the `BTreeMap`.
2047     #[inline]
2048     fn index(&self, key: &Q) -> &V {
2049         self.get(key).expect("no entry found for key")
2050     }
2051 }
2052
2053 #[stable(feature = "std_collections_from_array", since = "1.56.0")]
2054 impl<K: Ord, V, const N: usize> From<[(K, V); N]> for BTreeMap<K, V> {
2055     /// Converts a `[(K, V); N]` into a `BTreeMap<(K, V)>`.
2056     ///
2057     /// ```
2058     /// use std::collections::BTreeMap;
2059     ///
2060     /// let map1 = BTreeMap::from([(1, 2), (3, 4)]);
2061     /// let map2: BTreeMap<_, _> = [(1, 2), (3, 4)].into();
2062     /// assert_eq!(map1, map2);
2063     /// ```
2064     fn from(mut arr: [(K, V); N]) -> Self {
2065         if N == 0 {
2066             return BTreeMap::new();
2067         }
2068
2069         // use stable sort to preserve the insertion order.
2070         arr.sort_by(|a, b| a.0.cmp(&b.0));
2071         BTreeMap::bulk_build_from_sorted_iter(arr)
2072     }
2073 }
2074
2075 impl<K, V> BTreeMap<K, V> {
2076     /// Gets an iterator over the entries of the map, sorted by key.
2077     ///
2078     /// # Examples
2079     ///
2080     /// Basic usage:
2081     ///
2082     /// ```
2083     /// use std::collections::BTreeMap;
2084     ///
2085     /// let mut map = BTreeMap::new();
2086     /// map.insert(3, "c");
2087     /// map.insert(2, "b");
2088     /// map.insert(1, "a");
2089     ///
2090     /// for (key, value) in map.iter() {
2091     ///     println!("{}: {}", key, value);
2092     /// }
2093     ///
2094     /// let (first_key, first_value) = map.iter().next().unwrap();
2095     /// assert_eq!((*first_key, *first_value), (1, "a"));
2096     /// ```
2097     #[stable(feature = "rust1", since = "1.0.0")]
2098     pub fn iter(&self) -> Iter<'_, K, V> {
2099         if let Some(root) = &self.root {
2100             let full_range = root.reborrow().full_range();
2101
2102             Iter { range: full_range, length: self.length }
2103         } else {
2104             Iter { range: LazyLeafRange::none(), length: 0 }
2105         }
2106     }
2107
2108     /// Gets a mutable iterator over the entries of the map, sorted by key.
2109     ///
2110     /// # Examples
2111     ///
2112     /// Basic usage:
2113     ///
2114     /// ```
2115     /// use std::collections::BTreeMap;
2116     ///
2117     /// let mut map = BTreeMap::from([
2118     ///    ("a", 1),
2119     ///    ("b", 2),
2120     ///    ("c", 3),
2121     /// ]);
2122     ///
2123     /// // add 10 to the value if the key isn't "a"
2124     /// for (key, value) in map.iter_mut() {
2125     ///     if key != &"a" {
2126     ///         *value += 10;
2127     ///     }
2128     /// }
2129     /// ```
2130     #[stable(feature = "rust1", since = "1.0.0")]
2131     pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
2132         if let Some(root) = &mut self.root {
2133             let full_range = root.borrow_valmut().full_range();
2134
2135             IterMut { range: full_range, length: self.length, _marker: PhantomData }
2136         } else {
2137             IterMut { range: LazyLeafRange::none(), length: 0, _marker: PhantomData }
2138         }
2139     }
2140
2141     /// Gets an iterator over the keys of the map, in sorted order.
2142     ///
2143     /// # Examples
2144     ///
2145     /// Basic usage:
2146     ///
2147     /// ```
2148     /// use std::collections::BTreeMap;
2149     ///
2150     /// let mut a = BTreeMap::new();
2151     /// a.insert(2, "b");
2152     /// a.insert(1, "a");
2153     ///
2154     /// let keys: Vec<_> = a.keys().cloned().collect();
2155     /// assert_eq!(keys, [1, 2]);
2156     /// ```
2157     #[stable(feature = "rust1", since = "1.0.0")]
2158     pub fn keys(&self) -> Keys<'_, K, V> {
2159         Keys { inner: self.iter() }
2160     }
2161
2162     /// Gets an iterator over the values of the map, in order by key.
2163     ///
2164     /// # Examples
2165     ///
2166     /// Basic usage:
2167     ///
2168     /// ```
2169     /// use std::collections::BTreeMap;
2170     ///
2171     /// let mut a = BTreeMap::new();
2172     /// a.insert(1, "hello");
2173     /// a.insert(2, "goodbye");
2174     ///
2175     /// let values: Vec<&str> = a.values().cloned().collect();
2176     /// assert_eq!(values, ["hello", "goodbye"]);
2177     /// ```
2178     #[stable(feature = "rust1", since = "1.0.0")]
2179     pub fn values(&self) -> Values<'_, K, V> {
2180         Values { inner: self.iter() }
2181     }
2182
2183     /// Gets a mutable iterator over the values of the map, in order by key.
2184     ///
2185     /// # Examples
2186     ///
2187     /// Basic usage:
2188     ///
2189     /// ```
2190     /// use std::collections::BTreeMap;
2191     ///
2192     /// let mut a = BTreeMap::new();
2193     /// a.insert(1, String::from("hello"));
2194     /// a.insert(2, String::from("goodbye"));
2195     ///
2196     /// for value in a.values_mut() {
2197     ///     value.push_str("!");
2198     /// }
2199     ///
2200     /// let values: Vec<String> = a.values().cloned().collect();
2201     /// assert_eq!(values, [String::from("hello!"),
2202     ///                     String::from("goodbye!")]);
2203     /// ```
2204     #[stable(feature = "map_values_mut", since = "1.10.0")]
2205     pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {
2206         ValuesMut { inner: self.iter_mut() }
2207     }
2208
2209     /// Returns the number of elements in the map.
2210     ///
2211     /// # Examples
2212     ///
2213     /// Basic usage:
2214     ///
2215     /// ```
2216     /// use std::collections::BTreeMap;
2217     ///
2218     /// let mut a = BTreeMap::new();
2219     /// assert_eq!(a.len(), 0);
2220     /// a.insert(1, "a");
2221     /// assert_eq!(a.len(), 1);
2222     /// ```
2223     #[must_use]
2224     #[stable(feature = "rust1", since = "1.0.0")]
2225     #[rustc_const_unstable(feature = "const_btree_new", issue = "71835")]
2226     pub const fn len(&self) -> usize {
2227         self.length
2228     }
2229
2230     /// Returns `true` if the map contains no elements.
2231     ///
2232     /// # Examples
2233     ///
2234     /// Basic usage:
2235     ///
2236     /// ```
2237     /// use std::collections::BTreeMap;
2238     ///
2239     /// let mut a = BTreeMap::new();
2240     /// assert!(a.is_empty());
2241     /// a.insert(1, "a");
2242     /// assert!(!a.is_empty());
2243     /// ```
2244     #[must_use]
2245     #[stable(feature = "rust1", since = "1.0.0")]
2246     #[rustc_const_unstable(feature = "const_btree_new", issue = "71835")]
2247     pub const fn is_empty(&self) -> bool {
2248         self.len() == 0
2249     }
2250
2251     /// If the root node is the empty (non-allocated) root node, allocate our
2252     /// own node. Is an associated function to avoid borrowing the entire BTreeMap.
2253     fn ensure_is_owned(root: &mut Option<Root<K, V>>) -> &mut Root<K, V> {
2254         root.get_or_insert_with(Root::new)
2255     }
2256 }
2257
2258 #[cfg(test)]
2259 mod tests;