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};
12 use crate::alloc::{Allocator, Global};
14 use super::borrow::DormantMutRef;
15 use super::dedup_sorted_iter::DedupSortedIter;
16 use super::navigate::{LazyLeafRange, LeafRange};
17 use super::node::{self, marker, ForceResult::*, Handle, NodeRef, Root};
18 use super::search::SearchResult::*;
19 use super::set_val::SetValZST;
23 #[stable(feature = "rust1", since = "1.0.0")]
24 pub use entry::{Entry, OccupiedEntry, OccupiedError, VacantEntry};
28 /// Minimum number of elements in a node that is not a root.
29 /// We might temporarily have fewer elements during methods.
30 pub(super) const MIN_LEN: usize = node::MIN_LEN_AFTER_SPLIT;
32 // A tree in a `BTreeMap` is a tree in the `node` module with additional invariants:
33 // - Keys must appear in ascending order (according to the key's type).
34 // - Every non-leaf node contains at least 1 element (has at least 2 children).
35 // - Every non-root node contains at least MIN_LEN elements.
37 // An empty map is represented either by the absence of a root node or by a
38 // root node that is an empty leaf.
40 /// An ordered map based on a [B-Tree].
42 /// B-Trees represent a fundamental compromise between cache-efficiency and actually minimizing
43 /// the amount of work performed in a search. In theory, a binary search tree (BST) is the optimal
44 /// choice for a sorted map, as a perfectly balanced BST performs the theoretical minimum amount of
45 /// comparisons necessary to find an element (log<sub>2</sub>n). However, in practice the way this
46 /// is done is *very* inefficient for modern computer architectures. In particular, every element
47 /// is stored in its own individually heap-allocated node. This means that every single insertion
48 /// triggers a heap-allocation, and every single comparison should be a cache-miss. Since these
49 /// are both notably expensive things to do in practice, we are forced to, at the very least,
50 /// reconsider the BST strategy.
52 /// A B-Tree instead makes each node contain B-1 to 2B-1 elements in a contiguous array. By doing
53 /// this, we reduce the number of allocations by a factor of B, and improve cache efficiency in
54 /// searches. However, this does mean that searches will have to do *more* comparisons on average.
55 /// The precise number of comparisons depends on the node search strategy used. For optimal cache
56 /// efficiency, one could search the nodes linearly. For optimal comparisons, one could search
57 /// the node using binary search. As a compromise, one could also perform a linear search
58 /// that initially only checks every i<sup>th</sup> element for some choice of i.
60 /// Currently, our implementation simply performs naive linear search. This provides excellent
61 /// performance on *small* nodes of elements which are cheap to compare. However in the future we
62 /// would like to further explore choosing the optimal search strategy based on the choice of B,
63 /// and possibly other factors. Using linear search, searching for a random element is expected
64 /// to take B * log(n) comparisons, which is generally worse than a BST. In practice,
65 /// however, performance is excellent.
67 /// It is a logic error for a key to be modified in such a way that the key's ordering relative to
68 /// any other key, as determined by the [`Ord`] trait, changes while it is in the map. This is
69 /// normally only possible through [`Cell`], [`RefCell`], global state, I/O, or unsafe code.
70 /// The behavior resulting from such a logic error is not specified, but will be encapsulated to the
71 /// `BTreeMap` that observed the logic error and not result in undefined behavior. This could
72 /// include panics, incorrect results, aborts, memory leaks, and non-termination.
74 /// Iterators obtained from functions such as [`BTreeMap::iter`], [`BTreeMap::values`], or
75 /// [`BTreeMap::keys`] produce their items in order by key, and take worst-case logarithmic and
76 /// amortized constant time per item returned.
78 /// [B-Tree]: https://en.wikipedia.org/wiki/B-tree
79 /// [`Cell`]: core::cell::Cell
80 /// [`RefCell`]: core::cell::RefCell
85 /// use std::collections::BTreeMap;
87 /// // type inference lets us omit an explicit type signature (which
88 /// // would be `BTreeMap<&str, &str>` in this example).
89 /// let mut movie_reviews = BTreeMap::new();
91 /// // review some movies.
92 /// movie_reviews.insert("Office Space", "Deals with real issues in the workplace.");
93 /// movie_reviews.insert("Pulp Fiction", "Masterpiece.");
94 /// movie_reviews.insert("The Godfather", "Very enjoyable.");
95 /// movie_reviews.insert("The Blues Brothers", "Eye lyked it a lot.");
97 /// // check for a specific one.
98 /// if !movie_reviews.contains_key("Les Misérables") {
99 /// println!("We've got {} reviews, but Les Misérables ain't one.",
100 /// movie_reviews.len());
103 /// // oops, this review has a lot of spelling mistakes, let's delete it.
104 /// movie_reviews.remove("The Blues Brothers");
106 /// // look up the values associated with some keys.
107 /// let to_find = ["Up!", "Office Space"];
108 /// for movie in &to_find {
109 /// match movie_reviews.get(movie) {
110 /// Some(review) => println!("{movie}: {review}"),
111 /// None => println!("{movie} is unreviewed.")
115 /// // Look up the value for a key (will panic if the key is not found).
116 /// println!("Movie review: {}", movie_reviews["Office Space"]);
118 /// // iterate over everything.
119 /// for (movie, review) in &movie_reviews {
120 /// println!("{movie}: \"{review}\"");
124 /// A `BTreeMap` with a known list of items can be initialized from an array:
127 /// use std::collections::BTreeMap;
129 /// let solar_distance = BTreeMap::from([
130 /// ("Mercury", 0.4),
137 /// `BTreeMap` implements an [`Entry API`], which allows for complex
138 /// methods of getting, setting, updating and removing keys and their values:
140 /// [`Entry API`]: BTreeMap::entry
143 /// use std::collections::BTreeMap;
145 /// // type inference lets us omit an explicit type signature (which
146 /// // would be `BTreeMap<&str, u8>` in this example).
147 /// let mut player_stats = BTreeMap::new();
149 /// fn random_stat_buff() -> u8 {
150 /// // could actually return some random value here - let's just return
151 /// // some fixed value for now
155 /// // insert a key only if it doesn't already exist
156 /// player_stats.entry("health").or_insert(100);
158 /// // insert a key using a function that provides a new value only if it
159 /// // doesn't already exist
160 /// player_stats.entry("defence").or_insert_with(random_stat_buff);
162 /// // update a key, guarding against the key possibly not being set
163 /// let stat = player_stats.entry("attack").or_insert(100);
164 /// *stat += random_stat_buff();
166 /// // modify an entry before an insert with in-place mutation
167 /// player_stats.entry("mana").and_modify(|mana| *mana += 200).or_insert(100);
169 #[stable(feature = "rust1", since = "1.0.0")]
170 #[cfg_attr(not(test), rustc_diagnostic_item = "BTreeMap")]
171 #[rustc_insignificant_dtor]
175 #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + Clone = Global,
177 root: Option<Root<K, V>>,
179 /// `ManuallyDrop` to control drop order (needs to be dropped after all the nodes).
180 pub(super) alloc: ManuallyDrop<A>,
181 // For dropck; the `Box` avoids making the `Unpin` impl more strict than before
182 _marker: PhantomData<crate::boxed::Box<(K, V)>>,
185 #[stable(feature = "btree_drop", since = "1.7.0")]
186 unsafe impl<#[may_dangle] K, #[may_dangle] V, A: Allocator + Clone> Drop for BTreeMap<K, V, A> {
188 drop(unsafe { ptr::read(self) }.into_iter())
192 // FIXME: This implementation is "wrong", but changing it would be a breaking change.
193 // (The bounds of the automatic `UnwindSafe` implementation have been like this since Rust 1.50.)
194 // Maybe we can fix it nonetheless with a crater run, or if the `UnwindSafe`
195 // traits are deprecated, or disarmed (no longer causing hard errors) in the future.
196 #[stable(feature = "btree_unwindsafe", since = "1.64.0")]
197 impl<K, V, A: Allocator + Clone> core::panic::UnwindSafe for BTreeMap<K, V, A>
199 A: core::panic::UnwindSafe,
200 K: core::panic::RefUnwindSafe,
201 V: core::panic::RefUnwindSafe,
205 #[stable(feature = "rust1", since = "1.0.0")]
206 impl<K: Clone, V: Clone, A: Allocator + Clone> Clone for BTreeMap<K, V, A> {
207 fn clone(&self) -> BTreeMap<K, V, A> {
208 fn clone_subtree<'a, K: Clone, V: Clone, A: Allocator + Clone>(
209 node: NodeRef<marker::Immut<'a>, K, V, marker::LeafOrInternal>,
211 ) -> BTreeMap<K, V, A>
218 let mut out_tree = BTreeMap {
219 root: Some(Root::new(alloc.clone())),
221 alloc: ManuallyDrop::new(alloc),
222 _marker: PhantomData,
226 let root = out_tree.root.as_mut().unwrap(); // unwrap succeeds because we just wrapped
227 let mut out_node = match root.borrow_mut().force() {
229 Internal(_) => unreachable!(),
232 let mut in_edge = leaf.first_edge();
233 while let Ok(kv) = in_edge.right_kv() {
234 let (k, v) = kv.into_kv();
235 in_edge = kv.right_edge();
237 out_node.push(k.clone(), v.clone());
238 out_tree.length += 1;
244 Internal(internal) => {
246 clone_subtree(internal.first_edge().descend(), alloc.clone());
249 let out_root = out_tree.root.as_mut().unwrap();
250 let mut out_node = out_root.push_internal_level(alloc.clone());
251 let mut in_edge = internal.first_edge();
252 while let Ok(kv) = in_edge.right_kv() {
253 let (k, v) = kv.into_kv();
254 in_edge = kv.right_edge();
256 let k = (*k).clone();
257 let v = (*v).clone();
258 let subtree = clone_subtree(in_edge.descend(), alloc.clone());
260 // We can't destructure subtree directly
261 // because BTreeMap implements Drop
262 let (subroot, sublength) = unsafe {
263 let subtree = ManuallyDrop::new(subtree);
264 let root = ptr::read(&subtree.root);
265 let length = subtree.length;
272 subroot.unwrap_or_else(|| Root::new(alloc.clone())),
274 out_tree.length += 1 + sublength;
284 BTreeMap::new_in((*self.alloc).clone())
286 clone_subtree(self.root.as_ref().unwrap().reborrow(), (*self.alloc).clone()) // unwrap succeeds because not empty
291 impl<K, Q: ?Sized, A: Allocator + Clone> super::Recover<Q> for BTreeMap<K, SetValZST, A>
298 fn get(&self, key: &Q) -> Option<&K> {
299 let root_node = self.root.as_ref()?.reborrow();
300 match root_node.search_tree(key) {
301 Found(handle) => Some(handle.into_kv().0),
306 fn take(&mut self, key: &Q) -> Option<K> {
307 let (map, dormant_map) = DormantMutRef::new(self);
308 let root_node = map.root.as_mut()?.borrow_mut();
309 match root_node.search_tree(key) {
310 Found(handle) => Some(
314 alloc: (*map.alloc).clone(),
315 _marker: PhantomData,
324 fn replace(&mut self, key: K) -> Option<K> {
325 let (map, dormant_map) = DormantMutRef::new(self);
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)),
333 handle: Some(handle),
335 alloc: (*map.alloc).clone(),
336 _marker: PhantomData,
338 .insert(SetValZST::default());
345 /// An iterator over the entries of a `BTreeMap`.
347 /// This `struct` is created by the [`iter`] method on [`BTreeMap`]. See its
348 /// documentation for more.
350 /// [`iter`]: BTreeMap::iter
351 #[must_use = "iterators are lazy and do nothing unless consumed"]
352 #[stable(feature = "rust1", since = "1.0.0")]
353 pub struct Iter<'a, K: 'a, V: 'a> {
354 range: LazyLeafRange<marker::Immut<'a>, K, V>,
358 #[stable(feature = "collection_debug", since = "1.17.0")]
359 impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Iter<'_, K, V> {
360 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
361 f.debug_list().entries(self.clone()).finish()
365 /// A mutable iterator over the entries of a `BTreeMap`.
367 /// This `struct` is created by the [`iter_mut`] method on [`BTreeMap`]. See its
368 /// documentation for more.
370 /// [`iter_mut`]: BTreeMap::iter_mut
371 #[stable(feature = "rust1", since = "1.0.0")]
372 pub struct IterMut<'a, K: 'a, V: 'a> {
373 range: LazyLeafRange<marker::ValMut<'a>, K, V>,
376 // Be invariant in `K` and `V`
377 _marker: PhantomData<&'a mut (K, V)>,
380 #[must_use = "iterators are lazy and do nothing unless consumed"]
381 #[stable(feature = "collection_debug", since = "1.17.0")]
382 impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IterMut<'_, K, V> {
383 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
384 let range = Iter { range: self.range.reborrow(), length: self.length };
385 f.debug_list().entries(range).finish()
389 /// An owning iterator over the entries of a `BTreeMap`.
391 /// This `struct` is created by the [`into_iter`] method on [`BTreeMap`]
392 /// (provided by the [`IntoIterator`] trait). See its documentation for more.
394 /// [`into_iter`]: IntoIterator::into_iter
395 /// [`IntoIterator`]: core::iter::IntoIterator
396 #[stable(feature = "rust1", since = "1.0.0")]
397 #[rustc_insignificant_dtor]
401 #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + Clone = Global,
403 range: LazyLeafRange<marker::Dying, K, V>,
405 /// The BTreeMap will outlive this IntoIter so we don't care about drop order for `alloc`.
409 impl<K, V, A: Allocator + Clone> IntoIter<K, V, A> {
410 /// Returns an iterator of references over the remaining items.
412 pub(super) fn iter(&self) -> Iter<'_, K, V> {
413 Iter { range: self.range.reborrow(), length: self.length }
417 #[stable(feature = "collection_debug", since = "1.17.0")]
418 impl<K: Debug, V: Debug, A: Allocator + Clone> Debug for IntoIter<K, V, A> {
419 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
420 f.debug_list().entries(self.iter()).finish()
424 /// An iterator over the keys of a `BTreeMap`.
426 /// This `struct` is created by the [`keys`] method on [`BTreeMap`]. See its
427 /// documentation for more.
429 /// [`keys`]: BTreeMap::keys
430 #[must_use = "iterators are lazy and do nothing unless consumed"]
431 #[stable(feature = "rust1", since = "1.0.0")]
432 pub struct Keys<'a, K, V> {
433 inner: Iter<'a, K, V>,
436 #[stable(feature = "collection_debug", since = "1.17.0")]
437 impl<K: fmt::Debug, V> fmt::Debug for Keys<'_, K, V> {
438 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
439 f.debug_list().entries(self.clone()).finish()
443 /// An iterator over the values of a `BTreeMap`.
445 /// This `struct` is created by the [`values`] method on [`BTreeMap`]. See its
446 /// documentation for more.
448 /// [`values`]: BTreeMap::values
449 #[must_use = "iterators are lazy and do nothing unless consumed"]
450 #[stable(feature = "rust1", since = "1.0.0")]
451 pub struct Values<'a, K, V> {
452 inner: Iter<'a, K, V>,
455 #[stable(feature = "collection_debug", since = "1.17.0")]
456 impl<K, V: fmt::Debug> fmt::Debug for Values<'_, K, V> {
457 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
458 f.debug_list().entries(self.clone()).finish()
462 /// A mutable iterator over the values of a `BTreeMap`.
464 /// This `struct` is created by the [`values_mut`] method on [`BTreeMap`]. See its
465 /// documentation for more.
467 /// [`values_mut`]: BTreeMap::values_mut
468 #[must_use = "iterators are lazy and do nothing unless consumed"]
469 #[stable(feature = "map_values_mut", since = "1.10.0")]
470 pub struct ValuesMut<'a, K, V> {
471 inner: IterMut<'a, K, V>,
474 #[stable(feature = "map_values_mut", since = "1.10.0")]
475 impl<K, V: fmt::Debug> fmt::Debug for ValuesMut<'_, K, V> {
476 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
477 f.debug_list().entries(self.inner.iter().map(|(_, val)| val)).finish()
481 /// An owning iterator over the keys of a `BTreeMap`.
483 /// This `struct` is created by the [`into_keys`] method on [`BTreeMap`].
484 /// See its documentation for more.
486 /// [`into_keys`]: BTreeMap::into_keys
487 #[must_use = "iterators are lazy and do nothing unless consumed"]
488 #[stable(feature = "map_into_keys_values", since = "1.54.0")]
489 pub struct IntoKeys<K, V, A: Allocator + Clone = Global> {
490 inner: IntoIter<K, V, A>,
493 #[stable(feature = "map_into_keys_values", since = "1.54.0")]
494 impl<K: fmt::Debug, V, A: Allocator + Clone> fmt::Debug for IntoKeys<K, V, A> {
495 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
496 f.debug_list().entries(self.inner.iter().map(|(key, _)| key)).finish()
500 /// An owning iterator over the values of a `BTreeMap`.
502 /// This `struct` is created by the [`into_values`] method on [`BTreeMap`].
503 /// See its documentation for more.
505 /// [`into_values`]: BTreeMap::into_values
506 #[must_use = "iterators are lazy and do nothing unless consumed"]
507 #[stable(feature = "map_into_keys_values", since = "1.54.0")]
508 pub struct IntoValues<
511 #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + Clone = Global,
513 inner: IntoIter<K, V, A>,
516 #[stable(feature = "map_into_keys_values", since = "1.54.0")]
517 impl<K, V: fmt::Debug, A: Allocator + Clone> fmt::Debug for IntoValues<K, V, A> {
518 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
519 f.debug_list().entries(self.inner.iter().map(|(_, val)| val)).finish()
523 /// An iterator over a sub-range of entries in a `BTreeMap`.
525 /// This `struct` is created by the [`range`] method on [`BTreeMap`]. See its
526 /// documentation for more.
528 /// [`range`]: BTreeMap::range
529 #[must_use = "iterators are lazy and do nothing unless consumed"]
530 #[stable(feature = "btree_range", since = "1.17.0")]
531 pub struct Range<'a, K: 'a, V: 'a> {
532 inner: LeafRange<marker::Immut<'a>, K, V>,
535 #[stable(feature = "collection_debug", since = "1.17.0")]
536 impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Range<'_, K, V> {
537 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
538 f.debug_list().entries(self.clone()).finish()
542 /// A mutable iterator over a sub-range of entries in a `BTreeMap`.
544 /// This `struct` is created by the [`range_mut`] method on [`BTreeMap`]. See its
545 /// documentation for more.
547 /// [`range_mut`]: BTreeMap::range_mut
548 #[must_use = "iterators are lazy and do nothing unless consumed"]
549 #[stable(feature = "btree_range", since = "1.17.0")]
550 pub struct RangeMut<'a, K: 'a, V: 'a> {
551 inner: LeafRange<marker::ValMut<'a>, K, V>,
553 // Be invariant in `K` and `V`
554 _marker: PhantomData<&'a mut (K, V)>,
557 #[stable(feature = "collection_debug", since = "1.17.0")]
558 impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for RangeMut<'_, K, V> {
559 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
560 let range = Range { inner: self.inner.reborrow() };
561 f.debug_list().entries(range).finish()
565 impl<K, V> BTreeMap<K, V> {
566 /// Makes a new, empty `BTreeMap`.
568 /// Does not allocate anything on its own.
575 /// use std::collections::BTreeMap;
577 /// let mut map = BTreeMap::new();
579 /// // entries can now be inserted into the empty map
580 /// map.insert(1, "a");
582 #[stable(feature = "rust1", since = "1.0.0")]
583 #[rustc_const_stable(feature = "const_btree_new", since = "1.66.0")]
585 pub const fn new() -> BTreeMap<K, V> {
586 BTreeMap { root: None, length: 0, alloc: ManuallyDrop::new(Global), _marker: PhantomData }
590 impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> {
591 /// Clears the map, removing all elements.
598 /// use std::collections::BTreeMap;
600 /// let mut a = BTreeMap::new();
601 /// a.insert(1, "a");
603 /// assert!(a.is_empty());
605 #[stable(feature = "rust1", since = "1.0.0")]
606 pub fn clear(&mut self) {
607 // avoid moving the allocator
609 root: mem::replace(&mut self.root, None),
610 length: mem::replace(&mut self.length, 0),
611 alloc: self.alloc.clone(),
612 _marker: PhantomData,
616 /// Makes a new empty BTreeMap with a reasonable choice for B.
623 /// # #![feature(allocator_api)]
624 /// # #![feature(btreemap_alloc)]
625 /// use std::collections::BTreeMap;
626 /// use std::alloc::Global;
628 /// let mut map = BTreeMap::new_in(Global);
630 /// // entries can now be inserted into the empty map
631 /// map.insert(1, "a");
633 #[unstable(feature = "btreemap_alloc", issue = "32838")]
634 pub fn new_in(alloc: A) -> BTreeMap<K, V, A> {
635 BTreeMap { root: None, length: 0, alloc: ManuallyDrop::new(alloc), _marker: PhantomData }
639 impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> {
640 /// Returns a reference to the value corresponding to the key.
642 /// The key may be any borrowed form of the map's key type, but the ordering
643 /// on the borrowed form *must* match the ordering on the key type.
650 /// use std::collections::BTreeMap;
652 /// let mut map = BTreeMap::new();
653 /// map.insert(1, "a");
654 /// assert_eq!(map.get(&1), Some(&"a"));
655 /// assert_eq!(map.get(&2), None);
657 #[stable(feature = "rust1", since = "1.0.0")]
658 pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V>
663 let root_node = self.root.as_ref()?.reborrow();
664 match root_node.search_tree(key) {
665 Found(handle) => Some(handle.into_kv().1),
670 /// Returns the key-value pair corresponding to the supplied key.
672 /// The supplied key may be any borrowed form of the map's key type, but the ordering
673 /// on the borrowed form *must* match the ordering on the key type.
678 /// use std::collections::BTreeMap;
680 /// let mut map = BTreeMap::new();
681 /// map.insert(1, "a");
682 /// assert_eq!(map.get_key_value(&1), Some((&1, &"a")));
683 /// assert_eq!(map.get_key_value(&2), None);
685 #[stable(feature = "map_get_key_value", since = "1.40.0")]
686 pub fn get_key_value<Q: ?Sized>(&self, k: &Q) -> Option<(&K, &V)>
691 let root_node = self.root.as_ref()?.reborrow();
692 match root_node.search_tree(k) {
693 Found(handle) => Some(handle.into_kv()),
698 /// Returns the first key-value pair in the map.
699 /// The key in this pair is the minimum key in the map.
706 /// use std::collections::BTreeMap;
708 /// let mut map = BTreeMap::new();
709 /// assert_eq!(map.first_key_value(), None);
710 /// map.insert(1, "b");
711 /// map.insert(2, "a");
712 /// assert_eq!(map.first_key_value(), Some((&1, &"b")));
714 #[stable(feature = "map_first_last", since = "1.66.0")]
715 pub fn first_key_value(&self) -> Option<(&K, &V)>
719 let root_node = self.root.as_ref()?.reborrow();
720 root_node.first_leaf_edge().right_kv().ok().map(Handle::into_kv)
723 /// Returns the first entry in the map for in-place manipulation.
724 /// The key of this entry is the minimum key in the map.
729 /// use std::collections::BTreeMap;
731 /// let mut map = BTreeMap::new();
732 /// map.insert(1, "a");
733 /// map.insert(2, "b");
734 /// if let Some(mut entry) = map.first_entry() {
735 /// if *entry.key() > 0 {
736 /// entry.insert("first");
739 /// assert_eq!(*map.get(&1).unwrap(), "first");
740 /// assert_eq!(*map.get(&2).unwrap(), "b");
742 #[stable(feature = "map_first_last", since = "1.66.0")]
743 pub fn first_entry(&mut self) -> Option<OccupiedEntry<'_, K, V, A>>
747 let (map, dormant_map) = DormantMutRef::new(self);
748 let root_node = map.root.as_mut()?.borrow_mut();
749 let kv = root_node.first_leaf_edge().right_kv().ok()?;
751 handle: kv.forget_node_type(),
753 alloc: (*map.alloc).clone(),
754 _marker: PhantomData,
758 /// Removes and returns the first element in the map.
759 /// The key of this element is the minimum key that was in the map.
763 /// Draining elements in ascending order, while keeping a usable map each iteration.
766 /// use std::collections::BTreeMap;
768 /// let mut map = BTreeMap::new();
769 /// map.insert(1, "a");
770 /// map.insert(2, "b");
771 /// while let Some((key, _val)) = map.pop_first() {
772 /// assert!(map.iter().all(|(k, _v)| *k > key));
774 /// assert!(map.is_empty());
776 #[stable(feature = "map_first_last", since = "1.66.0")]
777 pub fn pop_first(&mut self) -> Option<(K, V)>
781 self.first_entry().map(|entry| entry.remove_entry())
784 /// Returns the last key-value pair in the map.
785 /// The key in this pair is the maximum key in the map.
792 /// use std::collections::BTreeMap;
794 /// let mut map = BTreeMap::new();
795 /// map.insert(1, "b");
796 /// map.insert(2, "a");
797 /// assert_eq!(map.last_key_value(), Some((&2, &"a")));
799 #[stable(feature = "map_first_last", since = "1.66.0")]
800 pub fn last_key_value(&self) -> Option<(&K, &V)>
804 let root_node = self.root.as_ref()?.reborrow();
805 root_node.last_leaf_edge().left_kv().ok().map(Handle::into_kv)
808 /// Returns the last entry in the map for in-place manipulation.
809 /// The key of this entry is the maximum key in the map.
814 /// use std::collections::BTreeMap;
816 /// let mut map = BTreeMap::new();
817 /// map.insert(1, "a");
818 /// map.insert(2, "b");
819 /// if let Some(mut entry) = map.last_entry() {
820 /// if *entry.key() > 0 {
821 /// entry.insert("last");
824 /// assert_eq!(*map.get(&1).unwrap(), "a");
825 /// assert_eq!(*map.get(&2).unwrap(), "last");
827 #[stable(feature = "map_first_last", since = "1.66.0")]
828 pub fn last_entry(&mut self) -> Option<OccupiedEntry<'_, K, V, A>>
832 let (map, dormant_map) = DormantMutRef::new(self);
833 let root_node = map.root.as_mut()?.borrow_mut();
834 let kv = root_node.last_leaf_edge().left_kv().ok()?;
836 handle: kv.forget_node_type(),
838 alloc: (*map.alloc).clone(),
839 _marker: PhantomData,
843 /// Removes and returns the last element in the map.
844 /// The key of this element is the maximum key that was in the map.
848 /// Draining elements in descending order, while keeping a usable map each iteration.
851 /// use std::collections::BTreeMap;
853 /// let mut map = BTreeMap::new();
854 /// map.insert(1, "a");
855 /// map.insert(2, "b");
856 /// while let Some((key, _val)) = map.pop_last() {
857 /// assert!(map.iter().all(|(k, _v)| *k < key));
859 /// assert!(map.is_empty());
861 #[stable(feature = "map_first_last", since = "1.66.0")]
862 pub fn pop_last(&mut self) -> Option<(K, V)>
866 self.last_entry().map(|entry| entry.remove_entry())
869 /// Returns `true` if the map contains a value for the specified key.
871 /// The key may be any borrowed form of the map's key type, but the ordering
872 /// on the borrowed form *must* match the ordering on the key type.
879 /// use std::collections::BTreeMap;
881 /// let mut map = BTreeMap::new();
882 /// map.insert(1, "a");
883 /// assert_eq!(map.contains_key(&1), true);
884 /// assert_eq!(map.contains_key(&2), false);
886 #[stable(feature = "rust1", since = "1.0.0")]
887 pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool
892 self.get(key).is_some()
895 /// Returns a mutable reference to the value corresponding to the key.
897 /// The key may be any borrowed form of the map's key type, but the ordering
898 /// on the borrowed form *must* match the ordering on the key type.
905 /// use std::collections::BTreeMap;
907 /// let mut map = BTreeMap::new();
908 /// map.insert(1, "a");
909 /// if let Some(x) = map.get_mut(&1) {
912 /// assert_eq!(map[&1], "b");
914 // See `get` for implementation notes, this is basically a copy-paste with mut's added
915 #[stable(feature = "rust1", since = "1.0.0")]
916 pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>
921 let root_node = self.root.as_mut()?.borrow_mut();
922 match root_node.search_tree(key) {
923 Found(handle) => Some(handle.into_val_mut()),
928 /// Inserts a key-value pair into the map.
930 /// If the map did not have this key present, `None` is returned.
932 /// If the map did have this key present, the value is updated, and the old
933 /// value is returned. The key is not updated, though; this matters for
934 /// types that can be `==` without being identical. See the [module-level
935 /// documentation] for more.
937 /// [module-level documentation]: index.html#insert-and-complex-keys
944 /// use std::collections::BTreeMap;
946 /// let mut map = BTreeMap::new();
947 /// assert_eq!(map.insert(37, "a"), None);
948 /// assert_eq!(map.is_empty(), false);
950 /// map.insert(37, "b");
951 /// assert_eq!(map.insert(37, "c"), Some("b"));
952 /// assert_eq!(map[&37], "c");
954 #[stable(feature = "rust1", since = "1.0.0")]
955 pub fn insert(&mut self, key: K, value: V) -> Option<V>
959 match self.entry(key) {
960 Occupied(mut entry) => Some(entry.insert(value)),
968 /// Tries to insert a key-value pair into the map, and returns
969 /// a mutable reference to the value in the entry.
971 /// If the map already had this key present, nothing is updated, and
972 /// an error containing the occupied entry and the value is returned.
979 /// #![feature(map_try_insert)]
981 /// use std::collections::BTreeMap;
983 /// let mut map = BTreeMap::new();
984 /// assert_eq!(map.try_insert(37, "a").unwrap(), &"a");
986 /// let err = map.try_insert(37, "b").unwrap_err();
987 /// assert_eq!(err.entry.key(), &37);
988 /// assert_eq!(err.entry.get(), &"a");
989 /// assert_eq!(err.value, "b");
991 #[unstable(feature = "map_try_insert", issue = "82766")]
992 pub fn try_insert(&mut self, key: K, value: V) -> Result<&mut V, OccupiedError<'_, K, V, A>>
996 match self.entry(key) {
997 Occupied(entry) => Err(OccupiedError { entry, value }),
998 Vacant(entry) => Ok(entry.insert(value)),
1002 /// Removes a key from the map, returning the value at the key if the key
1003 /// was previously in the map.
1005 /// The key may be any borrowed form of the map's key type, but the ordering
1006 /// on the borrowed form *must* match the ordering on the key type.
1013 /// use std::collections::BTreeMap;
1015 /// let mut map = BTreeMap::new();
1016 /// map.insert(1, "a");
1017 /// assert_eq!(map.remove(&1), Some("a"));
1018 /// assert_eq!(map.remove(&1), None);
1020 #[stable(feature = "rust1", since = "1.0.0")]
1021 pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V>
1026 self.remove_entry(key).map(|(_, v)| v)
1029 /// Removes a key from the map, returning the stored key and value if the key
1030 /// was previously in the map.
1032 /// The key may be any borrowed form of the map's key type, but the ordering
1033 /// on the borrowed form *must* match the ordering on the key type.
1040 /// use std::collections::BTreeMap;
1042 /// let mut map = BTreeMap::new();
1043 /// map.insert(1, "a");
1044 /// assert_eq!(map.remove_entry(&1), Some((1, "a")));
1045 /// assert_eq!(map.remove_entry(&1), None);
1047 #[stable(feature = "btreemap_remove_entry", since = "1.45.0")]
1048 pub fn remove_entry<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)>
1053 let (map, dormant_map) = DormantMutRef::new(self);
1054 let root_node = map.root.as_mut()?.borrow_mut();
1055 match root_node.search_tree(key) {
1056 Found(handle) => Some(
1060 alloc: (*map.alloc).clone(),
1061 _marker: PhantomData,
1069 /// Retains only the elements specified by the predicate.
1071 /// In other words, remove all pairs `(k, v)` for which `f(&k, &mut v)` returns `false`.
1072 /// The elements are visited in ascending key order.
1077 /// use std::collections::BTreeMap;
1079 /// let mut map: BTreeMap<i32, i32> = (0..8).map(|x| (x, x*10)).collect();
1080 /// // Keep only the elements with even-numbered keys.
1081 /// map.retain(|&k, _| k % 2 == 0);
1082 /// assert!(map.into_iter().eq(vec![(0, 0), (2, 20), (4, 40), (6, 60)]));
1085 #[stable(feature = "btree_retain", since = "1.53.0")]
1086 pub fn retain<F>(&mut self, mut f: F)
1089 F: FnMut(&K, &mut V) -> bool,
1091 self.drain_filter(|k, v| !f(k, v));
1094 /// Moves all elements from `other` into `self`, leaving `other` empty.
1096 /// If a key from `other` is already present in `self`, the respective
1097 /// value from `self` will be overwritten with the respective value from `other`.
1102 /// use std::collections::BTreeMap;
1104 /// let mut a = BTreeMap::new();
1105 /// a.insert(1, "a");
1106 /// a.insert(2, "b");
1107 /// a.insert(3, "c"); // Note: Key (3) also present in b.
1109 /// let mut b = BTreeMap::new();
1110 /// b.insert(3, "d"); // Note: Key (3) also present in a.
1111 /// b.insert(4, "e");
1112 /// b.insert(5, "f");
1114 /// a.append(&mut b);
1116 /// assert_eq!(a.len(), 5);
1117 /// assert_eq!(b.len(), 0);
1119 /// assert_eq!(a[&1], "a");
1120 /// assert_eq!(a[&2], "b");
1121 /// assert_eq!(a[&3], "d"); // Note: "c" has been overwritten.
1122 /// assert_eq!(a[&4], "e");
1123 /// assert_eq!(a[&5], "f");
1125 #[stable(feature = "btree_append", since = "1.11.0")]
1126 pub fn append(&mut self, other: &mut Self)
1131 // Do we have to append anything at all?
1132 if other.is_empty() {
1136 // We can just swap `self` and `other` if `self` is empty.
1137 if self.is_empty() {
1138 mem::swap(self, other);
1142 let self_iter = mem::replace(self, Self::new_in((*self.alloc).clone())).into_iter();
1143 let other_iter = mem::replace(other, Self::new_in((*self.alloc).clone())).into_iter();
1144 let root = self.root.get_or_insert_with(|| Root::new((*self.alloc).clone()));
1145 root.append_from_sorted_iters(
1149 (*self.alloc).clone(),
1153 /// Constructs a double-ended iterator over a sub-range of elements in the map.
1154 /// The simplest way is to use the range syntax `min..max`, thus `range(min..max)` will
1155 /// yield elements from min (inclusive) to max (exclusive).
1156 /// The range may also be entered as `(Bound<T>, Bound<T>)`, so for example
1157 /// `range((Excluded(4), Included(10)))` will yield a left-exclusive, right-inclusive
1158 /// range from 4 to 10.
1162 /// Panics if range `start > end`.
1163 /// Panics if range `start == end` and both bounds are `Excluded`.
1170 /// use std::collections::BTreeMap;
1171 /// use std::ops::Bound::Included;
1173 /// let mut map = BTreeMap::new();
1174 /// map.insert(3, "a");
1175 /// map.insert(5, "b");
1176 /// map.insert(8, "c");
1177 /// for (&key, &value) in map.range((Included(&4), Included(&8))) {
1178 /// println!("{key}: {value}");
1180 /// assert_eq!(Some((&5, &"b")), map.range(4..).next());
1182 #[stable(feature = "btree_range", since = "1.17.0")]
1183 pub fn range<T: ?Sized, R>(&self, range: R) -> Range<'_, K, V>
1189 if let Some(root) = &self.root {
1190 Range { inner: root.reborrow().range_search(range) }
1192 Range { inner: LeafRange::none() }
1196 /// Constructs a mutable double-ended iterator over a sub-range of elements in the map.
1197 /// The simplest way is to use the range syntax `min..max`, thus `range(min..max)` will
1198 /// yield elements from min (inclusive) to max (exclusive).
1199 /// The range may also be entered as `(Bound<T>, Bound<T>)`, so for example
1200 /// `range((Excluded(4), Included(10)))` will yield a left-exclusive, right-inclusive
1201 /// range from 4 to 10.
1205 /// Panics if range `start > end`.
1206 /// Panics if range `start == end` and both bounds are `Excluded`.
1213 /// use std::collections::BTreeMap;
1215 /// let mut map: BTreeMap<&str, i32> =
1216 /// [("Alice", 0), ("Bob", 0), ("Carol", 0), ("Cheryl", 0)].into();
1217 /// for (_, balance) in map.range_mut("B".."Cheryl") {
1218 /// *balance += 100;
1220 /// for (name, balance) in &map {
1221 /// println!("{name} => {balance}");
1224 #[stable(feature = "btree_range", since = "1.17.0")]
1225 pub fn range_mut<T: ?Sized, R>(&mut self, range: R) -> RangeMut<'_, K, V>
1231 if let Some(root) = &mut self.root {
1232 RangeMut { inner: root.borrow_valmut().range_search(range), _marker: PhantomData }
1234 RangeMut { inner: LeafRange::none(), _marker: PhantomData }
1238 /// Gets the given key's corresponding entry in the map for in-place manipulation.
1245 /// use std::collections::BTreeMap;
1247 /// let mut count: BTreeMap<&str, usize> = BTreeMap::new();
1249 /// // count the number of occurrences of letters in the vec
1250 /// for x in ["a", "b", "a", "c", "a", "b"] {
1251 /// count.entry(x).and_modify(|curr| *curr += 1).or_insert(1);
1254 /// assert_eq!(count["a"], 3);
1255 /// assert_eq!(count["b"], 2);
1256 /// assert_eq!(count["c"], 1);
1258 #[stable(feature = "rust1", since = "1.0.0")]
1259 pub fn entry(&mut self, key: K) -> Entry<'_, K, V, A>
1263 let (map, dormant_map) = DormantMutRef::new(self);
1265 None => Vacant(VacantEntry {
1269 alloc: (*map.alloc).clone(),
1270 _marker: PhantomData,
1272 Some(ref mut root) => match root.borrow_mut().search_tree(&key) {
1273 Found(handle) => Occupied(OccupiedEntry {
1276 alloc: (*map.alloc).clone(),
1277 _marker: PhantomData,
1279 GoDown(handle) => Vacant(VacantEntry {
1281 handle: Some(handle),
1283 alloc: (*map.alloc).clone(),
1284 _marker: PhantomData,
1290 /// Splits the collection into two at the given key. Returns everything after the given key,
1291 /// including the key.
1298 /// use std::collections::BTreeMap;
1300 /// let mut a = BTreeMap::new();
1301 /// a.insert(1, "a");
1302 /// a.insert(2, "b");
1303 /// a.insert(3, "c");
1304 /// a.insert(17, "d");
1305 /// a.insert(41, "e");
1307 /// let b = a.split_off(&3);
1309 /// assert_eq!(a.len(), 2);
1310 /// assert_eq!(b.len(), 3);
1312 /// assert_eq!(a[&1], "a");
1313 /// assert_eq!(a[&2], "b");
1315 /// assert_eq!(b[&3], "c");
1316 /// assert_eq!(b[&17], "d");
1317 /// assert_eq!(b[&41], "e");
1319 #[stable(feature = "btree_split_off", since = "1.11.0")]
1320 pub fn split_off<Q: ?Sized + Ord>(&mut self, key: &Q) -> Self
1325 if self.is_empty() {
1326 return Self::new_in((*self.alloc).clone());
1329 let total_num = self.len();
1330 let left_root = self.root.as_mut().unwrap(); // unwrap succeeds because not empty
1332 let right_root = left_root.split_off(key, (*self.alloc).clone());
1334 let (new_left_len, right_len) = Root::calc_split_length(total_num, &left_root, &right_root);
1335 self.length = new_left_len;
1338 root: Some(right_root),
1340 alloc: self.alloc.clone(),
1341 _marker: PhantomData,
1345 /// Creates an iterator that visits all elements (key-value pairs) in
1346 /// ascending key order and uses a closure to determine if an element should
1347 /// be removed. If the closure returns `true`, the element is removed from
1348 /// the map and yielded. If the closure returns `false`, or panics, the
1349 /// element remains in the map and will not be yielded.
1351 /// The iterator also lets you mutate the value of each element in the
1352 /// closure, regardless of whether you choose to keep or remove it.
1354 /// If the iterator is only partially consumed or not consumed at all, each
1355 /// of the remaining elements is still subjected to the closure, which may
1356 /// change its value and, by returning `true`, have the element removed and
1359 /// It is unspecified how many more elements will be subjected to the
1360 /// closure if a panic occurs in the closure, or a panic occurs while
1361 /// dropping an element, or if the `DrainFilter` value is leaked.
1365 /// Splitting a map into even and odd keys, reusing the original map:
1368 /// #![feature(btree_drain_filter)]
1369 /// use std::collections::BTreeMap;
1371 /// let mut map: BTreeMap<i32, i32> = (0..8).map(|x| (x, x)).collect();
1372 /// let evens: BTreeMap<_, _> = map.drain_filter(|k, _v| k % 2 == 0).collect();
1374 /// assert_eq!(evens.keys().copied().collect::<Vec<_>>(), [0, 2, 4, 6]);
1375 /// assert_eq!(odds.keys().copied().collect::<Vec<_>>(), [1, 3, 5, 7]);
1377 #[unstable(feature = "btree_drain_filter", issue = "70530")]
1378 pub fn drain_filter<F>(&mut self, pred: F) -> DrainFilter<'_, K, V, F, A>
1381 F: FnMut(&K, &mut V) -> bool,
1383 let (inner, alloc) = self.drain_filter_inner();
1384 DrainFilter { pred, inner, alloc }
1387 pub(super) fn drain_filter_inner(&mut self) -> (DrainFilterInner<'_, K, V>, A)
1391 if let Some(root) = self.root.as_mut() {
1392 let (root, dormant_root) = DormantMutRef::new(root);
1393 let front = root.borrow_mut().first_leaf_edge();
1396 length: &mut self.length,
1397 dormant_root: Some(dormant_root),
1398 cur_leaf_edge: Some(front),
1400 (*self.alloc).clone(),
1405 length: &mut self.length,
1407 cur_leaf_edge: None,
1409 (*self.alloc).clone(),
1414 /// Creates a consuming iterator visiting all the keys, in sorted order.
1415 /// The map cannot be used after calling this.
1416 /// The iterator element type is `K`.
1421 /// use std::collections::BTreeMap;
1423 /// let mut a = BTreeMap::new();
1424 /// a.insert(2, "b");
1425 /// a.insert(1, "a");
1427 /// let keys: Vec<i32> = a.into_keys().collect();
1428 /// assert_eq!(keys, [1, 2]);
1431 #[stable(feature = "map_into_keys_values", since = "1.54.0")]
1432 pub fn into_keys(self) -> IntoKeys<K, V, A> {
1433 IntoKeys { inner: self.into_iter() }
1436 /// Creates a consuming iterator visiting all the values, in order by key.
1437 /// The map cannot be used after calling this.
1438 /// The iterator element type is `V`.
1443 /// use std::collections::BTreeMap;
1445 /// let mut a = BTreeMap::new();
1446 /// a.insert(1, "hello");
1447 /// a.insert(2, "goodbye");
1449 /// let values: Vec<&str> = a.into_values().collect();
1450 /// assert_eq!(values, ["hello", "goodbye"]);
1453 #[stable(feature = "map_into_keys_values", since = "1.54.0")]
1454 pub fn into_values(self) -> IntoValues<K, V, A> {
1455 IntoValues { inner: self.into_iter() }
1458 /// Makes a `BTreeMap` from a sorted iterator.
1459 pub(crate) fn bulk_build_from_sorted_iter<I>(iter: I, alloc: A) -> Self
1462 I: IntoIterator<Item = (K, V)>,
1464 let mut root = Root::new(alloc.clone());
1466 root.bulk_push(DedupSortedIter::new(iter.into_iter()), &mut length, alloc.clone());
1467 BTreeMap { root: Some(root), length, alloc: ManuallyDrop::new(alloc), _marker: PhantomData }
1471 #[stable(feature = "rust1", since = "1.0.0")]
1472 impl<'a, K, V, A: Allocator + Clone> IntoIterator for &'a BTreeMap<K, V, A> {
1473 type Item = (&'a K, &'a V);
1474 type IntoIter = Iter<'a, K, V>;
1476 fn into_iter(self) -> Iter<'a, K, V> {
1481 #[stable(feature = "rust1", since = "1.0.0")]
1482 impl<'a, K: 'a, V: 'a> Iterator for Iter<'a, K, V> {
1483 type Item = (&'a K, &'a V);
1485 fn next(&mut self) -> Option<(&'a K, &'a V)> {
1486 if self.length == 0 {
1490 Some(unsafe { self.range.next_unchecked() })
1494 fn size_hint(&self) -> (usize, Option<usize>) {
1495 (self.length, Some(self.length))
1498 fn last(mut self) -> Option<(&'a K, &'a V)> {
1502 fn min(mut self) -> Option<(&'a K, &'a V)> {
1506 fn max(mut self) -> Option<(&'a K, &'a V)> {
1511 #[stable(feature = "fused", since = "1.26.0")]
1512 impl<K, V> FusedIterator for Iter<'_, K, V> {}
1514 #[stable(feature = "rust1", since = "1.0.0")]
1515 impl<'a, K: 'a, V: 'a> DoubleEndedIterator for Iter<'a, K, V> {
1516 fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
1517 if self.length == 0 {
1521 Some(unsafe { self.range.next_back_unchecked() })
1526 #[stable(feature = "rust1", since = "1.0.0")]
1527 impl<K, V> ExactSizeIterator for Iter<'_, K, V> {
1528 fn len(&self) -> usize {
1533 #[stable(feature = "rust1", since = "1.0.0")]
1534 impl<K, V> Clone for Iter<'_, K, V> {
1535 fn clone(&self) -> Self {
1536 Iter { range: self.range.clone(), length: self.length }
1540 #[stable(feature = "rust1", since = "1.0.0")]
1541 impl<'a, K, V, A: Allocator + Clone> IntoIterator for &'a mut BTreeMap<K, V, A> {
1542 type Item = (&'a K, &'a mut V);
1543 type IntoIter = IterMut<'a, K, V>;
1545 fn into_iter(self) -> IterMut<'a, K, V> {
1550 #[stable(feature = "rust1", since = "1.0.0")]
1551 impl<'a, K, V> Iterator for IterMut<'a, K, V> {
1552 type Item = (&'a K, &'a mut V);
1554 fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
1555 if self.length == 0 {
1559 Some(unsafe { self.range.next_unchecked() })
1563 fn size_hint(&self) -> (usize, Option<usize>) {
1564 (self.length, Some(self.length))
1567 fn last(mut self) -> Option<(&'a K, &'a mut V)> {
1571 fn min(mut self) -> Option<(&'a K, &'a mut V)> {
1575 fn max(mut self) -> Option<(&'a K, &'a mut V)> {
1580 #[stable(feature = "rust1", since = "1.0.0")]
1581 impl<'a, K, V> DoubleEndedIterator for IterMut<'a, K, V> {
1582 fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
1583 if self.length == 0 {
1587 Some(unsafe { self.range.next_back_unchecked() })
1592 #[stable(feature = "rust1", since = "1.0.0")]
1593 impl<K, V> ExactSizeIterator for IterMut<'_, K, V> {
1594 fn len(&self) -> usize {
1599 #[stable(feature = "fused", since = "1.26.0")]
1600 impl<K, V> FusedIterator for IterMut<'_, K, V> {}
1602 impl<'a, K, V> IterMut<'a, K, V> {
1603 /// Returns an iterator of references over the remaining items.
1605 pub(super) fn iter(&self) -> Iter<'_, K, V> {
1606 Iter { range: self.range.reborrow(), length: self.length }
1610 #[stable(feature = "rust1", since = "1.0.0")]
1611 impl<K, V, A: Allocator + Clone> IntoIterator for BTreeMap<K, V, A> {
1613 type IntoIter = IntoIter<K, V, A>;
1615 fn into_iter(self) -> IntoIter<K, V, A> {
1616 let mut me = ManuallyDrop::new(self);
1617 if let Some(root) = me.root.take() {
1618 let full_range = root.into_dying().full_range();
1623 alloc: unsafe { ManuallyDrop::take(&mut me.alloc) },
1627 range: LazyLeafRange::none(),
1629 alloc: unsafe { ManuallyDrop::take(&mut me.alloc) },
1635 #[stable(feature = "btree_drop", since = "1.7.0")]
1636 impl<K, V, A: Allocator + Clone> Drop for IntoIter<K, V, A> {
1637 fn drop(&mut self) {
1638 struct DropGuard<'a, K, V, A: Allocator + Clone>(&'a mut IntoIter<K, V, A>);
1640 impl<'a, K, V, A: Allocator + Clone> Drop for DropGuard<'a, K, V, A> {
1641 fn drop(&mut self) {
1642 // Continue the same loop we perform below. This only runs when unwinding, so we
1643 // don't have to care about panics this time (they'll abort).
1644 while let Some(kv) = self.0.dying_next() {
1645 // SAFETY: we consume the dying handle immediately.
1646 unsafe { kv.drop_key_val() };
1651 while let Some(kv) = self.dying_next() {
1652 let guard = DropGuard(self);
1653 // SAFETY: we don't touch the tree before consuming the dying handle.
1654 unsafe { kv.drop_key_val() };
1660 impl<K, V, A: Allocator + Clone> IntoIter<K, V, A> {
1661 /// Core of a `next` method returning a dying KV handle,
1662 /// invalidated by further calls to this function and some others.
1665 ) -> Option<Handle<NodeRef<marker::Dying, K, V, marker::LeafOrInternal>, marker::KV>> {
1666 if self.length == 0 {
1667 self.range.deallocating_end(self.alloc.clone());
1671 Some(unsafe { self.range.deallocating_next_unchecked(self.alloc.clone()) })
1675 /// Core of a `next_back` method returning a dying KV handle,
1676 /// invalidated by further calls to this function and some others.
1679 ) -> Option<Handle<NodeRef<marker::Dying, K, V, marker::LeafOrInternal>, marker::KV>> {
1680 if self.length == 0 {
1681 self.range.deallocating_end(self.alloc.clone());
1685 Some(unsafe { self.range.deallocating_next_back_unchecked(self.alloc.clone()) })
1690 #[stable(feature = "rust1", since = "1.0.0")]
1691 impl<K, V, A: Allocator + Clone> Iterator for IntoIter<K, V, A> {
1694 fn next(&mut self) -> Option<(K, V)> {
1695 // SAFETY: we consume the dying handle immediately.
1696 self.dying_next().map(unsafe { |kv| kv.into_key_val() })
1699 fn size_hint(&self) -> (usize, Option<usize>) {
1700 (self.length, Some(self.length))
1704 #[stable(feature = "rust1", since = "1.0.0")]
1705 impl<K, V, A: Allocator + Clone> DoubleEndedIterator for IntoIter<K, V, A> {
1706 fn next_back(&mut self) -> Option<(K, V)> {
1707 // SAFETY: we consume the dying handle immediately.
1708 self.dying_next_back().map(unsafe { |kv| kv.into_key_val() })
1712 #[stable(feature = "rust1", since = "1.0.0")]
1713 impl<K, V, A: Allocator + Clone> ExactSizeIterator for IntoIter<K, V, A> {
1714 fn len(&self) -> usize {
1719 #[stable(feature = "fused", since = "1.26.0")]
1720 impl<K, V, A: Allocator + Clone> FusedIterator for IntoIter<K, V, A> {}
1722 #[stable(feature = "rust1", since = "1.0.0")]
1723 impl<'a, K, V> Iterator for Keys<'a, K, V> {
1726 fn next(&mut self) -> Option<&'a K> {
1727 self.inner.next().map(|(k, _)| k)
1730 fn size_hint(&self) -> (usize, Option<usize>) {
1731 self.inner.size_hint()
1734 fn last(mut self) -> Option<&'a K> {
1738 fn min(mut self) -> Option<&'a K> {
1742 fn max(mut self) -> Option<&'a K> {
1747 #[stable(feature = "rust1", since = "1.0.0")]
1748 impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> {
1749 fn next_back(&mut self) -> Option<&'a K> {
1750 self.inner.next_back().map(|(k, _)| k)
1754 #[stable(feature = "rust1", since = "1.0.0")]
1755 impl<K, V> ExactSizeIterator for Keys<'_, K, V> {
1756 fn len(&self) -> usize {
1761 #[stable(feature = "fused", since = "1.26.0")]
1762 impl<K, V> FusedIterator for Keys<'_, K, V> {}
1764 #[stable(feature = "rust1", since = "1.0.0")]
1765 impl<K, V> Clone for Keys<'_, K, V> {
1766 fn clone(&self) -> Self {
1767 Keys { inner: self.inner.clone() }
1771 #[stable(feature = "rust1", since = "1.0.0")]
1772 impl<'a, K, V> Iterator for Values<'a, K, V> {
1775 fn next(&mut self) -> Option<&'a V> {
1776 self.inner.next().map(|(_, v)| v)
1779 fn size_hint(&self) -> (usize, Option<usize>) {
1780 self.inner.size_hint()
1783 fn last(mut self) -> Option<&'a V> {
1788 #[stable(feature = "rust1", since = "1.0.0")]
1789 impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> {
1790 fn next_back(&mut self) -> Option<&'a V> {
1791 self.inner.next_back().map(|(_, v)| v)
1795 #[stable(feature = "rust1", since = "1.0.0")]
1796 impl<K, V> ExactSizeIterator for Values<'_, K, V> {
1797 fn len(&self) -> usize {
1802 #[stable(feature = "fused", since = "1.26.0")]
1803 impl<K, V> FusedIterator for Values<'_, K, V> {}
1805 #[stable(feature = "rust1", since = "1.0.0")]
1806 impl<K, V> Clone for Values<'_, K, V> {
1807 fn clone(&self) -> Self {
1808 Values { inner: self.inner.clone() }
1812 /// An iterator produced by calling `drain_filter` on BTreeMap.
1813 #[unstable(feature = "btree_drain_filter", issue = "70530")]
1814 pub struct DrainFilter<
1819 #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + Clone = Global,
1821 F: 'a + FnMut(&K, &mut V) -> bool,
1824 inner: DrainFilterInner<'a, K, V>,
1825 /// The BTreeMap will outlive this IntoIter so we don't care about drop order for `alloc`.
1828 /// Most of the implementation of DrainFilter are generic over the type
1829 /// of the predicate, thus also serving for BTreeSet::DrainFilter.
1830 pub(super) struct DrainFilterInner<'a, K, V> {
1831 /// Reference to the length field in the borrowed map, updated live.
1832 length: &'a mut usize,
1833 /// Buried reference to the root field in the borrowed map.
1834 /// Wrapped in `Option` to allow drop handler to `take` it.
1835 dormant_root: Option<DormantMutRef<'a, Root<K, V>>>,
1836 /// Contains a leaf edge preceding the next element to be returned, or the last leaf edge.
1837 /// Empty if the map has no root, if iteration went beyond the last leaf edge,
1838 /// or if a panic occurred in the predicate.
1839 cur_leaf_edge: Option<Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>>,
1842 #[unstable(feature = "btree_drain_filter", issue = "70530")]
1843 impl<K, V, F, A: Allocator + Clone> Drop for DrainFilter<'_, K, V, F, A>
1845 F: FnMut(&K, &mut V) -> bool,
1847 fn drop(&mut self) {
1848 self.for_each(drop);
1852 #[unstable(feature = "btree_drain_filter", issue = "70530")]
1853 impl<K, V, F> fmt::Debug for DrainFilter<'_, K, V, F>
1857 F: FnMut(&K, &mut V) -> bool,
1859 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1860 f.debug_tuple("DrainFilter").field(&self.inner.peek()).finish()
1864 #[unstable(feature = "btree_drain_filter", issue = "70530")]
1865 impl<K, V, F, A: Allocator + Clone> Iterator for DrainFilter<'_, K, V, F, A>
1867 F: FnMut(&K, &mut V) -> bool,
1871 fn next(&mut self) -> Option<(K, V)> {
1872 self.inner.next(&mut self.pred, self.alloc.clone())
1875 fn size_hint(&self) -> (usize, Option<usize>) {
1876 self.inner.size_hint()
1880 impl<'a, K, V> DrainFilterInner<'a, K, V> {
1881 /// Allow Debug implementations to predict the next element.
1882 pub(super) fn peek(&self) -> Option<(&K, &V)> {
1883 let edge = self.cur_leaf_edge.as_ref()?;
1884 edge.reborrow().next_kv().ok().map(Handle::into_kv)
1887 /// Implementation of a typical `DrainFilter::next` method, given the predicate.
1888 pub(super) fn next<F, A: Allocator + Clone>(&mut self, pred: &mut F, alloc: A) -> Option<(K, V)>
1890 F: FnMut(&K, &mut V) -> bool,
1892 while let Ok(mut kv) = self.cur_leaf_edge.take()?.next_kv() {
1893 let (k, v) = kv.kv_mut();
1896 let (kv, pos) = kv.remove_kv_tracking(
1898 // SAFETY: we will touch the root in a way that will not
1899 // invalidate the position returned.
1900 let root = unsafe { self.dormant_root.take().unwrap().awaken() };
1901 root.pop_internal_level(alloc.clone());
1902 self.dormant_root = Some(DormantMutRef::new(root).1);
1906 self.cur_leaf_edge = Some(pos);
1909 self.cur_leaf_edge = Some(kv.next_leaf_edge());
1914 /// Implementation of a typical `DrainFilter::size_hint` method.
1915 pub(super) fn size_hint(&self) -> (usize, Option<usize>) {
1916 // In most of the btree iterators, `self.length` is the number of elements
1917 // yet to be visited. Here, it includes elements that were visited and that
1918 // the predicate decided not to drain. Making this upper bound more tight
1919 // during iteration would require an extra field.
1920 (0, Some(*self.length))
1924 #[unstable(feature = "btree_drain_filter", issue = "70530")]
1925 impl<K, V, F> FusedIterator for DrainFilter<'_, K, V, F> where F: FnMut(&K, &mut V) -> bool {}
1927 #[stable(feature = "btree_range", since = "1.17.0")]
1928 impl<'a, K, V> Iterator for Range<'a, K, V> {
1929 type Item = (&'a K, &'a V);
1931 fn next(&mut self) -> Option<(&'a K, &'a V)> {
1932 self.inner.next_checked()
1935 fn last(mut self) -> Option<(&'a K, &'a V)> {
1939 fn min(mut self) -> Option<(&'a K, &'a V)> {
1943 fn max(mut self) -> Option<(&'a K, &'a V)> {
1948 #[stable(feature = "map_values_mut", since = "1.10.0")]
1949 impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
1950 type Item = &'a mut V;
1952 fn next(&mut self) -> Option<&'a mut V> {
1953 self.inner.next().map(|(_, v)| v)
1956 fn size_hint(&self) -> (usize, Option<usize>) {
1957 self.inner.size_hint()
1960 fn last(mut self) -> Option<&'a mut V> {
1965 #[stable(feature = "map_values_mut", since = "1.10.0")]
1966 impl<'a, K, V> DoubleEndedIterator for ValuesMut<'a, K, V> {
1967 fn next_back(&mut self) -> Option<&'a mut V> {
1968 self.inner.next_back().map(|(_, v)| v)
1972 #[stable(feature = "map_values_mut", since = "1.10.0")]
1973 impl<K, V> ExactSizeIterator for ValuesMut<'_, K, V> {
1974 fn len(&self) -> usize {
1979 #[stable(feature = "fused", since = "1.26.0")]
1980 impl<K, V> FusedIterator for ValuesMut<'_, K, V> {}
1982 #[stable(feature = "map_into_keys_values", since = "1.54.0")]
1983 impl<K, V, A: Allocator + Clone> Iterator for IntoKeys<K, V, A> {
1986 fn next(&mut self) -> Option<K> {
1987 self.inner.next().map(|(k, _)| k)
1990 fn size_hint(&self) -> (usize, Option<usize>) {
1991 self.inner.size_hint()
1994 fn last(mut self) -> Option<K> {
1998 fn min(mut self) -> Option<K> {
2002 fn max(mut self) -> Option<K> {
2007 #[stable(feature = "map_into_keys_values", since = "1.54.0")]
2008 impl<K, V, A: Allocator + Clone> DoubleEndedIterator for IntoKeys<K, V, A> {
2009 fn next_back(&mut self) -> Option<K> {
2010 self.inner.next_back().map(|(k, _)| k)
2014 #[stable(feature = "map_into_keys_values", since = "1.54.0")]
2015 impl<K, V, A: Allocator + Clone> ExactSizeIterator for IntoKeys<K, V, A> {
2016 fn len(&self) -> usize {
2021 #[stable(feature = "map_into_keys_values", since = "1.54.0")]
2022 impl<K, V, A: Allocator + Clone> FusedIterator for IntoKeys<K, V, A> {}
2024 #[stable(feature = "map_into_keys_values", since = "1.54.0")]
2025 impl<K, V, A: Allocator + Clone> Iterator for IntoValues<K, V, A> {
2028 fn next(&mut self) -> Option<V> {
2029 self.inner.next().map(|(_, v)| v)
2032 fn size_hint(&self) -> (usize, Option<usize>) {
2033 self.inner.size_hint()
2036 fn last(mut self) -> Option<V> {
2041 #[stable(feature = "map_into_keys_values", since = "1.54.0")]
2042 impl<K, V, A: Allocator + Clone> DoubleEndedIterator for IntoValues<K, V, A> {
2043 fn next_back(&mut self) -> Option<V> {
2044 self.inner.next_back().map(|(_, v)| v)
2048 #[stable(feature = "map_into_keys_values", since = "1.54.0")]
2049 impl<K, V, A: Allocator + Clone> ExactSizeIterator for IntoValues<K, V, A> {
2050 fn len(&self) -> usize {
2055 #[stable(feature = "map_into_keys_values", since = "1.54.0")]
2056 impl<K, V, A: Allocator + Clone> FusedIterator for IntoValues<K, V, A> {}
2058 #[stable(feature = "btree_range", since = "1.17.0")]
2059 impl<'a, K, V> DoubleEndedIterator for Range<'a, K, V> {
2060 fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
2061 self.inner.next_back_checked()
2065 #[stable(feature = "fused", since = "1.26.0")]
2066 impl<K, V> FusedIterator for Range<'_, K, V> {}
2068 #[stable(feature = "btree_range", since = "1.17.0")]
2069 impl<K, V> Clone for Range<'_, K, V> {
2070 fn clone(&self) -> Self {
2071 Range { inner: self.inner.clone() }
2075 #[stable(feature = "btree_range", since = "1.17.0")]
2076 impl<'a, K, V> Iterator for RangeMut<'a, K, V> {
2077 type Item = (&'a K, &'a mut V);
2079 fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
2080 self.inner.next_checked()
2083 fn last(mut self) -> Option<(&'a K, &'a mut V)> {
2087 fn min(mut self) -> Option<(&'a K, &'a mut V)> {
2091 fn max(mut self) -> Option<(&'a K, &'a mut V)> {
2096 #[stable(feature = "btree_range", since = "1.17.0")]
2097 impl<'a, K, V> DoubleEndedIterator for RangeMut<'a, K, V> {
2098 fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
2099 self.inner.next_back_checked()
2103 #[stable(feature = "fused", since = "1.26.0")]
2104 impl<K, V> FusedIterator for RangeMut<'_, K, V> {}
2106 #[stable(feature = "rust1", since = "1.0.0")]
2107 impl<K: Ord, V> FromIterator<(K, V)> for BTreeMap<K, V> {
2108 fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> BTreeMap<K, V> {
2109 let mut inputs: Vec<_> = iter.into_iter().collect();
2111 if inputs.is_empty() {
2112 return BTreeMap::new();
2115 // use stable sort to preserve the insertion order.
2116 inputs.sort_by(|a, b| a.0.cmp(&b.0));
2117 BTreeMap::bulk_build_from_sorted_iter(inputs, Global)
2121 #[stable(feature = "rust1", since = "1.0.0")]
2122 impl<K: Ord, V, A: Allocator + Clone> Extend<(K, V)> for BTreeMap<K, V, A> {
2124 fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
2125 iter.into_iter().for_each(move |(k, v)| {
2131 fn extend_one(&mut self, (k, v): (K, V)) {
2136 #[stable(feature = "extend_ref", since = "1.2.0")]
2137 impl<'a, K: Ord + Copy, V: Copy, A: Allocator + Clone> Extend<(&'a K, &'a V)>
2138 for BTreeMap<K, V, A>
2140 fn extend<I: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: I) {
2141 self.extend(iter.into_iter().map(|(&key, &value)| (key, value)));
2145 fn extend_one(&mut self, (&k, &v): (&'a K, &'a V)) {
2150 #[stable(feature = "rust1", since = "1.0.0")]
2151 impl<K: Hash, V: Hash, A: Allocator + Clone> Hash for BTreeMap<K, V, A> {
2152 fn hash<H: Hasher>(&self, state: &mut H) {
2153 state.write_length_prefix(self.len());
2160 #[stable(feature = "rust1", since = "1.0.0")]
2161 impl<K, V> Default for BTreeMap<K, V> {
2162 /// Creates an empty `BTreeMap`.
2163 fn default() -> BTreeMap<K, V> {
2168 #[stable(feature = "rust1", since = "1.0.0")]
2169 impl<K: PartialEq, V: PartialEq, A: Allocator + Clone> PartialEq for BTreeMap<K, V, A> {
2170 fn eq(&self, other: &BTreeMap<K, V, A>) -> bool {
2171 self.len() == other.len() && self.iter().zip(other).all(|(a, b)| a == b)
2175 #[stable(feature = "rust1", since = "1.0.0")]
2176 impl<K: Eq, V: Eq, A: Allocator + Clone> Eq for BTreeMap<K, V, A> {}
2178 #[stable(feature = "rust1", since = "1.0.0")]
2179 impl<K: PartialOrd, V: PartialOrd, A: Allocator + Clone> PartialOrd for BTreeMap<K, V, A> {
2181 fn partial_cmp(&self, other: &BTreeMap<K, V, A>) -> Option<Ordering> {
2182 self.iter().partial_cmp(other.iter())
2186 #[stable(feature = "rust1", since = "1.0.0")]
2187 impl<K: Ord, V: Ord, A: Allocator + Clone> Ord for BTreeMap<K, V, A> {
2189 fn cmp(&self, other: &BTreeMap<K, V, A>) -> Ordering {
2190 self.iter().cmp(other.iter())
2194 #[stable(feature = "rust1", since = "1.0.0")]
2195 impl<K: Debug, V: Debug, A: Allocator + Clone> Debug for BTreeMap<K, V, A> {
2196 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2197 f.debug_map().entries(self.iter()).finish()
2201 #[stable(feature = "rust1", since = "1.0.0")]
2202 impl<K, Q: ?Sized, V, A: Allocator + Clone> Index<&Q> for BTreeMap<K, V, A>
2209 /// Returns a reference to the value corresponding to the supplied key.
2213 /// Panics if the key is not present in the `BTreeMap`.
2215 fn index(&self, key: &Q) -> &V {
2216 self.get(key).expect("no entry found for key")
2220 #[stable(feature = "std_collections_from_array", since = "1.56.0")]
2221 impl<K: Ord, V, const N: usize> From<[(K, V); N]> for BTreeMap<K, V> {
2222 /// Converts a `[(K, V); N]` into a `BTreeMap<(K, V)>`.
2225 /// use std::collections::BTreeMap;
2227 /// let map1 = BTreeMap::from([(1, 2), (3, 4)]);
2228 /// let map2: BTreeMap<_, _> = [(1, 2), (3, 4)].into();
2229 /// assert_eq!(map1, map2);
2231 fn from(mut arr: [(K, V); N]) -> Self {
2233 return BTreeMap::new();
2236 // use stable sort to preserve the insertion order.
2237 arr.sort_by(|a, b| a.0.cmp(&b.0));
2238 BTreeMap::bulk_build_from_sorted_iter(arr, Global)
2242 impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> {
2243 /// Gets an iterator over the entries of the map, sorted by key.
2250 /// use std::collections::BTreeMap;
2252 /// let mut map = BTreeMap::new();
2253 /// map.insert(3, "c");
2254 /// map.insert(2, "b");
2255 /// map.insert(1, "a");
2257 /// for (key, value) in map.iter() {
2258 /// println!("{key}: {value}");
2261 /// let (first_key, first_value) = map.iter().next().unwrap();
2262 /// assert_eq!((*first_key, *first_value), (1, "a"));
2264 #[stable(feature = "rust1", since = "1.0.0")]
2265 pub fn iter(&self) -> Iter<'_, K, V> {
2266 if let Some(root) = &self.root {
2267 let full_range = root.reborrow().full_range();
2269 Iter { range: full_range, length: self.length }
2271 Iter { range: LazyLeafRange::none(), length: 0 }
2275 /// Gets a mutable iterator over the entries of the map, sorted by key.
2282 /// use std::collections::BTreeMap;
2284 /// let mut map = BTreeMap::from([
2290 /// // add 10 to the value if the key isn't "a"
2291 /// for (key, value) in map.iter_mut() {
2292 /// if key != &"a" {
2297 #[stable(feature = "rust1", since = "1.0.0")]
2298 pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
2299 if let Some(root) = &mut self.root {
2300 let full_range = root.borrow_valmut().full_range();
2302 IterMut { range: full_range, length: self.length, _marker: PhantomData }
2304 IterMut { range: LazyLeafRange::none(), length: 0, _marker: PhantomData }
2308 /// Gets an iterator over the keys of the map, in sorted order.
2315 /// use std::collections::BTreeMap;
2317 /// let mut a = BTreeMap::new();
2318 /// a.insert(2, "b");
2319 /// a.insert(1, "a");
2321 /// let keys: Vec<_> = a.keys().cloned().collect();
2322 /// assert_eq!(keys, [1, 2]);
2324 #[stable(feature = "rust1", since = "1.0.0")]
2325 pub fn keys(&self) -> Keys<'_, K, V> {
2326 Keys { inner: self.iter() }
2329 /// Gets an iterator over the values of the map, in order by key.
2336 /// use std::collections::BTreeMap;
2338 /// let mut a = BTreeMap::new();
2339 /// a.insert(1, "hello");
2340 /// a.insert(2, "goodbye");
2342 /// let values: Vec<&str> = a.values().cloned().collect();
2343 /// assert_eq!(values, ["hello", "goodbye"]);
2345 #[stable(feature = "rust1", since = "1.0.0")]
2346 pub fn values(&self) -> Values<'_, K, V> {
2347 Values { inner: self.iter() }
2350 /// Gets a mutable iterator over the values of the map, in order by key.
2357 /// use std::collections::BTreeMap;
2359 /// let mut a = BTreeMap::new();
2360 /// a.insert(1, String::from("hello"));
2361 /// a.insert(2, String::from("goodbye"));
2363 /// for value in a.values_mut() {
2364 /// value.push_str("!");
2367 /// let values: Vec<String> = a.values().cloned().collect();
2368 /// assert_eq!(values, [String::from("hello!"),
2369 /// String::from("goodbye!")]);
2371 #[stable(feature = "map_values_mut", since = "1.10.0")]
2372 pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {
2373 ValuesMut { inner: self.iter_mut() }
2376 /// Returns the number of elements in the map.
2383 /// use std::collections::BTreeMap;
2385 /// let mut a = BTreeMap::new();
2386 /// assert_eq!(a.len(), 0);
2387 /// a.insert(1, "a");
2388 /// assert_eq!(a.len(), 1);
2391 #[stable(feature = "rust1", since = "1.0.0")]
2392 #[rustc_const_unstable(
2393 feature = "const_btree_len",
2395 implied_by = "const_btree_new"
2397 pub const fn len(&self) -> usize {
2401 /// Returns `true` if the map contains no elements.
2408 /// use std::collections::BTreeMap;
2410 /// let mut a = BTreeMap::new();
2411 /// assert!(a.is_empty());
2412 /// a.insert(1, "a");
2413 /// assert!(!a.is_empty());
2416 #[stable(feature = "rust1", since = "1.0.0")]
2417 #[rustc_const_unstable(
2418 feature = "const_btree_len",
2420 implied_by = "const_btree_new"
2422 pub const fn is_empty(&self) -> bool {