1 use core
::borrow
::Borrow
;
2 use core
::cmp
::Ordering
;
4 use core
::hash
::{Hash, Hasher}
;
5 use core
::iter
::{FromIterator, Peekable, FusedIterator}
;
6 use core
::marker
::PhantomData
;
7 use core
::ops
::Bound
::{Excluded, Included, Unbounded}
;
8 use core
::ops
::{Index, RangeBounds}
;
9 use core
::{fmt, intrinsics, mem, ptr}
;
11 use super::node
::{self, Handle, NodeRef, marker, InsertResult::*, ForceResult::*}
;
12 use super::search
::{self, SearchResult::*}
;
14 use UnderflowResult
::*;
17 /// A map based on a B-Tree.
19 /// B-Trees represent a fundamental compromise between cache-efficiency and actually minimizing
20 /// the amount of work performed in a search. In theory, a binary search tree (BST) is the optimal
21 /// choice for a sorted map, as a perfectly balanced BST performs the theoretical minimum amount of
22 /// comparisons necessary to find an element (log<sub>2</sub>n). However, in practice the way this
23 /// is done is *very* inefficient for modern computer architectures. In particular, every element
24 /// is stored in its own individually heap-allocated node. This means that every single insertion
25 /// triggers a heap-allocation, and every single comparison should be a cache-miss. Since these
26 /// are both notably expensive things to do in practice, we are forced to at very least reconsider
29 /// A B-Tree instead makes each node contain B-1 to 2B-1 elements in a contiguous array. By doing
30 /// this, we reduce the number of allocations by a factor of B, and improve cache efficiency in
31 /// searches. However, this does mean that searches will have to do *more* comparisons on average.
32 /// The precise number of comparisons depends on the node search strategy used. For optimal cache
33 /// efficiency, one could search the nodes linearly. For optimal comparisons, one could search
34 /// the node using binary search. As a compromise, one could also perform a linear search
35 /// that initially only checks every i<sup>th</sup> element for some choice of i.
37 /// Currently, our implementation simply performs naive linear search. This provides excellent
38 /// performance on *small* nodes of elements which are cheap to compare. However in the future we
39 /// would like to further explore choosing the optimal search strategy based on the choice of B,
40 /// and possibly other factors. Using linear search, searching for a random element is expected
41 /// to take O(B log<sub>B</sub>n) comparisons, which is generally worse than a BST. In practice,
42 /// however, performance is excellent.
44 /// It is a logic error for a key to be modified in such a way that the key's ordering relative to
45 /// any other key, as determined by the [`Ord`] trait, changes while it is in the map. This is
46 /// normally only possible through [`Cell`], [`RefCell`], global state, I/O, or unsafe code.
48 /// [`Ord`]: ../../std/cmp/trait.Ord.html
49 /// [`Cell`]: ../../std/cell/struct.Cell.html
50 /// [`RefCell`]: ../../std/cell/struct.RefCell.html
55 /// use std::collections::BTreeMap;
57 /// // type inference lets us omit an explicit type signature (which
58 /// // would be `BTreeMap<&str, &str>` in this example).
59 /// let mut movie_reviews = BTreeMap::new();
61 /// // review some movies.
62 /// movie_reviews.insert("Office Space", "Deals with real issues in the workplace.");
63 /// movie_reviews.insert("Pulp Fiction", "Masterpiece.");
64 /// movie_reviews.insert("The Godfather", "Very enjoyable.");
65 /// movie_reviews.insert("The Blues Brothers", "Eye lyked it a lot.");
67 /// // check for a specific one.
68 /// if !movie_reviews.contains_key("Les Misérables") {
69 /// println!("We've got {} reviews, but Les Misérables ain't one.",
70 /// movie_reviews.len());
73 /// // oops, this review has a lot of spelling mistakes, let's delete it.
74 /// movie_reviews.remove("The Blues Brothers");
76 /// // look up the values associated with some keys.
77 /// let to_find = ["Up!", "Office Space"];
78 /// for movie in &to_find {
79 /// match movie_reviews.get(movie) {
80 /// Some(review) => println!("{}: {}", movie, review),
81 /// None => println!("{} is unreviewed.", movie)
85 /// // Look up the value for a key (will panic if the key is not found).
86 /// println!("Movie review: {}", movie_reviews["Office Space"]);
88 /// // iterate over everything.
89 /// for (movie, review) in &movie_reviews {
90 /// println!("{}: \"{}\"", movie, review);
94 /// `BTreeMap` also implements an [`Entry API`](#method.entry), which allows
95 /// for more complex methods of getting, setting, updating and removing keys and
99 /// use std::collections::BTreeMap;
101 /// // type inference lets us omit an explicit type signature (which
102 /// // would be `BTreeMap<&str, u8>` in this example).
103 /// let mut player_stats = BTreeMap::new();
105 /// fn random_stat_buff() -> u8 {
106 /// // could actually return some random value here - let's just return
107 /// // some fixed value for now
111 /// // insert a key only if it doesn't already exist
112 /// player_stats.entry("health").or_insert(100);
114 /// // insert a key using a function that provides a new value only if it
115 /// // doesn't already exist
116 /// player_stats.entry("defence").or_insert_with(random_stat_buff);
118 /// // update a key, guarding against the key possibly not being set
119 /// let stat = player_stats.entry("attack").or_insert(100);
120 /// *stat += random_stat_buff();
122 #[stable(feature = "rust1", since = "1.0.0")]
123 pub struct BTreeMap
<K
, V
> {
124 root
: node
::Root
<K
, V
>,
128 #[stable(feature = "btree_drop", since = "1.7.0")]
129 unsafe impl<#[may_dangle] K, #[may_dangle] V> Drop for BTreeMap<K, V> {
132 drop(ptr
::read(self).into_iter());
137 #[stable(feature = "rust1", since = "1.0.0")]
138 impl<K
: Clone
, V
: Clone
> Clone
for BTreeMap
<K
, V
> {
139 fn clone(&self) -> BTreeMap
<K
, V
> {
140 fn clone_subtree
<'a
, K
: Clone
, V
: Clone
>(
141 node
: node
::NodeRef
<marker
::Immut
<'a
>, K
, V
, marker
::LeafOrInternal
>
147 let mut out_tree
= BTreeMap
{
148 root
: node
::Root
::new_leaf(),
153 let mut out_node
= match out_tree
.root
.as_mut().force() {
155 Internal(_
) => unreachable
!(),
158 let mut in_edge
= leaf
.first_edge();
159 while let Ok(kv
) = in_edge
.right_kv() {
160 let (k
, v
) = kv
.into_kv();
161 in_edge
= kv
.right_edge();
163 out_node
.push(k
.clone(), v
.clone());
164 out_tree
.length
+= 1;
170 Internal(internal
) => {
171 let mut out_tree
= clone_subtree(internal
.first_edge().descend());
174 let mut out_node
= out_tree
.root
.push_level();
175 let mut in_edge
= internal
.first_edge();
176 while let Ok(kv
) = in_edge
.right_kv() {
177 let (k
, v
) = kv
.into_kv();
178 in_edge
= kv
.right_edge();
180 let k
= (*k
).clone();
181 let v
= (*v
).clone();
182 let subtree
= clone_subtree(in_edge
.descend());
184 // We can't destructure subtree directly
185 // because BTreeMap implements Drop
186 let (subroot
, sublength
) = unsafe {
187 let root
= ptr
::read(&subtree
.root
);
188 let length
= subtree
.length
;
189 mem
::forget(subtree
);
193 out_node
.push(k
, v
, subroot
);
194 out_tree
.length
+= 1 + sublength
;
204 // Ideally we'd call `BTreeMap::new` here, but that has the `K:
205 // Ord` constraint, which this method lacks.
207 root
: node
::Root
::shared_empty_root(),
211 clone_subtree(self.root
.as_ref())
216 impl<K
, Q
: ?Sized
> super::Recover
<Q
> for BTreeMap
<K
, ()>
217 where K
: Borrow
<Q
> + Ord
,
222 fn get(&self, key
: &Q
) -> Option
<&K
> {
223 match search
::search_tree(self.root
.as_ref(), key
) {
224 Found(handle
) => Some(handle
.into_kv().0),
229 fn take(&mut self, key
: &Q
) -> Option
<K
> {
230 match search
::search_tree(self.root
.as_mut(), key
) {
234 length
: &mut self.length
,
235 _marker
: PhantomData
,
244 fn replace(&mut self, key
: K
) -> Option
<K
> {
245 self.ensure_root_is_owned();
246 match search
::search_tree
::<marker
::Mut
<'_
>, K
, (), K
>(self.root
.as_mut(), &key
) {
247 Found(handle
) => Some(mem
::replace(handle
.into_kv_mut().0, key
)),
252 length
: &mut self.length
,
253 _marker
: PhantomData
,
262 /// An iterator over the entries of a `BTreeMap`.
264 /// This `struct` is created by the [`iter`] method on [`BTreeMap`]. See its
265 /// documentation for more.
267 /// [`iter`]: struct.BTreeMap.html#method.iter
268 /// [`BTreeMap`]: struct.BTreeMap.html
269 #[stable(feature = "rust1", since = "1.0.0")]
270 pub struct Iter
<'a
, K
: 'a
, V
: 'a
> {
271 range
: Range
<'a
, K
, V
>,
275 #[stable(feature = "collection_debug", since = "1.17.0")]
276 impl<K
: fmt
::Debug
, V
: fmt
::Debug
> fmt
::Debug
for Iter
<'_
, K
, V
> {
277 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
278 f
.debug_list().entries(self.clone()).finish()
282 /// A mutable iterator over the entries of a `BTreeMap`.
284 /// This `struct` is created by the [`iter_mut`] method on [`BTreeMap`]. See its
285 /// documentation for more.
287 /// [`iter_mut`]: struct.BTreeMap.html#method.iter_mut
288 /// [`BTreeMap`]: struct.BTreeMap.html
289 #[stable(feature = "rust1", since = "1.0.0")]
291 pub struct IterMut
<'a
, K
: 'a
, V
: 'a
> {
292 range
: RangeMut
<'a
, K
, V
>,
296 /// An owning iterator over the entries of a `BTreeMap`.
298 /// This `struct` is created by the [`into_iter`] method on [`BTreeMap`][`BTreeMap`]
299 /// (provided by the `IntoIterator` trait). See its documentation for more.
301 /// [`into_iter`]: struct.BTreeMap.html#method.into_iter
302 /// [`BTreeMap`]: struct.BTreeMap.html
303 #[stable(feature = "rust1", since = "1.0.0")]
304 pub struct IntoIter
<K
, V
> {
305 front
: Handle
<NodeRef
<marker
::Owned
, K
, V
, marker
::Leaf
>, marker
::Edge
>,
306 back
: Handle
<NodeRef
<marker
::Owned
, K
, V
, marker
::Leaf
>, marker
::Edge
>,
310 #[stable(feature = "collection_debug", since = "1.17.0")]
311 impl<K
: fmt
::Debug
, V
: fmt
::Debug
> fmt
::Debug
for IntoIter
<K
, V
> {
312 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
314 front
: self.front
.reborrow(),
315 back
: self.back
.reborrow(),
317 f
.debug_list().entries(range
).finish()
321 /// An iterator over the keys of a `BTreeMap`.
323 /// This `struct` is created by the [`keys`] method on [`BTreeMap`]. See its
324 /// documentation for more.
326 /// [`keys`]: struct.BTreeMap.html#method.keys
327 /// [`BTreeMap`]: struct.BTreeMap.html
328 #[stable(feature = "rust1", since = "1.0.0")]
329 pub struct Keys
<'a
, K
: 'a
, V
: 'a
> {
330 inner
: Iter
<'a
, K
, V
>,
333 #[stable(feature = "collection_debug", since = "1.17.0")]
334 impl<K
: fmt
::Debug
, V
> fmt
::Debug
for Keys
<'_
, K
, V
> {
335 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
336 f
.debug_list().entries(self.clone()).finish()
340 /// An iterator over the values of a `BTreeMap`.
342 /// This `struct` is created by the [`values`] method on [`BTreeMap`]. See its
343 /// documentation for more.
345 /// [`values`]: struct.BTreeMap.html#method.values
346 /// [`BTreeMap`]: struct.BTreeMap.html
347 #[stable(feature = "rust1", since = "1.0.0")]
348 pub struct Values
<'a
, K
: 'a
, V
: 'a
> {
349 inner
: Iter
<'a
, K
, V
>,
352 #[stable(feature = "collection_debug", since = "1.17.0")]
353 impl<K
, V
: fmt
::Debug
> fmt
::Debug
for Values
<'_
, K
, V
> {
354 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
355 f
.debug_list().entries(self.clone()).finish()
359 /// A mutable iterator over the values of a `BTreeMap`.
361 /// This `struct` is created by the [`values_mut`] method on [`BTreeMap`]. See its
362 /// documentation for more.
364 /// [`values_mut`]: struct.BTreeMap.html#method.values_mut
365 /// [`BTreeMap`]: struct.BTreeMap.html
366 #[stable(feature = "map_values_mut", since = "1.10.0")]
368 pub struct ValuesMut
<'a
, K
: 'a
, V
: 'a
> {
369 inner
: IterMut
<'a
, K
, V
>,
372 /// An iterator over a sub-range of entries in a `BTreeMap`.
374 /// This `struct` is created by the [`range`] method on [`BTreeMap`]. See its
375 /// documentation for more.
377 /// [`range`]: struct.BTreeMap.html#method.range
378 /// [`BTreeMap`]: struct.BTreeMap.html
379 #[stable(feature = "btree_range", since = "1.17.0")]
380 pub struct Range
<'a
, K
: 'a
, V
: 'a
> {
381 front
: Handle
<NodeRef
<marker
::Immut
<'a
>, K
, V
, marker
::Leaf
>, marker
::Edge
>,
382 back
: Handle
<NodeRef
<marker
::Immut
<'a
>, K
, V
, marker
::Leaf
>, marker
::Edge
>,
385 #[stable(feature = "collection_debug", since = "1.17.0")]
386 impl<K
: fmt
::Debug
, V
: fmt
::Debug
> fmt
::Debug
for Range
<'_
, K
, V
> {
387 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
388 f
.debug_list().entries(self.clone()).finish()
392 /// A mutable iterator over a sub-range of entries in a `BTreeMap`.
394 /// This `struct` is created by the [`range_mut`] method on [`BTreeMap`]. See its
395 /// documentation for more.
397 /// [`range_mut`]: struct.BTreeMap.html#method.range_mut
398 /// [`BTreeMap`]: struct.BTreeMap.html
399 #[stable(feature = "btree_range", since = "1.17.0")]
400 pub struct RangeMut
<'a
, K
: 'a
, V
: 'a
> {
401 front
: Handle
<NodeRef
<marker
::Mut
<'a
>, K
, V
, marker
::Leaf
>, marker
::Edge
>,
402 back
: Handle
<NodeRef
<marker
::Mut
<'a
>, K
, V
, marker
::Leaf
>, marker
::Edge
>,
404 // Be invariant in `K` and `V`
405 _marker
: PhantomData
<&'a
mut (K
, V
)>,
408 #[stable(feature = "collection_debug", since = "1.17.0")]
409 impl<K
: fmt
::Debug
, V
: fmt
::Debug
> fmt
::Debug
for RangeMut
<'_
, K
, V
> {
410 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
412 front
: self.front
.reborrow(),
413 back
: self.back
.reborrow(),
415 f
.debug_list().entries(range
).finish()
419 /// A view into a single entry in a map, which may either be vacant or occupied.
421 /// This `enum` is constructed from the [`entry`] method on [`BTreeMap`].
423 /// [`BTreeMap`]: struct.BTreeMap.html
424 /// [`entry`]: struct.BTreeMap.html#method.entry
425 #[stable(feature = "rust1", since = "1.0.0")]
426 pub enum Entry
<'a
, K
: 'a
, V
: 'a
> {
428 #[stable(feature = "rust1", since = "1.0.0")]
429 Vacant(#[stable(feature = "rust1", since = "1.0.0")]
430 VacantEntry
<'a
, K
, V
>),
432 /// An occupied entry.
433 #[stable(feature = "rust1", since = "1.0.0")]
434 Occupied(#[stable(feature = "rust1", since = "1.0.0")]
435 OccupiedEntry
<'a
, K
, V
>),
438 #[stable(feature= "debug_btree_map", since = "1.12.0")]
439 impl<K
: Debug
+ Ord
, V
: Debug
> Debug
for Entry
<'_
, K
, V
> {
440 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
442 Vacant(ref v
) => f
.debug_tuple("Entry")
445 Occupied(ref o
) => f
.debug_tuple("Entry")
452 /// A view into a vacant entry in a `BTreeMap`.
453 /// It is part of the [`Entry`] enum.
455 /// [`Entry`]: enum.Entry.html
456 #[stable(feature = "rust1", since = "1.0.0")]
457 pub struct VacantEntry
<'a
, K
: 'a
, V
: 'a
> {
459 handle
: Handle
<NodeRef
<marker
::Mut
<'a
>, K
, V
, marker
::Leaf
>, marker
::Edge
>,
460 length
: &'a
mut usize,
462 // Be invariant in `K` and `V`
463 _marker
: PhantomData
<&'a
mut (K
, V
)>,
466 #[stable(feature= "debug_btree_map", since = "1.12.0")]
467 impl<K
: Debug
+ Ord
, V
> Debug
for VacantEntry
<'_
, K
, V
> {
468 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
469 f
.debug_tuple("VacantEntry")
475 /// A view into an occupied entry in a `BTreeMap`.
476 /// It is part of the [`Entry`] enum.
478 /// [`Entry`]: enum.Entry.html
479 #[stable(feature = "rust1", since = "1.0.0")]
480 pub struct OccupiedEntry
<'a
, K
: 'a
, V
: 'a
> {
481 handle
: Handle
<NodeRef
<marker
::Mut
<'a
>, K
, V
, marker
::LeafOrInternal
>, marker
::KV
>,
483 length
: &'a
mut usize,
485 // Be invariant in `K` and `V`
486 _marker
: PhantomData
<&'a
mut (K
, V
)>,
489 #[stable(feature= "debug_btree_map", since = "1.12.0")]
490 impl<K
: Debug
+ Ord
, V
: Debug
> Debug
for OccupiedEntry
<'_
, K
, V
> {
491 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
492 f
.debug_struct("OccupiedEntry")
493 .field("key", self.key())
494 .field("value", self.get())
499 // An iterator for merging two sorted sequences into one
500 struct MergeIter
<K
, V
, I
: Iterator
<Item
= (K
, V
)>> {
505 impl<K
: Ord
, V
> BTreeMap
<K
, V
> {
506 /// Makes a new empty BTreeMap with a reasonable choice for B.
513 /// use std::collections::BTreeMap;
515 /// let mut map = BTreeMap::new();
517 /// // entries can now be inserted into the empty map
518 /// map.insert(1, "a");
520 #[stable(feature = "rust1", since = "1.0.0")]
521 pub fn new() -> BTreeMap
<K
, V
> {
523 root
: node
::Root
::shared_empty_root(),
528 /// Clears the map, removing all values.
535 /// use std::collections::BTreeMap;
537 /// let mut a = BTreeMap::new();
538 /// a.insert(1, "a");
540 /// assert!(a.is_empty());
542 #[stable(feature = "rust1", since = "1.0.0")]
543 pub fn clear(&mut self) {
544 *self = BTreeMap
::new();
547 /// Returns a reference to the value corresponding to the key.
549 /// The key may be any borrowed form of the map's key type, but the ordering
550 /// on the borrowed form *must* match the ordering on the key type.
557 /// use std::collections::BTreeMap;
559 /// let mut map = BTreeMap::new();
560 /// map.insert(1, "a");
561 /// assert_eq!(map.get(&1), Some(&"a"));
562 /// assert_eq!(map.get(&2), None);
564 #[stable(feature = "rust1", since = "1.0.0")]
565 pub fn get
<Q
: ?Sized
>(&self, key
: &Q
) -> Option
<&V
>
569 match search
::search_tree(self.root
.as_ref(), key
) {
570 Found(handle
) => Some(handle
.into_kv().1),
575 /// Returns the key-value pair corresponding to the supplied key.
577 /// The supplied key may be any borrowed form of the map's key type, but the ordering
578 /// on the borrowed form *must* match the ordering on the key type.
583 /// use std::collections::BTreeMap;
585 /// let mut map = BTreeMap::new();
586 /// map.insert(1, "a");
587 /// assert_eq!(map.get_key_value(&1), Some((&1, &"a")));
588 /// assert_eq!(map.get_key_value(&2), None);
590 #[stable(feature = "map_get_key_value", since = "1.40.0")]
591 pub fn get_key_value
<Q
: ?Sized
>(&self, k
: &Q
) -> Option
<(&K
, &V
)>
595 match search
::search_tree(self.root
.as_ref(), k
) {
596 Found(handle
) => Some(handle
.into_kv()),
601 /// Returns `true` if the map contains a value for the specified key.
603 /// The key may be any borrowed form of the map's key type, but the ordering
604 /// on the borrowed form *must* match the ordering on the key type.
611 /// use std::collections::BTreeMap;
613 /// let mut map = BTreeMap::new();
614 /// map.insert(1, "a");
615 /// assert_eq!(map.contains_key(&1), true);
616 /// assert_eq!(map.contains_key(&2), false);
618 #[stable(feature = "rust1", since = "1.0.0")]
619 pub fn contains_key
<Q
: ?Sized
>(&self, key
: &Q
) -> bool
623 self.get(key
).is_some()
626 /// Returns a mutable reference to the value corresponding to the key.
628 /// The key may be any borrowed form of the map's key type, but the ordering
629 /// on the borrowed form *must* match the ordering on the key type.
636 /// use std::collections::BTreeMap;
638 /// let mut map = BTreeMap::new();
639 /// map.insert(1, "a");
640 /// if let Some(x) = map.get_mut(&1) {
643 /// assert_eq!(map[&1], "b");
645 // See `get` for implementation notes, this is basically a copy-paste with mut's added
646 #[stable(feature = "rust1", since = "1.0.0")]
647 pub fn get_mut
<Q
: ?Sized
>(&mut self, key
: &Q
) -> Option
<&mut V
>
651 match search
::search_tree(self.root
.as_mut(), key
) {
652 Found(handle
) => Some(handle
.into_kv_mut().1),
657 /// Inserts a key-value pair into the map.
659 /// If the map did not have this key present, `None` is returned.
661 /// If the map did have this key present, the value is updated, and the old
662 /// value is returned. The key is not updated, though; this matters for
663 /// types that can be `==` without being identical. See the [module-level
664 /// documentation] for more.
666 /// [module-level documentation]: index.html#insert-and-complex-keys
673 /// use std::collections::BTreeMap;
675 /// let mut map = BTreeMap::new();
676 /// assert_eq!(map.insert(37, "a"), None);
677 /// assert_eq!(map.is_empty(), false);
679 /// map.insert(37, "b");
680 /// assert_eq!(map.insert(37, "c"), Some("b"));
681 /// assert_eq!(map[&37], "c");
683 #[stable(feature = "rust1", since = "1.0.0")]
684 pub fn insert(&mut self, key
: K
, value
: V
) -> Option
<V
> {
685 match self.entry(key
) {
686 Occupied(mut entry
) => Some(entry
.insert(value
)),
694 /// Removes a key from the map, returning the value at the key if the key
695 /// was previously in the map.
697 /// The key may be any borrowed form of the map's key type, but the ordering
698 /// on the borrowed form *must* match the ordering on the key type.
705 /// use std::collections::BTreeMap;
707 /// let mut map = BTreeMap::new();
708 /// map.insert(1, "a");
709 /// assert_eq!(map.remove(&1), Some("a"));
710 /// assert_eq!(map.remove(&1), None);
712 #[stable(feature = "rust1", since = "1.0.0")]
713 pub fn remove
<Q
: ?Sized
>(&mut self, key
: &Q
) -> Option
<V
>
717 match search
::search_tree(self.root
.as_mut(), key
) {
721 length
: &mut self.length
,
722 _marker
: PhantomData
,
730 /// Moves all elements from `other` into `Self`, leaving `other` empty.
735 /// use std::collections::BTreeMap;
737 /// let mut a = BTreeMap::new();
738 /// a.insert(1, "a");
739 /// a.insert(2, "b");
740 /// a.insert(3, "c");
742 /// let mut b = BTreeMap::new();
743 /// b.insert(3, "d");
744 /// b.insert(4, "e");
745 /// b.insert(5, "f");
747 /// a.append(&mut b);
749 /// assert_eq!(a.len(), 5);
750 /// assert_eq!(b.len(), 0);
752 /// assert_eq!(a[&1], "a");
753 /// assert_eq!(a[&2], "b");
754 /// assert_eq!(a[&3], "d");
755 /// assert_eq!(a[&4], "e");
756 /// assert_eq!(a[&5], "f");
758 #[stable(feature = "btree_append", since = "1.11.0")]
759 pub fn append(&mut self, other
: &mut Self) {
760 // Do we have to append anything at all?
761 if other
.is_empty() {
765 // We can just swap `self` and `other` if `self` is empty.
767 mem
::swap(self, other
);
771 // First, we merge `self` and `other` into a sorted sequence in linear time.
772 let self_iter
= mem
::take(self).into_iter();
773 let other_iter
= mem
::take(other
).into_iter();
774 let iter
= MergeIter
{
775 left
: self_iter
.peekable(),
776 right
: other_iter
.peekable(),
779 // Second, we build a tree from the sorted sequence in linear time.
780 self.from_sorted_iter(iter
);
781 self.fix_right_edge();
784 /// Constructs a double-ended iterator over a sub-range of elements in the map.
785 /// The simplest way is to use the range syntax `min..max`, thus `range(min..max)` will
786 /// yield elements from min (inclusive) to max (exclusive).
787 /// The range may also be entered as `(Bound<T>, Bound<T>)`, so for example
788 /// `range((Excluded(4), Included(10)))` will yield a left-exclusive, right-inclusive
789 /// range from 4 to 10.
793 /// Panics if range `start > end`.
794 /// Panics if range `start == end` and both bounds are `Excluded`.
801 /// use std::collections::BTreeMap;
802 /// use std::ops::Bound::Included;
804 /// let mut map = BTreeMap::new();
805 /// map.insert(3, "a");
806 /// map.insert(5, "b");
807 /// map.insert(8, "c");
808 /// for (&key, &value) in map.range((Included(&4), Included(&8))) {
809 /// println!("{}: {}", key, value);
811 /// assert_eq!(Some((&5, &"b")), map.range(4..).next());
813 #[stable(feature = "btree_range", since = "1.17.0")]
814 pub fn range
<T
: ?Sized
, R
>(&self, range
: R
) -> Range
<'_
, K
, V
>
815 where T
: Ord
, K
: Borrow
<T
>, R
: RangeBounds
<T
>
817 let root1
= self.root
.as_ref();
818 let root2
= self.root
.as_ref();
819 let (f
, b
) = range_search(root1
, root2
, range
);
821 Range { front: f, back: b}
824 /// Constructs a mutable double-ended iterator over a sub-range of elements in the map.
825 /// The simplest way is to use the range syntax `min..max`, thus `range(min..max)` will
826 /// yield elements from min (inclusive) to max (exclusive).
827 /// The range may also be entered as `(Bound<T>, Bound<T>)`, so for example
828 /// `range((Excluded(4), Included(10)))` will yield a left-exclusive, right-inclusive
829 /// range from 4 to 10.
833 /// Panics if range `start > end`.
834 /// Panics if range `start == end` and both bounds are `Excluded`.
841 /// use std::collections::BTreeMap;
843 /// let mut map: BTreeMap<&str, i32> = ["Alice", "Bob", "Carol", "Cheryl"]
845 /// .map(|&s| (s, 0))
847 /// for (_, balance) in map.range_mut("B".."Cheryl") {
850 /// for (name, balance) in &map {
851 /// println!("{} => {}", name, balance);
854 #[stable(feature = "btree_range", since = "1.17.0")]
855 pub fn range_mut
<T
: ?Sized
, R
>(&mut self, range
: R
) -> RangeMut
<'_
, K
, V
>
856 where T
: Ord
, K
: Borrow
<T
>, R
: RangeBounds
<T
>
858 let root1
= self.root
.as_mut();
859 let root2
= unsafe { ptr::read(&root1) }
;
860 let (f
, b
) = range_search(root1
, root2
, range
);
865 _marker
: PhantomData
,
869 /// Gets the given key's corresponding entry in the map for in-place manipulation.
876 /// use std::collections::BTreeMap;
878 /// let mut count: BTreeMap<&str, usize> = BTreeMap::new();
880 /// // count the number of occurrences of letters in the vec
881 /// for x in vec!["a","b","a","c","a","b"] {
882 /// *count.entry(x).or_insert(0) += 1;
885 /// assert_eq!(count["a"], 3);
887 #[stable(feature = "rust1", since = "1.0.0")]
888 pub fn entry(&mut self, key
: K
) -> Entry
<'_
, K
, V
> {
889 // FIXME(@porglezomp) Avoid allocating if we don't insert
890 self.ensure_root_is_owned();
891 match search
::search_tree(self.root
.as_mut(), &key
) {
893 Occupied(OccupiedEntry
{
895 length
: &mut self.length
,
896 _marker
: PhantomData
,
903 length
: &mut self.length
,
904 _marker
: PhantomData
,
910 fn from_sorted_iter
<I
: Iterator
<Item
= (K
, V
)>>(&mut self, iter
: I
) {
911 self.ensure_root_is_owned();
912 let mut cur_node
= last_leaf_edge(self.root
.as_mut()).into_node();
913 // Iterate through all key-value pairs, pushing them into nodes at the right level.
914 for (key
, value
) in iter
{
915 // Try to push key-value pair into the current leaf node.
916 if cur_node
.len() < node
::CAPACITY
{
917 cur_node
.push(key
, value
);
919 // No space left, go up and push there.
921 let mut test_node
= cur_node
.forget_type();
923 match test_node
.ascend() {
925 let parent
= parent
.into_node();
926 if parent
.len() < node
::CAPACITY
{
927 // Found a node with space left, push here.
932 test_node
= parent
.forget_type();
936 // We are at the top, create a new root node and push there.
937 open_node
= node
.into_root_mut().push_level();
943 // Push key-value pair and new right subtree.
944 let tree_height
= open_node
.height() - 1;
945 let mut right_tree
= node
::Root
::new_leaf();
946 for _
in 0..tree_height
{
947 right_tree
.push_level();
949 open_node
.push(key
, value
, right_tree
);
951 // Go down to the right-most leaf again.
952 cur_node
= last_leaf_edge(open_node
.forget_type()).into_node();
959 fn fix_right_edge(&mut self) {
960 // Handle underfull nodes, start from the top.
961 let mut cur_node
= self.root
.as_mut();
962 while let Internal(internal
) = cur_node
.force() {
963 // Check if right-most child is underfull.
964 let mut last_edge
= internal
.last_edge();
965 let right_child_len
= last_edge
.reborrow().descend().len();
966 if right_child_len
< node
::MIN_LEN
{
968 let mut last_kv
= match last_edge
.left_kv() {
970 Err(_
) => unreachable
!(),
972 last_kv
.bulk_steal_left(node
::MIN_LEN
- right_child_len
);
973 last_edge
= last_kv
.right_edge();
977 cur_node
= last_edge
.descend();
981 /// Splits the collection into two at the given key. Returns everything after the given key,
982 /// including the key.
989 /// use std::collections::BTreeMap;
991 /// let mut a = BTreeMap::new();
992 /// a.insert(1, "a");
993 /// a.insert(2, "b");
994 /// a.insert(3, "c");
995 /// a.insert(17, "d");
996 /// a.insert(41, "e");
998 /// let b = a.split_off(&3);
1000 /// assert_eq!(a.len(), 2);
1001 /// assert_eq!(b.len(), 3);
1003 /// assert_eq!(a[&1], "a");
1004 /// assert_eq!(a[&2], "b");
1006 /// assert_eq!(b[&3], "c");
1007 /// assert_eq!(b[&17], "d");
1008 /// assert_eq!(b[&41], "e");
1010 #[stable(feature = "btree_split_off", since = "1.11.0")]
1011 pub fn split_off
<Q
: ?Sized
+ Ord
>(&mut self, key
: &Q
) -> Self
1014 if self.is_empty() {
1018 let total_num
= self.len();
1020 let mut right
= Self::new();
1021 right
.root
= node
::Root
::new_leaf();
1022 for _
in 0..(self.root
.as_ref().height()) {
1023 right
.root
.push_level();
1027 let mut left_node
= self.root
.as_mut();
1028 let mut right_node
= right
.root
.as_mut();
1031 let mut split_edge
= match search
::search_node(left_node
, key
) {
1032 // key is going to the right tree
1033 Found(handle
) => handle
.left_edge(),
1034 GoDown(handle
) => handle
,
1037 split_edge
.move_suffix(&mut right_node
);
1039 match (split_edge
.force(), right_node
.force()) {
1040 (Internal(edge
), Internal(node
)) => {
1041 left_node
= edge
.descend();
1042 right_node
= node
.first_edge().descend();
1044 (Leaf(_
), Leaf(_
)) => {
1054 self.fix_right_border();
1055 right
.fix_left_border();
1057 if self.root
.as_ref().height() < right
.root
.as_ref().height() {
1058 self.recalc_length();
1059 right
.length
= total_num
- self.len();
1061 right
.recalc_length();
1062 self.length
= total_num
- right
.len();
1068 /// Calculates the number of elements if it is incorrect.
1069 fn recalc_length(&mut self) {
1071 node
: NodeRef
<marker
::Immut
<'a
>, K
, V
, marker
::LeafOrInternal
>
1075 let mut res
= node
.len();
1077 if let Internal(node
) = node
.force() {
1078 let mut edge
= node
.first_edge();
1080 res
+= dfs(edge
.reborrow().descend());
1081 match edge
.right_kv() {
1083 edge
= right_kv
.right_edge();
1095 self.length
= dfs(self.root
.as_ref());
1098 /// Removes empty levels on the top.
1099 fn fix_top(&mut self) {
1102 let node
= self.root
.as_ref();
1103 if node
.height() == 0 || node
.len() > 0 {
1107 self.root
.pop_level();
1111 fn fix_right_border(&mut self) {
1115 let mut cur_node
= self.root
.as_mut();
1117 while let Internal(node
) = cur_node
.force() {
1118 let mut last_kv
= node
.last_kv();
1120 if last_kv
.can_merge() {
1121 cur_node
= last_kv
.merge().descend();
1123 let right_len
= last_kv
.reborrow().right_edge().descend().len();
1124 // `MINLEN + 1` to avoid readjust if merge happens on the next level.
1125 if right_len
< node
::MIN_LEN
+ 1 {
1126 last_kv
.bulk_steal_left(node
::MIN_LEN
+ 1 - right_len
);
1128 cur_node
= last_kv
.right_edge().descend();
1136 /// The symmetric clone of `fix_right_border`.
1137 fn fix_left_border(&mut self) {
1141 let mut cur_node
= self.root
.as_mut();
1143 while let Internal(node
) = cur_node
.force() {
1144 let mut first_kv
= node
.first_kv();
1146 if first_kv
.can_merge() {
1147 cur_node
= first_kv
.merge().descend();
1149 let left_len
= first_kv
.reborrow().left_edge().descend().len();
1150 if left_len
< node
::MIN_LEN
+ 1 {
1151 first_kv
.bulk_steal_right(node
::MIN_LEN
+ 1 - left_len
);
1153 cur_node
= first_kv
.left_edge().descend();
1161 /// If the root node is the shared root node, allocate our own node.
1162 fn ensure_root_is_owned(&mut self) {
1163 if self.root
.is_shared_root() {
1164 self.root
= node
::Root
::new_leaf();
1169 #[stable(feature = "rust1", since = "1.0.0")]
1170 impl<'a
, K
: 'a
, V
: 'a
> IntoIterator
for &'a BTreeMap
<K
, V
> {
1171 type Item
= (&'a K
, &'a V
);
1172 type IntoIter
= Iter
<'a
, K
, V
>;
1174 fn into_iter(self) -> Iter
<'a
, K
, V
> {
1179 #[stable(feature = "rust1", since = "1.0.0")]
1180 impl<'a
, K
: 'a
, V
: 'a
> Iterator
for Iter
<'a
, K
, V
> {
1181 type Item
= (&'a K
, &'a V
);
1183 fn next(&mut self) -> Option
<(&'a K
, &'a V
)> {
1184 if self.length
== 0 {
1188 unsafe { Some(self.range.next_unchecked()) }
1192 fn size_hint(&self) -> (usize, Option
<usize>) {
1193 (self.length
, Some(self.length
))
1196 fn last(mut self) -> Option
<(&'a K
, &'a V
)> {
1201 #[stable(feature = "fused", since = "1.26.0")]
1202 impl<K
, V
> FusedIterator
for Iter
<'_
, K
, V
> {}
1204 #[stable(feature = "rust1", since = "1.0.0")]
1205 impl<'a
, K
: 'a
, V
: 'a
> DoubleEndedIterator
for Iter
<'a
, K
, V
> {
1206 fn next_back(&mut self) -> Option
<(&'a K
, &'a V
)> {
1207 if self.length
== 0 {
1211 unsafe { Some(self.range.next_back_unchecked()) }
1216 #[stable(feature = "rust1", since = "1.0.0")]
1217 impl<K
, V
> ExactSizeIterator
for Iter
<'_
, K
, V
> {
1218 fn len(&self) -> usize {
1223 #[stable(feature = "rust1", since = "1.0.0")]
1224 impl<K
, V
> Clone
for Iter
<'_
, K
, V
> {
1225 fn clone(&self) -> Self {
1227 range
: self.range
.clone(),
1228 length
: self.length
,
1233 #[stable(feature = "rust1", since = "1.0.0")]
1234 impl<'a
, K
: 'a
, V
: 'a
> IntoIterator
for &'a
mut BTreeMap
<K
, V
> {
1235 type Item
= (&'a K
, &'a
mut V
);
1236 type IntoIter
= IterMut
<'a
, K
, V
>;
1238 fn into_iter(self) -> IterMut
<'a
, K
, V
> {
1243 #[stable(feature = "rust1", since = "1.0.0")]
1244 impl<'a
, K
: 'a
, V
: 'a
> Iterator
for IterMut
<'a
, K
, V
> {
1245 type Item
= (&'a K
, &'a
mut V
);
1247 fn next(&mut self) -> Option
<(&'a K
, &'a
mut V
)> {
1248 if self.length
== 0 {
1252 unsafe { Some(self.range.next_unchecked()) }
1256 fn size_hint(&self) -> (usize, Option
<usize>) {
1257 (self.length
, Some(self.length
))
1260 fn last(mut self) -> Option
<(&'a K
, &'a
mut V
)> {
1265 #[stable(feature = "rust1", since = "1.0.0")]
1266 impl<'a
, K
: 'a
, V
: 'a
> DoubleEndedIterator
for IterMut
<'a
, K
, V
> {
1267 fn next_back(&mut self) -> Option
<(&'a K
, &'a
mut V
)> {
1268 if self.length
== 0 {
1272 unsafe { Some(self.range.next_back_unchecked()) }
1277 #[stable(feature = "rust1", since = "1.0.0")]
1278 impl<K
, V
> ExactSizeIterator
for IterMut
<'_
, K
, V
> {
1279 fn len(&self) -> usize {
1284 #[stable(feature = "fused", since = "1.26.0")]
1285 impl<K
, V
> FusedIterator
for IterMut
<'_
, K
, V
> {}
1287 #[stable(feature = "rust1", since = "1.0.0")]
1288 impl<K
, V
> IntoIterator
for BTreeMap
<K
, V
> {
1290 type IntoIter
= IntoIter
<K
, V
>;
1292 fn into_iter(self) -> IntoIter
<K
, V
> {
1293 let root1
= unsafe { ptr::read(&self.root).into_ref() }
;
1294 let root2
= unsafe { ptr::read(&self.root).into_ref() }
;
1295 let len
= self.length
;
1299 front
: first_leaf_edge(root1
),
1300 back
: last_leaf_edge(root2
),
1306 #[stable(feature = "btree_drop", since = "1.7.0")]
1307 impl<K
, V
> Drop
for IntoIter
<K
, V
> {
1308 fn drop(&mut self) {
1309 self.for_each(drop
);
1311 let leaf_node
= ptr
::read(&self.front
).into_node();
1312 if leaf_node
.is_shared_root() {
1316 if let Some(first_parent
) = leaf_node
.deallocate_and_ascend() {
1317 let mut cur_node
= first_parent
.into_node();
1318 while let Some(parent
) = cur_node
.deallocate_and_ascend() {
1319 cur_node
= parent
.into_node()
1326 #[stable(feature = "rust1", since = "1.0.0")]
1327 impl<K
, V
> Iterator
for IntoIter
<K
, V
> {
1330 fn next(&mut self) -> Option
<(K
, V
)> {
1331 if self.length
== 0 {
1337 let handle
= unsafe { ptr::read(&self.front) }
;
1339 let mut cur_handle
= match handle
.right_kv() {
1341 let k
= unsafe { ptr::read(kv.reborrow().into_kv().0) }
;
1342 let v
= unsafe { ptr::read(kv.reborrow().into_kv().1) }
;
1343 self.front
= kv
.right_edge();
1344 return Some((k
, v
));
1346 Err(last_edge
) => unsafe {
1347 unwrap_unchecked(last_edge
.into_node().deallocate_and_ascend())
1352 match cur_handle
.right_kv() {
1354 let k
= unsafe { ptr::read(kv.reborrow().into_kv().0) }
;
1355 let v
= unsafe { ptr::read(kv.reborrow().into_kv().1) }
;
1356 self.front
= first_leaf_edge(kv
.right_edge().descend());
1357 return Some((k
, v
));
1359 Err(last_edge
) => unsafe {
1360 cur_handle
= unwrap_unchecked(last_edge
.into_node().deallocate_and_ascend());
1366 fn size_hint(&self) -> (usize, Option
<usize>) {
1367 (self.length
, Some(self.length
))
1371 #[stable(feature = "rust1", since = "1.0.0")]
1372 impl<K
, V
> DoubleEndedIterator
for IntoIter
<K
, V
> {
1373 fn next_back(&mut self) -> Option
<(K
, V
)> {
1374 if self.length
== 0 {
1380 let handle
= unsafe { ptr::read(&self.back) }
;
1382 let mut cur_handle
= match handle
.left_kv() {
1384 let k
= unsafe { ptr::read(kv.reborrow().into_kv().0) }
;
1385 let v
= unsafe { ptr::read(kv.reborrow().into_kv().1) }
;
1386 self.back
= kv
.left_edge();
1387 return Some((k
, v
));
1389 Err(last_edge
) => unsafe {
1390 unwrap_unchecked(last_edge
.into_node().deallocate_and_ascend())
1395 match cur_handle
.left_kv() {
1397 let k
= unsafe { ptr::read(kv.reborrow().into_kv().0) }
;
1398 let v
= unsafe { ptr::read(kv.reborrow().into_kv().1) }
;
1399 self.back
= last_leaf_edge(kv
.left_edge().descend());
1400 return Some((k
, v
));
1402 Err(last_edge
) => unsafe {
1403 cur_handle
= unwrap_unchecked(last_edge
.into_node().deallocate_and_ascend());
1410 #[stable(feature = "rust1", since = "1.0.0")]
1411 impl<K
, V
> ExactSizeIterator
for IntoIter
<K
, V
> {
1412 fn len(&self) -> usize {
1417 #[stable(feature = "fused", since = "1.26.0")]
1418 impl<K
, V
> FusedIterator
for IntoIter
<K
, V
> {}
1420 #[stable(feature = "rust1", since = "1.0.0")]
1421 impl<'a
, K
, V
> Iterator
for Keys
<'a
, K
, V
> {
1424 fn next(&mut self) -> Option
<&'a K
> {
1425 self.inner
.next().map(|(k
, _
)| k
)
1428 fn size_hint(&self) -> (usize, Option
<usize>) {
1429 self.inner
.size_hint()
1432 fn last(mut self) -> Option
<&'a K
> {
1437 #[stable(feature = "rust1", since = "1.0.0")]
1438 impl<'a
, K
, V
> DoubleEndedIterator
for Keys
<'a
, K
, V
> {
1439 fn next_back(&mut self) -> Option
<&'a K
> {
1440 self.inner
.next_back().map(|(k
, _
)| k
)
1444 #[stable(feature = "rust1", since = "1.0.0")]
1445 impl<K
, V
> ExactSizeIterator
for Keys
<'_
, K
, V
> {
1446 fn len(&self) -> usize {
1451 #[stable(feature = "fused", since = "1.26.0")]
1452 impl<K
, V
> FusedIterator
for Keys
<'_
, K
, V
> {}
1454 #[stable(feature = "rust1", since = "1.0.0")]
1455 impl<K
, V
> Clone
for Keys
<'_
, K
, V
> {
1456 fn clone(&self) -> Self {
1457 Keys { inner: self.inner.clone() }
1461 #[stable(feature = "rust1", since = "1.0.0")]
1462 impl<'a
, K
, V
> Iterator
for Values
<'a
, K
, V
> {
1465 fn next(&mut self) -> Option
<&'a V
> {
1466 self.inner
.next().map(|(_
, v
)| v
)
1469 fn size_hint(&self) -> (usize, Option
<usize>) {
1470 self.inner
.size_hint()
1473 fn last(mut self) -> Option
<&'a V
> {
1478 #[stable(feature = "rust1", since = "1.0.0")]
1479 impl<'a
, K
, V
> DoubleEndedIterator
for Values
<'a
, K
, V
> {
1480 fn next_back(&mut self) -> Option
<&'a V
> {
1481 self.inner
.next_back().map(|(_
, v
)| v
)
1485 #[stable(feature = "rust1", since = "1.0.0")]
1486 impl<K
, V
> ExactSizeIterator
for Values
<'_
, K
, V
> {
1487 fn len(&self) -> usize {
1492 #[stable(feature = "fused", since = "1.26.0")]
1493 impl<K
, V
> FusedIterator
for Values
<'_
, K
, V
> {}
1495 #[stable(feature = "rust1", since = "1.0.0")]
1496 impl<K
, V
> Clone
for Values
<'_
, K
, V
> {
1497 fn clone(&self) -> Self {
1498 Values { inner: self.inner.clone() }
1502 #[stable(feature = "btree_range", since = "1.17.0")]
1503 impl<'a
, K
, V
> Iterator
for Range
<'a
, K
, V
> {
1504 type Item
= (&'a K
, &'a V
);
1506 fn next(&mut self) -> Option
<(&'a K
, &'a V
)> {
1507 if self.front
== self.back
{
1510 unsafe { Some(self.next_unchecked()) }
1514 fn last(mut self) -> Option
<(&'a K
, &'a V
)> {
1519 #[stable(feature = "map_values_mut", since = "1.10.0")]
1520 impl<'a
, K
, V
> Iterator
for ValuesMut
<'a
, K
, V
> {
1521 type Item
= &'a
mut V
;
1523 fn next(&mut self) -> Option
<&'a
mut V
> {
1524 self.inner
.next().map(|(_
, v
)| v
)
1527 fn size_hint(&self) -> (usize, Option
<usize>) {
1528 self.inner
.size_hint()
1531 fn last(mut self) -> Option
<&'a
mut V
> {
1536 #[stable(feature = "map_values_mut", since = "1.10.0")]
1537 impl<'a
, K
, V
> DoubleEndedIterator
for ValuesMut
<'a
, K
, V
> {
1538 fn next_back(&mut self) -> Option
<&'a
mut V
> {
1539 self.inner
.next_back().map(|(_
, v
)| v
)
1543 #[stable(feature = "map_values_mut", since = "1.10.0")]
1544 impl<K
, V
> ExactSizeIterator
for ValuesMut
<'_
, K
, V
> {
1545 fn len(&self) -> usize {
1550 #[stable(feature = "fused", since = "1.26.0")]
1551 impl<K
, V
> FusedIterator
for ValuesMut
<'_
, K
, V
> {}
1553 impl<'a
, K
, V
> Range
<'a
, K
, V
> {
1554 unsafe fn next_unchecked(&mut self) -> (&'a K
, &'a V
) {
1555 let handle
= self.front
;
1557 let mut cur_handle
= match handle
.right_kv() {
1559 let ret
= kv
.into_kv();
1560 self.front
= kv
.right_edge();
1564 let next_level
= last_edge
.into_node().ascend().ok();
1565 unwrap_unchecked(next_level
)
1570 match cur_handle
.right_kv() {
1572 let ret
= kv
.into_kv();
1573 self.front
= first_leaf_edge(kv
.right_edge().descend());
1577 let next_level
= last_edge
.into_node().ascend().ok();
1578 cur_handle
= unwrap_unchecked(next_level
);
1585 #[stable(feature = "btree_range", since = "1.17.0")]
1586 impl<'a
, K
, V
> DoubleEndedIterator
for Range
<'a
, K
, V
> {
1587 fn next_back(&mut self) -> Option
<(&'a K
, &'a V
)> {
1588 if self.front
== self.back
{
1591 unsafe { Some(self.next_back_unchecked()) }
1596 impl<'a
, K
, V
> Range
<'a
, K
, V
> {
1597 unsafe fn next_back_unchecked(&mut self) -> (&'a K
, &'a V
) {
1598 let handle
= self.back
;
1600 let mut cur_handle
= match handle
.left_kv() {
1602 let ret
= kv
.into_kv();
1603 self.back
= kv
.left_edge();
1607 let next_level
= last_edge
.into_node().ascend().ok();
1608 unwrap_unchecked(next_level
)
1613 match cur_handle
.left_kv() {
1615 let ret
= kv
.into_kv();
1616 self.back
= last_leaf_edge(kv
.left_edge().descend());
1620 let next_level
= last_edge
.into_node().ascend().ok();
1621 cur_handle
= unwrap_unchecked(next_level
);
1628 #[stable(feature = "fused", since = "1.26.0")]
1629 impl<K
, V
> FusedIterator
for Range
<'_
, K
, V
> {}
1631 #[stable(feature = "btree_range", since = "1.17.0")]
1632 impl<K
, V
> Clone
for Range
<'_
, K
, V
> {
1633 fn clone(&self) -> Self {
1641 #[stable(feature = "btree_range", since = "1.17.0")]
1642 impl<'a
, K
, V
> Iterator
for RangeMut
<'a
, K
, V
> {
1643 type Item
= (&'a K
, &'a
mut V
);
1645 fn next(&mut self) -> Option
<(&'a K
, &'a
mut V
)> {
1646 if self.front
== self.back
{
1649 unsafe { Some(self.next_unchecked()) }
1653 fn last(mut self) -> Option
<(&'a K
, &'a
mut V
)> {
1658 impl<'a
, K
, V
> RangeMut
<'a
, K
, V
> {
1659 unsafe fn next_unchecked(&mut self) -> (&'a K
, &'a
mut V
) {
1660 let handle
= ptr
::read(&self.front
);
1662 let mut cur_handle
= match handle
.right_kv() {
1664 self.front
= ptr
::read(&kv
).right_edge();
1665 // Doing the descend invalidates the references returned by `into_kv_mut`,
1666 // so we have to do this last.
1667 let (k
, v
) = kv
.into_kv_mut();
1668 return (k
, v
); // coerce k from `&mut K` to `&K`
1671 let next_level
= last_edge
.into_node().ascend().ok();
1672 unwrap_unchecked(next_level
)
1677 match cur_handle
.right_kv() {
1679 self.front
= first_leaf_edge(ptr
::read(&kv
).right_edge().descend());
1680 // Doing the descend invalidates the references returned by `into_kv_mut`,
1681 // so we have to do this last.
1682 let (k
, v
) = kv
.into_kv_mut();
1683 return (k
, v
); // coerce k from `&mut K` to `&K`
1686 let next_level
= last_edge
.into_node().ascend().ok();
1687 cur_handle
= unwrap_unchecked(next_level
);
1694 #[stable(feature = "btree_range", since = "1.17.0")]
1695 impl<'a
, K
, V
> DoubleEndedIterator
for RangeMut
<'a
, K
, V
> {
1696 fn next_back(&mut self) -> Option
<(&'a K
, &'a
mut V
)> {
1697 if self.front
== self.back
{
1700 unsafe { Some(self.next_back_unchecked()) }
1705 #[stable(feature = "fused", since = "1.26.0")]
1706 impl<K
, V
> FusedIterator
for RangeMut
<'_
, K
, V
> {}
1708 impl<'a
, K
, V
> RangeMut
<'a
, K
, V
> {
1709 unsafe fn next_back_unchecked(&mut self) -> (&'a K
, &'a
mut V
) {
1710 let handle
= ptr
::read(&self.back
);
1712 let mut cur_handle
= match handle
.left_kv() {
1714 self.back
= ptr
::read(&kv
).left_edge();
1715 // Doing the descend invalidates the references returned by `into_kv_mut`,
1716 // so we have to do this last.
1717 let (k
, v
) = kv
.into_kv_mut();
1718 return (k
, v
); // coerce k from `&mut K` to `&K`
1721 let next_level
= last_edge
.into_node().ascend().ok();
1722 unwrap_unchecked(next_level
)
1727 match cur_handle
.left_kv() {
1729 self.back
= last_leaf_edge(ptr
::read(&kv
).left_edge().descend());
1730 // Doing the descend invalidates the references returned by `into_kv_mut`,
1731 // so we have to do this last.
1732 let (k
, v
) = kv
.into_kv_mut();
1733 return (k
, v
); // coerce k from `&mut K` to `&K`
1736 let next_level
= last_edge
.into_node().ascend().ok();
1737 cur_handle
= unwrap_unchecked(next_level
);
1744 #[stable(feature = "rust1", since = "1.0.0")]
1745 impl<K
: Ord
, V
> FromIterator
<(K
, V
)> for BTreeMap
<K
, V
> {
1746 fn from_iter
<T
: IntoIterator
<Item
= (K
, V
)>>(iter
: T
) -> BTreeMap
<K
, V
> {
1747 let mut map
= BTreeMap
::new();
1753 #[stable(feature = "rust1", since = "1.0.0")]
1754 impl<K
: Ord
, V
> Extend
<(K
, V
)> for BTreeMap
<K
, V
> {
1756 fn extend
<T
: IntoIterator
<Item
= (K
, V
)>>(&mut self, iter
: T
) {
1757 iter
.into_iter().for_each(move |(k
, v
)| {
1763 #[stable(feature = "extend_ref", since = "1.2.0")]
1764 impl<'a
, K
: Ord
+ Copy
, V
: Copy
> Extend
<(&'a K
, &'a V
)> for BTreeMap
<K
, V
> {
1765 fn extend
<I
: IntoIterator
<Item
= (&'a K
, &'a V
)>>(&mut self, iter
: I
) {
1766 self.extend(iter
.into_iter().map(|(&key
, &value
)| (key
, value
)));
1770 #[stable(feature = "rust1", since = "1.0.0")]
1771 impl<K
: Hash
, V
: Hash
> Hash
for BTreeMap
<K
, V
> {
1772 fn hash
<H
: Hasher
>(&self, state
: &mut H
) {
1779 #[stable(feature = "rust1", since = "1.0.0")]
1780 impl<K
: Ord
, V
> Default
for BTreeMap
<K
, V
> {
1781 /// Creates an empty `BTreeMap<K, V>`.
1782 fn default() -> BTreeMap
<K
, V
> {
1787 #[stable(feature = "rust1", since = "1.0.0")]
1788 impl<K
: PartialEq
, V
: PartialEq
> PartialEq
for BTreeMap
<K
, V
> {
1789 fn eq(&self, other
: &BTreeMap
<K
, V
>) -> bool
{
1790 self.len() == other
.len() && self.iter().zip(other
).all(|(a
, b
)| a
== b
)
1794 #[stable(feature = "rust1", since = "1.0.0")]
1795 impl<K
: Eq
, V
: Eq
> Eq
for BTreeMap
<K
, V
> {}
1797 #[stable(feature = "rust1", since = "1.0.0")]
1798 impl<K
: PartialOrd
, V
: PartialOrd
> PartialOrd
for BTreeMap
<K
, V
> {
1800 fn partial_cmp(&self, other
: &BTreeMap
<K
, V
>) -> Option
<Ordering
> {
1801 self.iter().partial_cmp(other
.iter())
1805 #[stable(feature = "rust1", since = "1.0.0")]
1806 impl<K
: Ord
, V
: Ord
> Ord
for BTreeMap
<K
, V
> {
1808 fn cmp(&self, other
: &BTreeMap
<K
, V
>) -> Ordering
{
1809 self.iter().cmp(other
.iter())
1813 #[stable(feature = "rust1", since = "1.0.0")]
1814 impl<K
: Debug
, V
: Debug
> Debug
for BTreeMap
<K
, V
> {
1815 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
1816 f
.debug_map().entries(self.iter()).finish()
1820 #[stable(feature = "rust1", since = "1.0.0")]
1821 impl<K
: Ord
, Q
: ?Sized
, V
> Index
<&Q
> for BTreeMap
<K
, V
>
1827 /// Returns a reference to the value corresponding to the supplied key.
1831 /// Panics if the key is not present in the `BTreeMap`.
1833 fn index(&self, key
: &Q
) -> &V
{
1834 self.get(key
).expect("no entry found for key")
1838 fn first_leaf_edge
<BorrowType
, K
, V
>
1839 (mut node
: NodeRef
<BorrowType
, K
, V
, marker
::LeafOrInternal
>)
1840 -> Handle
<NodeRef
<BorrowType
, K
, V
, marker
::Leaf
>, marker
::Edge
> {
1842 match node
.force() {
1843 Leaf(leaf
) => return leaf
.first_edge(),
1844 Internal(internal
) => {
1845 node
= internal
.first_edge().descend();
1851 fn last_leaf_edge
<BorrowType
, K
, V
>
1852 (mut node
: NodeRef
<BorrowType
, K
, V
, marker
::LeafOrInternal
>)
1853 -> Handle
<NodeRef
<BorrowType
, K
, V
, marker
::Leaf
>, marker
::Edge
> {
1855 match node
.force() {
1856 Leaf(leaf
) => return leaf
.last_edge(),
1857 Internal(internal
) => {
1858 node
= internal
.last_edge().descend();
1864 fn range_search
<BorrowType
, K
, V
, Q
: ?Sized
, R
: RangeBounds
<Q
>>(
1865 root1
: NodeRef
<BorrowType
, K
, V
, marker
::LeafOrInternal
>,
1866 root2
: NodeRef
<BorrowType
, K
, V
, marker
::LeafOrInternal
>,
1868 )-> (Handle
<NodeRef
<BorrowType
, K
, V
, marker
::Leaf
>, marker
::Edge
>,
1869 Handle
<NodeRef
<BorrowType
, K
, V
, marker
::Leaf
>, marker
::Edge
>)
1870 where Q
: Ord
, K
: Borrow
<Q
>
1872 match (range
.start_bound(), range
.end_bound()) {
1873 (Excluded(s
), Excluded(e
)) if s
==e
=>
1874 panic
!("range start and end are equal and excluded in BTreeMap"),
1875 (Included(s
), Included(e
)) |
1876 (Included(s
), Excluded(e
)) |
1877 (Excluded(s
), Included(e
)) |
1878 (Excluded(s
), Excluded(e
)) if s
>e
=>
1879 panic
!("range start is greater than range end in BTreeMap"),
1883 let mut min_node
= root1
;
1884 let mut max_node
= root2
;
1885 let mut min_found
= false;
1886 let mut max_found
= false;
1887 let mut diverged
= false;
1890 let min_edge
= match (min_found
, range
.start_bound()) {
1891 (false, Included(key
)) => match search
::search_linear(&min_node
, key
) {
1892 (i
, true) => { min_found = true; i }
,
1895 (false, Excluded(key
)) => match search
::search_linear(&min_node
, key
) {
1896 (i
, true) => { min_found = true; i+1 }
,
1899 (_
, Unbounded
) => 0,
1900 (true, Included(_
)) => min_node
.keys().len(),
1901 (true, Excluded(_
)) => 0,
1904 let max_edge
= match (max_found
, range
.end_bound()) {
1905 (false, Included(key
)) => match search
::search_linear(&max_node
, key
) {
1906 (i
, true) => { max_found = true; i+1 }
,
1909 (false, Excluded(key
)) => match search
::search_linear(&max_node
, key
) {
1910 (i
, true) => { max_found = true; i }
,
1913 (_
, Unbounded
) => max_node
.keys().len(),
1914 (true, Included(_
)) => 0,
1915 (true, Excluded(_
)) => max_node
.keys().len(),
1919 if max_edge
< min_edge { panic!("Ord is ill-defined in BTreeMap range") }
1920 if min_edge
!= max_edge { diverged = true; }
1923 let front
= Handle
::new_edge(min_node
, min_edge
);
1924 let back
= Handle
::new_edge(max_node
, max_edge
);
1925 match (front
.force(), back
.force()) {
1926 (Leaf(f
), Leaf(b
)) => {
1929 (Internal(min_int
), Internal(max_int
)) => {
1930 min_node
= min_int
.descend();
1931 max_node
= max_int
.descend();
1933 _
=> unreachable
!("BTreeMap has different depths"),
1939 unsafe fn unwrap_unchecked
<T
>(val
: Option
<T
>) -> T
{
1940 val
.unwrap_or_else(|| {
1941 if cfg
!(debug_assertions
) {
1942 panic
!("'unchecked' unwrap on None in BTreeMap");
1944 intrinsics
::unreachable();
1949 impl<K
, V
> BTreeMap
<K
, V
> {
1950 /// Gets an iterator over the entries of the map, sorted by key.
1957 /// use std::collections::BTreeMap;
1959 /// let mut map = BTreeMap::new();
1960 /// map.insert(3, "c");
1961 /// map.insert(2, "b");
1962 /// map.insert(1, "a");
1964 /// for (key, value) in map.iter() {
1965 /// println!("{}: {}", key, value);
1968 /// let (first_key, first_value) = map.iter().next().unwrap();
1969 /// assert_eq!((*first_key, *first_value), (1, "a"));
1971 #[stable(feature = "rust1", since = "1.0.0")]
1972 pub fn iter(&self) -> Iter
<'_
, K
, V
> {
1975 front
: first_leaf_edge(self.root
.as_ref()),
1976 back
: last_leaf_edge(self.root
.as_ref()),
1978 length
: self.length
,
1982 /// Gets a mutable iterator over the entries of the map, sorted by key.
1989 /// use std::collections::BTreeMap;
1991 /// let mut map = BTreeMap::new();
1992 /// map.insert("a", 1);
1993 /// map.insert("b", 2);
1994 /// map.insert("c", 3);
1996 /// // add 10 to the value if the key isn't "a"
1997 /// for (key, value) in map.iter_mut() {
1998 /// if key != &"a" {
2003 #[stable(feature = "rust1", since = "1.0.0")]
2004 pub fn iter_mut(&mut self) -> IterMut
<'_
, K
, V
> {
2005 let root1
= self.root
.as_mut();
2006 let root2
= unsafe { ptr::read(&root1) }
;
2009 front
: first_leaf_edge(root1
),
2010 back
: last_leaf_edge(root2
),
2011 _marker
: PhantomData
,
2013 length
: self.length
,
2017 /// Gets an iterator over the keys of the map, in sorted order.
2024 /// use std::collections::BTreeMap;
2026 /// let mut a = BTreeMap::new();
2027 /// a.insert(2, "b");
2028 /// a.insert(1, "a");
2030 /// let keys: Vec<_> = a.keys().cloned().collect();
2031 /// assert_eq!(keys, [1, 2]);
2033 #[stable(feature = "rust1", since = "1.0.0")]
2034 pub fn keys(&self) -> Keys
<'_
, K
, V
> {
2035 Keys { inner: self.iter() }
2038 /// Gets an iterator over the values of the map, in order by key.
2045 /// use std::collections::BTreeMap;
2047 /// let mut a = BTreeMap::new();
2048 /// a.insert(1, "hello");
2049 /// a.insert(2, "goodbye");
2051 /// let values: Vec<&str> = a.values().cloned().collect();
2052 /// assert_eq!(values, ["hello", "goodbye"]);
2054 #[stable(feature = "rust1", since = "1.0.0")]
2055 pub fn values(&self) -> Values
<'_
, K
, V
> {
2056 Values { inner: self.iter() }
2059 /// Gets a mutable iterator over the values of the map, in order by key.
2066 /// use std::collections::BTreeMap;
2068 /// let mut a = BTreeMap::new();
2069 /// a.insert(1, String::from("hello"));
2070 /// a.insert(2, String::from("goodbye"));
2072 /// for value in a.values_mut() {
2073 /// value.push_str("!");
2076 /// let values: Vec<String> = a.values().cloned().collect();
2077 /// assert_eq!(values, [String::from("hello!"),
2078 /// String::from("goodbye!")]);
2080 #[stable(feature = "map_values_mut", since = "1.10.0")]
2081 pub fn values_mut(&mut self) -> ValuesMut
<'_
, K
, V
> {
2082 ValuesMut { inner: self.iter_mut() }
2085 /// Returns the number of elements in the map.
2092 /// use std::collections::BTreeMap;
2094 /// let mut a = BTreeMap::new();
2095 /// assert_eq!(a.len(), 0);
2096 /// a.insert(1, "a");
2097 /// assert_eq!(a.len(), 1);
2099 #[stable(feature = "rust1", since = "1.0.0")]
2100 pub fn len(&self) -> usize {
2104 /// Returns `true` if the map contains no elements.
2111 /// use std::collections::BTreeMap;
2113 /// let mut a = BTreeMap::new();
2114 /// assert!(a.is_empty());
2115 /// a.insert(1, "a");
2116 /// assert!(!a.is_empty());
2118 #[stable(feature = "rust1", since = "1.0.0")]
2119 pub fn is_empty(&self) -> bool
{
2124 impl<'a
, K
: Ord
, V
> Entry
<'a
, K
, V
> {
2125 /// Ensures a value is in the entry by inserting the default if empty, and returns
2126 /// a mutable reference to the value in the entry.
2131 /// use std::collections::BTreeMap;
2133 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2134 /// map.entry("poneyland").or_insert(12);
2136 /// assert_eq!(map["poneyland"], 12);
2138 #[stable(feature = "rust1", since = "1.0.0")]
2139 pub fn or_insert(self, default: V
) -> &'a
mut V
{
2141 Occupied(entry
) => entry
.into_mut(),
2142 Vacant(entry
) => entry
.insert(default),
2146 /// Ensures a value is in the entry by inserting the result of the default function if empty,
2147 /// and returns a mutable reference to the value in the entry.
2152 /// use std::collections::BTreeMap;
2154 /// let mut map: BTreeMap<&str, String> = BTreeMap::new();
2155 /// let s = "hoho".to_string();
2157 /// map.entry("poneyland").or_insert_with(|| s);
2159 /// assert_eq!(map["poneyland"], "hoho".to_string());
2161 #[stable(feature = "rust1", since = "1.0.0")]
2162 pub fn or_insert_with
<F
: FnOnce() -> V
>(self, default: F
) -> &'a
mut V
{
2164 Occupied(entry
) => entry
.into_mut(),
2165 Vacant(entry
) => entry
.insert(default()),
2169 /// Returns a reference to this entry's key.
2174 /// use std::collections::BTreeMap;
2176 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2177 /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
2179 #[stable(feature = "map_entry_keys", since = "1.10.0")]
2180 pub fn key(&self) -> &K
{
2182 Occupied(ref entry
) => entry
.key(),
2183 Vacant(ref entry
) => entry
.key(),
2187 /// Provides in-place mutable access to an occupied entry before any
2188 /// potential inserts into the map.
2193 /// use std::collections::BTreeMap;
2195 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2197 /// map.entry("poneyland")
2198 /// .and_modify(|e| { *e += 1 })
2200 /// assert_eq!(map["poneyland"], 42);
2202 /// map.entry("poneyland")
2203 /// .and_modify(|e| { *e += 1 })
2205 /// assert_eq!(map["poneyland"], 43);
2207 #[stable(feature = "entry_and_modify", since = "1.26.0")]
2208 pub fn and_modify
<F
>(self, f
: F
) -> Self
2209 where F
: FnOnce(&mut V
)
2212 Occupied(mut entry
) => {
2216 Vacant(entry
) => Vacant(entry
),
2221 impl<'a
, K
: Ord
, V
: Default
> Entry
<'a
, K
, V
> {
2222 #[stable(feature = "entry_or_default", since = "1.28.0")]
2223 /// Ensures a value is in the entry by inserting the default value if empty,
2224 /// and returns a mutable reference to the value in the entry.
2229 /// use std::collections::BTreeMap;
2231 /// let mut map: BTreeMap<&str, Option<usize>> = BTreeMap::new();
2232 /// map.entry("poneyland").or_default();
2234 /// assert_eq!(map["poneyland"], None);
2236 pub fn or_default(self) -> &'a
mut V
{
2238 Occupied(entry
) => entry
.into_mut(),
2239 Vacant(entry
) => entry
.insert(Default
::default()),
2245 impl<'a
, K
: Ord
, V
> VacantEntry
<'a
, K
, V
> {
2246 /// Gets a reference to the key that would be used when inserting a value
2247 /// through the VacantEntry.
2252 /// use std::collections::BTreeMap;
2254 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2255 /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
2257 #[stable(feature = "map_entry_keys", since = "1.10.0")]
2258 pub fn key(&self) -> &K
{
2262 /// Take ownership of the key.
2267 /// use std::collections::BTreeMap;
2268 /// use std::collections::btree_map::Entry;
2270 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2272 /// if let Entry::Vacant(v) = map.entry("poneyland") {
2276 #[stable(feature = "map_entry_recover_keys2", since = "1.12.0")]
2277 pub fn into_key(self) -> K
{
2281 /// Sets the value of the entry with the `VacantEntry`'s key,
2282 /// and returns a mutable reference to it.
2287 /// use std::collections::BTreeMap;
2289 /// let mut count: BTreeMap<&str, usize> = BTreeMap::new();
2291 /// // count the number of occurrences of letters in the vec
2292 /// for x in vec!["a","b","a","c","a","b"] {
2293 /// *count.entry(x).or_insert(0) += 1;
2296 /// assert_eq!(count["a"], 3);
2298 #[stable(feature = "rust1", since = "1.0.0")]
2299 pub fn insert(self, value
: V
) -> &'a
mut V
{
2308 let mut cur_parent
= match self.handle
.insert(self.key
, value
) {
2309 (Fit(handle
), _
) => return handle
.into_kv_mut().1,
2310 (Split(left
, k
, v
, right
), ptr
) => {
2315 left
.ascend().map_err(|n
| n
.into_root_mut())
2322 match parent
.insert(ins_k
, ins_v
, ins_edge
) {
2323 Fit(_
) => return unsafe { &mut *out_ptr }
,
2324 Split(left
, k
, v
, right
) => {
2328 cur_parent
= left
.ascend().map_err(|n
| n
.into_root_mut());
2333 root
.push_level().push(ins_k
, ins_v
, ins_edge
);
2334 return unsafe { &mut *out_ptr }
;
2341 impl<'a
, K
: Ord
, V
> OccupiedEntry
<'a
, K
, V
> {
2342 /// Gets a reference to the key in the entry.
2347 /// use std::collections::BTreeMap;
2349 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2350 /// map.entry("poneyland").or_insert(12);
2351 /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
2353 #[stable(feature = "map_entry_keys", since = "1.10.0")]
2354 pub fn key(&self) -> &K
{
2355 self.handle
.reborrow().into_kv().0
2358 /// Take ownership of the key and value from the map.
2363 /// use std::collections::BTreeMap;
2364 /// use std::collections::btree_map::Entry;
2366 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2367 /// map.entry("poneyland").or_insert(12);
2369 /// if let Entry::Occupied(o) = map.entry("poneyland") {
2370 /// // We delete the entry from the map.
2371 /// o.remove_entry();
2374 /// // If now try to get the value, it will panic:
2375 /// // println!("{}", map["poneyland"]);
2377 #[stable(feature = "map_entry_recover_keys2", since = "1.12.0")]
2378 pub fn remove_entry(self) -> (K
, V
) {
2382 /// Gets a reference to the value in the entry.
2387 /// use std::collections::BTreeMap;
2388 /// use std::collections::btree_map::Entry;
2390 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2391 /// map.entry("poneyland").or_insert(12);
2393 /// if let Entry::Occupied(o) = map.entry("poneyland") {
2394 /// assert_eq!(o.get(), &12);
2397 #[stable(feature = "rust1", since = "1.0.0")]
2398 pub fn get(&self) -> &V
{
2399 self.handle
.reborrow().into_kv().1
2402 /// Gets a mutable reference to the value in the entry.
2404 /// If you need a reference to the `OccupiedEntry` that may outlive the
2405 /// destruction of the `Entry` value, see [`into_mut`].
2407 /// [`into_mut`]: #method.into_mut
2412 /// use std::collections::BTreeMap;
2413 /// use std::collections::btree_map::Entry;
2415 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2416 /// map.entry("poneyland").or_insert(12);
2418 /// assert_eq!(map["poneyland"], 12);
2419 /// if let Entry::Occupied(mut o) = map.entry("poneyland") {
2420 /// *o.get_mut() += 10;
2421 /// assert_eq!(*o.get(), 22);
2423 /// // We can use the same Entry multiple times.
2424 /// *o.get_mut() += 2;
2426 /// assert_eq!(map["poneyland"], 24);
2428 #[stable(feature = "rust1", since = "1.0.0")]
2429 pub fn get_mut(&mut self) -> &mut V
{
2430 self.handle
.kv_mut().1
2433 /// Converts the entry into a mutable reference to its value.
2435 /// If you need multiple references to the `OccupiedEntry`, see [`get_mut`].
2437 /// [`get_mut`]: #method.get_mut
2442 /// use std::collections::BTreeMap;
2443 /// use std::collections::btree_map::Entry;
2445 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2446 /// map.entry("poneyland").or_insert(12);
2448 /// assert_eq!(map["poneyland"], 12);
2449 /// if let Entry::Occupied(o) = map.entry("poneyland") {
2450 /// *o.into_mut() += 10;
2452 /// assert_eq!(map["poneyland"], 22);
2454 #[stable(feature = "rust1", since = "1.0.0")]
2455 pub fn into_mut(self) -> &'a
mut V
{
2456 self.handle
.into_kv_mut().1
2459 /// Sets the value of the entry with the `OccupiedEntry`'s key,
2460 /// and returns the entry's old value.
2465 /// use std::collections::BTreeMap;
2466 /// use std::collections::btree_map::Entry;
2468 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2469 /// map.entry("poneyland").or_insert(12);
2471 /// if let Entry::Occupied(mut o) = map.entry("poneyland") {
2472 /// assert_eq!(o.insert(15), 12);
2474 /// assert_eq!(map["poneyland"], 15);
2476 #[stable(feature = "rust1", since = "1.0.0")]
2477 pub fn insert(&mut self, value
: V
) -> V
{
2478 mem
::replace(self.get_mut(), value
)
2481 /// Takes the value of the entry out of the map, and returns it.
2486 /// use std::collections::BTreeMap;
2487 /// use std::collections::btree_map::Entry;
2489 /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
2490 /// map.entry("poneyland").or_insert(12);
2492 /// if let Entry::Occupied(o) = map.entry("poneyland") {
2493 /// assert_eq!(o.remove(), 12);
2495 /// // If we try to get "poneyland"'s value, it'll panic:
2496 /// // println!("{}", map["poneyland"]);
2498 #[stable(feature = "rust1", since = "1.0.0")]
2499 pub fn remove(self) -> V
{
2503 fn remove_kv(self) -> (K
, V
) {
2506 let (small_leaf
, old_key
, old_val
) = match self.handle
.force() {
2508 let (hole
, old_key
, old_val
) = leaf
.remove();
2509 (hole
.into_node(), old_key
, old_val
)
2511 Internal(mut internal
) => {
2512 let key_loc
= internal
.kv_mut().0 as *mut K
;
2513 let val_loc
= internal
.kv_mut().1 as *mut V
;
2515 let to_remove
= first_leaf_edge(internal
.right_edge().descend()).right_kv().ok();
2516 let to_remove
= unsafe { unwrap_unchecked(to_remove) }
;
2518 let (hole
, key
, val
) = to_remove
.remove();
2520 let old_key
= unsafe { mem::replace(&mut *key_loc, key) }
;
2521 let old_val
= unsafe { mem::replace(&mut *val_loc, val) }
;
2523 (hole
.into_node(), old_key
, old_val
)
2528 let mut cur_node
= small_leaf
.forget_type();
2529 while cur_node
.len() < node
::CAPACITY
/ 2 {
2530 match handle_underfull_node(cur_node
) {
2532 EmptyParent(_
) => unreachable
!(),
2534 if parent
.len() == 0 {
2535 // We must be at the root
2536 parent
.into_root_mut().pop_level();
2539 cur_node
= parent
.forget_type();
2550 enum UnderflowResult
<'a
, K
, V
> {
2552 EmptyParent(NodeRef
<marker
::Mut
<'a
>, K
, V
, marker
::Internal
>),
2553 Merged(NodeRef
<marker
::Mut
<'a
>, K
, V
, marker
::Internal
>),
2554 Stole(NodeRef
<marker
::Mut
<'a
>, K
, V
, marker
::Internal
>),
2557 fn handle_underfull_node
<K
, V
>(node
: NodeRef
<marker
::Mut
<'_
>, K
, V
, marker
::LeafOrInternal
>)
2558 -> UnderflowResult
<'_
, K
, V
> {
2559 let parent
= if let Ok(parent
) = node
.ascend() {
2565 let (is_left
, mut handle
) = match parent
.left_kv() {
2566 Ok(left
) => (true, left
),
2568 match parent
.right_kv() {
2569 Ok(right
) => (false, right
),
2571 return EmptyParent(parent
.into_node());
2577 if handle
.can_merge() {
2578 Merged(handle
.merge().into_node())
2581 handle
.steal_left();
2583 handle
.steal_right();
2585 Stole(handle
.into_node())
2589 impl<K
: Ord
, V
, I
: Iterator
<Item
= (K
, V
)>> Iterator
for MergeIter
<K
, V
, I
> {
2592 fn next(&mut self) -> Option
<(K
, V
)> {
2593 let res
= match (self.left
.peek(), self.right
.peek()) {
2594 (Some(&(ref left_key
, _
)), Some(&(ref right_key
, _
))) => left_key
.cmp(right_key
),
2595 (Some(_
), None
) => Ordering
::Less
,
2596 (None
, Some(_
)) => Ordering
::Greater
,
2597 (None
, None
) => return None
,
2600 // Check which elements comes first and only advance the corresponding iterator.
2601 // If two keys are equal, take the value from `right`.
2603 Ordering
::Less
=> self.left
.next(),
2604 Ordering
::Greater
=> self.right
.next(),
2605 Ordering
::Equal
=> {