1 use core
::borrow
::Borrow
;
2 use core
::cmp
::Ordering
;
3 use core
::fmt
::{self, Debug}
;
4 use core
::hash
::{Hash, Hasher}
;
5 use core
::iter
::{FromIterator, FusedIterator, Peekable}
;
6 use core
::marker
::PhantomData
;
7 use core
::mem
::{self, ManuallyDrop}
;
8 use core
::ops
::{Index, RangeBounds}
;
11 use super::borrow
::DormantMutRef
;
12 use super::node
::{self, marker, ForceResult::*, Handle, InsertResult::*, NodeRef}
;
13 use super::search
::{self, SearchResult::*}
;
14 use super::unwrap_unchecked
;
17 use UnderflowResult
::*;
19 /// A map based on a B-Tree.
21 /// B-Trees represent a fundamental compromise between cache-efficiency and actually minimizing
22 /// the amount of work performed in a search. In theory, a binary search tree (BST) is the optimal
23 /// choice for a sorted map, as a perfectly balanced BST performs the theoretical minimum amount of
24 /// comparisons necessary to find an element (log<sub>2</sub>n). However, in practice the way this
25 /// is done is *very* inefficient for modern computer architectures. In particular, every element
26 /// is stored in its own individually heap-allocated node. This means that every single insertion
27 /// triggers a heap-allocation, and every single comparison should be a cache-miss. Since these
28 /// are both notably expensive things to do in practice, we are forced to at very least reconsider
31 /// A B-Tree instead makes each node contain B-1 to 2B-1 elements in a contiguous array. By doing
32 /// this, we reduce the number of allocations by a factor of B, and improve cache efficiency in
33 /// searches. However, this does mean that searches will have to do *more* comparisons on average.
34 /// The precise number of comparisons depends on the node search strategy used. For optimal cache
35 /// efficiency, one could search the nodes linearly. For optimal comparisons, one could search
36 /// the node using binary search. As a compromise, one could also perform a linear search
37 /// that initially only checks every i<sup>th</sup> element for some choice of i.
39 /// Currently, our implementation simply performs naive linear search. This provides excellent
40 /// performance on *small* nodes of elements which are cheap to compare. However in the future we
41 /// would like to further explore choosing the optimal search strategy based on the choice of B,
42 /// and possibly other factors. Using linear search, searching for a random element is expected
43 /// to take O(B * log(n)) comparisons, which is generally worse than a BST. In practice,
44 /// however, performance is excellent.
46 /// It is a logic error for a key to be modified in such a way that the key's ordering relative to
47 /// any other key, as determined by the [`Ord`] trait, changes while it is in the map. This is
48 /// normally only possible through [`Cell`], [`RefCell`], global state, I/O, or unsafe code.
50 /// [`Cell`]: core::cell::Cell
51 /// [`RefCell`]: core::cell::RefCell
56 /// use std::collections::BTreeMap;
58 /// // type inference lets us omit an explicit type signature (which
59 /// // would be `BTreeMap<&str, &str>` in this example).
60 /// let mut movie_reviews = BTreeMap::new();
62 /// // review some movies.
63 /// movie_reviews.insert("Office Space", "Deals with real issues in the workplace.");
64 /// movie_reviews.insert("Pulp Fiction", "Masterpiece.");
65 /// movie_reviews.insert("The Godfather", "Very enjoyable.");
66 /// movie_reviews.insert("The Blues Brothers", "Eye lyked it a lot.");
68 /// // check for a specific one.
69 /// if !movie_reviews.contains_key("Les Misérables") {
70 /// println!("We've got {} reviews, but Les Misérables ain't one.",
71 /// movie_reviews.len());
74 /// // oops, this review has a lot of spelling mistakes, let's delete it.
75 /// movie_reviews.remove("The Blues Brothers");
77 /// // look up the values associated with some keys.
78 /// let to_find = ["Up!", "Office Space"];
79 /// for movie in &to_find {
80 /// match movie_reviews.get(movie) {
81 /// Some(review) => println!("{}: {}", movie, review),
82 /// None => println!("{} is unreviewed.", movie)
86 /// // Look up the value for a key (will panic if the key is not found).
87 /// println!("Movie review: {}", movie_reviews["Office Space"]);
89 /// // iterate over everything.
90 /// for (movie, review) in &movie_reviews {
91 /// println!("{}: \"{}\"", movie, review);
95 /// `BTreeMap` also implements an [`Entry API`], which allows for more complex
96 /// methods of getting, setting, updating and removing keys and their values:
98 /// [`Entry API`]: BTreeMap::entry
101 /// use std::collections::BTreeMap;
103 /// // type inference lets us omit an explicit type signature (which
104 /// // would be `BTreeMap<&str, u8>` in this example).
105 /// let mut player_stats = BTreeMap::new();
107 /// fn random_stat_buff() -> u8 {
108 /// // could actually return some random value here - let's just return
109 /// // some fixed value for now
113 /// // insert a key only if it doesn't already exist
114 /// player_stats.entry("health").or_insert(100);
116 /// // insert a key using a function that provides a new value only if it
117 /// // doesn't already exist
118 /// player_stats.entry("defence").or_insert_with(random_stat_buff);
120 /// // update a key, guarding against the key possibly not being set
121 /// let stat = player_stats.entry("attack").or_insert(100);
122 /// *stat += random_stat_buff();
124 #[stable(feature = "rust1", since = "1.0.0")]
125 pub struct BTreeMap
<K
, V
> {
126 root
: Option
<node
::Root
<K
, V
>>,
130 #[stable(feature = "btree_drop", since = "1.7.0")]
131 unsafe impl<#[may_dangle] K, #[may_dangle] V> Drop for BTreeMap<K, V> {
134 drop(ptr
::read(self).into_iter());
139 #[stable(feature = "rust1", since = "1.0.0")]
140 impl<K
: Clone
, V
: Clone
> Clone
for BTreeMap
<K
, V
> {
141 fn clone(&self) -> BTreeMap
<K
, V
> {
142 fn clone_subtree
<'a
, K
: Clone
, V
: Clone
>(
143 node
: node
::NodeRef
<marker
::Immut
<'a
>, K
, V
, marker
::LeafOrInternal
>,
151 let mut out_tree
= BTreeMap { root: Some(node::Root::new_leaf()), length: 0 }
;
154 let root
= out_tree
.root
.as_mut().unwrap(); // unwrap succeeds because we just wrapped
155 let mut out_node
= match root
.node_as_mut().force() {
157 Internal(_
) => unreachable
!(),
160 let mut in_edge
= leaf
.first_edge();
161 while let Ok(kv
) = in_edge
.right_kv() {
162 let (k
, v
) = kv
.into_kv();
163 in_edge
= kv
.right_edge();
165 out_node
.push(k
.clone(), v
.clone());
166 out_tree
.length
+= 1;
172 Internal(internal
) => {
173 let mut out_tree
= clone_subtree(internal
.first_edge().descend());
176 let out_root
= BTreeMap
::ensure_is_owned(&mut out_tree
.root
);
177 let mut out_node
= out_root
.push_internal_level();
178 let mut in_edge
= internal
.first_edge();
179 while let Ok(kv
) = in_edge
.right_kv() {
180 let (k
, v
) = kv
.into_kv();
181 in_edge
= kv
.right_edge();
183 let k
= (*k
).clone();
184 let v
= (*v
).clone();
185 let subtree
= clone_subtree(in_edge
.descend());
187 // We can't destructure subtree directly
188 // because BTreeMap implements Drop
189 let (subroot
, sublength
) = unsafe {
190 let subtree
= ManuallyDrop
::new(subtree
);
191 let root
= ptr
::read(&subtree
.root
);
192 let length
= subtree
.length
;
196 out_node
.push(k
, v
, subroot
.unwrap_or_else(node
::Root
::new_leaf
));
197 out_tree
.length
+= 1 + sublength
;
207 // Ideally we'd call `BTreeMap::new` here, but that has the `K:
208 // Ord` constraint, which this method lacks.
209 BTreeMap { root: None, length: 0 }
211 clone_subtree(self.root
.as_ref().unwrap().node_as_ref()) // unwrap succeeds because not empty
216 impl<K
, Q
: ?Sized
> super::Recover
<Q
> for BTreeMap
<K
, ()>
223 fn get(&self, key
: &Q
) -> Option
<&K
> {
224 let root_node
= self.root
.as_ref()?
.node_as_ref();
225 match search
::search_tree(root_node
, key
) {
226 Found(handle
) => Some(handle
.into_kv().0),
231 fn take(&mut self, key
: &Q
) -> Option
<K
> {
232 let (map
, dormant_map
) = DormantMutRef
::new(self);
233 let root_node
= map
.root
.as_mut()?
.node_as_mut();
234 match search
::search_tree(root_node
, key
) {
236 Some(OccupiedEntry { handle, dormant_map, _marker: PhantomData }
.remove_kv().0)
242 fn replace(&mut self, key
: K
) -> Option
<K
> {
243 let (map
, dormant_map
) = DormantMutRef
::new(self);
244 let root_node
= Self::ensure_is_owned(&mut map
.root
).node_as_mut();
245 match search
::search_tree
::<marker
::Mut
<'_
>, K
, (), K
>(root_node
, &key
) {
246 Found(handle
) => Some(mem
::replace(handle
.into_key_mut(), key
)),
248 VacantEntry { key, handle, dormant_map, _marker: PhantomData }
.insert(());
255 /// An iterator over the entries of a `BTreeMap`.
257 /// This `struct` is created by the [`iter`] method on [`BTreeMap`]. See its
258 /// documentation for more.
260 /// [`iter`]: BTreeMap::iter
261 #[stable(feature = "rust1", since = "1.0.0")]
262 pub struct Iter
<'a
, K
: 'a
, V
: 'a
> {
263 range
: Range
<'a
, K
, V
>,
267 #[stable(feature = "collection_debug", since = "1.17.0")]
268 impl<K
: fmt
::Debug
, V
: fmt
::Debug
> fmt
::Debug
for Iter
<'_
, K
, V
> {
269 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
270 f
.debug_list().entries(self.clone()).finish()
274 /// A mutable iterator over the entries of a `BTreeMap`.
276 /// This `struct` is created by the [`iter_mut`] method on [`BTreeMap`]. See its
277 /// documentation for more.
279 /// [`iter_mut`]: BTreeMap::iter_mut
280 #[stable(feature = "rust1", since = "1.0.0")]
282 pub struct IterMut
<'a
, K
: 'a
, V
: 'a
> {
283 range
: RangeMut
<'a
, K
, V
>,
287 /// An owning iterator over the entries of a `BTreeMap`.
289 /// This `struct` is created by the [`into_iter`] method on [`BTreeMap`]
290 /// (provided by the `IntoIterator` trait). See its documentation for more.
292 /// [`into_iter`]: IntoIterator::into_iter
293 #[stable(feature = "rust1", since = "1.0.0")]
294 pub struct IntoIter
<K
, V
> {
295 front
: Option
<Handle
<NodeRef
<marker
::Owned
, K
, V
, marker
::Leaf
>, marker
::Edge
>>,
296 back
: Option
<Handle
<NodeRef
<marker
::Owned
, K
, V
, marker
::Leaf
>, marker
::Edge
>>,
300 impl<K
, V
> IntoIter
<K
, V
> {
301 /// Returns an iterator of references over the remaining items.
303 pub(super) fn iter(&self) -> Iter
<'_
, K
, V
> {
305 front
: self.front
.as_ref().map(|f
| f
.reborrow()),
306 back
: self.back
.as_ref().map(|b
| b
.reborrow()),
309 Iter { range: range, length: self.length }
313 #[stable(feature = "collection_debug", since = "1.17.0")]
314 impl<K
: fmt
::Debug
, V
: fmt
::Debug
> fmt
::Debug
for IntoIter
<K
, V
> {
315 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
316 f
.debug_list().entries(self.iter()).finish()
320 /// An iterator over the keys of a `BTreeMap`.
322 /// This `struct` is created by the [`keys`] method on [`BTreeMap`]. See its
323 /// documentation for more.
325 /// [`keys`]: BTreeMap::keys
326 #[stable(feature = "rust1", since = "1.0.0")]
327 pub struct Keys
<'a
, K
: 'a
, V
: 'a
> {
328 inner
: Iter
<'a
, K
, V
>,
331 #[stable(feature = "collection_debug", since = "1.17.0")]
332 impl<K
: fmt
::Debug
, V
> fmt
::Debug
for Keys
<'_
, K
, V
> {
333 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
334 f
.debug_list().entries(self.clone()).finish()
338 /// An iterator over the values of a `BTreeMap`.
340 /// This `struct` is created by the [`values`] method on [`BTreeMap`]. See its
341 /// documentation for more.
343 /// [`values`]: BTreeMap::values
344 #[stable(feature = "rust1", since = "1.0.0")]
345 pub struct Values
<'a
, K
: 'a
, V
: 'a
> {
346 inner
: Iter
<'a
, K
, V
>,
349 #[stable(feature = "collection_debug", since = "1.17.0")]
350 impl<K
, V
: fmt
::Debug
> fmt
::Debug
for Values
<'_
, K
, V
> {
351 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
352 f
.debug_list().entries(self.clone()).finish()
356 /// A mutable iterator over the values of a `BTreeMap`.
358 /// This `struct` is created by the [`values_mut`] method on [`BTreeMap`]. See its
359 /// documentation for more.
361 /// [`values_mut`]: BTreeMap::values_mut
362 #[stable(feature = "map_values_mut", since = "1.10.0")]
363 pub struct ValuesMut
<'a
, K
: 'a
, V
: 'a
> {
364 inner
: IterMut
<'a
, K
, V
>,
367 #[stable(feature = "map_values_mut", since = "1.10.0")]
368 impl<K
, V
: fmt
::Debug
> fmt
::Debug
for ValuesMut
<'_
, K
, V
> {
369 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
370 f
.debug_list().entries(self.inner
.iter().map(|(_
, val
)| val
)).finish()
374 /// An owning iterator over the keys of a `BTreeMap`.
376 /// This `struct` is created by the [`into_keys`] method on [`BTreeMap`].
377 /// See its documentation for more.
379 /// [`into_keys`]: BTreeMap::into_keys
380 #[unstable(feature = "map_into_keys_values", issue = "75294")]
381 pub struct IntoKeys
<K
, V
> {
382 inner
: IntoIter
<K
, V
>,
385 #[unstable(feature = "map_into_keys_values", issue = "75294")]
386 impl<K
: fmt
::Debug
, V
> fmt
::Debug
for IntoKeys
<K
, V
> {
387 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
388 f
.debug_list().entries(self.inner
.iter().map(|(key
, _
)| key
)).finish()
392 /// An owning iterator over the values of a `BTreeMap`.
394 /// This `struct` is created by the [`into_values`] method on [`BTreeMap`].
395 /// See its documentation for more.
397 /// [`into_values`]: BTreeMap::into_values
398 #[unstable(feature = "map_into_keys_values", issue = "75294")]
399 pub struct IntoValues
<K
, V
> {
400 inner
: IntoIter
<K
, V
>,
403 #[unstable(feature = "map_into_keys_values", issue = "75294")]
404 impl<K
, V
: fmt
::Debug
> fmt
::Debug
for IntoValues
<K
, V
> {
405 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
406 f
.debug_list().entries(self.inner
.iter().map(|(_
, val
)| val
)).finish()
410 /// An iterator over a sub-range of entries in a `BTreeMap`.
412 /// This `struct` is created by the [`range`] method on [`BTreeMap`]. See its
413 /// documentation for more.
415 /// [`range`]: BTreeMap::range
416 #[stable(feature = "btree_range", since = "1.17.0")]
417 pub struct Range
<'a
, K
: 'a
, V
: 'a
> {
418 front
: Option
<Handle
<NodeRef
<marker
::Immut
<'a
>, K
, V
, marker
::Leaf
>, marker
::Edge
>>,
419 back
: Option
<Handle
<NodeRef
<marker
::Immut
<'a
>, K
, V
, marker
::Leaf
>, marker
::Edge
>>,
422 #[stable(feature = "collection_debug", since = "1.17.0")]
423 impl<K
: fmt
::Debug
, V
: fmt
::Debug
> fmt
::Debug
for Range
<'_
, K
, V
> {
424 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
425 f
.debug_list().entries(self.clone()).finish()
429 /// A mutable iterator over a sub-range of entries in a `BTreeMap`.
431 /// This `struct` is created by the [`range_mut`] method on [`BTreeMap`]. See its
432 /// documentation for more.
434 /// [`range_mut`]: BTreeMap::range_mut
435 #[stable(feature = "btree_range", since = "1.17.0")]
436 pub struct RangeMut
<'a
, K
: 'a
, V
: 'a
> {
437 front
: Option
<Handle
<NodeRef
<marker
::ValMut
<'a
>, K
, V
, marker
::Leaf
>, marker
::Edge
>>,
438 back
: Option
<Handle
<NodeRef
<marker
::ValMut
<'a
>, K
, V
, marker
::Leaf
>, marker
::Edge
>>,
440 // Be invariant in `K` and `V`
441 _marker
: PhantomData
<&'a
mut (K
, V
)>,
444 #[stable(feature = "collection_debug", since = "1.17.0")]
445 impl<K
: fmt
::Debug
, V
: fmt
::Debug
> fmt
::Debug
for RangeMut
<'_
, K
, V
> {
446 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
448 front
: self.front
.as_ref().map(|f
| f
.reborrow()),
449 back
: self.back
.as_ref().map(|b
| b
.reborrow()),
451 f
.debug_list().entries(range
).finish()
455 /// A view into a single entry in a map, which may either be vacant or occupied.
457 /// This `enum` is constructed from the [`entry`] method on [`BTreeMap`].
459 /// [`entry`]: BTreeMap::entry
460 #[stable(feature = "rust1", since = "1.0.0")]
461 pub enum Entry
<'a
, K
: 'a
, V
: 'a
> {
463 #[stable(feature = "rust1", since = "1.0.0")]
464 Vacant(#[stable(feature = "rust1", since = "1.0.0")] VacantEntry<'a, K, V>),
466 /// An occupied entry.
467 #[stable(feature = "rust1", since = "1.0.0")]
468 Occupied(#[stable(feature = "rust1", since = "1.0.0")] OccupiedEntry<'a, K, V>),
471 #[stable(feature = "debug_btree_map", since = "1.12.0")]
472 impl<K
: Debug
+ Ord
, V
: Debug
> Debug
for Entry
<'_
, K
, V
> {
473 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
475 Vacant(ref v
) => f
.debug_tuple("Entry").field(v
).finish(),
476 Occupied(ref o
) => f
.debug_tuple("Entry").field(o
).finish(),
481 /// A view into a vacant entry in a `BTreeMap`.
482 /// It is part of the [`Entry`] enum.
483 #[stable(feature = "rust1", since = "1.0.0")]
484 pub struct VacantEntry
<'a
, K
: 'a
, V
: 'a
> {
486 handle
: Handle
<NodeRef
<marker
::Mut
<'a
>, K
, V
, marker
::Leaf
>, marker
::Edge
>,
487 dormant_map
: DormantMutRef
<'a
, BTreeMap
<K
, V
>>,
489 // Be invariant in `K` and `V`
490 _marker
: PhantomData
<&'a
mut (K
, V
)>,
493 #[stable(feature = "debug_btree_map", since = "1.12.0")]
494 impl<K
: Debug
+ Ord
, V
> Debug
for VacantEntry
<'_
, K
, V
> {
495 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
496 f
.debug_tuple("VacantEntry").field(self.key()).finish()
500 /// A view into an occupied entry in a `BTreeMap`.
501 /// It is part of the [`Entry`] enum.
502 #[stable(feature = "rust1", since = "1.0.0")]
503 pub struct OccupiedEntry
<'a
, K
: 'a
, V
: 'a
> {
504 handle
: Handle
<NodeRef
<marker
::Mut
<'a
>, K
, V
, marker
::LeafOrInternal
>, marker
::KV
>,
505 dormant_map
: DormantMutRef
<'a
, BTreeMap
<K
, V
>>,
507 // Be invariant in `K` and `V`
508 _marker
: PhantomData
<&'a
mut (K
, V
)>,
511 #[stable(feature = "debug_btree_map", since = "1.12.0")]
512 impl<K
: Debug
+ Ord
, V
: Debug
> Debug
for OccupiedEntry
<'_
, K
, V
> {
513 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
514 f
.debug_struct("OccupiedEntry").field("key", self.key()).field("value", self.get()).finish()
518 // An iterator for merging two sorted sequences into one
519 struct MergeIter
<K
, V
, I
: Iterator
<Item
= (K
, V
)>> {
524 impl<K
: Ord
, V
> BTreeMap
<K
, V
> {
525 /// Makes a new empty BTreeMap.
527 /// Does not allocate anything on its own.
534 /// use std::collections::BTreeMap;
536 /// let mut map = BTreeMap::new();
538 /// // entries can now be inserted into the empty map
539 /// map.insert(1, "a");
541 #[stable(feature = "rust1", since = "1.0.0")]
542 #[rustc_const_unstable(feature = "const_btree_new", issue = "71835")]
543 pub const fn new() -> BTreeMap
<K
, V
> {
544 BTreeMap { root: None, length: 0 }
547 /// Clears the map, removing all elements.
554 /// use std::collections::BTreeMap;
556 /// let mut a = BTreeMap::new();
557 /// a.insert(1, "a");
559 /// assert!(a.is_empty());
561 #[stable(feature = "rust1", since = "1.0.0")]
562 pub fn clear(&mut self) {
563 *self = BTreeMap
::new();
566 /// Returns a reference to the value corresponding to the key.
568 /// The key may be any borrowed form of the map's key type, but the ordering
569 /// on the borrowed form *must* match the ordering on the key type.
576 /// use std::collections::BTreeMap;
578 /// let mut map = BTreeMap::new();
579 /// map.insert(1, "a");
580 /// assert_eq!(map.get(&1), Some(&"a"));
581 /// assert_eq!(map.get(&2), None);
583 #[stable(feature = "rust1", since = "1.0.0")]
584 pub fn get
<Q
: ?Sized
>(&self, key
: &Q
) -> Option
<&V
>
589 let root_node
= self.root
.as_ref()?
.node_as_ref();
590 match search
::search_tree(root_node
, key
) {
591 Found(handle
) => Some(handle
.into_kv().1),
596 /// Returns the key-value pair corresponding to the supplied key.
598 /// The supplied key may be any borrowed form of the map's key type, but the ordering
599 /// on the borrowed form *must* match the ordering on the key type.
604 /// use std::collections::BTreeMap;
606 /// let mut map = BTreeMap::new();
607 /// map.insert(1, "a");
608 /// assert_eq!(map.get_key_value(&1), Some((&1, &"a")));
609 /// assert_eq!(map.get_key_value(&2), None);
611 #[stable(feature = "map_get_key_value", since = "1.40.0")]
612 pub fn get_key_value
<Q
: ?Sized
>(&self, k
: &Q
) -> Option
<(&K
, &V
)>
617 let root_node
= self.root
.as_ref()?
.node_as_ref();
618 match search
::search_tree(root_node
, k
) {
619 Found(handle
) => Some(handle
.into_kv()),
624 /// Returns the first key-value pair in the map.
625 /// The key in this pair is the minimum key in the map.
632 /// #![feature(map_first_last)]
633 /// use std::collections::BTreeMap;
635 /// let mut map = BTreeMap::new();
636 /// assert_eq!(map.first_key_value(), None);
637 /// map.insert(1, "b");
638 /// map.insert(2, "a");
639 /// assert_eq!(map.first_key_value(), Some((&1, &"b")));
641 #[unstable(feature = "map_first_last", issue = "62924")]
642 pub fn first_key_value(&self) -> Option
<(&K
, &V
)> {
643 let root_node
= self.root
.as_ref()?
.node_as_ref();
644 root_node
.first_leaf_edge().right_kv().ok().map(Handle
::into_kv
)
647 /// Returns the first entry in the map for in-place manipulation.
648 /// The key of this entry is the minimum key in the map.
653 /// #![feature(map_first_last)]
654 /// use std::collections::BTreeMap;
656 /// let mut map = BTreeMap::new();
657 /// map.insert(1, "a");
658 /// map.insert(2, "b");
659 /// if let Some(mut entry) = map.first_entry() {
660 /// if *entry.key() > 0 {
661 /// entry.insert("first");
664 /// assert_eq!(*map.get(&1).unwrap(), "first");
665 /// assert_eq!(*map.get(&2).unwrap(), "b");
667 #[unstable(feature = "map_first_last", issue = "62924")]
668 pub fn first_entry(&mut self) -> Option
<OccupiedEntry
<'_
, K
, V
>> {
669 let (map
, dormant_map
) = DormantMutRef
::new(self);
670 let root_node
= map
.root
.as_mut()?
.node_as_mut();
671 let kv
= root_node
.first_leaf_edge().right_kv().ok()?
;
672 Some(OccupiedEntry { handle: kv.forget_node_type(), dormant_map, _marker: PhantomData }
)
675 /// Removes and returns the first element in the map.
676 /// The key of this element is the minimum key that was in the map.
680 /// Draining elements in ascending order, while keeping a usable map each iteration.
683 /// #![feature(map_first_last)]
684 /// use std::collections::BTreeMap;
686 /// let mut map = BTreeMap::new();
687 /// map.insert(1, "a");
688 /// map.insert(2, "b");
689 /// while let Some((key, _val)) = map.pop_first() {
690 /// assert!(map.iter().all(|(k, _v)| *k > key));
692 /// assert!(map.is_empty());
694 #[unstable(feature = "map_first_last", issue = "62924")]
695 pub fn pop_first(&mut self) -> Option
<(K
, V
)> {
696 self.first_entry().map(|entry
| entry
.remove_entry())
699 /// Returns the last key-value pair in the map.
700 /// The key in this pair is the maximum key in the map.
707 /// #![feature(map_first_last)]
708 /// use std::collections::BTreeMap;
710 /// let mut map = BTreeMap::new();
711 /// map.insert(1, "b");
712 /// map.insert(2, "a");
713 /// assert_eq!(map.last_key_value(), Some((&2, &"a")));
715 #[unstable(feature = "map_first_last", issue = "62924")]
716 pub fn last_key_value(&self) -> Option
<(&K
, &V
)> {
717 let root_node
= self.root
.as_ref()?
.node_as_ref();
718 root_node
.last_leaf_edge().left_kv().ok().map(Handle
::into_kv
)
721 /// Returns the last entry in the map for in-place manipulation.
722 /// The key of this entry is the maximum key in the map.
727 /// #![feature(map_first_last)]
728 /// use std::collections::BTreeMap;
730 /// let mut map = BTreeMap::new();
731 /// map.insert(1, "a");
732 /// map.insert(2, "b");
733 /// if let Some(mut entry) = map.last_entry() {
734 /// if *entry.key() > 0 {
735 /// entry.insert("last");
738 /// assert_eq!(*map.get(&1).unwrap(), "a");
739 /// assert_eq!(*map.get(&2).unwrap(), "last");
741 #[unstable(feature = "map_first_last", issue = "62924")]
742 pub fn last_entry(&mut self) -> Option
<OccupiedEntry
<'_
, K
, V
>> {
743 let (map
, dormant_map
) = DormantMutRef
::new(self);
744 let root_node
= map
.root
.as_mut()?
.node_as_mut();
745 let kv
= root_node
.last_leaf_edge().left_kv().ok()?
;
746 Some(OccupiedEntry { handle: kv.forget_node_type(), dormant_map, _marker: PhantomData }
)
749 /// Removes and returns the last element in the map.
750 /// The key of this element is the maximum key that was in the map.
754 /// Draining elements in descending order, while keeping a usable map each iteration.
757 /// #![feature(map_first_last)]
758 /// use std::collections::BTreeMap;
760 /// let mut map = BTreeMap::new();
761 /// map.insert(1, "a");
762 /// map.insert(2, "b");
763 /// while let Some((key, _val)) = map.pop_last() {
764 /// assert!(map.iter().all(|(k, _v)| *k < key));
766 /// assert!(map.is_empty());
768 #[unstable(feature = "map_first_last", issue = "62924")]
769 pub fn pop_last(&mut self) -> Option
<(K
, V
)> {
770 self.last_entry().map(|entry
| entry
.remove_entry())
773 /// Returns `true` if the map contains a value for the specified key.
775 /// The key may be any borrowed form of the map's key type, but the ordering
776 /// on the borrowed form *must* match the ordering on the key type.
783 /// use std::collections::BTreeMap;
785 /// let mut map = BTreeMap::new();
786 /// map.insert(1, "a");
787 /// assert_eq!(map.contains_key(&1), true);
788 /// assert_eq!(map.contains_key(&2), false);
790 #[stable(feature = "rust1", since = "1.0.0")]
791 pub fn contains_key
<Q
: ?Sized
>(&self, key
: &Q
) -> bool
796 self.get(key
).is_some()
799 /// Returns a mutable reference to the value corresponding to the key.
801 /// The key may be any borrowed form of the map's key type, but the ordering
802 /// on the borrowed form *must* match the ordering on the key type.
809 /// use std::collections::BTreeMap;
811 /// let mut map = BTreeMap::new();
812 /// map.insert(1, "a");
813 /// if let Some(x) = map.get_mut(&1) {
816 /// assert_eq!(map[&1], "b");
818 // See `get` for implementation notes, this is basically a copy-paste with mut's added
819 #[stable(feature = "rust1", since = "1.0.0")]
820 pub fn get_mut
<Q
: ?Sized
>(&mut self, key
: &Q
) -> Option
<&mut V
>
825 let root_node
= self.root
.as_mut()?
.node_as_mut();
826 match search
::search_tree(root_node
, key
) {
827 Found(handle
) => Some(handle
.into_val_mut()),
832 /// Inserts a key-value pair into the map.
834 /// If the map did not have this key present, `None` is returned.
836 /// If the map did have this key present, the value is updated, and the old
837 /// value is returned. The key is not updated, though; this matters for
838 /// types that can be `==` without being identical. See the [module-level
839 /// documentation] for more.
841 /// [module-level documentation]: index.html#insert-and-complex-keys
848 /// use std::collections::BTreeMap;
850 /// let mut map = BTreeMap::new();
851 /// assert_eq!(map.insert(37, "a"), None);
852 /// assert_eq!(map.is_empty(), false);
854 /// map.insert(37, "b");
855 /// assert_eq!(map.insert(37, "c"), Some("b"));
856 /// assert_eq!(map[&37], "c");
858 #[stable(feature = "rust1", since = "1.0.0")]
859 pub fn insert(&mut self, key
: K
, value
: V
) -> Option
<V
> {
860 match self.entry(key
) {
861 Occupied(mut entry
) => Some(entry
.insert(value
)),
869 /// Removes a key from the map, returning the value at the key if the key
870 /// was previously in the map.
872 /// The key may be any borrowed form of the map's key type, but the ordering
873 /// on the borrowed form *must* match the ordering on the key type.
880 /// use std::collections::BTreeMap;
882 /// let mut map = BTreeMap::new();
883 /// map.insert(1, "a");
884 /// assert_eq!(map.remove(&1), Some("a"));
885 /// assert_eq!(map.remove(&1), None);
887 #[stable(feature = "rust1", since = "1.0.0")]
888 pub fn remove
<Q
: ?Sized
>(&mut self, key
: &Q
) -> Option
<V
>
893 self.remove_entry(key
).map(|(_
, v
)| v
)
896 /// Removes a key from the map, returning the stored key and value if the key
897 /// was previously in the map.
899 /// The key may be any borrowed form of the map's key type, but the ordering
900 /// on the borrowed form *must* match the ordering on the key type.
907 /// use std::collections::BTreeMap;
909 /// let mut map = BTreeMap::new();
910 /// map.insert(1, "a");
911 /// assert_eq!(map.remove_entry(&1), Some((1, "a")));
912 /// assert_eq!(map.remove_entry(&1), None);
914 #[stable(feature = "btreemap_remove_entry", since = "1.45.0")]
915 pub fn remove_entry
<Q
: ?Sized
>(&mut self, key
: &Q
) -> Option
<(K
, V
)>
920 let (map
, dormant_map
) = DormantMutRef
::new(self);
921 let root_node
= map
.root
.as_mut()?
.node_as_mut();
922 match search
::search_tree(root_node
, key
) {
924 Some(OccupiedEntry { handle, dormant_map, _marker: PhantomData }
.remove_entry())
930 /// Moves all elements from `other` into `Self`, leaving `other` empty.
935 /// use std::collections::BTreeMap;
937 /// let mut a = BTreeMap::new();
938 /// a.insert(1, "a");
939 /// a.insert(2, "b");
940 /// a.insert(3, "c");
942 /// let mut b = BTreeMap::new();
943 /// b.insert(3, "d");
944 /// b.insert(4, "e");
945 /// b.insert(5, "f");
947 /// a.append(&mut b);
949 /// assert_eq!(a.len(), 5);
950 /// assert_eq!(b.len(), 0);
952 /// assert_eq!(a[&1], "a");
953 /// assert_eq!(a[&2], "b");
954 /// assert_eq!(a[&3], "d");
955 /// assert_eq!(a[&4], "e");
956 /// assert_eq!(a[&5], "f");
958 #[stable(feature = "btree_append", since = "1.11.0")]
959 pub fn append(&mut self, other
: &mut Self) {
960 // Do we have to append anything at all?
961 if other
.is_empty() {
965 // We can just swap `self` and `other` if `self` is empty.
967 mem
::swap(self, other
);
971 // First, we merge `self` and `other` into a sorted sequence in linear time.
972 let self_iter
= mem
::take(self).into_iter();
973 let other_iter
= mem
::take(other
).into_iter();
974 let iter
= MergeIter { left: self_iter.peekable(), right: other_iter.peekable() }
;
976 // Second, we build a tree from the sorted sequence in linear time.
977 self.from_sorted_iter(iter
);
980 /// Constructs a double-ended iterator over a sub-range of elements in the map.
981 /// The simplest way is to use the range syntax `min..max`, thus `range(min..max)` will
982 /// yield elements from min (inclusive) to max (exclusive).
983 /// The range may also be entered as `(Bound<T>, Bound<T>)`, so for example
984 /// `range((Excluded(4), Included(10)))` will yield a left-exclusive, right-inclusive
985 /// range from 4 to 10.
989 /// Panics if range `start > end`.
990 /// Panics if range `start == end` and both bounds are `Excluded`.
997 /// use std::collections::BTreeMap;
998 /// use std::ops::Bound::Included;
1000 /// let mut map = BTreeMap::new();
1001 /// map.insert(3, "a");
1002 /// map.insert(5, "b");
1003 /// map.insert(8, "c");
1004 /// for (&key, &value) in map.range((Included(&4), Included(&8))) {
1005 /// println!("{}: {}", key, value);
1007 /// assert_eq!(Some((&5, &"b")), map.range(4..).next());
1009 #[stable(feature = "btree_range", since = "1.17.0")]
1010 pub fn range
<T
: ?Sized
, R
>(&self, range
: R
) -> Range
<'_
, K
, V
>
1016 if let Some(root
) = &self.root
{
1017 let (f
, b
) = root
.node_as_ref().range_search(range
);
1019 Range { front: Some(f), back: Some(b) }
1021 Range { front: None, back: None }
1025 /// Constructs a mutable double-ended iterator over a sub-range of elements in the map.
1026 /// The simplest way is to use the range syntax `min..max`, thus `range(min..max)` will
1027 /// yield elements from min (inclusive) to max (exclusive).
1028 /// The range may also be entered as `(Bound<T>, Bound<T>)`, so for example
1029 /// `range((Excluded(4), Included(10)))` will yield a left-exclusive, right-inclusive
1030 /// range from 4 to 10.
1034 /// Panics if range `start > end`.
1035 /// Panics if range `start == end` and both bounds are `Excluded`.
1042 /// use std::collections::BTreeMap;
1044 /// let mut map: BTreeMap<&str, i32> = ["Alice", "Bob", "Carol", "Cheryl"]
1046 /// .map(|&s| (s, 0))
1048 /// for (_, balance) in map.range_mut("B".."Cheryl") {
1049 /// *balance += 100;
1051 /// for (name, balance) in &map {
1052 /// println!("{} => {}", name, balance);
1055 #[stable(feature = "btree_range", since = "1.17.0")]
1056 pub fn range_mut
<T
: ?Sized
, R
>(&mut self, range
: R
) -> RangeMut
<'_
, K
, V
>
1062 if let Some(root
) = &mut self.root
{
1063 let (f
, b
) = root
.node_as_valmut().range_search(range
);
1065 RangeMut { front: Some(f), back: Some(b), _marker: PhantomData }
1067 RangeMut { front: None, back: None, _marker: PhantomData }
1071 /// Gets the given key's corresponding entry in the map for in-place manipulation.
1078 /// use std::collections::BTreeMap;
1080 /// let mut count: BTreeMap<&str, usize> = BTreeMap::new();
1082 /// // count the number of occurrences of letters in the vec
1083 /// for x in vec!["a","b","a","c","a","b"] {
1084 /// *count.entry(x).or_insert(0) += 1;
1087 /// assert_eq!(count["a"], 3);
1089 #[stable(feature = "rust1", since = "1.0.0")]
1090 pub fn entry(&mut self, key
: K
) -> Entry
<'_
, K
, V
> {
1091 // FIXME(@porglezomp) Avoid allocating if we don't insert
1092 let (map
, dormant_map
) = DormantMutRef
::new(self);
1093 let root_node
= Self::ensure_is_owned(&mut map
.root
).node_as_mut();
1094 match search
::search_tree(root_node
, &key
) {
1095 Found(handle
) => Occupied(OccupiedEntry { handle, dormant_map, _marker: PhantomData }
),
1097 Vacant(VacantEntry { key, handle, dormant_map, _marker: PhantomData }
)
1102 fn from_sorted_iter
<I
: Iterator
<Item
= (K
, V
)>>(&mut self, iter
: I
) {
1103 let root
= Self::ensure_is_owned(&mut self.root
);
1104 let mut cur_node
= root
.node_as_mut().last_leaf_edge().into_node();
1105 // Iterate through all key-value pairs, pushing them into nodes at the right level.
1106 for (key
, value
) in iter
{
1107 // Try to push key-value pair into the current leaf node.
1108 if cur_node
.len() < node
::CAPACITY
{
1109 cur_node
.push(key
, value
);
1111 // No space left, go up and push there.
1113 let mut test_node
= cur_node
.forget_type();
1115 match test_node
.ascend() {
1117 let parent
= parent
.into_node();
1118 if parent
.len() < node
::CAPACITY
{
1119 // Found a node with space left, push here.
1124 test_node
= parent
.forget_type();
1128 // We are at the top, create a new root node and push there.
1129 open_node
= root
.push_internal_level();
1135 // Push key-value pair and new right subtree.
1136 let tree_height
= open_node
.height() - 1;
1137 let mut right_tree
= node
::Root
::new_leaf();
1138 for _
in 0..tree_height
{
1139 right_tree
.push_internal_level();
1141 open_node
.push(key
, value
, right_tree
);
1143 // Go down to the right-most leaf again.
1144 cur_node
= open_node
.forget_type().last_leaf_edge().into_node();
1149 Self::fix_right_edge(root
)
1152 fn fix_right_edge(root
: &mut node
::Root
<K
, V
>) {
1153 // Handle underfull nodes, start from the top.
1154 let mut cur_node
= root
.node_as_mut();
1155 while let Internal(internal
) = cur_node
.force() {
1156 // Check if right-most child is underfull.
1157 let mut last_edge
= internal
.last_edge();
1158 let right_child_len
= last_edge
.reborrow().descend().len();
1159 if right_child_len
< node
::MIN_LEN
{
1160 // We need to steal.
1161 let mut last_kv
= match last_edge
.left_kv() {
1163 Err(_
) => unreachable
!(),
1165 last_kv
.bulk_steal_left(node
::MIN_LEN
- right_child_len
);
1166 last_edge
= last_kv
.right_edge();
1170 cur_node
= last_edge
.descend();
1174 /// Splits the collection into two at the given key. Returns everything after the given key,
1175 /// including the key.
1182 /// use std::collections::BTreeMap;
1184 /// let mut a = BTreeMap::new();
1185 /// a.insert(1, "a");
1186 /// a.insert(2, "b");
1187 /// a.insert(3, "c");
1188 /// a.insert(17, "d");
1189 /// a.insert(41, "e");
1191 /// let b = a.split_off(&3);
1193 /// assert_eq!(a.len(), 2);
1194 /// assert_eq!(b.len(), 3);
1196 /// assert_eq!(a[&1], "a");
1197 /// assert_eq!(a[&2], "b");
1199 /// assert_eq!(b[&3], "c");
1200 /// assert_eq!(b[&17], "d");
1201 /// assert_eq!(b[&41], "e");
1203 #[stable(feature = "btree_split_off", since = "1.11.0")]
1204 pub fn split_off
<Q
: ?Sized
+ Ord
>(&mut self, key
: &Q
) -> Self
1208 if self.is_empty() {
1212 let total_num
= self.len();
1213 let left_root
= self.root
.as_mut().unwrap(); // unwrap succeeds because not empty
1215 let mut right
= Self::new();
1216 let right_root
= Self::ensure_is_owned(&mut right
.root
);
1217 for _
in 0..left_root
.height() {
1218 right_root
.push_internal_level();
1222 let mut left_node
= left_root
.node_as_mut();
1223 let mut right_node
= right_root
.node_as_mut();
1226 let mut split_edge
= match search
::search_node(left_node
, key
) {
1227 // key is going to the right tree
1228 Found(handle
) => handle
.left_edge(),
1229 GoDown(handle
) => handle
,
1232 split_edge
.move_suffix(&mut right_node
);
1234 match (split_edge
.force(), right_node
.force()) {
1235 (Internal(edge
), Internal(node
)) => {
1236 left_node
= edge
.descend();
1237 right_node
= node
.first_edge().descend();
1239 (Leaf(_
), Leaf(_
)) => {
1249 left_root
.fix_right_border();
1250 right_root
.fix_left_border();
1252 if left_root
.height() < right_root
.height() {
1253 self.length
= left_root
.node_as_ref().calc_length();
1254 right
.length
= total_num
- self.len();
1256 right
.length
= right_root
.node_as_ref().calc_length();
1257 self.length
= total_num
- right
.len();
1263 /// Creates an iterator which uses a closure to determine if an element should be removed.
1265 /// If the closure returns true, the element is removed from the map and yielded.
1266 /// If the closure returns false, or panics, the element remains in the map and will not be
1269 /// Note that `drain_filter` lets you mutate every value in the filter closure, regardless of
1270 /// whether you choose to keep or remove it.
1272 /// If the iterator is only partially consumed or not consumed at all, each of the remaining
1273 /// elements will still be subjected to the closure and removed and dropped if it returns true.
1275 /// It is unspecified how many more elements will be subjected to the closure
1276 /// if a panic occurs in the closure, or a panic occurs while dropping an element,
1277 /// or if the `DrainFilter` value is leaked.
1281 /// Splitting a map into even and odd keys, reusing the original map:
1284 /// #![feature(btree_drain_filter)]
1285 /// use std::collections::BTreeMap;
1287 /// let mut map: BTreeMap<i32, i32> = (0..8).map(|x| (x, x)).collect();
1288 /// let evens: BTreeMap<_, _> = map.drain_filter(|k, _v| k % 2 == 0).collect();
1290 /// assert_eq!(evens.keys().copied().collect::<Vec<_>>(), vec![0, 2, 4, 6]);
1291 /// assert_eq!(odds.keys().copied().collect::<Vec<_>>(), vec![1, 3, 5, 7]);
1293 #[unstable(feature = "btree_drain_filter", issue = "70530")]
1294 pub fn drain_filter
<F
>(&mut self, pred
: F
) -> DrainFilter
<'_
, K
, V
, F
>
1296 F
: FnMut(&K
, &mut V
) -> bool
,
1298 DrainFilter { pred, inner: self.drain_filter_inner() }
1301 pub(super) fn drain_filter_inner(&mut self) -> DrainFilterInner
<'_
, K
, V
> {
1302 if let Some(root
) = self.root
.as_mut() {
1303 let (root
, dormant_root
) = DormantMutRef
::new(root
);
1304 let front
= root
.node_as_mut().first_leaf_edge();
1306 length
: &mut self.length
,
1307 dormant_root
: Some(dormant_root
),
1308 cur_leaf_edge
: Some(front
),
1311 DrainFilterInner { length: &mut self.length, dormant_root: None, cur_leaf_edge: None }
1315 /// Creates a consuming iterator visiting all the keys, in sorted order.
1316 /// The map cannot be used after calling this.
1317 /// The iterator element type is `K`.
1322 /// #![feature(map_into_keys_values)]
1323 /// use std::collections::BTreeMap;
1325 /// let mut a = BTreeMap::new();
1326 /// a.insert(2, "b");
1327 /// a.insert(1, "a");
1329 /// let keys: Vec<i32> = a.into_keys().collect();
1330 /// assert_eq!(keys, [1, 2]);
1333 #[unstable(feature = "map_into_keys_values", issue = "75294")]
1334 pub fn into_keys(self) -> IntoKeys
<K
, V
> {
1335 IntoKeys { inner: self.into_iter() }
1338 /// Creates a consuming iterator visiting all the values, in order by key.
1339 /// The map cannot be used after calling this.
1340 /// The iterator element type is `V`.
1345 /// #![feature(map_into_keys_values)]
1346 /// use std::collections::BTreeMap;
1348 /// let mut a = BTreeMap::new();
1349 /// a.insert(1, "hello");
1350 /// a.insert(2, "goodbye");
1352 /// let values: Vec<&str> = a.into_values().collect();
1353 /// assert_eq!(values, ["hello", "goodbye"]);
1356 #[unstable(feature = "map_into_keys_values", issue = "75294")]
1357 pub fn into_values(self) -> IntoValues
<K
, V
> {
1358 IntoValues { inner: self.into_iter() }
1362 #[stable(feature = "rust1", since = "1.0.0")]
1363 impl<'a
, K
, V
> IntoIterator
for &'a BTreeMap
<K
, V
> {
1364 type Item
= (&'a K
, &'a V
);
1365 type IntoIter
= Iter
<'a
, K
, V
>;
1367 fn into_iter(self) -> Iter
<'a
, K
, V
> {
1372 #[stable(feature = "rust1", since = "1.0.0")]
1373 impl<'a
, K
: 'a
, V
: 'a
> Iterator
for Iter
<'a
, K
, V
> {
1374 type Item
= (&'a K
, &'a V
);
1376 fn next(&mut self) -> Option
<(&'a K
, &'a V
)> {
1377 if self.length
== 0 {
1381 unsafe { Some(self.range.next_unchecked()) }
1385 fn size_hint(&self) -> (usize, Option
<usize>) {
1386 (self.length
, Some(self.length
))
1389 fn last(mut self) -> Option
<(&'a K
, &'a V
)> {
1393 fn min(mut self) -> Option
<(&'a K
, &'a V
)> {
1397 fn max(mut self) -> Option
<(&'a K
, &'a V
)> {
1402 #[stable(feature = "fused", since = "1.26.0")]
1403 impl<K
, V
> FusedIterator
for Iter
<'_
, K
, V
> {}
1405 #[stable(feature = "rust1", since = "1.0.0")]
1406 impl<'a
, K
: 'a
, V
: 'a
> DoubleEndedIterator
for Iter
<'a
, K
, V
> {
1407 fn next_back(&mut self) -> Option
<(&'a K
, &'a V
)> {
1408 if self.length
== 0 {
1412 unsafe { Some(self.range.next_back_unchecked()) }
1417 #[stable(feature = "rust1", since = "1.0.0")]
1418 impl<K
, V
> ExactSizeIterator
for Iter
<'_
, K
, V
> {
1419 fn len(&self) -> usize {
1424 #[stable(feature = "rust1", since = "1.0.0")]
1425 impl<K
, V
> Clone
for Iter
<'_
, K
, V
> {
1426 fn clone(&self) -> Self {
1427 Iter { range: self.range.clone(), length: self.length }
1431 #[stable(feature = "rust1", since = "1.0.0")]
1432 impl<'a
, K
, V
> IntoIterator
for &'a
mut BTreeMap
<K
, V
> {
1433 type Item
= (&'a K
, &'a
mut V
);
1434 type IntoIter
= IterMut
<'a
, K
, V
>;
1436 fn into_iter(self) -> IterMut
<'a
, K
, V
> {
1441 #[stable(feature = "rust1", since = "1.0.0")]
1442 impl<'a
, K
: 'a
, V
: 'a
> Iterator
for IterMut
<'a
, K
, V
> {
1443 type Item
= (&'a K
, &'a
mut V
);
1445 fn next(&mut self) -> Option
<(&'a K
, &'a
mut V
)> {
1446 if self.length
== 0 {
1450 let (k
, v
) = unsafe { self.range.next_unchecked() }
;
1451 Some((k
, v
)) // coerce k from `&mut K` to `&K`
1455 fn size_hint(&self) -> (usize, Option
<usize>) {
1456 (self.length
, Some(self.length
))
1459 fn last(mut self) -> Option
<(&'a K
, &'a
mut V
)> {
1463 fn min(mut self) -> Option
<(&'a K
, &'a
mut V
)> {
1467 fn max(mut self) -> Option
<(&'a K
, &'a
mut V
)> {
1472 #[stable(feature = "rust1", since = "1.0.0")]
1473 impl<'a
, K
: 'a
, V
: 'a
> DoubleEndedIterator
for IterMut
<'a
, K
, V
> {
1474 fn next_back(&mut self) -> Option
<(&'a K
, &'a
mut V
)> {
1475 if self.length
== 0 {
1479 let (k
, v
) = unsafe { self.range.next_back_unchecked() }
;
1480 Some((k
, v
)) // coerce k from `&mut K` to `&K`
1485 #[stable(feature = "rust1", since = "1.0.0")]
1486 impl<K
, V
> ExactSizeIterator
for IterMut
<'_
, K
, V
> {
1487 fn len(&self) -> usize {
1492 #[stable(feature = "fused", since = "1.26.0")]
1493 impl<K
, V
> FusedIterator
for IterMut
<'_
, K
, V
> {}
1495 impl<'a
, K
, V
> IterMut
<'a
, K
, V
> {
1496 /// Returns an iterator of references over the remaining items.
1498 pub(super) fn iter(&self) -> Iter
<'_
, K
, V
> {
1499 Iter { range: self.range.iter(), length: self.length }
1503 #[stable(feature = "rust1", since = "1.0.0")]
1504 impl<K
, V
> IntoIterator
for BTreeMap
<K
, V
> {
1506 type IntoIter
= IntoIter
<K
, V
>;
1508 fn into_iter(self) -> IntoIter
<K
, V
> {
1509 let mut me
= ManuallyDrop
::new(self);
1510 if let Some(root
) = me
.root
.take() {
1511 let (f
, b
) = root
.into_ref().full_range();
1513 IntoIter { front: Some(f), back: Some(b), length: me.length }
1515 IntoIter { front: None, back: None, length: 0 }
1520 #[stable(feature = "btree_drop", since = "1.7.0")]
1521 impl<K
, V
> Drop
for IntoIter
<K
, V
> {
1522 fn drop(&mut self) {
1523 struct DropGuard
<'a
, K
, V
>(&'a
mut IntoIter
<K
, V
>);
1525 impl<'a
, K
, V
> Drop
for DropGuard
<'a
, K
, V
> {
1526 fn drop(&mut self) {
1527 // Continue the same loop we perform below. This only runs when unwinding, so we
1528 // don't have to care about panics this time (they'll abort).
1529 while let Some(_
) = self.0.next() {}
1533 unwrap_unchecked(ptr
::read(&self.0.front
)).into_node().forget_type();
1534 while let Some(parent
) = node
.deallocate_and_ascend() {
1535 node
= parent
.into_node().forget_type();
1541 while let Some(pair
) = self.next() {
1542 let guard
= DropGuard(self);
1548 if let Some(front
) = ptr
::read(&self.front
) {
1549 let mut node
= front
.into_node().forget_type();
1550 // Most of the nodes have been deallocated while traversing
1551 // but one pile from a leaf up to the root is left standing.
1552 while let Some(parent
) = node
.deallocate_and_ascend() {
1553 node
= parent
.into_node().forget_type();
1560 #[stable(feature = "rust1", since = "1.0.0")]
1561 impl<K
, V
> Iterator
for IntoIter
<K
, V
> {
1564 fn next(&mut self) -> Option
<(K
, V
)> {
1565 if self.length
== 0 {
1569 Some(unsafe { self.front.as_mut().unwrap().next_unchecked() }
)
1573 fn size_hint(&self) -> (usize, Option
<usize>) {
1574 (self.length
, Some(self.length
))
1578 #[stable(feature = "rust1", since = "1.0.0")]
1579 impl<K
, V
> DoubleEndedIterator
for IntoIter
<K
, V
> {
1580 fn next_back(&mut self) -> Option
<(K
, V
)> {
1581 if self.length
== 0 {
1585 Some(unsafe { self.back.as_mut().unwrap().next_back_unchecked() }
)
1590 #[stable(feature = "rust1", since = "1.0.0")]
1591 impl<K
, V
> ExactSizeIterator
for IntoIter
<K
, V
> {
1592 fn len(&self) -> usize {
1597 #[stable(feature = "fused", since = "1.26.0")]
1598 impl<K
, V
> FusedIterator
for IntoIter
<K
, V
> {}
1600 #[stable(feature = "rust1", since = "1.0.0")]
1601 impl<'a
, K
, V
> Iterator
for Keys
<'a
, K
, V
> {
1604 fn next(&mut self) -> Option
<&'a K
> {
1605 self.inner
.next().map(|(k
, _
)| k
)
1608 fn size_hint(&self) -> (usize, Option
<usize>) {
1609 self.inner
.size_hint()
1612 fn last(mut self) -> Option
<&'a K
> {
1616 fn min(mut self) -> Option
<&'a K
> {
1620 fn max(mut self) -> Option
<&'a K
> {
1625 #[stable(feature = "rust1", since = "1.0.0")]
1626 impl<'a
, K
, V
> DoubleEndedIterator
for Keys
<'a
, K
, V
> {
1627 fn next_back(&mut self) -> Option
<&'a K
> {
1628 self.inner
.next_back().map(|(k
, _
)| k
)
1632 #[stable(feature = "rust1", since = "1.0.0")]
1633 impl<K
, V
> ExactSizeIterator
for Keys
<'_
, K
, V
> {
1634 fn len(&self) -> usize {
1639 #[stable(feature = "fused", since = "1.26.0")]
1640 impl<K
, V
> FusedIterator
for Keys
<'_
, K
, V
> {}
1642 #[stable(feature = "rust1", since = "1.0.0")]
1643 impl<K
, V
> Clone
for Keys
<'_
, K
, V
> {
1644 fn clone(&self) -> Self {
1645 Keys { inner: self.inner.clone() }
1649 #[stable(feature = "rust1", since = "1.0.0")]
1650 impl<'a
, K
, V
> Iterator
for Values
<'a
, K
, V
> {
1653 fn next(&mut self) -> Option
<&'a V
> {
1654 self.inner
.next().map(|(_
, v
)| v
)
1657 fn size_hint(&self) -> (usize, Option
<usize>) {
1658 self.inner
.size_hint()
1661 fn last(mut self) -> Option
<&'a V
> {
1666 #[stable(feature = "rust1", since = "1.0.0")]
1667 impl<'a
, K
, V
> DoubleEndedIterator
for Values
<'a
, K
, V
> {
1668 fn next_back(&mut self) -> Option
<&'a V
> {
1669 self.inner
.next_back().map(|(_
, v
)| v
)
1673 #[stable(feature = "rust1", since = "1.0.0")]
1674 impl<K
, V
> ExactSizeIterator
for Values
<'_
, K
, V
> {
1675 fn len(&self) -> usize {
1680 #[stable(feature = "fused", since = "1.26.0")]
1681 impl<K
, V
> FusedIterator
for Values
<'_
, K
, V
> {}
1683 #[stable(feature = "rust1", since = "1.0.0")]
1684 impl<K
, V
> Clone
for Values
<'_
, K
, V
> {
1685 fn clone(&self) -> Self {
1686 Values { inner: self.inner.clone() }
1690 /// An iterator produced by calling `drain_filter` on BTreeMap.
1691 #[unstable(feature = "btree_drain_filter", issue = "70530")]
1692 pub struct DrainFilter
<'a
, K
, V
, F
>
1696 F
: 'a
+ FnMut(&K
, &mut V
) -> bool
,
1699 inner
: DrainFilterInner
<'a
, K
, V
>,
1701 /// Most of the implementation of DrainFilter, independent of the type
1702 /// of the predicate, thus also serving for BTreeSet::DrainFilter.
1703 pub(super) struct DrainFilterInner
<'a
, K
: 'a
, V
: 'a
> {
1704 length
: &'a
mut usize,
1705 // dormant_root is wrapped in an Option to be able to `take` it.
1706 dormant_root
: Option
<DormantMutRef
<'a
, node
::Root
<K
, V
>>>,
1707 // cur_leaf_edge is wrapped in an Option because maps without root lack a leaf edge.
1708 cur_leaf_edge
: Option
<Handle
<NodeRef
<marker
::Mut
<'a
>, K
, V
, marker
::Leaf
>, marker
::Edge
>>,
1711 #[unstable(feature = "btree_drain_filter", issue = "70530")]
1712 impl<K
, V
, F
> Drop
for DrainFilter
<'_
, K
, V
, F
>
1714 F
: FnMut(&K
, &mut V
) -> bool
,
1716 fn drop(&mut self) {
1717 self.for_each(drop
);
1721 #[unstable(feature = "btree_drain_filter", issue = "70530")]
1722 impl<K
, V
, F
> fmt
::Debug
for DrainFilter
<'_
, K
, V
, F
>
1726 F
: FnMut(&K
, &mut V
) -> bool
,
1728 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
1729 f
.debug_tuple("DrainFilter").field(&self.inner
.peek()).finish()
1733 #[unstable(feature = "btree_drain_filter", issue = "70530")]
1734 impl<K
, V
, F
> Iterator
for DrainFilter
<'_
, K
, V
, F
>
1736 F
: FnMut(&K
, &mut V
) -> bool
,
1740 fn next(&mut self) -> Option
<(K
, V
)> {
1741 self.inner
.next(&mut self.pred
)
1744 fn size_hint(&self) -> (usize, Option
<usize>) {
1745 self.inner
.size_hint()
1749 impl<'a
, K
: 'a
, V
: 'a
> DrainFilterInner
<'a
, K
, V
> {
1750 /// Allow Debug implementations to predict the next element.
1751 pub(super) fn peek(&self) -> Option
<(&K
, &V
)> {
1752 let edge
= self.cur_leaf_edge
.as_ref()?
;
1753 edge
.reborrow().next_kv().ok().map(Handle
::into_kv
)
1756 /// Implementation of a typical `DrainFilter::next` method, given the predicate.
1757 pub(super) fn next
<F
>(&mut self, pred
: &mut F
) -> Option
<(K
, V
)>
1759 F
: FnMut(&K
, &mut V
) -> bool
,
1761 while let Ok(mut kv
) = self.cur_leaf_edge
.take()?
.next_kv() {
1762 let (k
, v
) = kv
.kv_mut();
1765 let (kv
, pos
) = kv
.remove_kv_tracking(|| {
1766 // SAFETY: we will touch the root in a way that will not
1767 // invalidate the position returned.
1768 let root
= unsafe { self.dormant_root.take().unwrap().awaken() }
;
1769 root
.pop_internal_level();
1770 self.dormant_root
= Some(DormantMutRef
::new(root
).1);
1772 self.cur_leaf_edge
= Some(pos
);
1775 self.cur_leaf_edge
= Some(kv
.next_leaf_edge());
1780 /// Implementation of a typical `DrainFilter::size_hint` method.
1781 pub(super) fn size_hint(&self) -> (usize, Option
<usize>) {
1782 (0, Some(*self.length
))
1786 #[unstable(feature = "btree_drain_filter", issue = "70530")]
1787 impl<K
, V
, F
> FusedIterator
for DrainFilter
<'_
, K
, V
, F
> where F
: FnMut(&K
, &mut V
) -> bool {}
1789 #[stable(feature = "btree_range", since = "1.17.0")]
1790 impl<'a
, K
, V
> Iterator
for Range
<'a
, K
, V
> {
1791 type Item
= (&'a K
, &'a V
);
1793 fn next(&mut self) -> Option
<(&'a K
, &'a V
)> {
1794 if self.is_empty() { None }
else { unsafe { Some(self.next_unchecked()) }
}
1797 fn last(mut self) -> Option
<(&'a K
, &'a V
)> {
1801 fn min(mut self) -> Option
<(&'a K
, &'a V
)> {
1805 fn max(mut self) -> Option
<(&'a K
, &'a V
)> {
1810 #[stable(feature = "map_values_mut", since = "1.10.0")]
1811 impl<'a
, K
, V
> Iterator
for ValuesMut
<'a
, K
, V
> {
1812 type Item
= &'a
mut V
;
1814 fn next(&mut self) -> Option
<&'a
mut V
> {
1815 self.inner
.next().map(|(_
, v
)| v
)
1818 fn size_hint(&self) -> (usize, Option
<usize>) {
1819 self.inner
.size_hint()
1822 fn last(mut self) -> Option
<&'a
mut V
> {
1827 #[stable(feature = "map_values_mut", since = "1.10.0")]
1828 impl<'a
, K
, V
> DoubleEndedIterator
for ValuesMut
<'a
, K
, V
> {
1829 fn next_back(&mut self) -> Option
<&'a
mut V
> {
1830 self.inner
.next_back().map(|(_
, v
)| v
)
1834 #[stable(feature = "map_values_mut", since = "1.10.0")]
1835 impl<K
, V
> ExactSizeIterator
for ValuesMut
<'_
, K
, V
> {
1836 fn len(&self) -> usize {
1841 #[stable(feature = "fused", since = "1.26.0")]
1842 impl<K
, V
> FusedIterator
for ValuesMut
<'_
, K
, V
> {}
1844 impl<'a
, K
, V
> Range
<'a
, K
, V
> {
1845 fn is_empty(&self) -> bool
{
1846 self.front
== self.back
1849 unsafe fn next_unchecked(&mut self) -> (&'a K
, &'a V
) {
1850 unsafe { unwrap_unchecked(self.front.as_mut()).next_unchecked() }
1854 #[unstable(feature = "map_into_keys_values", issue = "75294")]
1855 impl<K
, V
> Iterator
for IntoKeys
<K
, V
> {
1858 fn next(&mut self) -> Option
<K
> {
1859 self.inner
.next().map(|(k
, _
)| k
)
1862 fn size_hint(&self) -> (usize, Option
<usize>) {
1863 self.inner
.size_hint()
1866 fn last(mut self) -> Option
<K
> {
1870 fn min(mut self) -> Option
<K
> {
1874 fn max(mut self) -> Option
<K
> {
1879 #[unstable(feature = "map_into_keys_values", issue = "75294")]
1880 impl<K
, V
> DoubleEndedIterator
for IntoKeys
<K
, V
> {
1881 fn next_back(&mut self) -> Option
<K
> {
1882 self.inner
.next_back().map(|(k
, _
)| k
)
1886 #[unstable(feature = "map_into_keys_values", issue = "75294")]
1887 impl<K
, V
> ExactSizeIterator
for IntoKeys
<K
, V
> {
1888 fn len(&self) -> usize {
1893 #[unstable(feature = "map_into_keys_values", issue = "75294")]
1894 impl<K
, V
> FusedIterator
for IntoKeys
<K
, V
> {}
1896 #[unstable(feature = "map_into_keys_values", issue = "75294")]
1897 impl<K
, V
> Iterator
for IntoValues
<K
, V
> {
1900 fn next(&mut self) -> Option
<V
> {
1901 self.inner
.next().map(|(_
, v
)| v
)
1904 fn size_hint(&self) -> (usize, Option
<usize>) {
1905 self.inner
.size_hint()
1908 fn last(mut self) -> Option
<V
> {
1913 #[unstable(feature = "map_into_keys_values", issue = "75294")]
1914 impl<K
, V
> DoubleEndedIterator
for IntoValues
<K
, V
> {
1915 fn next_back(&mut self) -> Option
<V
> {
1916 self.inner
.next_back().map(|(_
, v
)| v
)
1920 #[unstable(feature = "map_into_keys_values", issue = "75294")]
1921 impl<K
, V
> ExactSizeIterator
for IntoValues
<K
, V
> {
1922 fn len(&self) -> usize {
1927 #[unstable(feature = "map_into_keys_values", issue = "75294")]
1928 impl<K
, V
> FusedIterator
for IntoValues
<K
, V
> {}
1930 #[stable(feature = "btree_range", since = "1.17.0")]
1931 impl<'a
, K
, V
> DoubleEndedIterator
for Range
<'a
, K
, V
> {
1932 fn next_back(&mut self) -> Option
<(&'a K
, &'a V
)> {
1933 if self.is_empty() { None }
else { Some(unsafe { self.next_back_unchecked() }
) }
1937 impl<'a
, K
, V
> Range
<'a
, K
, V
> {
1938 unsafe fn next_back_unchecked(&mut self) -> (&'a K
, &'a V
) {
1939 unsafe { unwrap_unchecked(self.back.as_mut()).next_back_unchecked() }
1943 #[stable(feature = "fused", since = "1.26.0")]
1944 impl<K
, V
> FusedIterator
for Range
<'_
, K
, V
> {}
1946 #[stable(feature = "btree_range", since = "1.17.0")]
1947 impl<K
, V
> Clone
for Range
<'_
, K
, V
> {
1948 fn clone(&self) -> Self {
1949 Range { front: self.front, back: self.back }
1953 #[stable(feature = "btree_range", since = "1.17.0")]
1954 impl<'a
, K
, V
> Iterator
for RangeMut
<'a
, K
, V
> {
1955 type Item
= (&'a K
, &'a
mut V
);
1957 fn next(&mut self) -> Option
<(&'a K
, &'a
mut V
)> {
1958 if self.is_empty() {
1961 let (k
, v
) = unsafe { self.next_unchecked() }
;
1962 Some((k
, v
)) // coerce k from `&mut K` to `&K`
1966 fn last(mut self) -> Option
<(&'a K
, &'a
mut V
)> {
1970 fn min(mut self) -> Option
<(&'a K
, &'a
mut V
)> {
1974 fn max(mut self) -> Option
<(&'a K
, &'a
mut V
)> {
1979 impl<'a
, K
, V
> RangeMut
<'a
, K
, V
> {
1980 fn is_empty(&self) -> bool
{
1981 self.front
== self.back
1984 unsafe fn next_unchecked(&mut self) -> (&'a K
, &'a
mut V
) {
1985 unsafe { unwrap_unchecked(self.front.as_mut()).next_unchecked() }
1988 /// Returns an iterator of references over the remaining items.
1990 pub(super) fn iter(&self) -> Range
<'_
, K
, V
> {
1992 front
: self.front
.as_ref().map(|f
| f
.reborrow()),
1993 back
: self.back
.as_ref().map(|b
| b
.reborrow()),
1998 #[stable(feature = "btree_range", since = "1.17.0")]
1999 impl<'a
, K
, V
> DoubleEndedIterator
for RangeMut
<'a
, K
, V
> {
2000 fn next_back(&mut self) -> Option
<(&'a K
, &'a
mut V
)> {
2001 if self.is_empty() {
2004 let (k
, v
) = unsafe { self.next_back_unchecked() }
;
2005 Some((k
, v
)) // coerce k from `&mut K` to `&K`
2010 #[stable(feature = "fused", since = "1.26.0")]
2011 impl<K
, V
> FusedIterator
for RangeMut
<'_
, K
, V
> {}
2013 impl<'a
, K
, V
> RangeMut
<'a
, K
, V
> {
2014 unsafe fn next_back_unchecked(&mut self) -> (&'a K
, &'a
mut V
) {
2015 unsafe { unwrap_unchecked(self.back.as_mut()).next_back_unchecked() }
2019 #[stable(feature = "rust1", since = "1.0.0")]
2020 impl<K
: Ord
, V
> FromIterator
<(K
, V
)> for BTreeMap
<K
, V
> {
2021 fn from_iter
<T
: IntoIterator
<Item
= (K
, V
)>>(iter
: T
) -> BTreeMap
<K
, V
> {
2022 let mut map
= BTreeMap
::new();
2028 #[stable(feature = "rust1", since = "1.0.0")]
2029 impl<K
: Ord
, V
> Extend
<(K
, V
)> for BTreeMap
<K
, V
> {
2031 fn extend
<T
: IntoIterator
<Item
= (K
, V
)>>(&mut self, iter
: T
) {
2032 iter
.into_iter().for_each(move |(k
, v
)| {
2038 fn extend_one(&mut self, (k
, v
): (K
, V
)) {
2043 #[stable(feature = "extend_ref", since = "1.2.0")]
2044 impl<'a
, K
: Ord
+ Copy
, V
: Copy
> Extend
<(&'a K
, &'a V
)> for BTreeMap
<K
, V
> {
2045 fn extend
<I
: IntoIterator
<Item
= (&'a K
, &'a V
)>>(&mut self, iter
: I
) {
2046 self.extend(iter
.into_iter().map(|(&key
, &value
)| (key
, value
)));
2050 fn extend_one(&mut self, (&k
, &v
): (&'a K
, &'a V
)) {
2055 #[stable(feature = "rust1", since = "1.0.0")]
2056 impl<K
: Hash
, V
: Hash
> Hash
for BTreeMap
<K
, V
> {
2057 fn hash
<H
: Hasher
>(&self, state
: &mut H
) {
2064 #[stable(feature = "rust1", since = "1.0.0")]
2065 impl<K
: Ord
, V
> Default
for BTreeMap
<K
, V
> {
2066 /// Creates an empty `BTreeMap<K, V>`.
2067 fn default() -> BTreeMap
<K
, V
> {
2072 #[stable(feature = "rust1", since = "1.0.0")]
2073 impl<K
: PartialEq
, V
: PartialEq
> PartialEq
for BTreeMap
<K
, V
> {
2074 fn eq(&self, other
: &BTreeMap
<K
, V
>) -> bool
{
2075 self.len() == other
.len() && self.iter().zip(other
).all(|(a
, b
)| a
== b
)
2079 #[stable(feature = "rust1", since = "1.0.0")]
2080 impl<K
: Eq
, V
: Eq
> Eq
for BTreeMap
<K
, V
> {}
2082 #[stable(feature = "rust1", since = "1.0.0")]
2083 impl<K
: PartialOrd
, V
: PartialOrd
> PartialOrd
for BTreeMap
<K
, V
> {
2085 fn partial_cmp(&self, other
: &BTreeMap
<K
, V
>) -> Option
<Ordering
> {
2086 self.iter().partial_cmp(other
.iter())
2090 #[stable(feature = "rust1", since = "1.0.0")]
2091 impl<K
: Ord
, V
: Ord
> Ord
for BTreeMap
<K
, V
> {
2093 fn cmp(&self, other
: &BTreeMap
<K
, V
>) -> Ordering
{
2094 self.iter().cmp(other
.iter())
2098 #[stable(feature = "rust1", since = "1.0.0")]
2099 impl<K
: Debug
, V
: Debug
> Debug
for BTreeMap
<K
, V
> {
2100 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
2101 f
.debug_map().entries(self.iter()).finish()
2105 #[stable(feature = "rust1", since = "1.0.0")]
2106 impl<K
: Ord
, Q
: ?Sized
, V
> Index
<&Q
> for BTreeMap
<K
, V
>
2113 /// Returns a reference to the value corresponding to the supplied key.
2117 /// Panics if the key is not present in the `BTreeMap`.
2119 fn index(&self, key
: &Q
) -> &V
{
2120 self.get(key
).expect("no entry found for key")
2124 impl<K
, V
> BTreeMap
<K
, V
> {
2125 /// Gets an iterator over the entries of the map, sorted by key.
2132 /// use std::collections::BTreeMap;
2134 /// let mut map = BTreeMap::new();
2135 /// map.insert(3, "c");
2136 /// map.insert(2, "b");
2137 /// map.insert(1, "a");
2139 /// for (key, value) in map.iter() {
2140 /// println!("{}: {}", key, value);
2143 /// let (first_key, first_value) = map.iter().next().unwrap();
2144 /// assert_eq!((*first_key, *first_value), (1, "a"));
2146 #[stable(feature = "rust1", since = "1.0.0")]
2147 pub fn iter(&self) -> Iter
<'_
, K
, V
> {
2148 if let Some(root
) = &self.root
{
2149 let (f
, b
) = root
.node_as_ref().full_range();
2151 Iter { range: Range { front: Some(f), back: Some(b) }
, length
: self.length
}
2153 Iter { range: Range { front: None, back: None }
, length
: 0 }
2157 /// Gets a mutable iterator over the entries of the map, sorted by key.
2164 /// use std::collections::BTreeMap;
2166 /// let mut map = BTreeMap::new();
2167 /// map.insert("a", 1);
2168 /// map.insert("b", 2);
2169 /// map.insert("c", 3);
2171 /// // add 10 to the value if the key isn't "a"
2172 /// for (key, value) in map.iter_mut() {
2173 /// if key != &"a" {
2178 #[stable(feature = "rust1", since = "1.0.0")]
2179 pub fn iter_mut(&mut self) -> IterMut
<'_
, K
, V
> {
2180 if let Some(root
) = &mut self.root
{
2181 let (f
, b
) = root
.node_as_valmut().full_range();
2184 range
: RangeMut { front: Some(f), back: Some(b), _marker: PhantomData }
,
2185 length
: self.length
,
2188 IterMut { range: RangeMut { front: None, back: None, _marker: PhantomData }
, length
: 0 }
2192 /// Gets an iterator over the keys of the map, in sorted order.
2199 /// use std::collections::BTreeMap;
2201 /// let mut a = BTreeMap::new();
2202 /// a.insert(2, "b");
2203 /// a.insert(1, "a");
2205 /// let keys: Vec<_> = a.keys().cloned().collect();
2206 /// assert_eq!(keys, [1, 2]);
2208 #[stable(feature = "rust1", since = "1.0.0")]
2209 pub fn keys(&self) -> Keys
<'_
, K
, V
> {
2210 Keys { inner: self.iter() }
2213 /// Gets an iterator over the values of the map, in order by key.
2220 /// use std::collections::BTreeMap;
2222 /// let mut a = BTreeMap::new();
2223 /// a.insert(1, "hello");
2224 /// a.insert(2, "goodbye");
2226 /// let values: Vec<&str> = a.values().cloned().collect();
2227 /// assert_eq!(values, ["hello", "goodbye"]);
2229 #[stable(feature = "rust1", since = "1.0.0")]
2230 pub fn values(&self) -> Values
<'_
, K
, V
> {
2231 Values { inner: self.iter() }
2234 /// Gets a mutable iterator over the values of the map, in order by key.
2241 /// use std::collections::BTreeMap;
2243 /// let mut a = BTreeMap::new();
2244 /// a.insert(1, String::from("hello"));
2245 /// a.insert(2, String::from("goodbye"));
2247 /// for value in a.values_mut() {
2248 /// value.push_str("!");
2251 /// let values: Vec<String> = a.values().cloned().collect();
2252 /// assert_eq!(values, [String::from("hello!"),
2253 /// String::from("goodbye!")]);
2255 #[stable(feature = "map_values_mut", since = "1.10.0")]
2256 pub fn values_mut(&mut self) -> ValuesMut
<'_
, K
, V
> {
2257 ValuesMut { inner: self.iter_mut() }
2260 /// Returns the number of elements in the map.
2267 /// use std::collections::BTreeMap;
2269 /// let mut a = BTreeMap::new();
2270 /// assert_eq!(a.len(), 0);
2271 /// a.insert(1, "a");
2272 /// assert_eq!(a.len(), 1);
2274 #[stable(feature = "rust1", since = "1.0.0")]
2275 pub fn len(&self) -> usize {
2279 /// Returns `true` if the map contains no elements.
2286 /// use std::collections::BTreeMap;
2288 /// let mut a = BTreeMap::new();
2289 /// assert!(a.is_empty());
2290 /// a.insert(1, "a");
2291 /// assert!(!a.is_empty());
2293 #[stable(feature = "rust1", since = "1.0.0")]
2294 pub fn is_empty(&self) -> bool
{
2298 /// If the root node is the empty (non-allocated) root node, allocate our
2299 /// own node. Is an associated function to avoid borrowing the entire BTreeMap.
2300 fn ensure_is_owned(root
: &mut Option
<node
::Root
<K
, V
>>) -> &mut node
::Root
<K
, V
> {
2301 root
.get_or_insert_with(node
::Root
::new_leaf
)
2305 impl<'a
, K
: Ord
, V
> Entry
<'a
, K
, V
> {
2306 /// Ensures a value is in the entry by inserting the default if empty, and returns
2307 /// a mutable reference to the value in the entry.
2312 /// use std::collections::BTreeMap;
2314 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2315 /// map.entry("poneyland").or_insert(12);
2317 /// assert_eq!(map["poneyland"], 12);
2319 #[stable(feature = "rust1", since = "1.0.0")]
2320 pub fn or_insert(self, default: V
) -> &'a
mut V
{
2322 Occupied(entry
) => entry
.into_mut(),
2323 Vacant(entry
) => entry
.insert(default),
2327 /// Ensures a value is in the entry by inserting the result of the default function if empty,
2328 /// and returns a mutable reference to the value in the entry.
2333 /// use std::collections::BTreeMap;
2335 /// let mut map: BTreeMap<&str, String> = BTreeMap::new();
2336 /// let s = "hoho".to_string();
2338 /// map.entry("poneyland").or_insert_with(|| s);
2340 /// assert_eq!(map["poneyland"], "hoho".to_string());
2342 #[stable(feature = "rust1", since = "1.0.0")]
2343 pub fn or_insert_with
<F
: FnOnce() -> V
>(self, default: F
) -> &'a
mut V
{
2345 Occupied(entry
) => entry
.into_mut(),
2346 Vacant(entry
) => entry
.insert(default()),
2350 #[unstable(feature = "or_insert_with_key", issue = "71024")]
2351 /// Ensures a value is in the entry by inserting, if empty, the result of the default function,
2352 /// which takes the key as its argument, and returns a mutable reference to the value in the
2358 /// #![feature(or_insert_with_key)]
2359 /// use std::collections::BTreeMap;
2361 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2363 /// map.entry("poneyland").or_insert_with_key(|key| key.chars().count());
2365 /// assert_eq!(map["poneyland"], 9);
2368 pub fn or_insert_with_key
<F
: FnOnce(&K
) -> V
>(self, default: F
) -> &'a
mut V
{
2370 Occupied(entry
) => entry
.into_mut(),
2372 let value
= default(entry
.key());
2378 /// Returns a reference to this entry's key.
2383 /// use std::collections::BTreeMap;
2385 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2386 /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
2388 #[stable(feature = "map_entry_keys", since = "1.10.0")]
2389 pub fn key(&self) -> &K
{
2391 Occupied(ref entry
) => entry
.key(),
2392 Vacant(ref entry
) => entry
.key(),
2396 /// Provides in-place mutable access to an occupied entry before any
2397 /// potential inserts into the map.
2402 /// use std::collections::BTreeMap;
2404 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2406 /// map.entry("poneyland")
2407 /// .and_modify(|e| { *e += 1 })
2409 /// assert_eq!(map["poneyland"], 42);
2411 /// map.entry("poneyland")
2412 /// .and_modify(|e| { *e += 1 })
2414 /// assert_eq!(map["poneyland"], 43);
2416 #[stable(feature = "entry_and_modify", since = "1.26.0")]
2417 pub fn and_modify
<F
>(self, f
: F
) -> Self
2422 Occupied(mut entry
) => {
2426 Vacant(entry
) => Vacant(entry
),
2431 impl<'a
, K
: Ord
, V
: Default
> Entry
<'a
, K
, V
> {
2432 #[stable(feature = "entry_or_default", since = "1.28.0")]
2433 /// Ensures a value is in the entry by inserting the default value if empty,
2434 /// and returns a mutable reference to the value in the entry.
2439 /// use std::collections::BTreeMap;
2441 /// let mut map: BTreeMap<&str, Option<usize>> = BTreeMap::new();
2442 /// map.entry("poneyland").or_default();
2444 /// assert_eq!(map["poneyland"], None);
2446 pub fn or_default(self) -> &'a
mut V
{
2448 Occupied(entry
) => entry
.into_mut(),
2449 Vacant(entry
) => entry
.insert(Default
::default()),
2454 impl<'a
, K
: Ord
, V
> VacantEntry
<'a
, K
, V
> {
2455 /// Gets a reference to the key that would be used when inserting a value
2456 /// through the VacantEntry.
2461 /// use std::collections::BTreeMap;
2463 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2464 /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
2466 #[stable(feature = "map_entry_keys", since = "1.10.0")]
2467 pub fn key(&self) -> &K
{
2471 /// Take ownership of the key.
2476 /// use std::collections::BTreeMap;
2477 /// use std::collections::btree_map::Entry;
2479 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2481 /// if let Entry::Vacant(v) = map.entry("poneyland") {
2485 #[stable(feature = "map_entry_recover_keys2", since = "1.12.0")]
2486 pub fn into_key(self) -> K
{
2490 /// Sets the value of the entry with the `VacantEntry`'s key,
2491 /// and returns a mutable reference to it.
2496 /// use std::collections::BTreeMap;
2497 /// use std::collections::btree_map::Entry;
2499 /// let mut map: BTreeMap<&str, u32> = BTreeMap::new();
2501 /// if let Entry::Vacant(o) = map.entry("poneyland") {
2504 /// assert_eq!(map["poneyland"], 37);
2506 #[stable(feature = "rust1", since = "1.0.0")]
2507 pub fn insert(self, value
: V
) -> &'a
mut V
{
2508 let out_ptr
= match self.handle
.insert_recursing(self.key
, value
) {
2509 (Fit(_
), val_ptr
) => {
2510 // Safety: We have consumed self.handle and the handle returned.
2511 let map
= unsafe { self.dormant_map.awaken() }
;
2515 (Split(ins
), val_ptr
) => {
2517 // Safety: We have consumed self.handle and the reference returned.
2518 let map
= unsafe { self.dormant_map.awaken() }
;
2519 let root
= map
.root
.as_mut().unwrap();
2520 root
.push_internal_level().push(ins
.k
, ins
.v
, ins
.right
);
2525 // Now that we have finished growing the tree using borrowed references,
2526 // dereference the pointer to a part of it, that we picked up along the way.
2527 unsafe { &mut *out_ptr }
2531 impl<'a
, K
: Ord
, V
> OccupiedEntry
<'a
, K
, V
> {
2532 /// Gets a reference to the key in the entry.
2537 /// use std::collections::BTreeMap;
2539 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2540 /// map.entry("poneyland").or_insert(12);
2541 /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
2543 #[stable(feature = "map_entry_keys", since = "1.10.0")]
2544 pub fn key(&self) -> &K
{
2545 self.handle
.reborrow().into_kv().0
2548 /// Take ownership of the key and value from the map.
2553 /// use std::collections::BTreeMap;
2554 /// use std::collections::btree_map::Entry;
2556 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2557 /// map.entry("poneyland").or_insert(12);
2559 /// if let Entry::Occupied(o) = map.entry("poneyland") {
2560 /// // We delete the entry from the map.
2561 /// o.remove_entry();
2564 /// // If now try to get the value, it will panic:
2565 /// // println!("{}", map["poneyland"]);
2567 #[stable(feature = "map_entry_recover_keys2", since = "1.12.0")]
2568 pub fn remove_entry(self) -> (K
, V
) {
2572 /// Gets a reference to the value in the entry.
2577 /// use std::collections::BTreeMap;
2578 /// use std::collections::btree_map::Entry;
2580 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2581 /// map.entry("poneyland").or_insert(12);
2583 /// if let Entry::Occupied(o) = map.entry("poneyland") {
2584 /// assert_eq!(o.get(), &12);
2587 #[stable(feature = "rust1", since = "1.0.0")]
2588 pub fn get(&self) -> &V
{
2589 self.handle
.reborrow().into_kv().1
2592 /// Gets a mutable reference to the value in the entry.
2594 /// If you need a reference to the `OccupiedEntry` that may outlive the
2595 /// destruction of the `Entry` value, see [`into_mut`].
2597 /// [`into_mut`]: OccupiedEntry::into_mut
2602 /// use std::collections::BTreeMap;
2603 /// use std::collections::btree_map::Entry;
2605 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2606 /// map.entry("poneyland").or_insert(12);
2608 /// assert_eq!(map["poneyland"], 12);
2609 /// if let Entry::Occupied(mut o) = map.entry("poneyland") {
2610 /// *o.get_mut() += 10;
2611 /// assert_eq!(*o.get(), 22);
2613 /// // We can use the same Entry multiple times.
2614 /// *o.get_mut() += 2;
2616 /// assert_eq!(map["poneyland"], 24);
2618 #[stable(feature = "rust1", since = "1.0.0")]
2619 pub fn get_mut(&mut self) -> &mut V
{
2620 self.handle
.kv_mut().1
2623 /// Converts the entry into a mutable reference to its value.
2625 /// If you need multiple references to the `OccupiedEntry`, see [`get_mut`].
2627 /// [`get_mut`]: OccupiedEntry::get_mut
2632 /// use std::collections::BTreeMap;
2633 /// use std::collections::btree_map::Entry;
2635 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2636 /// map.entry("poneyland").or_insert(12);
2638 /// assert_eq!(map["poneyland"], 12);
2639 /// if let Entry::Occupied(o) = map.entry("poneyland") {
2640 /// *o.into_mut() += 10;
2642 /// assert_eq!(map["poneyland"], 22);
2644 #[stable(feature = "rust1", since = "1.0.0")]
2645 pub fn into_mut(self) -> &'a
mut V
{
2646 self.handle
.into_val_mut()
2649 /// Sets the value of the entry with the `OccupiedEntry`'s key,
2650 /// and returns the entry's old value.
2655 /// use std::collections::BTreeMap;
2656 /// use std::collections::btree_map::Entry;
2658 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2659 /// map.entry("poneyland").or_insert(12);
2661 /// if let Entry::Occupied(mut o) = map.entry("poneyland") {
2662 /// assert_eq!(o.insert(15), 12);
2664 /// assert_eq!(map["poneyland"], 15);
2666 #[stable(feature = "rust1", since = "1.0.0")]
2667 pub fn insert(&mut self, value
: V
) -> V
{
2668 mem
::replace(self.get_mut(), value
)
2671 /// Takes the value of the entry out of the map, and returns it.
2676 /// use std::collections::BTreeMap;
2677 /// use std::collections::btree_map::Entry;
2679 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2680 /// map.entry("poneyland").or_insert(12);
2682 /// if let Entry::Occupied(o) = map.entry("poneyland") {
2683 /// assert_eq!(o.remove(), 12);
2685 /// // If we try to get "poneyland"'s value, it'll panic:
2686 /// // println!("{}", map["poneyland"]);
2688 #[stable(feature = "rust1", since = "1.0.0")]
2689 pub fn remove(self) -> V
{
2693 // Body of `remove_entry`, separate to keep the above implementations short.
2694 fn remove_kv(self) -> (K
, V
) {
2695 let mut emptied_internal_root
= false;
2696 let (old_kv
, _
) = self.handle
.remove_kv_tracking(|| emptied_internal_root
= true);
2697 // SAFETY: we consumed the intermediate root borrow, `self.handle`.
2698 let map
= unsafe { self.dormant_map.awaken() }
;
2700 if emptied_internal_root
{
2701 let root
= map
.root
.as_mut().unwrap();
2702 root
.pop_internal_level();
2708 impl<'a
, K
: 'a
, V
: 'a
> Handle
<NodeRef
<marker
::Mut
<'a
>, K
, V
, marker
::LeafOrInternal
>, marker
::KV
> {
2709 /// Removes a key/value-pair from the map, and returns that pair, as well as
2710 /// the leaf edge corresponding to that former pair.
2711 fn remove_kv_tracking
<F
: FnOnce()>(
2713 handle_emptied_internal_root
: F
,
2714 ) -> ((K
, V
), Handle
<NodeRef
<marker
::Mut
<'a
>, K
, V
, marker
::Leaf
>, marker
::Edge
>) {
2715 let (old_kv
, mut pos
, was_internal
) = match self.force() {
2717 let (old_kv
, pos
) = leaf
.remove();
2718 (old_kv
, pos
, false)
2720 Internal(mut internal
) => {
2721 // Replace the location freed in the internal node with an
2722 // adjacent KV, and remove that adjacent KV from its leaf.
2723 // Always choose the adjacent KV on the left side because
2724 // it is typically faster to pop an element from the end
2725 // of the KV arrays without needing to shift other elements.
2727 let key_loc
= internal
.kv_mut().0 as *mut K
;
2728 let val_loc
= internal
.kv_mut().1 as *mut V
;
2730 let to_remove
= internal
.left_edge().descend().last_leaf_edge().left_kv().ok();
2731 let to_remove
= unsafe { unwrap_unchecked(to_remove) }
;
2733 let (kv
, pos
) = to_remove
.remove();
2735 let old_key
= unsafe { mem::replace(&mut *key_loc, kv.0) }
;
2736 let old_val
= unsafe { mem::replace(&mut *val_loc, kv.1) }
;
2738 ((old_key
, old_val
), pos
, true)
2743 let mut cur_node
= unsafe { ptr::read(&pos).into_node().forget_type() }
;
2744 let mut at_leaf
= true;
2745 while cur_node
.len() < node
::MIN_LEN
{
2746 match handle_underfull_node(cur_node
) {
2748 Merged(edge
, merged_with_left
, offset
) => {
2749 // If we merged with our right sibling then our tracked
2750 // position has not changed. However if we merged with our
2751 // left sibling then our tracked position is now dangling.
2752 if at_leaf
&& merged_with_left
{
2753 let idx
= pos
.idx() + offset
;
2754 let node
= match unsafe { ptr::read(&edge).descend().force() }
{
2756 Internal(_
) => unreachable
!(),
2758 pos
= unsafe { Handle::new_edge(node, idx) }
;
2761 let parent
= edge
.into_node();
2762 if parent
.len() == 0 {
2763 // The parent that was just emptied must be the root,
2764 // because nodes on a lower level would not have been
2765 // left with a single child.
2766 handle_emptied_internal_root();
2769 cur_node
= parent
.forget_type();
2773 Stole(stole_from_left
) => {
2774 // Adjust the tracked position if we stole from a left sibling
2775 if stole_from_left
&& at_leaf
{
2776 // SAFETY: This is safe since we just added an element to our node.
2778 pos
.move_next_unchecked();
2786 // If we deleted from an internal node then we need to compensate for
2787 // the earlier swap and adjust the tracked position to point to the
2790 pos
= unsafe { unwrap_unchecked(pos.next_kv().ok()).next_leaf_edge() }
;
2797 impl<K
, V
> node
::Root
<K
, V
> {
2798 /// Removes empty levels on the top, but keep an empty leaf if the entire tree is empty.
2799 fn fix_top(&mut self) {
2800 while self.height() > 0 && self.node_as_ref().len() == 0 {
2801 self.pop_internal_level();
2805 fn fix_right_border(&mut self) {
2809 let mut cur_node
= self.node_as_mut();
2811 while let Internal(node
) = cur_node
.force() {
2812 let mut last_kv
= node
.last_kv();
2814 if last_kv
.can_merge() {
2815 cur_node
= last_kv
.merge().descend();
2817 let right_len
= last_kv
.reborrow().right_edge().descend().len();
2818 // `MINLEN + 1` to avoid readjust if merge happens on the next level.
2819 if right_len
< node
::MIN_LEN
+ 1 {
2820 last_kv
.bulk_steal_left(node
::MIN_LEN
+ 1 - right_len
);
2822 cur_node
= last_kv
.right_edge().descend();
2830 /// The symmetric clone of `fix_right_border`.
2831 fn fix_left_border(&mut self) {
2835 let mut cur_node
= self.node_as_mut();
2837 while let Internal(node
) = cur_node
.force() {
2838 let mut first_kv
= node
.first_kv();
2840 if first_kv
.can_merge() {
2841 cur_node
= first_kv
.merge().descend();
2843 let left_len
= first_kv
.reborrow().left_edge().descend().len();
2844 if left_len
< node
::MIN_LEN
+ 1 {
2845 first_kv
.bulk_steal_right(node
::MIN_LEN
+ 1 - left_len
);
2847 cur_node
= first_kv
.left_edge().descend();
2856 enum UnderflowResult
<'a
, K
, V
> {
2858 Merged(Handle
<NodeRef
<marker
::Mut
<'a
>, K
, V
, marker
::Internal
>, marker
::Edge
>, bool
, usize),
2862 fn handle_underfull_node
<'a
, K
: 'a
, V
: 'a
>(
2863 node
: NodeRef
<marker
::Mut
<'a
>, K
, V
, marker
::LeafOrInternal
>,
2864 ) -> UnderflowResult
<'_
, K
, V
> {
2865 let parent
= match node
.ascend() {
2866 Ok(parent
) => parent
,
2867 Err(_
) => return AtRoot
,
2870 // Prefer the left KV if it exists. Merging with the left side is faster,
2871 // since merging happens towards the left and `node` has fewer elements.
2872 // Stealing from the left side is faster, since we can pop from the end of
2874 let (is_left
, mut handle
) = match parent
.left_kv() {
2875 Ok(left
) => (true, left
),
2877 let right
= unsafe { unwrap_unchecked(parent.right_kv().ok()) }
;
2882 if handle
.can_merge() {
2883 let offset
= if is_left { handle.reborrow().left_edge().descend().len() + 1 }
else { 0 }
;
2884 Merged(handle
.merge(), is_left
, offset
)
2887 handle
.steal_left();
2889 handle
.steal_right();
2895 impl<K
: Ord
, V
, I
: Iterator
<Item
= (K
, V
)>> Iterator
for MergeIter
<K
, V
, I
> {
2898 fn next(&mut self) -> Option
<(K
, V
)> {
2899 let res
= match (self.left
.peek(), self.right
.peek()) {
2900 (Some(&(ref left_key
, _
)), Some(&(ref right_key
, _
))) => left_key
.cmp(right_key
),
2901 (Some(_
), None
) => Ordering
::Less
,
2902 (None
, Some(_
)) => Ordering
::Greater
,
2903 (None
, None
) => return None
,
2906 // Check which elements comes first and only advance the corresponding iterator.
2907 // If two keys are equal, take the value from `right`.
2909 Ordering
::Less
=> self.left
.next(),
2910 Ordering
::Greater
=> self.right
.next(),
2911 Ordering
::Equal
=> {