map.rs - source (original) (raw)
alloc/collections/btree/
map.rs
1use core::borrow::Borrow;
2use core::cmp::Ordering;
3use core::error::Error;
4use core::fmt::{self, Debug};
5use core::hash::{Hash, Hasher};
6use core::iter::FusedIterator;
7use core:📑:PhantomData;
8use core::mem::{self, ManuallyDrop};
9use core::ops::{Bound, Index, RangeBounds};
10use core::ptr;
11
12use super::borrow::DormantMutRef;
13use super::dedup_sorted_iter::DedupSortedIter;
14use super::navigate::{LazyLeafRange, LeafRange};
15use super::node::ForceResult::*;
16use super::node::{self, Handle, NodeRef, Root, marker};
17use super::search::SearchBound;
18use super::search::SearchResult::*;
19use super::set_val::SetValZST;
20use crate::alloc::{Allocator, Global};
21use crate::vec::Vec;
22
23mod entry;
24
25use Entry::*;
26#[stable(feature = "rust1", since = "1.0.0")]
27pub use entry::{Entry, OccupiedEntry, OccupiedError, VacantEntry};
28
29/// Minimum number of elements in a node that is not a root.
30/// We might temporarily have fewer elements during methods.
31pub(super) const MIN_LEN: usize = node::MIN_LEN_AFTER_SPLIT;
32
33// A tree in a `BTreeMap` is a tree in the `node` module with additional invariants:
34// - Keys must appear in ascending order (according to the key's type).
35// - Every non-leaf node contains at least 1 element (has at least 2 children).
36// - Every non-root node contains at least MIN_LEN elements.
37//
38// An empty map is represented either by the absence of a root node or by a
39// root node that is an empty leaf.
40
41/// An ordered map based on a [B-Tree].
42///
43/// B-Trees represent a fundamental compromise between cache-efficiency and actually minimizing
44/// the amount of work performed in a search. In theory, a binary search tree (BST) is the optimal
45/// choice for a sorted map, as a perfectly balanced BST performs the theoretical minimum amount of
46/// comparisons necessary to find an element (log<sub>2</sub>n). However, in practice the way this
47/// is done is *very* inefficient for modern computer architectures. In particular, every element
48/// is stored in its own individually heap-allocated node. This means that every single insertion
49/// triggers a heap-allocation, and every single comparison should be a cache-miss. Since these
50/// are both notably expensive things to do in practice, we are forced to, at the very least,
51/// reconsider the BST strategy.
52///
53/// A B-Tree instead makes each node contain B-1 to 2B-1 elements in a contiguous array. By doing
54/// this, we reduce the number of allocations by a factor of B, and improve cache efficiency in
55/// searches. However, this does mean that searches will have to do *more* comparisons on average.
56/// The precise number of comparisons depends on the node search strategy used. For optimal cache
57/// efficiency, one could search the nodes linearly. For optimal comparisons, one could search
58/// the node using binary search. As a compromise, one could also perform a linear search
59/// that initially only checks every i<sup>th</sup> element for some choice of i.
60///
61/// Currently, our implementation simply performs naive linear search. This provides excellent
62/// performance on *small* nodes of elements which are cheap to compare. However in the future we
63/// would like to further explore choosing the optimal search strategy based on the choice of B,
64/// and possibly other factors. Using linear search, searching for a random element is expected
65/// to take B * log(n) comparisons, which is generally worse than a BST. In practice,
66/// however, performance is excellent.
67///
68/// It is a logic error for a key to be modified in such a way that the key's ordering relative to
69/// any other key, as determined by the [`Ord`] trait, changes while it is in the map. This is
70/// normally only possible through [`Cell`], [`RefCell`], global state, I/O, or unsafe code.
71/// The behavior resulting from such a logic error is not specified, but will be encapsulated to the
72/// `BTreeMap` that observed the logic error and not result in undefined behavior. This could
73/// include panics, incorrect results, aborts, memory leaks, and non-termination.
74///
75/// Iterators obtained from functions such as [`BTreeMap::iter`], [`BTreeMap::into_iter`], [`BTreeMap::values`], or
76/// [`BTreeMap::keys`] produce their items in order by key, and take worst-case logarithmic and
77/// amortized constant time per item returned.
78///
79/// [B-Tree]: https://en.wikipedia.org/wiki/B-tree
80/// [`Cell`]: core::cell::Cell
81/// [`RefCell`]: core::cell::RefCell
82///
83/// # Examples
84///
85/// ```
86/// use std::collections::BTreeMap;
87///
88/// // type inference lets us omit an explicit type signature (which
89/// // would be `BTreeMap<&str, &str>` in this example).
90/// let mut movie_reviews = BTreeMap::new();
91///
92/// // review some movies.
93/// movie_reviews.insert("Office Space", "Deals with real issues in the workplace.");
94/// movie_reviews.insert("Pulp Fiction", "Masterpiece.");
95/// movie_reviews.insert("The Godfather", "Very enjoyable.");
96/// movie_reviews.insert("The Blues Brothers", "Eye lyked it a lot.");
97///
98/// // check for a specific one.
99/// if !movie_reviews.contains_key("Les Misérables") {
100/// println!("We've got {} reviews, but Les Misérables ain't one.",
101/// movie_reviews.len());
102/// }
103///
104/// // oops, this review has a lot of spelling mistakes, let's delete it.
105/// movie_reviews.remove("The Blues Brothers");
106///
107/// // look up the values associated with some keys.
108/// let to_find = ["Up!", "Office Space"];
109/// for movie in &to_find {
110/// match movie_reviews.get(movie) {
111/// Some(review) => println!("{movie}: {review}"),
112/// None => println!("{movie} is unreviewed.")
113/// }
114/// }
115///
116/// // Look up the value for a key (will panic if the key is not found).
117/// println!("Movie review: {}", movie_reviews["Office Space"]);
118///
119/// // iterate over everything.
120/// for (movie, review) in &movie_reviews {
121/// println!("{movie}: \"{review}\"");
122/// }
123/// ```
124///
125/// A `BTreeMap` with a known list of items can be initialized from an array:
126///
127/// ```
128/// use std::collections::BTreeMap;
129///
130/// let solar_distance = BTreeMap::from([
131/// ("Mercury", 0.4),
132/// ("Venus", 0.7),
133/// ("Earth", 1.0),
134/// ("Mars", 1.5),
135/// ]);
136/// ```
137///
138/// `BTreeMap` implements an [`Entry API`], which allows for complex
139/// methods of getting, setting, updating and removing keys and their values:
140///
141/// [`Entry API`]: BTreeMap::entry
142///
143/// ```
144/// use std::collections::BTreeMap;
145///
146/// // type inference lets us omit an explicit type signature (which
147/// // would be `BTreeMap<&str, u8>` in this example).
148/// let mut player_stats = BTreeMap::new();
149///
150/// fn random_stat_buff() -> u8 {
151/// // could actually return some random value here - let's just return
152/// // some fixed value for now
153/// 42
154/// }
155///
156/// // insert a key only if it doesn't already exist
157/// player_stats.entry("health").or_insert(100);
158///
159/// // insert a key using a function that provides a new value only if it
160/// // doesn't already exist
161/// player_stats.entry("defence").or_insert_with(random_stat_buff);
162///
163/// // update a key, guarding against the key possibly not being set
164/// let stat = player_stats.entry("attack").or_insert(100);
165/// *stat += random_stat_buff();
166///
167/// // modify an entry before an insert with in-place mutation
168/// player_stats.entry("mana").and_modify(|mana| *mana += 200).or_insert(100);
169/// ```
170#[stable(feature = "rust1", since = "1.0.0")]
171#[cfg_attr(not(test), rustc_diagnostic_item = "BTreeMap")]
172#[rustc_insignificant_dtor]
173pub struct BTreeMap<
174 K,
175 V,
176 #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + Clone = Global,
177> {
178 root: Option<Root<K, V>>,
179 length: usize,
180 /// `ManuallyDrop` to control drop order (needs to be dropped after all the nodes).
181 pub(super) alloc: ManuallyDrop<A>,
182 // For dropck; the `Box` avoids making the `Unpin` impl more strict than before
183 _marker: PhantomData<crate::boxed::Box<(K, V), A>>,
184}
185
186#[stable(feature = "btree_drop", since = "1.7.0")]
187unsafe impl<#[may_dangle] K, #[may_dangle] V, A: Allocator + Clone> Drop for BTreeMap<K, V, A> {
188 fn drop(&mut self) {
189 drop(unsafe { ptr::read(self) }.into_iter())
190 }
191}
192
193// FIXME: This implementation is "wrong", but changing it would be a breaking change.
194// (The bounds of the automatic `UnwindSafe` implementation have been like this since Rust 1.50.)
195// Maybe we can fix it nonetheless with a crater run, or if the `UnwindSafe`
196// traits are deprecated, or disarmed (no longer causing hard errors) in the future.
197#[stable(feature = "btree_unwindsafe", since = "1.64.0")]
198impl<K, V, A: Allocator + Clone> core::panic::UnwindSafe for BTreeMap<K, V, A>
199where
200 A: core::panic::UnwindSafe,
201 K: core::panic::RefUnwindSafe,
202 V: core::panic::RefUnwindSafe,
203{
204}
205
206#[stable(feature = "rust1", since = "1.0.0")]
207impl<K: Clone, V: Clone, A: Allocator + Clone> Clone for BTreeMap<K, V, A> {
208 fn clone(&self) -> BTreeMap<K, V, A> {
209 fn clone_subtree<'a, K: Clone, V: Clone, A: Allocator + Clone>(
210 node: NodeRef<marker::Immut<'a>, K, V, marker::LeafOrInternal>,
211 alloc: A,
212 ) -> BTreeMap<K, V, A>
213 where
214 K: 'a,
215 V: 'a,
216 {
217 match node.force() {
218 Leaf(leaf) => {
219 let mut out_tree = BTreeMap {
220 root: Some(Root::new(alloc.clone())),
221 length: 0,
222 alloc: ManuallyDrop::new(alloc),
223 _marker: PhantomData,
224 };
225
226 {
227 let root = out_tree.root.as_mut().unwrap(); // unwrap succeeds because we just wrapped
228 let mut out_node = match root.borrow_mut().force() {
229 Leaf(leaf) => leaf,
230 Internal(_) => unreachable!(),
231 };
232
233 let mut in_edge = leaf.first_edge();
234 while let Ok(kv) = in_edge.right_kv() {
235 let (k, v) = kv.into_kv();
236 in_edge = kv.right_edge();
237
238 out_node.push(k.clone(), v.clone());
239 out_tree.length += 1;
240 }
241 }
242
243 out_tree
244 }
245 Internal(internal) => {
246 let mut out_tree =
247 clone_subtree(internal.first_edge().descend(), alloc.clone());
248
249 {
250 let out_root = out_tree.root.as_mut().unwrap();
251 let mut out_node = out_root.push_internal_level(alloc.clone());
252 let mut in_edge = internal.first_edge();
253 while let Ok(kv) = in_edge.right_kv() {
254 let (k, v) = kv.into_kv();
255 in_edge = kv.right_edge();
256
257 let k = (*k).clone();
258 let v = (*v).clone();
259 let subtree = clone_subtree(in_edge.descend(), alloc.clone());
260
261 // We can't destructure subtree directly
262 // because BTreeMap implements Drop
263 let (subroot, sublength) = unsafe {
264 let subtree = ManuallyDrop::new(subtree);
265 let root = ptr::read(&subtree.root);
266 let length = subtree.length;
267 (root, length)
268 };
269
270 out_node.push(
271 k,
272 v,
273 subroot.unwrap_or_else(|| Root::new(alloc.clone())),
274 );
275 out_tree.length += 1 + sublength;
276 }
277 }
278
279 out_tree
280 }
281 }
282 }
283
284 if self.is_empty() {
285 BTreeMap::new_in((*self.alloc).clone())
286 } else {
287 clone_subtree(self.root.as_ref().unwrap().reborrow(), (*self.alloc).clone()) // unwrap succeeds because not empty
288 }
289 }
290}
291
292// Internal functionality for `BTreeSet`.
293impl<K, A: Allocator + Clone> BTreeMap<K, SetValZST, A> {
294 pub(super) fn replace(&mut self, key: K) -> Option<K>
295 where
296 K: Ord,
297 {
298 let (map, dormant_map) = DormantMutRef::new(self);
299 let root_node =
300 map.root.get_or_insert_with(|| Root::new((*map.alloc).clone())).borrow_mut();
301 match root_node.search_tree::<K>(&key) {
302 Found(mut kv) => Some(mem::replace(kv.key_mut(), key)),
303 GoDown(handle) => {
304 VacantEntry {
305 key,
306 handle: Some(handle),
307 dormant_map,
308 alloc: (*map.alloc).clone(),
309 _marker: PhantomData,
310 }
311 .insert(SetValZST);
312 None
313 }
314 }
315 }
316
317 pub(super) fn get_or_insert_with<Q: ?Sized, F>(&mut self, q: &Q, f: F) -> &K
318 where
319 K: Borrow<Q> + Ord,
320 Q: Ord,
321 F: FnOnce(&Q) -> K,
322 {
323 let (map, dormant_map) = DormantMutRef::new(self);
324 let root_node =
325 map.root.get_or_insert_with(|| Root::new((*map.alloc).clone())).borrow_mut();
326 match root_node.search_tree(q) {
327 Found(handle) => handle.into_kv_mut().0,
328 GoDown(handle) => {
329 let key = f(q);
330 assert!(*key.borrow() == *q, "new value is not equal");
331 VacantEntry {
332 key,
333 handle: Some(handle),
334 dormant_map,
335 alloc: (*map.alloc).clone(),
336 _marker: PhantomData,
337 }
338 .insert_entry(SetValZST)
339 .into_key()
340 }
341 }
342 }
343}
344
345/// An iterator over the entries of a `BTreeMap`.
346///
347/// This `struct` is created by the [`iter`] method on [`BTreeMap`]. See its
348/// documentation for more.
349///
350/// [`iter`]: BTreeMap::iter
351#[must_use = "iterators are lazy and do nothing unless consumed"]
352#[stable(feature = "rust1", since = "1.0.0")]
353pub struct Iter<'a, K: 'a, V: 'a> {
354 range: LazyLeafRange<marker::Immut<'a>, K, V>,
355 length: usize,
356}
357
358#[stable(feature = "collection_debug", since = "1.17.0")]
359impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Iter<'_, K, V> {
360 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
361 f.debug_list().entries(self.clone()).finish()
362 }
363}
364
365#[stable(feature = "default_iters", since = "1.70.0")]
366impl<'a, K: 'a, V: 'a> Default for Iter<'a, K, V> {
367 /// Creates an empty `btree_map::Iter`.
368 ///
369 /// ```
370 /// # use std::collections::btree_map;
371 /// let iter: btree_map::Iter<'_, u8, u8> = Default::default();
372 /// assert_eq!(iter.len(), 0);
373 /// ```
374 fn default() -> Self {
375 Iter { range: Default::default(), length: 0 }
376 }
377}
378
379/// A mutable iterator over the entries of a `BTreeMap`.
380///
381/// This `struct` is created by the [`iter_mut`] method on [`BTreeMap`]. See its
382/// documentation for more.
383///
384/// [`iter_mut`]: BTreeMap::iter_mut
385#[stable(feature = "rust1", since = "1.0.0")]
386pub struct IterMut<'a, K: 'a, V: 'a> {
387 range: LazyLeafRange<marker::ValMut<'a>, K, V>,
388 length: usize,
389
390 // Be invariant in `K` and `V`
391 _marker: PhantomData<&'a mut (K, V)>,
392}
393
394#[must_use = "iterators are lazy and do nothing unless consumed"]
395#[stable(feature = "collection_debug", since = "1.17.0")]
396impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IterMut<'_, K, V> {
397 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
398 let range = Iter { range: self.range.reborrow(), length: self.length };
399 f.debug_list().entries(range).finish()
400 }
401}
402
403#[stable(feature = "default_iters", since = "1.70.0")]
404impl<'a, K: 'a, V: 'a> Default for IterMut<'a, K, V> {
405 /// Creates an empty `btree_map::IterMut`.
406 ///
407 /// ```
408 /// # use std::collections::btree_map;
409 /// let iter: btree_map::IterMut<'_, u8, u8> = Default::default();
410 /// assert_eq!(iter.len(), 0);
411 /// ```
412 fn default() -> Self {
413 IterMut { range: Default::default(), length: 0, _marker: PhantomData {} }
414 }
415}
416
417/// An owning iterator over the entries of a `BTreeMap`, sorted by key.
418///
419/// This `struct` is created by the [`into_iter`] method on [`BTreeMap`]
420/// (provided by the [`IntoIterator`] trait). See its documentation for more.
421///
422/// [`into_iter`]: IntoIterator::into_iter
423#[stable(feature = "rust1", since = "1.0.0")]
424#[rustc_insignificant_dtor]
425pub struct IntoIter<
426 K,
427 V,
428 #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + Clone = Global,
429> {
430 range: LazyLeafRange<marker::Dying, K, V>,
431 length: usize,
432 /// The BTreeMap will outlive this IntoIter so we don't care about drop order for `alloc`.
433 alloc: A,
434}
435
436impl<K, V, A: Allocator + Clone> IntoIter<K, V, A> {
437 /// Returns an iterator of references over the remaining items.
438 #[inline]
439 pub(super) fn iter(&self) -> Iter<'_, K, V> {
440 Iter { range: self.range.reborrow(), length: self.length }
441 }
442}
443
444#[stable(feature = "collection_debug", since = "1.17.0")]
445impl<K: Debug, V: Debug, A: Allocator + Clone> Debug for IntoIter<K, V, A> {
446 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
447 f.debug_list().entries(self.iter()).finish()
448 }
449}
450
451#[stable(feature = "default_iters", since = "1.70.0")]
452impl<K, V, A> Default for IntoIter<K, V, A>
453where
454 A: Allocator + Default + Clone,
455{
456 /// Creates an empty `btree_map::IntoIter`.
457 ///
458 /// ```
459 /// # use std::collections::btree_map;
460 /// let iter: btree_map::IntoIter<u8, u8> = Default::default();
461 /// assert_eq!(iter.len(), 0);
462 /// ```
463 fn default() -> Self {
464 IntoIter { range: Default::default(), length: 0, alloc: Default::default() }
465 }
466}
467
468/// An iterator over the keys of a `BTreeMap`.
469///
470/// This `struct` is created by the [`keys`] method on [`BTreeMap`]. See its
471/// documentation for more.
472///
473/// [`keys`]: BTreeMap::keys
474#[must_use = "iterators are lazy and do nothing unless consumed"]
475#[stable(feature = "rust1", since = "1.0.0")]
476pub struct Keys<'a, K, V> {
477 inner: Iter<'a, K, V>,
478}
479
480#[stable(feature = "collection_debug", since = "1.17.0")]
481impl<K: fmt::Debug, V> fmt::Debug for Keys<'_, K, V> {
482 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
483 f.debug_list().entries(self.clone()).finish()
484 }
485}
486
487/// An iterator over the values of a `BTreeMap`.
488///
489/// This `struct` is created by the [`values`] method on [`BTreeMap`]. See its
490/// documentation for more.
491///
492/// [`values`]: BTreeMap::values
493#[must_use = "iterators are lazy and do nothing unless consumed"]
494#[stable(feature = "rust1", since = "1.0.0")]
495pub struct Values<'a, K, V> {
496 inner: Iter<'a, K, V>,
497}
498
499#[stable(feature = "collection_debug", since = "1.17.0")]
500impl<K, V: fmt::Debug> fmt::Debug for Values<'_, K, V> {
501 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
502 f.debug_list().entries(self.clone()).finish()
503 }
504}
505
506/// A mutable iterator over the values of a `BTreeMap`.
507///
508/// This `struct` is created by the [`values_mut`] method on [`BTreeMap`]. See its
509/// documentation for more.
510///
511/// [`values_mut`]: BTreeMap::values_mut
512#[must_use = "iterators are lazy and do nothing unless consumed"]
513#[stable(feature = "map_values_mut", since = "1.10.0")]
514pub struct ValuesMut<'a, K, V> {
515 inner: IterMut<'a, K, V>,
516}
517
518#[stable(feature = "map_values_mut", since = "1.10.0")]
519impl<K, V: fmt::Debug> fmt::Debug for ValuesMut<'_, K, V> {
520 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
521 f.debug_list().entries(self.inner.iter().map(|(_, val)| val)).finish()
522 }
523}
524
525/// An owning iterator over the keys of a `BTreeMap`.
526///
527/// This `struct` is created by the [`into_keys`] method on [`BTreeMap`].
528/// See its documentation for more.
529///
530/// [`into_keys`]: BTreeMap::into_keys
531#[must_use = "iterators are lazy and do nothing unless consumed"]
532#[stable(feature = "map_into_keys_values", since = "1.54.0")]
533pub struct IntoKeys<K, V, A: Allocator + Clone = Global> {
534 inner: IntoIter<K, V, A>,
535}
536
537#[stable(feature = "map_into_keys_values", since = "1.54.0")]
538impl<K: fmt::Debug, V, A: Allocator + Clone> fmt::Debug for IntoKeys<K, V, A> {
539 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
540 f.debug_list().entries(self.inner.iter().map(|(key, _)| key)).finish()
541 }
542}
543
544/// An owning iterator over the values of a `BTreeMap`.
545///
546/// This `struct` is created by the [`into_values`] method on [`BTreeMap`].
547/// See its documentation for more.
548///
549/// [`into_values`]: BTreeMap::into_values
550#[must_use = "iterators are lazy and do nothing unless consumed"]
551#[stable(feature = "map_into_keys_values", since = "1.54.0")]
552pub struct IntoValues<
553 K,
554 V,
555 #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + Clone = Global,
556> {
557 inner: IntoIter<K, V, A>,
558}
559
560#[stable(feature = "map_into_keys_values", since = "1.54.0")]
561impl<K, V: fmt::Debug, A: Allocator + Clone> fmt::Debug for IntoValues<K, V, A> {
562 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
563 f.debug_list().entries(self.inner.iter().map(|(_, val)| val)).finish()
564 }
565}
566
567/// An iterator over a sub-range of entries in a `BTreeMap`.
568///
569/// This `struct` is created by the [`range`] method on [`BTreeMap`]. See its
570/// documentation for more.
571///
572/// [`range`]: BTreeMap::range
573#[must_use = "iterators are lazy and do nothing unless consumed"]
574#[stable(feature = "btree_range", since = "1.17.0")]
575pub struct Range<'a, K: 'a, V: 'a> {
576 inner: LeafRange<marker::Immut<'a>, K, V>,
577}
578
579#[stable(feature = "collection_debug", since = "1.17.0")]
580impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Range<'_, K, V> {
581 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
582 f.debug_list().entries(self.clone()).finish()
583 }
584}
585
586/// A mutable iterator over a sub-range of entries in a `BTreeMap`.
587///
588/// This `struct` is created by the [`range_mut`] method on [`BTreeMap`]. See its
589/// documentation for more.
590///
591/// [`range_mut`]: BTreeMap::range_mut
592#[must_use = "iterators are lazy and do nothing unless consumed"]
593#[stable(feature = "btree_range", since = "1.17.0")]
594pub struct RangeMut<'a, K: 'a, V: 'a> {
595 inner: LeafRange<marker::ValMut<'a>, K, V>,
596
597 // Be invariant in `K` and `V`
598 _marker: PhantomData<&'a mut (K, V)>,
599}
600
601#[stable(feature = "collection_debug", since = "1.17.0")]
602impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for RangeMut<'_, K, V> {
603 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
604 let range = Range { inner: self.inner.reborrow() };
605 f.debug_list().entries(range).finish()
606 }
607}
608
609impl<K, V> BTreeMap<K, V> {
610 /// Makes a new, empty `BTreeMap`.
611 ///
612 /// Does not allocate anything on its own.
613 ///
614 /// # Examples
615 ///
616 /// ```
617 /// use std::collections::BTreeMap;
618 ///
619 /// let mut map = BTreeMap::new();
620 ///
621 /// // entries can now be inserted into the empty map
622 /// map.insert(1, "a");
623 /// ```
624 #[stable(feature = "rust1", since = "1.0.0")]
625 #[rustc_const_stable(feature = "const_btree_new", since = "1.66.0")]
626 #[inline]
627 #[must_use]
628 pub const fn new() -> BTreeMap<K, V> {
629 BTreeMap { root: None, length: 0, alloc: ManuallyDrop::new(Global), _marker: PhantomData }
630 }
631}
632
633impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> {
634 /// Clears the map, removing all elements.
635 ///
636 /// # Examples
637 ///
638 /// ```
639 /// use std::collections::BTreeMap;
640 ///
641 /// let mut a = BTreeMap::new();
642 /// a.insert(1, "a");
643 /// a.clear();
644 /// assert!(a.is_empty());
645 /// ```
646 #[stable(feature = "rust1", since = "1.0.0")]
647 pub fn clear(&mut self) {
648 // avoid moving the allocator
649 drop(BTreeMap {
650 root: mem::replace(&mut self.root, None),
651 length: mem::replace(&mut self.length, 0),
652 alloc: self.alloc.clone(),
653 _marker: PhantomData,
654 });
655 }
656
657 /// Makes a new empty BTreeMap with a reasonable choice for B.
658 ///
659 /// # Examples
660 ///
661 /// ```
662 /// # #![feature(allocator_api)]
663 /// # #![feature(btreemap_alloc)]
664 /// use std::collections::BTreeMap;
665 /// use std::alloc::Global;
666 ///
667 /// let mut map = BTreeMap::new_in(Global);
668 ///
669 /// // entries can now be inserted into the empty map
670 /// map.insert(1, "a");
671 /// ```
672 #[unstable(feature = "btreemap_alloc", issue = "32838")]
673 pub const fn new_in(alloc: A) -> BTreeMap<K, V, A> {
674 BTreeMap { root: None, length: 0, alloc: ManuallyDrop::new(alloc), _marker: PhantomData }
675 }
676}
677
678impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> {
679 /// Returns a reference to the value corresponding to the key.
680 ///
681 /// The key may be any borrowed form of the map's key type, but the ordering
682 /// on the borrowed form *must* match the ordering on the key type.
683 ///
684 /// # Examples
685 ///
686 /// ```
687 /// use std::collections::BTreeMap;
688 ///
689 /// let mut map = BTreeMap::new();
690 /// map.insert(1, "a");
691 /// assert_eq!(map.get(&1), Some(&"a"));
692 /// assert_eq!(map.get(&2), None);
693 /// ```
694 #[stable(feature = "rust1", since = "1.0.0")]
695 pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V>
696 where
697 K: Borrow<Q> + Ord,
698 Q: Ord,
699 {
700 let root_node = self.root.as_ref()?.reborrow();
701 match root_node.search_tree(key) {
702 Found(handle) => Some(handle.into_kv().1),
703 GoDown(_) => None,
704 }
705 }
706
707 /// Returns the key-value pair corresponding to the supplied key. This is
708 /// potentially useful:
709 /// - for key types where non-identical keys can be considered equal;
710 /// - for getting the `&K` stored key value from a borrowed `&Q` lookup key; or
711 /// - for getting a reference to a key with the same lifetime as the collection.
712 ///
713 /// The supplied key may be any borrowed form of the map's key type, but the ordering
714 /// on the borrowed form *must* match the ordering on the key type.
715 ///
716 /// # Examples
717 ///
718 /// ```
719 /// use std::cmp::Ordering;
720 /// use std::collections::BTreeMap;
721 ///
722 /// #[derive(Clone, Copy, Debug)]
723 /// struct S {
724 /// id: u32,
725 /// # #[allow(unused)] // prevents a "field `name` is never read" error
726 /// name: &'static str, // ignored by equality and ordering operations
727 /// }
728 ///
729 /// impl PartialEq for S {
730 /// fn eq(&self, other: &S) -> bool {
731 /// self.id == other.id
732 /// }
733 /// }
734 ///
735 /// impl Eq for S {}
736 ///
737 /// impl PartialOrd for S {
738 /// fn partial_cmp(&self, other: &S) -> Option<Ordering> {
739 /// self.id.partial_cmp(&other.id)
740 /// }
741 /// }
742 ///
743 /// impl Ord for S {
744 /// fn cmp(&self, other: &S) -> Ordering {
745 /// self.id.cmp(&other.id)
746 /// }
747 /// }
748 ///
749 /// let j_a = S { id: 1, name: "Jessica" };
750 /// let j_b = S { id: 1, name: "Jess" };
751 /// let p = S { id: 2, name: "Paul" };
752 /// assert_eq!(j_a, j_b);
753 ///
754 /// let mut map = BTreeMap::new();
755 /// map.insert(j_a, "Paris");
756 /// assert_eq!(map.get_key_value(&j_a), Some((&j_a, &"Paris")));
757 /// assert_eq!(map.get_key_value(&j_b), Some((&j_a, &"Paris"))); // the notable case
758 /// assert_eq!(map.get_key_value(&p), None);
759 /// ```
760 #[stable(feature = "map_get_key_value", since = "1.40.0")]
761 pub fn get_key_value<Q: ?Sized>(&self, k: &Q) -> Option<(&K, &V)>
762 where
763 K: Borrow<Q> + Ord,
764 Q: Ord,
765 {
766 let root_node = self.root.as_ref()?.reborrow();
767 match root_node.search_tree(k) {
768 Found(handle) => Some(handle.into_kv()),
769 GoDown(_) => None,
770 }
771 }
772
773 /// Returns the first key-value pair in the map.
774 /// The key in this pair is the minimum key in the map.
775 ///
776 /// # Examples
777 ///
778 /// ```
779 /// use std::collections::BTreeMap;
780 ///
781 /// let mut map = BTreeMap::new();
782 /// assert_eq!(map.first_key_value(), None);
783 /// map.insert(1, "b");
784 /// map.insert(2, "a");
785 /// assert_eq!(map.first_key_value(), Some((&1, &"b")));
786 /// ```
787 #[stable(feature = "map_first_last", since = "1.66.0")]
788 pub fn first_key_value(&self) -> Option<(&K, &V)>
789 where
790 K: Ord,
791 {
792 let root_node = self.root.as_ref()?.reborrow();
793 root_node.first_leaf_edge().right_kv().ok().map(Handle::into_kv)
794 }
795
796 /// Returns the first entry in the map for in-place manipulation.
797 /// The key of this entry is the minimum key in the map.
798 ///
799 /// # Examples
800 ///
801 /// ```
802 /// use std::collections::BTreeMap;
803 ///
804 /// let mut map = BTreeMap::new();
805 /// map.insert(1, "a");
806 /// map.insert(2, "b");
807 /// if let Some(mut entry) = map.first_entry() {
808 /// if *entry.key() > 0 {
809 /// entry.insert("first");
810 /// }
811 /// }
812 /// assert_eq!(*map.get(&1).unwrap(), "first");
813 /// assert_eq!(*map.get(&2).unwrap(), "b");
814 /// ```
815 #[stable(feature = "map_first_last", since = "1.66.0")]
816 pub fn first_entry(&mut self) -> Option<OccupiedEntry<'_, K, V, A>>
817 where
818 K: Ord,
819 {
820 let (map, dormant_map) = DormantMutRef::new(self);
821 let root_node = map.root.as_mut()?.borrow_mut();
822 let kv = root_node.first_leaf_edge().right_kv().ok()?;
823 Some(OccupiedEntry {
824 handle: kv.forget_node_type(),
825 dormant_map,
826 alloc: (*map.alloc).clone(),
827 _marker: PhantomData,
828 })
829 }
830
831 /// Removes and returns the first element in the map.
832 /// The key of this element is the minimum key that was in the map.
833 ///
834 /// # Examples
835 ///
836 /// Draining elements in ascending order, while keeping a usable map each iteration.
837 ///
838 /// ```
839 /// use std::collections::BTreeMap;
840 ///
841 /// let mut map = BTreeMap::new();
842 /// map.insert(1, "a");
843 /// map.insert(2, "b");
844 /// while let Some((key, _val)) = map.pop_first() {
845 /// assert!(map.iter().all(|(k, _v)| *k > key));
846 /// }
847 /// assert!(map.is_empty());
848 /// ```
849 #[stable(feature = "map_first_last", since = "1.66.0")]
850 pub fn pop_first(&mut self) -> Option<(K, V)>
851 where
852 K: Ord,
853 {
854 self.first_entry().map(|entry| entry.remove_entry())
855 }
856
857 /// Returns the last key-value pair in the map.
858 /// The key in this pair is the maximum key in the map.
859 ///
860 /// # Examples
861 ///
862 /// ```
863 /// use std::collections::BTreeMap;
864 ///
865 /// let mut map = BTreeMap::new();
866 /// map.insert(1, "b");
867 /// map.insert(2, "a");
868 /// assert_eq!(map.last_key_value(), Some((&2, &"a")));
869 /// ```
870 #[stable(feature = "map_first_last", since = "1.66.0")]
871 pub fn last_key_value(&self) -> Option<(&K, &V)>
872 where
873 K: Ord,
874 {
875 let root_node = self.root.as_ref()?.reborrow();
876 root_node.last_leaf_edge().left_kv().ok().map(Handle::into_kv)
877 }
878
879 /// Returns the last entry in the map for in-place manipulation.
880 /// The key of this entry is the maximum key in the map.
881 ///
882 /// # Examples
883 ///
884 /// ```
885 /// use std::collections::BTreeMap;
886 ///
887 /// let mut map = BTreeMap::new();
888 /// map.insert(1, "a");
889 /// map.insert(2, "b");
890 /// if let Some(mut entry) = map.last_entry() {
891 /// if *entry.key() > 0 {
892 /// entry.insert("last");
893 /// }
894 /// }
895 /// assert_eq!(*map.get(&1).unwrap(), "a");
896 /// assert_eq!(*map.get(&2).unwrap(), "last");
897 /// ```
898 #[stable(feature = "map_first_last", since = "1.66.0")]
899 pub fn last_entry(&mut self) -> Option<OccupiedEntry<'_, K, V, A>>
900 where
901 K: Ord,
902 {
903 let (map, dormant_map) = DormantMutRef::new(self);
904 let root_node = map.root.as_mut()?.borrow_mut();
905 let kv = root_node.last_leaf_edge().left_kv().ok()?;
906 Some(OccupiedEntry {
907 handle: kv.forget_node_type(),
908 dormant_map,
909 alloc: (*map.alloc).clone(),
910 _marker: PhantomData,
911 })
912 }
913
914 /// Removes and returns the last element in the map.
915 /// The key of this element is the maximum key that was in the map.
916 ///
917 /// # Examples
918 ///
919 /// Draining elements in descending order, while keeping a usable map each iteration.
920 ///
921 /// ```
922 /// use std::collections::BTreeMap;
923 ///
924 /// let mut map = BTreeMap::new();
925 /// map.insert(1, "a");
926 /// map.insert(2, "b");
927 /// while let Some((key, _val)) = map.pop_last() {
928 /// assert!(map.iter().all(|(k, _v)| *k < key));
929 /// }
930 /// assert!(map.is_empty());
931 /// ```
932 #[stable(feature = "map_first_last", since = "1.66.0")]
933 pub fn pop_last(&mut self) -> Option<(K, V)>
934 where
935 K: Ord,
936 {
937 self.last_entry().map(|entry| entry.remove_entry())
938 }
939
940 /// Returns `true` if the map contains a value for the specified key.
941 ///
942 /// The key may be any borrowed form of the map's key type, but the ordering
943 /// on the borrowed form *must* match the ordering on the key type.
944 ///
945 /// # Examples
946 ///
947 /// ```
948 /// use std::collections::BTreeMap;
949 ///
950 /// let mut map = BTreeMap::new();
951 /// map.insert(1, "a");
952 /// assert_eq!(map.contains_key(&1), true);
953 /// assert_eq!(map.contains_key(&2), false);
954 /// ```
955 #[stable(feature = "rust1", since = "1.0.0")]
956 #[cfg_attr(not(test), rustc_diagnostic_item = "btreemap_contains_key")]
957 pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool
958 where
959 K: Borrow<Q> + Ord,
960 Q: Ord,
961 {
962 self.get(key).is_some()
963 }
964
965 /// Returns a mutable reference to the value corresponding to the key.
966 ///
967 /// The key may be any borrowed form of the map's key type, but the ordering
968 /// on the borrowed form *must* match the ordering on the key type.
969 ///
970 /// # Examples
971 ///
972 /// ```
973 /// use std::collections::BTreeMap;
974 ///
975 /// let mut map = BTreeMap::new();
976 /// map.insert(1, "a");
977 /// if let Some(x) = map.get_mut(&1) {
978 /// *x = "b";
979 /// }
980 /// assert_eq!(map[&1], "b");
981 /// ```
982 // See `get` for implementation notes, this is basically a copy-paste with mut's added
983 #[stable(feature = "rust1", since = "1.0.0")]
984 pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>
985 where
986 K: Borrow<Q> + Ord,
987 Q: Ord,
988 {
989 let root_node = self.root.as_mut()?.borrow_mut();
990 match root_node.search_tree(key) {
991 Found(handle) => Some(handle.into_val_mut()),
992 GoDown(_) => None,
993 }
994 }
995
996 /// Inserts a key-value pair into the map.
997 ///
998 /// If the map did not have this key present, `None` is returned.
999 ///
1000 /// If the map did have this key present, the value is updated, and the old
1001 /// value is returned. The key is not updated, though; this matters for
1002 /// types that can be `==` without being identical. See the [module-level
1003 /// documentation] for more.
1004 ///
1005 /// [module-level documentation]: index.html#insert-and-complex-keys
1006 ///
1007 /// # Examples
1008 ///
1009 /// ```
1010 /// use std::collections::BTreeMap;
1011 ///
1012 /// let mut map = BTreeMap::new();
1013 /// assert_eq!(map.insert(37, "a"), None);
1014 /// assert_eq!(map.is_empty(), false);
1015 ///
1016 /// map.insert(37, "b");
1017 /// assert_eq!(map.insert(37, "c"), Some("b"));
1018 /// assert_eq!(map[&37], "c");
1019 /// ```
1020 #[stable(feature = "rust1", since = "1.0.0")]
1021 #[rustc_confusables("push", "put", "set")]
1022 #[cfg_attr(not(test), rustc_diagnostic_item = "btreemap_insert")]
1023 pub fn insert(&mut self, key: K, value: V) -> Option<V>
1024 where
1025 K: Ord,
1026 {
1027 match self.entry(key) {
1028 Occupied(mut entry) => Some(entry.insert(value)),
1029 Vacant(entry) => {
1030 entry.insert(value);
1031 None
1032 }
1033 }
1034 }
1035
1036 /// Tries to insert a key-value pair into the map, and returns
1037 /// a mutable reference to the value in the entry.
1038 ///
1039 /// If the map already had this key present, nothing is updated, and
1040 /// an error containing the occupied entry and the value is returned.
1041 ///
1042 /// # Examples
1043 ///
1044 /// ```
1045 /// #![feature(map_try_insert)]
1046 ///
1047 /// use std::collections::BTreeMap;
1048 ///
1049 /// let mut map = BTreeMap::new();
1050 /// assert_eq!(map.try_insert(37, "a").unwrap(), &"a");
1051 ///
1052 /// let err = map.try_insert(37, "b").unwrap_err();
1053 /// assert_eq!(err.entry.key(), &37);
1054 /// assert_eq!(err.entry.get(), &"a");
1055 /// assert_eq!(err.value, "b");
1056 /// ```
1057 #[unstable(feature = "map_try_insert", issue = "82766")]
1058 pub fn try_insert(&mut self, key: K, value: V) -> Result<&mut V, OccupiedError<'_, K, V, A>>
1059 where
1060 K: Ord,
1061 {
1062 match self.entry(key) {
1063 Occupied(entry) => Err(OccupiedError { entry, value }),
1064 Vacant(entry) => Ok(entry.insert(value)),
1065 }
1066 }
1067
1068 /// Removes a key from the map, returning the value at the key if the key
1069 /// was previously in the map.
1070 ///
1071 /// The key may be any borrowed form of the map's key type, but the ordering
1072 /// on the borrowed form *must* match the ordering on the key type.
1073 ///
1074 /// # Examples
1075 ///
1076 /// ```
1077 /// use std::collections::BTreeMap;
1078 ///
1079 /// let mut map = BTreeMap::new();
1080 /// map.insert(1, "a");
1081 /// assert_eq!(map.remove(&1), Some("a"));
1082 /// assert_eq!(map.remove(&1), None);
1083 /// ```
1084 #[stable(feature = "rust1", since = "1.0.0")]
1085 #[rustc_confusables("delete", "take")]
1086 pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V>
1087 where
1088 K: Borrow<Q> + Ord,
1089 Q: Ord,
1090 {
1091 self.remove_entry(key).map(|(_, v)| v)
1092 }
1093
1094 /// Removes a key from the map, returning the stored key and value if the key
1095 /// was previously in the map.
1096 ///
1097 /// The key may be any borrowed form of the map's key type, but the ordering
1098 /// on the borrowed form *must* match the ordering on the key type.
1099 ///
1100 /// # Examples
1101 ///
1102 /// ```
1103 /// use std::collections::BTreeMap;
1104 ///
1105 /// let mut map = BTreeMap::new();
1106 /// map.insert(1, "a");
1107 /// assert_eq!(map.remove_entry(&1), Some((1, "a")));
1108 /// assert_eq!(map.remove_entry(&1), None);
1109 /// ```
1110 #[stable(feature = "btreemap_remove_entry", since = "1.45.0")]
1111 pub fn remove_entry<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)>
1112 where
1113 K: Borrow<Q> + Ord,
1114 Q: Ord,
1115 {
1116 let (map, dormant_map) = DormantMutRef::new(self);
1117 let root_node = map.root.as_mut()?.borrow_mut();
1118 match root_node.search_tree(key) {
1119 Found(handle) => Some(
1120 OccupiedEntry {
1121 handle,
1122 dormant_map,
1123 alloc: (*map.alloc).clone(),
1124 _marker: PhantomData,
1125 }
1126 .remove_entry(),
1127 ),
1128 GoDown(_) => None,
1129 }
1130 }
1131
1132 /// Retains only the elements specified by the predicate.
1133 ///
1134 /// In other words, remove all pairs `(k, v)` for which `f(&k, &mut v)` returns `false`.
1135 /// The elements are visited in ascending key order.
1136 ///
1137 /// # Examples
1138 ///
1139 /// ```
1140 /// use std::collections::BTreeMap;
1141 ///
1142 /// let mut map: BTreeMap<i32, i32> = (0..8).map(|x| (x, x*10)).collect();
1143 /// // Keep only the elements with even-numbered keys.
1144 /// map.retain(|&k, _| k % 2 == 0);
1145 /// assert!(map.into_iter().eq(vec![(0, 0), (2, 20), (4, 40), (6, 60)]));
1146 /// ```
1147 #[inline]
1148 #[stable(feature = "btree_retain", since = "1.53.0")]
1149 pub fn retain<F>(&mut self, mut f: F)
1150 where
1151 K: Ord,
1152 F: FnMut(&K, &mut V) -> bool,
1153 {
1154 self.extract_if(.., |k, v| !f(k, v)).for_each(drop);
1155 }
1156
1157 /// Moves all elements from `other` into `self`, leaving `other` empty.
1158 ///
1159 /// If a key from `other` is already present in `self`, the respective
1160 /// value from `self` will be overwritten with the respective value from `other`.
1161 ///
1162 /// # Examples
1163 ///
1164 /// ```
1165 /// use std::collections::BTreeMap;
1166 ///
1167 /// let mut a = BTreeMap::new();
1168 /// a.insert(1, "a");
1169 /// a.insert(2, "b");
1170 /// a.insert(3, "c"); // Note: Key (3) also present in b.
1171 ///
1172 /// let mut b = BTreeMap::new();
1173 /// b.insert(3, "d"); // Note: Key (3) also present in a.
1174 /// b.insert(4, "e");
1175 /// b.insert(5, "f");
1176 ///
1177 /// a.append(&mut b);
1178 ///
1179 /// assert_eq!(a.len(), 5);
1180 /// assert_eq!(b.len(), 0);
1181 ///
1182 /// assert_eq!(a[&1], "a");
1183 /// assert_eq!(a[&2], "b");
1184 /// assert_eq!(a[&3], "d"); // Note: "c" has been overwritten.
1185 /// assert_eq!(a[&4], "e");
1186 /// assert_eq!(a[&5], "f");
1187 /// ```
1188 #[stable(feature = "btree_append", since = "1.11.0")]
1189 pub fn append(&mut self, other: &mut Self)
1190 where
1191 K: Ord,
1192 A: Clone,
1193 {
1194 // Do we have to append anything at all?
1195 if other.is_empty() {
1196 return;
1197 }
1198
1199 // We can just swap `self` and `other` if `self` is empty.
1200 if self.is_empty() {
1201 mem::swap(self, other);
1202 return;
1203 }
1204
1205 let self_iter = mem::replace(self, Self::new_in((*self.alloc).clone())).into_iter();
1206 let other_iter = mem::replace(other, Self::new_in((*self.alloc).clone())).into_iter();
1207 let root = self.root.get_or_insert_with(|| Root::new((*self.alloc).clone()));
1208 root.append_from_sorted_iters(
1209 self_iter,
1210 other_iter,
1211 &mut self.length,
1212 (*self.alloc).clone(),
1213 )
1214 }
1215
1216 /// Constructs a double-ended iterator over a sub-range of elements in the map.
1217 /// The simplest way is to use the range syntax `min..max`, thus `range(min..max)` will
1218 /// yield elements from min (inclusive) to max (exclusive).
1219 /// The range may also be entered as `(Bound<T>, Bound<T>)`, so for example
1220 /// `range((Excluded(4), Included(10)))` will yield a left-exclusive, right-inclusive
1221 /// range from 4 to 10.
1222 ///
1223 /// # Panics
1224 ///
1225 /// Panics if range `start > end`.
1226 /// Panics if range `start == end` and both bounds are `Excluded`.
1227 ///
1228 /// # Examples
1229 ///
1230 /// ```
1231 /// use std::collections::BTreeMap;
1232 /// use std::ops::Bound::Included;
1233 ///
1234 /// let mut map = BTreeMap::new();
1235 /// map.insert(3, "a");
1236 /// map.insert(5, "b");
1237 /// map.insert(8, "c");
1238 /// for (&key, &value) in map.range((Included(&4), Included(&8))) {
1239 /// println!("{key}: {value}");
1240 /// }
1241 /// assert_eq!(Some((&5, &"b")), map.range(4..).next());
1242 /// ```
1243 #[stable(feature = "btree_range", since = "1.17.0")]
1244 pub fn range<T: ?Sized, R>(&self, range: R) -> Range<'_, K, V>
1245 where
1246 T: Ord,
1247 K: Borrow<T> + Ord,
1248 R: RangeBounds<T>,
1249 {
1250 if let Some(root) = &self.root {
1251 Range { inner: root.reborrow().range_search(range) }
1252 } else {
1253 Range { inner: LeafRange::none() }
1254 }
1255 }
1256
1257 /// Constructs a mutable double-ended iterator over a sub-range of elements in the map.
1258 /// The simplest way is to use the range syntax `min..max`, thus `range(min..max)` will
1259 /// yield elements from min (inclusive) to max (exclusive).
1260 /// The range may also be entered as `(Bound<T>, Bound<T>)`, so for example
1261 /// `range((Excluded(4), Included(10)))` will yield a left-exclusive, right-inclusive
1262 /// range from 4 to 10.
1263 ///
1264 /// # Panics
1265 ///
1266 /// Panics if range `start > end`.
1267 /// Panics if range `start == end` and both bounds are `Excluded`.
1268 ///
1269 /// # Examples
1270 ///
1271 /// ```
1272 /// use std::collections::BTreeMap;
1273 ///
1274 /// let mut map: BTreeMap<&str, i32> =
1275 /// [("Alice", 0), ("Bob", 0), ("Carol", 0), ("Cheryl", 0)].into();
1276 /// for (_, balance) in map.range_mut("B".."Cheryl") {
1277 /// *balance += 100;
1278 /// }
1279 /// for (name, balance) in &map {
1280 /// println!("{name} => {balance}");
1281 /// }
1282 /// ```
1283 #[stable(feature = "btree_range", since = "1.17.0")]
1284 pub fn range_mut<T: ?Sized, R>(&mut self, range: R) -> RangeMut<'_, K, V>
1285 where
1286 T: Ord,
1287 K: Borrow<T> + Ord,
1288 R: RangeBounds<T>,
1289 {
1290 if let Some(root) = &mut self.root {
1291 RangeMut { inner: root.borrow_valmut().range_search(range), _marker: PhantomData }
1292 } else {
1293 RangeMut { inner: LeafRange::none(), _marker: PhantomData }
1294 }
1295 }
1296
1297 /// Gets the given key's corresponding entry in the map for in-place manipulation.
1298 ///
1299 /// # Examples
1300 ///
1301 /// ```
1302 /// use std::collections::BTreeMap;
1303 ///
1304 /// let mut count: BTreeMap<&str, usize> = BTreeMap::new();
1305 ///
1306 /// // count the number of occurrences of letters in the vec
1307 /// for x in ["a", "b", "a", "c", "a", "b"] {
1308 /// count.entry(x).and_modify(|curr| *curr += 1).or_insert(1);
1309 /// }
1310 ///
1311 /// assert_eq!(count["a"], 3);
1312 /// assert_eq!(count["b"], 2);
1313 /// assert_eq!(count["c"], 1);
1314 /// ```
1315 #[stable(feature = "rust1", since = "1.0.0")]
1316 pub fn entry(&mut self, key: K) -> Entry<'_, K, V, A>
1317 where
1318 K: Ord,
1319 {
1320 let (map, dormant_map) = DormantMutRef::new(self);
1321 match map.root {
1322 None => Vacant(VacantEntry {
1323 key,
1324 handle: None,
1325 dormant_map,
1326 alloc: (*map.alloc).clone(),
1327 _marker: PhantomData,
1328 }),
1329 Some(ref mut root) => match root.borrow_mut().search_tree(&key) {
1330 Found(handle) => Occupied(OccupiedEntry {
1331 handle,
1332 dormant_map,
1333 alloc: (*map.alloc).clone(),
1334 _marker: PhantomData,
1335 }),
1336 GoDown(handle) => Vacant(VacantEntry {
1337 key,
1338 handle: Some(handle),
1339 dormant_map,
1340 alloc: (*map.alloc).clone(),
1341 _marker: PhantomData,
1342 }),
1343 },
1344 }
1345 }
1346
1347 /// Splits the collection into two at the given key. Returns everything after the given key,
1348 /// including the key.
1349 ///
1350 /// # Examples
1351 ///
1352 /// ```
1353 /// use std::collections::BTreeMap;
1354 ///
1355 /// let mut a = BTreeMap::new();
1356 /// a.insert(1, "a");
1357 /// a.insert(2, "b");
1358 /// a.insert(3, "c");
1359 /// a.insert(17, "d");
1360 /// a.insert(41, "e");
1361 ///
1362 /// let b = a.split_off(&3);
1363 ///
1364 /// assert_eq!(a.len(), 2);
1365 /// assert_eq!(b.len(), 3);
1366 ///
1367 /// assert_eq!(a[&1], "a");
1368 /// assert_eq!(a[&2], "b");
1369 ///
1370 /// assert_eq!(b[&3], "c");
1371 /// assert_eq!(b[&17], "d");
1372 /// assert_eq!(b[&41], "e");
1373 /// ```
1374 #[stable(feature = "btree_split_off", since = "1.11.0")]
1375 pub fn split_off<Q: ?Sized + Ord>(&mut self, key: &Q) -> Self
1376 where
1377 K: Borrow<Q> + Ord,
1378 A: Clone,
1379 {
1380 if self.is_empty() {
1381 return Self::new_in((*self.alloc).clone());
1382 }
1383
1384 let total_num = self.len();
1385 let left_root = self.root.as_mut().unwrap(); // unwrap succeeds because not empty
1386
1387 let right_root = left_root.split_off(key, (*self.alloc).clone());
1388
1389 let (new_left_len, right_len) = Root::calc_split_length(total_num, &left_root, &right_root);
1390 self.length = new_left_len;
1391
1392 BTreeMap {
1393 root: Some(right_root),
1394 length: right_len,
1395 alloc: self.alloc.clone(),
1396 _marker: PhantomData,
1397 }
1398 }
1399
1400 /// Creates an iterator that visits elements (key-value pairs) in the specified range in
1401 /// ascending key order and uses a closure to determine if an element
1402 /// should be removed.
1403 ///
1404 /// If the closure returns `true`, the element is removed from the map and
1405 /// yielded. If the closure returns `false`, or panics, the element remains
1406 /// in the map and will not be yielded.
1407 ///
1408 /// The iterator also lets you mutate the value of each element in the
1409 /// closure, regardless of whether you choose to keep or remove it.
1410 ///
1411 /// If the returned `ExtractIf` is not exhausted, e.g. because it is dropped without iterating
1412 /// or the iteration short-circuits, then the remaining elements will be retained.
1413 /// Use [`retain`] with a negated predicate if you do not need the returned iterator.
1414 ///
1415 /// [`retain`]: BTreeMap::retain
1416 ///
1417 /// # Examples
1418 ///
1419 /// ```
1420 /// #![feature(btree_extract_if)]
1421 /// use std::collections::BTreeMap;
1422 ///
1423 /// // Splitting a map into even and odd keys, reusing the original map:
1424 /// let mut map: BTreeMap<i32, i32> = (0..8).map(|x| (x, x)).collect();
1425 /// let evens: BTreeMap<_, _> = map.extract_if(.., |k, _v| k % 2 == 0).collect();
1426 /// let odds = map;
1427 /// assert_eq!(evens.keys().copied().collect::<Vec<_>>(), [0, 2, 4, 6]);
1428 /// assert_eq!(odds.keys().copied().collect::<Vec<_>>(), [1, 3, 5, 7]);
1429 ///
1430 /// // Splitting a map into low and high halves, reusing the original map:
1431 /// let mut map: BTreeMap<i32, i32> = (0..8).map(|x| (x, x)).collect();
1432 /// let low: BTreeMap<_, _> = map.extract_if(0..4, |_k, _v| true).collect();
1433 /// let high = map;
1434 /// assert_eq!(low.keys().copied().collect::<Vec<_>>(), [0, 1, 2, 3]);
1435 /// assert_eq!(high.keys().copied().collect::<Vec<_>>(), [4, 5, 6, 7]);
1436 /// ```
1437 #[unstable(feature = "btree_extract_if", issue = "70530")]
1438 pub fn extract_if<F, R>(&mut self, range: R, pred: F) -> ExtractIf<'_, K, V, R, F, A>
1439 where
1440 K: Ord,
1441 R: RangeBounds<K>,
1442 F: FnMut(&K, &mut V) -> bool,
1443 {
1444 let (inner, alloc) = self.extract_if_inner(range);
1445 ExtractIf { pred, inner, alloc }
1446 }
1447
1448 pub(super) fn extract_if_inner<R>(&mut self, range: R) -> (ExtractIfInner<'_, K, V, R>, A)
1449 where
1450 K: Ord,
1451 R: RangeBounds<K>,
1452 {
1453 if let Some(root) = self.root.as_mut() {
1454 let (root, dormant_root) = DormantMutRef::new(root);
1455 let first = root.borrow_mut().lower_bound(SearchBound::from_range(range.start_bound()));
1456 (
1457 ExtractIfInner {
1458 length: &mut self.length,
1459 dormant_root: Some(dormant_root),
1460 cur_leaf_edge: Some(first),
1461 range,
1462 },
1463 (*self.alloc).clone(),
1464 )
1465 } else {
1466 (
1467 ExtractIfInner {
1468 length: &mut self.length,
1469 dormant_root: None,
1470 cur_leaf_edge: None,
1471 range,
1472 },
1473 (*self.alloc).clone(),
1474 )
1475 }
1476 }
1477
1478 /// Creates a consuming iterator visiting all the keys, in sorted order.
1479 /// The map cannot be used after calling this.
1480 /// The iterator element type is `K`.
1481 ///
1482 /// # Examples
1483 ///
1484 /// ```
1485 /// use std::collections::BTreeMap;
1486 ///
1487 /// let mut a = BTreeMap::new();
1488 /// a.insert(2, "b");
1489 /// a.insert(1, "a");
1490 ///
1491 /// let keys: Vec<i32> = a.into_keys().collect();
1492 /// assert_eq!(keys, [1, 2]);
1493 /// ```
1494 #[inline]
1495 #[stable(feature = "map_into_keys_values", since = "1.54.0")]
1496 pub fn into_keys(self) -> IntoKeys<K, V, A> {
1497 IntoKeys { inner: self.into_iter() }
1498 }
1499
1500 /// Creates a consuming iterator visiting all the values, in order by key.
1501 /// The map cannot be used after calling this.
1502 /// The iterator element type is `V`.
1503 ///
1504 /// # Examples
1505 ///
1506 /// ```
1507 /// use std::collections::BTreeMap;
1508 ///
1509 /// let mut a = BTreeMap::new();
1510 /// a.insert(1, "hello");
1511 /// a.insert(2, "goodbye");
1512 ///
1513 /// let values: Vec<&str> = a.into_values().collect();
1514 /// assert_eq!(values, ["hello", "goodbye"]);
1515 /// ```
1516 #[inline]
1517 #[stable(feature = "map_into_keys_values", since = "1.54.0")]
1518 pub fn into_values(self) -> IntoValues<K, V, A> {
1519 IntoValues { inner: self.into_iter() }
1520 }
1521
1522 /// Makes a `BTreeMap` from a sorted iterator.
1523 pub(crate) fn bulk_build_from_sorted_iter<I>(iter: I, alloc: A) -> Self
1524 where
1525 K: Ord,
1526 I: IntoIterator<Item = (K, V)>,
1527 {
1528 let mut root = Root::new(alloc.clone());
1529 let mut length = 0;
1530 root.bulk_push(DedupSortedIter::new(iter.into_iter()), &mut length, alloc.clone());
1531 BTreeMap { root: Some(root), length, alloc: ManuallyDrop::new(alloc), _marker: PhantomData }
1532 }
1533}
1534
1535#[stable(feature = "rust1", since = "1.0.0")]
1536impl<'a, K, V, A: Allocator + Clone> IntoIterator for &'a BTreeMap<K, V, A> {
1537 type Item = (&'a K, &'a V);
1538 type IntoIter = Iter<'a, K, V>;
1539
1540 fn into_iter(self) -> Iter<'a, K, V> {
1541 self.iter()
1542 }
1543}
1544
1545#[stable(feature = "rust1", since = "1.0.0")]
1546impl<'a, K: 'a, V: 'a> Iterator for Iter<'a, K, V> {
1547 type Item = (&'a K, &'a V);
1548
1549 fn next(&mut self) -> Option<(&'a K, &'a V)> {
1550 if self.length == 0 {
1551 None
1552 } else {
1553 self.length -= 1;
1554 Some(unsafe { self.range.next_unchecked() })
1555 }
1556 }
1557
1558 fn size_hint(&self) -> (usize, Option<usize>) {
1559 (self.length, Some(self.length))
1560 }
1561
1562 fn last(mut self) -> Option<(&'a K, &'a V)> {
1563 self.next_back()
1564 }
1565
1566 fn min(mut self) -> Option<(&'a K, &'a V)>
1567 where
1568 (&'a K, &'a V): Ord,
1569 {
1570 self.next()
1571 }
1572
1573 fn max(mut self) -> Option<(&'a K, &'a V)>
1574 where
1575 (&'a K, &'a V): Ord,
1576 {
1577 self.next_back()
1578 }
1579}
1580
1581#[stable(feature = "fused", since = "1.26.0")]
1582impl<K, V> FusedIterator for Iter<'_, K, V> {}
1583
1584#[stable(feature = "rust1", since = "1.0.0")]
1585impl<'a, K: 'a, V: 'a> DoubleEndedIterator for Iter<'a, K, V> {
1586 fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
1587 if self.length == 0 {
1588 None
1589 } else {
1590 self.length -= 1;
1591 Some(unsafe { self.range.next_back_unchecked() })
1592 }
1593 }
1594}
1595
1596#[stable(feature = "rust1", since = "1.0.0")]
1597impl<K, V> ExactSizeIterator for Iter<'_, K, V> {
1598 fn len(&self) -> usize {
1599 self.length
1600 }
1601}
1602
1603#[stable(feature = "rust1", since = "1.0.0")]
1604impl<K, V> Clone for Iter<'_, K, V> {
1605 fn clone(&self) -> Self {
1606 Iter { range: self.range.clone(), length: self.length }
1607 }
1608}
1609
1610#[stable(feature = "rust1", since = "1.0.0")]
1611impl<'a, K, V, A: Allocator + Clone> IntoIterator for &'a mut BTreeMap<K, V, A> {
1612 type Item = (&'a K, &'a mut V);
1613 type IntoIter = IterMut<'a, K, V>;
1614
1615 fn into_iter(self) -> IterMut<'a, K, V> {
1616 self.iter_mut()
1617 }
1618}
1619
1620#[stable(feature = "rust1", since = "1.0.0")]
1621impl<'a, K, V> Iterator for IterMut<'a, K, V> {
1622 type Item = (&'a K, &'a mut V);
1623
1624 fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
1625 if self.length == 0 {
1626 None
1627 } else {
1628 self.length -= 1;
1629 Some(unsafe { self.range.next_unchecked() })
1630 }
1631 }
1632
1633 fn size_hint(&self) -> (usize, Option<usize>) {
1634 (self.length, Some(self.length))
1635 }
1636
1637 fn last(mut self) -> Option<(&'a K, &'a mut V)> {
1638 self.next_back()
1639 }
1640
1641 fn min(mut self) -> Option<(&'a K, &'a mut V)>
1642 where
1643 (&'a K, &'a mut V): Ord,
1644 {
1645 self.next()
1646 }
1647
1648 fn max(mut self) -> Option<(&'a K, &'a mut V)>
1649 where
1650 (&'a K, &'a mut V): Ord,
1651 {
1652 self.next_back()
1653 }
1654}
1655
1656#[stable(feature = "rust1", since = "1.0.0")]
1657impl<'a, K, V> DoubleEndedIterator for IterMut<'a, K, V> {
1658 fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
1659 if self.length == 0 {
1660 None
1661 } else {
1662 self.length -= 1;
1663 Some(unsafe { self.range.next_back_unchecked() })
1664 }
1665 }
1666}
1667
1668#[stable(feature = "rust1", since = "1.0.0")]
1669impl<K, V> ExactSizeIterator for IterMut<'_, K, V> {
1670 fn len(&self) -> usize {
1671 self.length
1672 }
1673}
1674
1675#[stable(feature = "fused", since = "1.26.0")]
1676impl<K, V> FusedIterator for IterMut<'_, K, V> {}
1677
1678impl<'a, K, V> IterMut<'a, K, V> {
1679 /// Returns an iterator of references over the remaining items.
1680 #[inline]
1681 pub(super) fn iter(&self) -> Iter<'_, K, V> {
1682 Iter { range: self.range.reborrow(), length: self.length }
1683 }
1684}
1685
1686#[stable(feature = "rust1", since = "1.0.0")]
1687impl<K, V, A: Allocator + Clone> IntoIterator for BTreeMap<K, V, A> {
1688 type Item = (K, V);
1689 type IntoIter = IntoIter<K, V, A>;
1690
1691 /// Gets an owning iterator over the entries of the map, sorted by key.
1692 fn into_iter(self) -> IntoIter<K, V, A> {
1693 let mut me = ManuallyDrop::new(self);
1694 if let Some(root) = me.root.take() {
1695 let full_range = root.into_dying().full_range();
1696
1697 IntoIter {
1698 range: full_range,
1699 length: me.length,
1700 alloc: unsafe { ManuallyDrop::take(&mut me.alloc) },
1701 }
1702 } else {
1703 IntoIter {
1704 range: LazyLeafRange::none(),
1705 length: 0,
1706 alloc: unsafe { ManuallyDrop::take(&mut me.alloc) },
1707 }
1708 }
1709 }
1710}
1711
1712#[stable(feature = "btree_drop", since = "1.7.0")]
1713impl<K, V, A: Allocator + Clone> Drop for IntoIter<K, V, A> {
1714 fn drop(&mut self) {
1715 struct DropGuard<'a, K, V, A: Allocator + Clone>(&'a mut IntoIter<K, V, A>);
1716
1717 impl<'a, K, V, A: Allocator + Clone> Drop for DropGuard<'a, K, V, A> {
1718 fn drop(&mut self) {
1719 // Continue the same loop we perform below. This only runs when unwinding, so we
1720 // don't have to care about panics this time (they'll abort).
1721 while let Some(kv) = self.0.dying_next() {
1722 // SAFETY: we consume the dying handle immediately.
1723 unsafe { kv.drop_key_val() };
1724 }
1725 }
1726 }
1727
1728 while let Some(kv) = self.dying_next() {
1729 let guard = DropGuard(self);
1730 // SAFETY: we don't touch the tree before consuming the dying handle.
1731 unsafe { kv.drop_key_val() };
1732 mem::forget(guard);
1733 }
1734 }
1735}
1736
1737impl<K, V, A: Allocator + Clone> IntoIter<K, V, A> {
1738 /// Core of a `next` method returning a dying KV handle,
1739 /// invalidated by further calls to this function and some others.
1740 fn dying_next(
1741 &mut self,
1742 ) -> Option<Handle<NodeRef<marker::Dying, K, V, marker::LeafOrInternal>, marker::KV>> {
1743 if self.length == 0 {
1744 self.range.deallocating_end(self.alloc.clone());
1745 None
1746 } else {
1747 self.length -= 1;
1748 Some(unsafe { self.range.deallocating_next_unchecked(self.alloc.clone()) })
1749 }
1750 }
1751
1752 /// Core of a `next_back` method returning a dying KV handle,
1753 /// invalidated by further calls to this function and some others.
1754 fn dying_next_back(
1755 &mut self,
1756 ) -> Option<Handle<NodeRef<marker::Dying, K, V, marker::LeafOrInternal>, marker::KV>> {
1757 if self.length == 0 {
1758 self.range.deallocating_end(self.alloc.clone());
1759 None
1760 } else {
1761 self.length -= 1;
1762 Some(unsafe { self.range.deallocating_next_back_unchecked(self.alloc.clone()) })
1763 }
1764 }
1765}
1766
1767#[stable(feature = "rust1", since = "1.0.0")]
1768impl<K, V, A: Allocator + Clone> Iterator for IntoIter<K, V, A> {
1769 type Item = (K, V);
1770
1771 fn next(&mut self) -> Option<(K, V)> {
1772 // SAFETY: we consume the dying handle immediately.
1773 self.dying_next().map(unsafe { |kv| kv.into_key_val() })
1774 }
1775
1776 fn size_hint(&self) -> (usize, Option<usize>) {
1777 (self.length, Some(self.length))
1778 }
1779}
1780
1781#[stable(feature = "rust1", since = "1.0.0")]
1782impl<K, V, A: Allocator + Clone> DoubleEndedIterator for IntoIter<K, V, A> {
1783 fn next_back(&mut self) -> Option<(K, V)> {
1784 // SAFETY: we consume the dying handle immediately.
1785 self.dying_next_back().map(unsafe { |kv| kv.into_key_val() })
1786 }
1787}
1788
1789#[stable(feature = "rust1", since = "1.0.0")]
1790impl<K, V, A: Allocator + Clone> ExactSizeIterator for IntoIter<K, V, A> {
1791 fn len(&self) -> usize {
1792 self.length
1793 }
1794}
1795
1796#[stable(feature = "fused", since = "1.26.0")]
1797impl<K, V, A: Allocator + Clone> FusedIterator for IntoIter<K, V, A> {}
1798
1799#[stable(feature = "rust1", since = "1.0.0")]
1800impl<'a, K, V> Iterator for Keys<'a, K, V> {
1801 type Item = &'a K;
1802
1803 fn next(&mut self) -> Option<&'a K> {
1804 self.inner.next().map(|(k, _)| k)
1805 }
1806
1807 fn size_hint(&self) -> (usize, Option<usize>) {
1808 self.inner.size_hint()
1809 }
1810
1811 fn last(mut self) -> Option<&'a K> {
1812 self.next_back()
1813 }
1814
1815 fn min(mut self) -> Option<&'a K>
1816 where
1817 &'a K: Ord,
1818 {
1819 self.next()
1820 }
1821
1822 fn max(mut self) -> Option<&'a K>
1823 where
1824 &'a K: Ord,
1825 {
1826 self.next_back()
1827 }
1828}
1829
1830#[stable(feature = "rust1", since = "1.0.0")]
1831impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> {
1832 fn next_back(&mut self) -> Option<&'a K> {
1833 self.inner.next_back().map(|(k, _)| k)
1834 }
1835}
1836
1837#[stable(feature = "rust1", since = "1.0.0")]
1838impl<K, V> ExactSizeIterator for Keys<'_, K, V> {
1839 fn len(&self) -> usize {
1840 self.inner.len()
1841 }
1842}
1843
1844#[stable(feature = "fused", since = "1.26.0")]
1845impl<K, V> FusedIterator for Keys<'_, K, V> {}
1846
1847#[stable(feature = "rust1", since = "1.0.0")]
1848impl<K, V> Clone for Keys<'_, K, V> {
1849 fn clone(&self) -> Self {
1850 Keys { inner: self.inner.clone() }
1851 }
1852}
1853
1854#[stable(feature = "default_iters", since = "1.70.0")]
1855impl<K, V> Default for Keys<'_, K, V> {
1856 /// Creates an empty `btree_map::Keys`.
1857 ///
1858 /// ```
1859 /// # use std::collections::btree_map;
1860 /// let iter: btree_map::Keys<'_, u8, u8> = Default::default();
1861 /// assert_eq!(iter.len(), 0);
1862 /// ```
1863 fn default() -> Self {
1864 Keys { inner: Default::default() }
1865 }
1866}
1867
1868#[stable(feature = "rust1", since = "1.0.0")]
1869impl<'a, K, V> Iterator for Values<'a, K, V> {
1870 type Item = &'a V;
1871
1872 fn next(&mut self) -> Option<&'a V> {
1873 self.inner.next().map(|(_, v)| v)
1874 }
1875
1876 fn size_hint(&self) -> (usize, Option<usize>) {
1877 self.inner.size_hint()
1878 }
1879
1880 fn last(mut self) -> Option<&'a V> {
1881 self.next_back()
1882 }
1883}
1884
1885#[stable(feature = "rust1", since = "1.0.0")]
1886impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> {
1887 fn next_back(&mut self) -> Option<&'a V> {
1888 self.inner.next_back().map(|(_, v)| v)
1889 }
1890}
1891
1892#[stable(feature = "rust1", since = "1.0.0")]
1893impl<K, V> ExactSizeIterator for Values<'_, K, V> {
1894 fn len(&self) -> usize {
1895 self.inner.len()
1896 }
1897}
1898
1899#[stable(feature = "fused", since = "1.26.0")]
1900impl<K, V> FusedIterator for Values<'_, K, V> {}
1901
1902#[stable(feature = "rust1", since = "1.0.0")]
1903impl<K, V> Clone for Values<'_, K, V> {
1904 fn clone(&self) -> Self {
1905 Values { inner: self.inner.clone() }
1906 }
1907}
1908
1909#[stable(feature = "default_iters", since = "1.70.0")]
1910impl<K, V> Default for Values<'_, K, V> {
1911 /// Creates an empty `btree_map::Values`.
1912 ///
1913 /// ```
1914 /// # use std::collections::btree_map;
1915 /// let iter: btree_map::Values<'_, u8, u8> = Default::default();
1916 /// assert_eq!(iter.len(), 0);
1917 /// ```
1918 fn default() -> Self {
1919 Values { inner: Default::default() }
1920 }
1921}
1922
1923/// An iterator produced by calling `extract_if` on BTreeMap.
1924#[unstable(feature = "btree_extract_if", issue = "70530")]
1925#[must_use = "iterators are lazy and do nothing unless consumed"]
1926pub struct ExtractIf<
1927 'a,
1928 K,
1929 V,
1930 R,
1931 F,
1932 #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + Clone = Global,
1933> {
1934 pred: F,
1935 inner: ExtractIfInner<'a, K, V, R>,
1936 /// The BTreeMap will outlive this IntoIter so we don't care about drop order for `alloc`.
1937 alloc: A,
1938}
1939
1940/// Most of the implementation of ExtractIf are generic over the type
1941/// of the predicate, thus also serving for BTreeSet::ExtractIf.
1942pub(super) struct ExtractIfInner<'a, K, V, R> {
1943 /// Reference to the length field in the borrowed map, updated live.
1944 length: &'a mut usize,
1945 /// Buried reference to the root field in the borrowed map.
1946 /// Wrapped in `Option` to allow drop handler to `take` it.
1947 dormant_root: Option<DormantMutRef<'a, Root<K, V>>>,
1948 /// Contains a leaf edge preceding the next element to be returned, or the last leaf edge.
1949 /// Empty if the map has no root, if iteration went beyond the last leaf edge,
1950 /// or if a panic occurred in the predicate.
1951 cur_leaf_edge: Option<Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>>,
1952 /// Range over which iteration was requested. We don't need the left side, but we
1953 /// can't extract the right side without requiring K: Clone.
1954 range: R,
1955}
1956
1957#[unstable(feature = "btree_extract_if", issue = "70530")]
1958impl<K, V, R, F, A> fmt::Debug for ExtractIf<'_, K, V, R, F, A>
1959where
1960 K: fmt::Debug,
1961 V: fmt::Debug,
1962 A: Allocator + Clone,
1963{
1964 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1965 f.debug_struct("ExtractIf").field("peek", &self.inner.peek()).finish_non_exhaustive()
1966 }
1967}
1968
1969#[unstable(feature = "btree_extract_if", issue = "70530")]
1970impl<K, V, R, F, A: Allocator + Clone> Iterator for ExtractIf<'_, K, V, R, F, A>
1971where
1972 K: PartialOrd,
1973 R: RangeBounds<K>,
1974 F: FnMut(&K, &mut V) -> bool,
1975{
1976 type Item = (K, V);
1977
1978 fn next(&mut self) -> Option<(K, V)> {
1979 self.inner.next(&mut self.pred, self.alloc.clone())
1980 }
1981
1982 fn size_hint(&self) -> (usize, Option<usize>) {
1983 self.inner.size_hint()
1984 }
1985}
1986
1987impl<'a, K, V, R> ExtractIfInner<'a, K, V, R> {
1988 /// Allow Debug implementations to predict the next element.
1989 pub(super) fn peek(&self) -> Option<(&K, &V)> {
1990 let edge = self.cur_leaf_edge.as_ref()?;
1991 edge.reborrow().next_kv().ok().map(Handle::into_kv)
1992 }
1993
1994 /// Implementation of a typical `ExtractIf::next` method, given the predicate.
1995 pub(super) fn next<F, A: Allocator + Clone>(&mut self, pred: &mut F, alloc: A) -> Option<(K, V)>
1996 where
1997 K: PartialOrd,
1998 R: RangeBounds<K>,
1999 F: FnMut(&K, &mut V) -> bool,
2000 {
2001 while let Ok(mut kv) = self.cur_leaf_edge.take()?.next_kv() {
2002 let (k, v) = kv.kv_mut();
2003
2004 // On creation, we navigated directly to the left bound, so we need only check the
2005 // right bound here to decide whether to stop.
2006 match self.range.end_bound() {
2007 Bound::Included(ref end) if (*k).le(end) => (),
2008 Bound::Excluded(ref end) if (*k).lt(end) => (),
2009 Bound::Unbounded => (),
2010 _ => return None,
2011 }
2012
2013 if pred(k, v) {
2014 *self.length -= 1;
2015 let (kv, pos) = kv.remove_kv_tracking(
2016 || {
2017 // SAFETY: we will touch the root in a way that will not
2018 // invalidate the position returned.
2019 let root = unsafe { self.dormant_root.take().unwrap().awaken() };
2020 root.pop_internal_level(alloc.clone());
2021 self.dormant_root = Some(DormantMutRef::new(root).1);
2022 },
2023 alloc.clone(),
2024 );
2025 self.cur_leaf_edge = Some(pos);
2026 return Some(kv);
2027 }
2028 self.cur_leaf_edge = Some(kv.next_leaf_edge());
2029 }
2030 None
2031 }
2032
2033 /// Implementation of a typical `ExtractIf::size_hint` method.
2034 pub(super) fn size_hint(&self) -> (usize, Option<usize>) {
2035 // In most of the btree iterators, `self.length` is the number of elements
2036 // yet to be visited. Here, it includes elements that were visited and that
2037 // the predicate decided not to drain. Making this upper bound more tight
2038 // during iteration would require an extra field.
2039 (0, Some(*self.length))
2040 }
2041}
2042
2043#[unstable(feature = "btree_extract_if", issue = "70530")]
2044impl<K, V, R, F> FusedIterator for ExtractIf<'_, K, V, R, F>
2045where
2046 K: PartialOrd,
2047 R: RangeBounds<K>,
2048 F: FnMut(&K, &mut V) -> bool,
2049{
2050}
2051
2052#[stable(feature = "btree_range", since = "1.17.0")]
2053impl<'a, K, V> Iterator for Range<'a, K, V> {
2054 type Item = (&'a K, &'a V);
2055
2056 fn next(&mut self) -> Option<(&'a K, &'a V)> {
2057 self.inner.next_checked()
2058 }
2059
2060 fn last(mut self) -> Option<(&'a K, &'a V)> {
2061 self.next_back()
2062 }
2063
2064 fn min(mut self) -> Option<(&'a K, &'a V)>
2065 where
2066 (&'a K, &'a V): Ord,
2067 {
2068 self.next()
2069 }
2070
2071 fn max(mut self) -> Option<(&'a K, &'a V)>
2072 where
2073 (&'a K, &'a V): Ord,
2074 {
2075 self.next_back()
2076 }
2077}
2078
2079#[stable(feature = "default_iters", since = "1.70.0")]
2080impl<K, V> Default for Range<'_, K, V> {
2081 /// Creates an empty `btree_map::Range`.
2082 ///
2083 /// ```
2084 /// # use std::collections::btree_map;
2085 /// let iter: btree_map::Range<'_, u8, u8> = Default::default();
2086 /// assert_eq!(iter.count(), 0);
2087 /// ```
2088 fn default() -> Self {
2089 Range { inner: Default::default() }
2090 }
2091}
2092
2093#[stable(feature = "default_iters_sequel", since = "1.82.0")]
2094impl<K, V> Default for RangeMut<'_, K, V> {
2095 /// Creates an empty `btree_map::RangeMut`.
2096 ///
2097 /// ```
2098 /// # use std::collections::btree_map;
2099 /// let iter: btree_map::RangeMut<'_, u8, u8> = Default::default();
2100 /// assert_eq!(iter.count(), 0);
2101 /// ```
2102 fn default() -> Self {
2103 RangeMut { inner: Default::default(), _marker: PhantomData }
2104 }
2105}
2106
2107#[stable(feature = "map_values_mut", since = "1.10.0")]
2108impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
2109 type Item = &'a mut V;
2110
2111 fn next(&mut self) -> Option<&'a mut V> {
2112 self.inner.next().map(|(_, v)| v)
2113 }
2114
2115 fn size_hint(&self) -> (usize, Option<usize>) {
2116 self.inner.size_hint()
2117 }
2118
2119 fn last(mut self) -> Option<&'a mut V> {
2120 self.next_back()
2121 }
2122}
2123
2124#[stable(feature = "map_values_mut", since = "1.10.0")]
2125impl<'a, K, V> DoubleEndedIterator for ValuesMut<'a, K, V> {
2126 fn next_back(&mut self) -> Option<&'a mut V> {
2127 self.inner.next_back().map(|(_, v)| v)
2128 }
2129}
2130
2131#[stable(feature = "map_values_mut", since = "1.10.0")]
2132impl<K, V> ExactSizeIterator for ValuesMut<'_, K, V> {
2133 fn len(&self) -> usize {
2134 self.inner.len()
2135 }
2136}
2137
2138#[stable(feature = "fused", since = "1.26.0")]
2139impl<K, V> FusedIterator for ValuesMut<'_, K, V> {}
2140
2141#[stable(feature = "default_iters_sequel", since = "1.82.0")]
2142impl<K, V> Default for ValuesMut<'_, K, V> {
2143 /// Creates an empty `btree_map::ValuesMut`.
2144 ///
2145 /// ```
2146 /// # use std::collections::btree_map;
2147 /// let iter: btree_map::ValuesMut<'_, u8, u8> = Default::default();
2148 /// assert_eq!(iter.count(), 0);
2149 /// ```
2150 fn default() -> Self {
2151 ValuesMut { inner: Default::default() }
2152 }
2153}
2154
2155#[stable(feature = "map_into_keys_values", since = "1.54.0")]
2156impl<K, V, A: Allocator + Clone> Iterator for IntoKeys<K, V, A> {
2157 type Item = K;
2158
2159 fn next(&mut self) -> Option<K> {
2160 self.inner.next().map(|(k, _)| k)
2161 }
2162
2163 fn size_hint(&self) -> (usize, Option<usize>) {
2164 self.inner.size_hint()
2165 }
2166
2167 fn last(mut self) -> Option<K> {
2168 self.next_back()
2169 }
2170
2171 fn min(mut self) -> Option<K>
2172 where
2173 K: Ord,
2174 {
2175 self.next()
2176 }
2177
2178 fn max(mut self) -> Option<K>
2179 where
2180 K: Ord,
2181 {
2182 self.next_back()
2183 }
2184}
2185
2186#[stable(feature = "map_into_keys_values", since = "1.54.0")]
2187impl<K, V, A: Allocator + Clone> DoubleEndedIterator for IntoKeys<K, V, A> {
2188 fn next_back(&mut self) -> Option<K> {
2189 self.inner.next_back().map(|(k, _)| k)
2190 }
2191}
2192
2193#[stable(feature = "map_into_keys_values", since = "1.54.0")]
2194impl<K, V, A: Allocator + Clone> ExactSizeIterator for IntoKeys<K, V, A> {
2195 fn len(&self) -> usize {
2196 self.inner.len()
2197 }
2198}
2199
2200#[stable(feature = "map_into_keys_values", since = "1.54.0")]
2201impl<K, V, A: Allocator + Clone> FusedIterator for IntoKeys<K, V, A> {}
2202
2203#[stable(feature = "default_iters", since = "1.70.0")]
2204impl<K, V, A> Default for IntoKeys<K, V, A>
2205where
2206 A: Allocator + Default + Clone,
2207{
2208 /// Creates an empty `btree_map::IntoKeys`.
2209 ///
2210 /// ```
2211 /// # use std::collections::btree_map;
2212 /// let iter: btree_map::IntoKeys<u8, u8> = Default::default();
2213 /// assert_eq!(iter.len(), 0);
2214 /// ```
2215 fn default() -> Self {
2216 IntoKeys { inner: Default::default() }
2217 }
2218}
2219
2220#[stable(feature = "map_into_keys_values", since = "1.54.0")]
2221impl<K, V, A: Allocator + Clone> Iterator for IntoValues<K, V, A> {
2222 type Item = V;
2223
2224 fn next(&mut self) -> Option<V> {
2225 self.inner.next().map(|(_, v)| v)
2226 }
2227
2228 fn size_hint(&self) -> (usize, Option<usize>) {
2229 self.inner.size_hint()
2230 }
2231
2232 fn last(mut self) -> Option<V> {
2233 self.next_back()
2234 }
2235}
2236
2237#[stable(feature = "map_into_keys_values", since = "1.54.0")]
2238impl<K, V, A: Allocator + Clone> DoubleEndedIterator for IntoValues<K, V, A> {
2239 fn next_back(&mut self) -> Option<V> {
2240 self.inner.next_back().map(|(_, v)| v)
2241 }
2242}
2243
2244#[stable(feature = "map_into_keys_values", since = "1.54.0")]
2245impl<K, V, A: Allocator + Clone> ExactSizeIterator for IntoValues<K, V, A> {
2246 fn len(&self) -> usize {
2247 self.inner.len()
2248 }
2249}
2250
2251#[stable(feature = "map_into_keys_values", since = "1.54.0")]
2252impl<K, V, A: Allocator + Clone> FusedIterator for IntoValues<K, V, A> {}
2253
2254#[stable(feature = "default_iters", since = "1.70.0")]
2255impl<K, V, A> Default for IntoValues<K, V, A>
2256where
2257 A: Allocator + Default + Clone,
2258{
2259 /// Creates an empty `btree_map::IntoValues`.
2260 ///
2261 /// ```
2262 /// # use std::collections::btree_map;
2263 /// let iter: btree_map::IntoValues<u8, u8> = Default::default();
2264 /// assert_eq!(iter.len(), 0);
2265 /// ```
2266 fn default() -> Self {
2267 IntoValues { inner: Default::default() }
2268 }
2269}
2270
2271#[stable(feature = "btree_range", since = "1.17.0")]
2272impl<'a, K, V> DoubleEndedIterator for Range<'a, K, V> {
2273 fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
2274 self.inner.next_back_checked()
2275 }
2276}
2277
2278#[stable(feature = "fused", since = "1.26.0")]
2279impl<K, V> FusedIterator for Range<'_, K, V> {}
2280
2281#[stable(feature = "btree_range", since = "1.17.0")]
2282impl<K, V> Clone for Range<'_, K, V> {
2283 fn clone(&self) -> Self {
2284 Range { inner: self.inner.clone() }
2285 }
2286}
2287
2288#[stable(feature = "btree_range", since = "1.17.0")]
2289impl<'a, K, V> Iterator for RangeMut<'a, K, V> {
2290 type Item = (&'a K, &'a mut V);
2291
2292 fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
2293 self.inner.next_checked()
2294 }
2295
2296 fn last(mut self) -> Option<(&'a K, &'a mut V)> {
2297 self.next_back()
2298 }
2299
2300 fn min(mut self) -> Option<(&'a K, &'a mut V)>
2301 where
2302 (&'a K, &'a mut V): Ord,
2303 {
2304 self.next()
2305 }
2306
2307 fn max(mut self) -> Option<(&'a K, &'a mut V)>
2308 where
2309 (&'a K, &'a mut V): Ord,
2310 {
2311 self.next_back()
2312 }
2313}
2314
2315#[stable(feature = "btree_range", since = "1.17.0")]
2316impl<'a, K, V> DoubleEndedIterator for RangeMut<'a, K, V> {
2317 fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
2318 self.inner.next_back_checked()
2319 }
2320}
2321
2322#[stable(feature = "fused", since = "1.26.0")]
2323impl<K, V> FusedIterator for RangeMut<'_, K, V> {}
2324
2325#[stable(feature = "rust1", since = "1.0.0")]
2326impl<K: Ord, V> FromIterator<(K, V)> for BTreeMap<K, V> {
2327 /// Constructs a `BTreeMap<K, V>` from an iterator of key-value pairs.
2328 ///
2329 /// If the iterator produces any pairs with equal keys,
2330 /// all but one of the corresponding values will be dropped.
2331 fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> BTreeMap<K, V> {
2332 let mut inputs: Vec<_> = iter.into_iter().collect();
2333
2334 if inputs.is_empty() {
2335 return BTreeMap::new();
2336 }
2337
2338 // use stable sort to preserve the insertion order.
2339 inputs.sort_by(|a, b| a.0.cmp(&b.0));
2340 BTreeMap::bulk_build_from_sorted_iter(inputs, Global)
2341 }
2342}
2343
2344#[stable(feature = "rust1", since = "1.0.0")]
2345impl<K: Ord, V, A: Allocator + Clone> Extend<(K, V)> for BTreeMap<K, V, A> {
2346 #[inline]
2347 fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
2348 iter.into_iter().for_each(move |(k, v)| {
2349 self.insert(k, v);
2350 });
2351 }
2352
2353 #[inline]
2354 fn extend_one(&mut self, (k, v): (K, V)) {
2355 self.insert(k, v);
2356 }
2357}
2358
2359#[stable(feature = "extend_ref", since = "1.2.0")]
2360impl<'a, K: Ord + Copy, V: Copy, A: Allocator + Clone> Extend<(&'a K, &'a V)>
2361 for BTreeMap<K, V, A>
2362{
2363 fn extend<I: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: I) {
2364 self.extend(iter.into_iter().map(|(&key, &value)| (key, value)));
2365 }
2366
2367 #[inline]
2368 fn extend_one(&mut self, (&k, &v): (&'a K, &'a V)) {
2369 self.insert(k, v);
2370 }
2371}
2372
2373#[stable(feature = "rust1", since = "1.0.0")]
2374impl<K: Hash, V: Hash, A: Allocator + Clone> Hash for BTreeMap<K, V, A> {
2375 fn hash<H: Hasher>(&self, state: &mut H) {
2376 state.write_length_prefix(self.len());
2377 for elt in self {
2378 elt.hash(state);
2379 }
2380 }
2381}
2382
2383#[stable(feature = "rust1", since = "1.0.0")]
2384impl<K, V> Default for BTreeMap<K, V> {
2385 /// Creates an empty `BTreeMap`.
2386 fn default() -> BTreeMap<K, V> {
2387 BTreeMap::new()
2388 }
2389}
2390
2391#[stable(feature = "rust1", since = "1.0.0")]
2392impl<K: PartialEq, V: PartialEq, A: Allocator + Clone> PartialEq for BTreeMap<K, V, A> {
2393 fn eq(&self, other: &BTreeMap<K, V, A>) -> bool {
2394 self.len() == other.len() && self.iter().zip(other).all(|(a, b)| a == b)
2395 }
2396}
2397
2398#[stable(feature = "rust1", since = "1.0.0")]
2399impl<K: Eq, V: Eq, A: Allocator + Clone> Eq for BTreeMap<K, V, A> {}
2400
2401#[stable(feature = "rust1", since = "1.0.0")]
2402impl<K: PartialOrd, V: PartialOrd, A: Allocator + Clone> PartialOrd for BTreeMap<K, V, A> {
2403 #[inline]
2404 fn partial_cmp(&self, other: &BTreeMap<K, V, A>) -> Option<Ordering> {
2405 self.iter().partial_cmp(other.iter())
2406 }
2407}
2408
2409#[stable(feature = "rust1", since = "1.0.0")]
2410impl<K: Ord, V: Ord, A: Allocator + Clone> Ord for BTreeMap<K, V, A> {
2411 #[inline]
2412 fn cmp(&self, other: &BTreeMap<K, V, A>) -> Ordering {
2413 self.iter().cmp(other.iter())
2414 }
2415}
2416
2417#[stable(feature = "rust1", since = "1.0.0")]
2418impl<K: Debug, V: Debug, A: Allocator + Clone> Debug for BTreeMap<K, V, A> {
2419 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2420 f.debug_map().entries(self.iter()).finish()
2421 }
2422}
2423
2424#[stable(feature = "rust1", since = "1.0.0")]
2425impl<K, Q: ?Sized, V, A: Allocator + Clone> Index<&Q> for BTreeMap<K, V, A>
2426where
2427 K: Borrow<Q> + Ord,
2428 Q: Ord,
2429{
2430 type Output = V;
2431
2432 /// Returns a reference to the value corresponding to the supplied key.
2433 ///
2434 /// # Panics
2435 ///
2436 /// Panics if the key is not present in the `BTreeMap`.
2437 #[inline]
2438 fn index(&self, key: &Q) -> &V {
2439 self.get(key).expect("no entry found for key")
2440 }
2441}
2442
2443#[stable(feature = "std_collections_from_array", since = "1.56.0")]
2444impl<K: Ord, V, const N: usize> From<[(K, V); N]> for BTreeMap<K, V> {
2445 /// Converts a `[(K, V); N]` into a `BTreeMap<K, V>`.
2446 ///
2447 /// If any entries in the array have equal keys,
2448 /// all but one of the corresponding values will be dropped.
2449 ///
2450 /// ```
2451 /// use std::collections::BTreeMap;
2452 ///
2453 /// let map1 = BTreeMap::from([(1, 2), (3, 4)]);
2454 /// let map2: BTreeMap<_, _> = [(1, 2), (3, 4)].into();
2455 /// assert_eq!(map1, map2);
2456 /// ```
2457 fn from(mut arr: [(K, V); N]) -> Self {
2458 if N == 0 {
2459 return BTreeMap::new();
2460 }
2461
2462 // use stable sort to preserve the insertion order.
2463 arr.sort_by(|a, b| a.0.cmp(&b.0));
2464 BTreeMap::bulk_build_from_sorted_iter(arr, Global)
2465 }
2466}
2467
2468impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> {
2469 /// Gets an iterator over the entries of the map, sorted by key.
2470 ///
2471 /// # Examples
2472 ///
2473 /// ```
2474 /// use std::collections::BTreeMap;
2475 ///
2476 /// let mut map = BTreeMap::new();
2477 /// map.insert(3, "c");
2478 /// map.insert(2, "b");
2479 /// map.insert(1, "a");
2480 ///
2481 /// for (key, value) in map.iter() {
2482 /// println!("{key}: {value}");
2483 /// }
2484 ///
2485 /// let (first_key, first_value) = map.iter().next().unwrap();
2486 /// assert_eq!((*first_key, *first_value), (1, "a"));
2487 /// ```
2488 #[stable(feature = "rust1", since = "1.0.0")]
2489 pub fn iter(&self) -> Iter<'_, K, V> {
2490 if let Some(root) = &self.root {
2491 let full_range = root.reborrow().full_range();
2492
2493 Iter { range: full_range, length: self.length }
2494 } else {
2495 Iter { range: LazyLeafRange::none(), length: 0 }
2496 }
2497 }
2498
2499 /// Gets a mutable iterator over the entries of the map, sorted by key.
2500 ///
2501 /// # Examples
2502 ///
2503 /// ```
2504 /// use std::collections::BTreeMap;
2505 ///
2506 /// let mut map = BTreeMap::from([
2507 /// ("a", 1),
2508 /// ("b", 2),
2509 /// ("c", 3),
2510 /// ]);
2511 ///
2512 /// // add 10 to the value if the key isn't "a"
2513 /// for (key, value) in map.iter_mut() {
2514 /// if key != &"a" {
2515 /// *value += 10;
2516 /// }
2517 /// }
2518 /// ```
2519 #[stable(feature = "rust1", since = "1.0.0")]
2520 pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
2521 if let Some(root) = &mut self.root {
2522 let full_range = root.borrow_valmut().full_range();
2523
2524 IterMut { range: full_range, length: self.length, _marker: PhantomData }
2525 } else {
2526 IterMut { range: LazyLeafRange::none(), length: 0, _marker: PhantomData }
2527 }
2528 }
2529
2530 /// Gets an iterator over the keys of the map, in sorted order.
2531 ///
2532 /// # Examples
2533 ///
2534 /// ```
2535 /// use std::collections::BTreeMap;
2536 ///
2537 /// let mut a = BTreeMap::new();
2538 /// a.insert(2, "b");
2539 /// a.insert(1, "a");
2540 ///
2541 /// let keys: Vec<_> = a.keys().cloned().collect();
2542 /// assert_eq!(keys, [1, 2]);
2543 /// ```
2544 #[stable(feature = "rust1", since = "1.0.0")]
2545 pub fn keys(&self) -> Keys<'_, K, V> {
2546 Keys { inner: self.iter() }
2547 }
2548
2549 /// Gets an iterator over the values of the map, in order by key.
2550 ///
2551 /// # Examples
2552 ///
2553 /// ```
2554 /// use std::collections::BTreeMap;
2555 ///
2556 /// let mut a = BTreeMap::new();
2557 /// a.insert(1, "hello");
2558 /// a.insert(2, "goodbye");
2559 ///
2560 /// let values: Vec<&str> = a.values().cloned().collect();
2561 /// assert_eq!(values, ["hello", "goodbye"]);
2562 /// ```
2563 #[stable(feature = "rust1", since = "1.0.0")]
2564 pub fn values(&self) -> Values<'_, K, V> {
2565 Values { inner: self.iter() }
2566 }
2567
2568 /// Gets a mutable iterator over the values of the map, in order by key.
2569 ///
2570 /// # Examples
2571 ///
2572 /// ```
2573 /// use std::collections::BTreeMap;
2574 ///
2575 /// let mut a = BTreeMap::new();
2576 /// a.insert(1, String::from("hello"));
2577 /// a.insert(2, String::from("goodbye"));
2578 ///
2579 /// for value in a.values_mut() {
2580 /// value.push_str("!");
2581 /// }
2582 ///
2583 /// let values: Vec<String> = a.values().cloned().collect();
2584 /// assert_eq!(values, [String::from("hello!"),
2585 /// String::from("goodbye!")]);
2586 /// ```
2587 #[stable(feature = "map_values_mut", since = "1.10.0")]
2588 pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {
2589 ValuesMut { inner: self.iter_mut() }
2590 }
2591
2592 /// Returns the number of elements in the map.
2593 ///
2594 /// # Examples
2595 ///
2596 /// ```
2597 /// use std::collections::BTreeMap;
2598 ///
2599 /// let mut a = BTreeMap::new();
2600 /// assert_eq!(a.len(), 0);
2601 /// a.insert(1, "a");
2602 /// assert_eq!(a.len(), 1);
2603 /// ```
2604 #[must_use]
2605 #[stable(feature = "rust1", since = "1.0.0")]
2606 #[rustc_const_unstable(
2607 feature = "const_btree_len",
2608 issue = "71835",
2609 implied_by = "const_btree_new"
2610 )]
2611 #[rustc_confusables("length", "size")]
2612 pub const fn len(&self) -> usize {
2613 self.length
2614 }
2615
2616 /// Returns `true` if the map contains no elements.
2617 ///
2618 /// # Examples
2619 ///
2620 /// ```
2621 /// use std::collections::BTreeMap;
2622 ///
2623 /// let mut a = BTreeMap::new();
2624 /// assert!(a.is_empty());
2625 /// a.insert(1, "a");
2626 /// assert!(!a.is_empty());
2627 /// ```
2628 #[must_use]
2629 #[stable(feature = "rust1", since = "1.0.0")]
2630 #[rustc_const_unstable(
2631 feature = "const_btree_len",
2632 issue = "71835",
2633 implied_by = "const_btree_new"
2634 )]
2635 pub const fn is_empty(&self) -> bool {
2636 self.len() == 0
2637 }
2638
2639 /// Returns a [`Cursor`] pointing at the gap before the smallest key
2640 /// greater than the given bound.
2641 ///
2642 /// Passing `Bound::Included(x)` will return a cursor pointing to the
2643 /// gap before the smallest key greater than or equal to `x`.
2644 ///
2645 /// Passing `Bound::Excluded(x)` will return a cursor pointing to the
2646 /// gap before the smallest key greater than `x`.
2647 ///
2648 /// Passing `Bound::Unbounded` will return a cursor pointing to the
2649 /// gap before the smallest key in the map.
2650 ///
2651 /// # Examples
2652 ///
2653 /// ```
2654 /// #![feature(btree_cursors)]
2655 ///
2656 /// use std::collections::BTreeMap;
2657 /// use std::ops::Bound;
2658 ///
2659 /// let map = BTreeMap::from([
2660 /// (1, "a"),
2661 /// (2, "b"),
2662 /// (3, "c"),
2663 /// (4, "d"),
2664 /// ]);
2665 ///
2666 /// let cursor = map.lower_bound(Bound::Included(&2));
2667 /// assert_eq!(cursor.peek_prev(), Some((&1, &"a")));
2668 /// assert_eq!(cursor.peek_next(), Some((&2, &"b")));
2669 ///
2670 /// let cursor = map.lower_bound(Bound::Excluded(&2));
2671 /// assert_eq!(cursor.peek_prev(), Some((&2, &"b")));
2672 /// assert_eq!(cursor.peek_next(), Some((&3, &"c")));
2673 ///
2674 /// let cursor = map.lower_bound(Bound::Unbounded);
2675 /// assert_eq!(cursor.peek_prev(), None);
2676 /// assert_eq!(cursor.peek_next(), Some((&1, &"a")));
2677 /// ```
2678 #[unstable(feature = "btree_cursors", issue = "107540")]
2679 pub fn lower_bound<Q: ?Sized>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V>
2680 where
2681 K: Borrow<Q> + Ord,
2682 Q: Ord,
2683 {
2684 let root_node = match self.root.as_ref() {
2685 None => return Cursor { current: None, root: None },
2686 Some(root) => root.reborrow(),
2687 };
2688 let edge = root_node.lower_bound(SearchBound::from_range(bound));
2689 Cursor { current: Some(edge), root: self.root.as_ref() }
2690 }
2691
2692 /// Returns a [`CursorMut`] pointing at the gap before the smallest key
2693 /// greater than the given bound.
2694 ///
2695 /// Passing `Bound::Included(x)` will return a cursor pointing to the
2696 /// gap before the smallest key greater than or equal to `x`.
2697 ///
2698 /// Passing `Bound::Excluded(x)` will return a cursor pointing to the
2699 /// gap before the smallest key greater than `x`.
2700 ///
2701 /// Passing `Bound::Unbounded` will return a cursor pointing to the
2702 /// gap before the smallest key in the map.
2703 ///
2704 /// # Examples
2705 ///
2706 /// ```
2707 /// #![feature(btree_cursors)]
2708 ///
2709 /// use std::collections::BTreeMap;
2710 /// use std::ops::Bound;
2711 ///
2712 /// let mut map = BTreeMap::from([
2713 /// (1, "a"),
2714 /// (2, "b"),
2715 /// (3, "c"),
2716 /// (4, "d"),
2717 /// ]);
2718 ///
2719 /// let mut cursor = map.lower_bound_mut(Bound::Included(&2));
2720 /// assert_eq!(cursor.peek_prev(), Some((&1, &mut "a")));
2721 /// assert_eq!(cursor.peek_next(), Some((&2, &mut "b")));
2722 ///
2723 /// let mut cursor = map.lower_bound_mut(Bound::Excluded(&2));
2724 /// assert_eq!(cursor.peek_prev(), Some((&2, &mut "b")));
2725 /// assert_eq!(cursor.peek_next(), Some((&3, &mut "c")));
2726 ///
2727 /// let mut cursor = map.lower_bound_mut(Bound::Unbounded);
2728 /// assert_eq!(cursor.peek_prev(), None);
2729 /// assert_eq!(cursor.peek_next(), Some((&1, &mut "a")));
2730 /// ```
2731 #[unstable(feature = "btree_cursors", issue = "107540")]
2732 pub fn lower_bound_mut<Q: ?Sized>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V, A>
2733 where
2734 K: Borrow<Q> + Ord,
2735 Q: Ord,
2736 {
2737 let (root, dormant_root) = DormantMutRef::new(&mut self.root);
2738 let root_node = match root.as_mut() {
2739 None => {
2740 return CursorMut {
2741 inner: CursorMutKey {
2742 current: None,
2743 root: dormant_root,
2744 length: &mut self.length,
2745 alloc: &mut *self.alloc,
2746 },
2747 };
2748 }
2749 Some(root) => root.borrow_mut(),
2750 };
2751 let edge = root_node.lower_bound(SearchBound::from_range(bound));
2752 CursorMut {
2753 inner: CursorMutKey {
2754 current: Some(edge),
2755 root: dormant_root,
2756 length: &mut self.length,
2757 alloc: &mut *self.alloc,
2758 },
2759 }
2760 }
2761
2762 /// Returns a [`Cursor`] pointing at the gap after the greatest key
2763 /// smaller than the given bound.
2764 ///
2765 /// Passing `Bound::Included(x)` will return a cursor pointing to the
2766 /// gap after the greatest key smaller than or equal to `x`.
2767 ///
2768 /// Passing `Bound::Excluded(x)` will return a cursor pointing to the
2769 /// gap after the greatest key smaller than `x`.
2770 ///
2771 /// Passing `Bound::Unbounded` will return a cursor pointing to the
2772 /// gap after the greatest key in the map.
2773 ///
2774 /// # Examples
2775 ///
2776 /// ```
2777 /// #![feature(btree_cursors)]
2778 ///
2779 /// use std::collections::BTreeMap;
2780 /// use std::ops::Bound;
2781 ///
2782 /// let map = BTreeMap::from([
2783 /// (1, "a"),
2784 /// (2, "b"),
2785 /// (3, "c"),
2786 /// (4, "d"),
2787 /// ]);
2788 ///
2789 /// let cursor = map.upper_bound(Bound::Included(&3));
2790 /// assert_eq!(cursor.peek_prev(), Some((&3, &"c")));
2791 /// assert_eq!(cursor.peek_next(), Some((&4, &"d")));
2792 ///
2793 /// let cursor = map.upper_bound(Bound::Excluded(&3));
2794 /// assert_eq!(cursor.peek_prev(), Some((&2, &"b")));
2795 /// assert_eq!(cursor.peek_next(), Some((&3, &"c")));
2796 ///
2797 /// let cursor = map.upper_bound(Bound::Unbounded);
2798 /// assert_eq!(cursor.peek_prev(), Some((&4, &"d")));
2799 /// assert_eq!(cursor.peek_next(), None);
2800 /// ```
2801 #[unstable(feature = "btree_cursors", issue = "107540")]
2802 pub fn upper_bound<Q: ?Sized>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V>
2803 where
2804 K: Borrow<Q> + Ord,
2805 Q: Ord,
2806 {
2807 let root_node = match self.root.as_ref() {
2808 None => return Cursor { current: None, root: None },
2809 Some(root) => root.reborrow(),
2810 };
2811 let edge = root_node.upper_bound(SearchBound::from_range(bound));
2812 Cursor { current: Some(edge), root: self.root.as_ref() }
2813 }
2814
2815 /// Returns a [`CursorMut`] pointing at the gap after the greatest key
2816 /// smaller than the given bound.
2817 ///
2818 /// Passing `Bound::Included(x)` will return a cursor pointing to the
2819 /// gap after the greatest key smaller than or equal to `x`.
2820 ///
2821 /// Passing `Bound::Excluded(x)` will return a cursor pointing to the
2822 /// gap after the greatest key smaller than `x`.
2823 ///
2824 /// Passing `Bound::Unbounded` will return a cursor pointing to the
2825 /// gap after the greatest key in the map.
2826 ///
2827 /// # Examples
2828 ///
2829 /// ```
2830 /// #![feature(btree_cursors)]
2831 ///
2832 /// use std::collections::BTreeMap;
2833 /// use std::ops::Bound;
2834 ///
2835 /// let mut map = BTreeMap::from([
2836 /// (1, "a"),
2837 /// (2, "b"),
2838 /// (3, "c"),
2839 /// (4, "d"),
2840 /// ]);
2841 ///
2842 /// let mut cursor = map.upper_bound_mut(Bound::Included(&3));
2843 /// assert_eq!(cursor.peek_prev(), Some((&3, &mut "c")));
2844 /// assert_eq!(cursor.peek_next(), Some((&4, &mut "d")));
2845 ///
2846 /// let mut cursor = map.upper_bound_mut(Bound::Excluded(&3));
2847 /// assert_eq!(cursor.peek_prev(), Some((&2, &mut "b")));
2848 /// assert_eq!(cursor.peek_next(), Some((&3, &mut "c")));
2849 ///
2850 /// let mut cursor = map.upper_bound_mut(Bound::Unbounded);
2851 /// assert_eq!(cursor.peek_prev(), Some((&4, &mut "d")));
2852 /// assert_eq!(cursor.peek_next(), None);
2853 /// ```
2854 #[unstable(feature = "btree_cursors", issue = "107540")]
2855 pub fn upper_bound_mut<Q: ?Sized>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V, A>
2856 where
2857 K: Borrow<Q> + Ord,
2858 Q: Ord,
2859 {
2860 let (root, dormant_root) = DormantMutRef::new(&mut self.root);
2861 let root_node = match root.as_mut() {
2862 None => {
2863 return CursorMut {
2864 inner: CursorMutKey {
2865 current: None,
2866 root: dormant_root,
2867 length: &mut self.length,
2868 alloc: &mut *self.alloc,
2869 },
2870 };
2871 }
2872 Some(root) => root.borrow_mut(),
2873 };
2874 let edge = root_node.upper_bound(SearchBound::from_range(bound));
2875 CursorMut {
2876 inner: CursorMutKey {
2877 current: Some(edge),
2878 root: dormant_root,
2879 length: &mut self.length,
2880 alloc: &mut *self.alloc,
2881 },
2882 }
2883 }
2884}
2885
2886/// A cursor over a `BTreeMap`.
2887///
2888/// A `Cursor` is like an iterator, except that it can freely seek back-and-forth.
2889///
2890/// Cursors always point to a gap between two elements in the map, and can
2891/// operate on the two immediately adjacent elements.
2892///
2893/// A `Cursor` is created with the [`BTreeMap::lower_bound`] and [`BTreeMap::upper_bound`] methods.
2894#[unstable(feature = "btree_cursors", issue = "107540")]
2895pub struct Cursor<'a, K: 'a, V: 'a> {
2896 // If current is None then it means the tree has not been allocated yet.
2897 current: Option<Handle<NodeRef<marker::Immut<'a>, K, V, marker::Leaf>, marker::Edge>>,
2898 root: Option<&'a node::Root<K, V>>,
2899}
2900
2901#[unstable(feature = "btree_cursors", issue = "107540")]
2902impl<K, V> Clone for Cursor<'_, K, V> {
2903 fn clone(&self) -> Self {
2904 let Cursor { current, root } = *self;
2905 Cursor { current, root }
2906 }
2907}
2908
2909#[unstable(feature = "btree_cursors", issue = "107540")]
2910impl<K: Debug, V: Debug> Debug for Cursor<'_, K, V> {
2911 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2912 f.write_str("Cursor")
2913 }
2914}
2915
2916/// A cursor over a `BTreeMap` with editing operations.
2917///
2918/// A `Cursor` is like an iterator, except that it can freely seek back-and-forth, and can
2919/// safely mutate the map during iteration. This is because the lifetime of its yielded
2920/// references is tied to its own lifetime, instead of just the underlying map. This means
2921/// cursors cannot yield multiple elements at once.
2922///
2923/// Cursors always point to a gap between two elements in the map, and can
2924/// operate on the two immediately adjacent elements.
2925///
2926/// A `CursorMut` is created with the [`BTreeMap::lower_bound_mut`] and [`BTreeMap::upper_bound_mut`]
2927/// methods.
2928#[unstable(feature = "btree_cursors", issue = "107540")]
2929pub struct CursorMut<
2930 'a,
2931 K: 'a,
2932 V: 'a,
2933 #[unstable(feature = "allocator_api", issue = "32838")] A = Global,
2934> {
2935 inner: CursorMutKey<'a, K, V, A>,
2936}
2937
2938#[unstable(feature = "btree_cursors", issue = "107540")]
2939impl<K: Debug, V: Debug, A> Debug for CursorMut<'_, K, V, A> {
2940 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2941 f.write_str("CursorMut")
2942 }
2943}
2944
2945/// A cursor over a `BTreeMap` with editing operations, and which allows
2946/// mutating the key of elements.
2947///
2948/// A `Cursor` is like an iterator, except that it can freely seek back-and-forth, and can
2949/// safely mutate the map during iteration. This is because the lifetime of its yielded
2950/// references is tied to its own lifetime, instead of just the underlying map. This means
2951/// cursors cannot yield multiple elements at once.
2952///
2953/// Cursors always point to a gap between two elements in the map, and can
2954/// operate on the two immediately adjacent elements.
2955///
2956/// A `CursorMutKey` is created from a [`CursorMut`] with the
2957/// [`CursorMut::with_mutable_key`] method.
2958///
2959/// # Safety
2960///
2961/// Since this cursor allows mutating keys, you must ensure that the `BTreeMap`
2962/// invariants are maintained. Specifically:
2963///
2964/// * The key of the newly inserted element must be unique in the tree.
2965/// * All keys in the tree must remain in sorted order.
2966#[unstable(feature = "btree_cursors", issue = "107540")]
2967pub struct CursorMutKey<
2968 'a,
2969 K: 'a,
2970 V: 'a,
2971 #[unstable(feature = "allocator_api", issue = "32838")] A = Global,
2972> {
2973 // If current is None then it means the tree has not been allocated yet.
2974 current: Option<Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>>,
2975 root: DormantMutRef<'a, Option<node::Root<K, V>>>,
2976 length: &'a mut usize,
2977 alloc: &'a mut A,
2978}
2979
2980#[unstable(feature = "btree_cursors", issue = "107540")]
2981impl<K: Debug, V: Debug, A> Debug for CursorMutKey<'_, K, V, A> {
2982 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2983 f.write_str("CursorMutKey")
2984 }
2985}
2986
2987impl<'a, K, V> Cursor<'a, K, V> {
2988 /// Advances the cursor to the next gap, returning the key and value of the
2989 /// element that it moved over.
2990 ///
2991 /// If the cursor is already at the end of the map then `None` is returned
2992 /// and the cursor is not moved.
2993 #[unstable(feature = "btree_cursors", issue = "107540")]
2994 pub fn next(&mut self) -> Option<(&'a K, &'a V)> {
2995 let current = self.current.take()?;
2996 match current.next_kv() {
2997 Ok(kv) => {
2998 let result = kv.into_kv();
2999 self.current = Some(kv.next_leaf_edge());
3000 Some(result)
3001 }
3002 Err(root) => {
3003 self.current = Some(root.last_leaf_edge());
3004 None
3005 }
3006 }
3007 }
3008
3009 /// Advances the cursor to the previous gap, returning the key and value of
3010 /// the element that it moved over.
3011 ///
3012 /// If the cursor is already at the start of the map then `None` is returned
3013 /// and the cursor is not moved.
3014 #[unstable(feature = "btree_cursors", issue = "107540")]
3015 pub fn prev(&mut self) -> Option<(&'a K, &'a V)> {
3016 let current = self.current.take()?;
3017 match current.next_back_kv() {
3018 Ok(kv) => {
3019 let result = kv.into_kv();
3020 self.current = Some(kv.next_back_leaf_edge());
3021 Some(result)
3022 }
3023 Err(root) => {
3024 self.current = Some(root.first_leaf_edge());
3025 None
3026 }
3027 }
3028 }
3029
3030 /// Returns a reference to the key and value of the next element without
3031 /// moving the cursor.
3032 ///
3033 /// If the cursor is at the end of the map then `None` is returned.
3034 #[unstable(feature = "btree_cursors", issue = "107540")]
3035 pub fn peek_next(&self) -> Option<(&'a K, &'a V)> {
3036 self.clone().next()
3037 }
3038
3039 /// Returns a reference to the key and value of the previous element
3040 /// without moving the cursor.
3041 ///
3042 /// If the cursor is at the start of the map then `None` is returned.
3043 #[unstable(feature = "btree_cursors", issue = "107540")]
3044 pub fn peek_prev(&self) -> Option<(&'a K, &'a V)> {
3045 self.clone().prev()
3046 }
3047}
3048
3049impl<'a, K, V, A> CursorMut<'a, K, V, A> {
3050 /// Advances the cursor to the next gap, returning the key and value of the
3051 /// element that it moved over.
3052 ///
3053 /// If the cursor is already at the end of the map then `None` is returned
3054 /// and the cursor is not moved.
3055 #[unstable(feature = "btree_cursors", issue = "107540")]
3056 pub fn next(&mut self) -> Option<(&K, &mut V)> {
3057 let (k, v) = self.inner.next()?;
3058 Some((&*k, v))
3059 }
3060
3061 /// Advances the cursor to the previous gap, returning the key and value of
3062 /// the element that it moved over.
3063 ///
3064 /// If the cursor is already at the start of the map then `None` is returned
3065 /// and the cursor is not moved.
3066 #[unstable(feature = "btree_cursors", issue = "107540")]
3067 pub fn prev(&mut self) -> Option<(&K, &mut V)> {
3068 let (k, v) = self.inner.prev()?;
3069 Some((&*k, v))
3070 }
3071
3072 /// Returns a reference to the key and value of the next element without
3073 /// moving the cursor.
3074 ///
3075 /// If the cursor is at the end of the map then `None` is returned.
3076 #[unstable(feature = "btree_cursors", issue = "107540")]
3077 pub fn peek_next(&mut self) -> Option<(&K, &mut V)> {
3078 let (k, v) = self.inner.peek_next()?;
3079 Some((&*k, v))
3080 }
3081
3082 /// Returns a reference to the key and value of the previous element
3083 /// without moving the cursor.
3084 ///
3085 /// If the cursor is at the start of the map then `None` is returned.
3086 #[unstable(feature = "btree_cursors", issue = "107540")]
3087 pub fn peek_prev(&mut self) -> Option<(&K, &mut V)> {
3088 let (k, v) = self.inner.peek_prev()?;
3089 Some((&*k, v))
3090 }
3091
3092 /// Returns a read-only cursor pointing to the same location as the
3093 /// `CursorMut`.
3094 ///
3095 /// The lifetime of the returned `Cursor` is bound to that of the
3096 /// `CursorMut`, which means it cannot outlive the `CursorMut` and that the
3097 /// `CursorMut` is frozen for the lifetime of the `Cursor`.
3098 #[unstable(feature = "btree_cursors", issue = "107540")]
3099 pub fn as_cursor(&self) -> Cursor<'_, K, V> {
3100 self.inner.as_cursor()
3101 }
3102
3103 /// Converts the cursor into a [`CursorMutKey`], which allows mutating
3104 /// the key of elements in the tree.
3105 ///
3106 /// # Safety
3107 ///
3108 /// Since this cursor allows mutating keys, you must ensure that the `BTreeMap`
3109 /// invariants are maintained. Specifically:
3110 ///
3111 /// * The key of the newly inserted element must be unique in the tree.
3112 /// * All keys in the tree must remain in sorted order.
3113 #[unstable(feature = "btree_cursors", issue = "107540")]
3114 pub unsafe fn with_mutable_key(self) -> CursorMutKey<'a, K, V, A> {
3115 self.inner
3116 }
3117}
3118
3119impl<'a, K, V, A> CursorMutKey<'a, K, V, A> {
3120 /// Advances the cursor to the next gap, returning the key and value of the
3121 /// element that it moved over.
3122 ///
3123 /// If the cursor is already at the end of the map then `None` is returned
3124 /// and the cursor is not moved.
3125 #[unstable(feature = "btree_cursors", issue = "107540")]
3126 pub fn next(&mut self) -> Option<(&mut K, &mut V)> {
3127 let current = self.current.take()?;
3128 match current.next_kv() {
3129 Ok(mut kv) => {
3130 // SAFETY: The key/value pointers remain valid even after the
3131 // cursor is moved forward. The lifetimes then prevent any
3132 // further access to the cursor.
3133 let (k, v) = unsafe { kv.reborrow_mut().into_kv_mut() };
3134 let (k, v) = (k as *mut _, v as *mut _);
3135 self.current = Some(kv.next_leaf_edge());
3136 Some(unsafe { (&mut *k, &mut *v) })
3137 }
3138 Err(root) => {
3139 self.current = Some(root.last_leaf_edge());
3140 None
3141 }
3142 }
3143 }
3144
3145 /// Advances the cursor to the previous gap, returning the key and value of
3146 /// the element that it moved over.
3147 ///
3148 /// If the cursor is already at the start of the map then `None` is returned
3149 /// and the cursor is not moved.
3150 #[unstable(feature = "btree_cursors", issue = "107540")]
3151 pub fn prev(&mut self) -> Option<(&mut K, &mut V)> {
3152 let current = self.current.take()?;
3153 match current.next_back_kv() {
3154 Ok(mut kv) => {
3155 // SAFETY: The key/value pointers remain valid even after the
3156 // cursor is moved forward. The lifetimes then prevent any
3157 // further access to the cursor.
3158 let (k, v) = unsafe { kv.reborrow_mut().into_kv_mut() };
3159 let (k, v) = (k as *mut _, v as *mut _);
3160 self.current = Some(kv.next_back_leaf_edge());
3161 Some(unsafe { (&mut *k, &mut *v) })
3162 }
3163 Err(root) => {
3164 self.current = Some(root.first_leaf_edge());
3165 None
3166 }
3167 }
3168 }
3169
3170 /// Returns a reference to the key and value of the next element without
3171 /// moving the cursor.
3172 ///
3173 /// If the cursor is at the end of the map then `None` is returned.
3174 #[unstable(feature = "btree_cursors", issue = "107540")]
3175 pub fn peek_next(&mut self) -> Option<(&mut K, &mut V)> {
3176 let current = self.current.as_mut()?;
3177 // SAFETY: We're not using this to mutate the tree.
3178 let kv = unsafe { current.reborrow_mut() }.next_kv().ok()?.into_kv_mut();
3179 Some(kv)
3180 }
3181
3182 /// Returns a reference to the key and value of the previous element
3183 /// without moving the cursor.
3184 ///
3185 /// If the cursor is at the start of the map then `None` is returned.
3186 #[unstable(feature = "btree_cursors", issue = "107540")]
3187 pub fn peek_prev(&mut self) -> Option<(&mut K, &mut V)> {
3188 let current = self.current.as_mut()?;
3189 // SAFETY: We're not using this to mutate the tree.
3190 let kv = unsafe { current.reborrow_mut() }.next_back_kv().ok()?.into_kv_mut();
3191 Some(kv)
3192 }
3193
3194 /// Returns a read-only cursor pointing to the same location as the
3195 /// `CursorMutKey`.
3196 ///
3197 /// The lifetime of the returned `Cursor` is bound to that of the
3198 /// `CursorMutKey`, which means it cannot outlive the `CursorMutKey` and that the
3199 /// `CursorMutKey` is frozen for the lifetime of the `Cursor`.
3200 #[unstable(feature = "btree_cursors", issue = "107540")]
3201 pub fn as_cursor(&self) -> Cursor<'_, K, V> {
3202 Cursor {
3203 // SAFETY: The tree is immutable while the cursor exists.
3204 root: unsafe { self.root.reborrow_shared().as_ref() },
3205 current: self.current.as_ref().map(|current| current.reborrow()),
3206 }
3207 }
3208}
3209
3210// Now the tree editing operations
3211impl<'a, K: Ord, V, A: Allocator + Clone> CursorMutKey<'a, K, V, A> {
3212 /// Inserts a new key-value pair into the map in the gap that the
3213 /// cursor is currently pointing to.
3214 ///
3215 /// After the insertion the cursor will be pointing at the gap before the
3216 /// newly inserted element.
3217 ///
3218 /// # Safety
3219 ///
3220 /// You must ensure that the `BTreeMap` invariants are maintained.
3221 /// Specifically:
3222 ///
3223 /// * The key of the newly inserted element must be unique in the tree.
3224 /// * All keys in the tree must remain in sorted order.
3225 #[unstable(feature = "btree_cursors", issue = "107540")]
3226 pub unsafe fn insert_after_unchecked(&mut self, key: K, value: V) {
3227 let edge = match self.current.take() {
3228 None => {
3229 // Tree is empty, allocate a new root.
3230 // SAFETY: We have no other reference to the tree.
3231 let root = unsafe { self.root.reborrow() };
3232 debug_assert!(root.is_none());
3233 let mut node = NodeRef::new_leaf(self.alloc.clone());
3234 // SAFETY: We don't touch the root while the handle is alive.
3235 let handle = unsafe { node.borrow_mut().push_with_handle(key, value) };
3236 *root = Some(node.forget_type());
3237 *self.length += 1;
3238 self.current = Some(handle.left_edge());
3239 return;
3240 }
3241 Some(current) => current,
3242 };
3243
3244 let handle = edge.insert_recursing(key, value, self.alloc.clone(), |ins| {
3245 drop(ins.left);
3246 // SAFETY: The handle to the newly inserted value is always on a
3247 // leaf node, so adding a new root node doesn't invalidate it.
3248 let root = unsafe { self.root.reborrow().as_mut().unwrap() };
3249 root.push_internal_level(self.alloc.clone()).push(ins.kv.0, ins.kv.1, ins.right)
3250 });
3251 self.current = Some(handle.left_edge());
3252 *self.length += 1;
3253 }
3254
3255 /// Inserts a new key-value pair into the map in the gap that the
3256 /// cursor is currently pointing to.
3257 ///
3258 /// After the insertion the cursor will be pointing at the gap after the
3259 /// newly inserted element.
3260 ///
3261 /// # Safety
3262 ///
3263 /// You must ensure that the `BTreeMap` invariants are maintained.
3264 /// Specifically:
3265 ///
3266 /// * The key of the newly inserted element must be unique in the tree.
3267 /// * All keys in the tree must remain in sorted order.
3268 #[unstable(feature = "btree_cursors", issue = "107540")]
3269 pub unsafe fn insert_before_unchecked(&mut self, key: K, value: V) {
3270 let edge = match self.current.take() {
3271 None => {
3272 // SAFETY: We have no other reference to the tree.
3273 match unsafe { self.root.reborrow() } {
3274 root @ None => {
3275 // Tree is empty, allocate a new root.
3276 let mut node = NodeRef::new_leaf(self.alloc.clone());
3277 // SAFETY: We don't touch the root while the handle is alive.
3278 let handle = unsafe { node.borrow_mut().push_with_handle(key, value) };
3279 *root = Some(node.forget_type());
3280 *self.length += 1;
3281 self.current = Some(handle.right_edge());
3282 return;
3283 }
3284 Some(root) => root.borrow_mut().last_leaf_edge(),
3285 }
3286 }
3287 Some(current) => current,
3288 };
3289
3290 let handle = edge.insert_recursing(key, value, self.alloc.clone(), |ins| {
3291 drop(ins.left);
3292 // SAFETY: The handle to the newly inserted value is always on a
3293 // leaf node, so adding a new root node doesn't invalidate it.
3294 let root = unsafe { self.root.reborrow().as_mut().unwrap() };
3295 root.push_internal_level(self.alloc.clone()).push(ins.kv.0, ins.kv.1, ins.right)
3296 });
3297 self.current = Some(handle.right_edge());
3298 *self.length += 1;
3299 }
3300
3301 /// Inserts a new key-value pair into the map in the gap that the
3302 /// cursor is currently pointing to.
3303 ///
3304 /// After the insertion the cursor will be pointing at the gap before the
3305 /// newly inserted element.
3306 ///
3307 /// If the inserted key is not greater than the key before the cursor
3308 /// (if any), or if it not less than the key after the cursor (if any),
3309 /// then an [`UnorderedKeyError`] is returned since this would
3310 /// invalidate the [`Ord`] invariant between the keys of the map.
3311 #[unstable(feature = "btree_cursors", issue = "107540")]
3312 pub fn insert_after(&mut self, key: K, value: V) -> Result<(), UnorderedKeyError> {
3313 if let Some((prev, _)) = self.peek_prev() {
3314 if &key <= prev {
3315 return Err(UnorderedKeyError {});
3316 }
3317 }
3318 if let Some((next, _)) = self.peek_next() {
3319 if &key >= next {
3320 return Err(UnorderedKeyError {});
3321 }
3322 }
3323 unsafe {
3324 self.insert_after_unchecked(key, value);
3325 }
3326 Ok(())
3327 }
3328
3329 /// Inserts a new key-value pair into the map in the gap that the
3330 /// cursor is currently pointing to.
3331 ///
3332 /// After the insertion the cursor will be pointing at the gap after the
3333 /// newly inserted element.
3334 ///
3335 /// If the inserted key is not greater than the key before the cursor
3336 /// (if any), or if it not less than the key after the cursor (if any),
3337 /// then an [`UnorderedKeyError`] is returned since this would
3338 /// invalidate the [`Ord`] invariant between the keys of the map.
3339 #[unstable(feature = "btree_cursors", issue = "107540")]
3340 pub fn insert_before(&mut self, key: K, value: V) -> Result<(), UnorderedKeyError> {
3341 if let Some((prev, _)) = self.peek_prev() {
3342 if &key <= prev {
3343 return Err(UnorderedKeyError {});
3344 }
3345 }
3346 if let Some((next, _)) = self.peek_next() {
3347 if &key >= next {
3348 return Err(UnorderedKeyError {});
3349 }
3350 }
3351 unsafe {
3352 self.insert_before_unchecked(key, value);
3353 }
3354 Ok(())
3355 }
3356
3357 /// Removes the next element from the `BTreeMap`.
3358 ///
3359 /// The element that was removed is returned. The cursor position is
3360 /// unchanged (before the removed element).
3361 #[unstable(feature = "btree_cursors", issue = "107540")]
3362 pub fn remove_next(&mut self) -> Option<(K, V)> {
3363 let current = self.current.take()?;
3364 if current.reborrow().next_kv().is_err() {
3365 self.current = Some(current);
3366 return None;
3367 }
3368 let mut emptied_internal_root = false;
3369 let (kv, pos) = current
3370 .next_kv()
3371 // This should be unwrap(), but that doesn't work because NodeRef
3372 // doesn't implement Debug. The condition is checked above.
3373 .ok()?
3374 .remove_kv_tracking(|| emptied_internal_root = true, self.alloc.clone());
3375 self.current = Some(pos);
3376 *self.length -= 1;
3377 if emptied_internal_root {
3378 // SAFETY: This is safe since current does not point within the now
3379 // empty root node.
3380 let root = unsafe { self.root.reborrow().as_mut().unwrap() };
3381 root.pop_internal_level(self.alloc.clone());
3382 }
3383 Some(kv)
3384 }
3385
3386 /// Removes the preceding element from the `BTreeMap`.
3387 ///
3388 /// The element that was removed is returned. The cursor position is
3389 /// unchanged (after the removed element).
3390 #[unstable(feature = "btree_cursors", issue = "107540")]
3391 pub fn remove_prev(&mut self) -> Option<(K, V)> {
3392 let current = self.current.take()?;
3393 if current.reborrow().next_back_kv().is_err() {
3394 self.current = Some(current);
3395 return None;
3396 }
3397 let mut emptied_internal_root = false;
3398 let (kv, pos) = current
3399 .next_back_kv()
3400 // This should be unwrap(), but that doesn't work because NodeRef
3401 // doesn't implement Debug. The condition is checked above.
3402 .ok()?
3403 .remove_kv_tracking(|| emptied_internal_root = true, self.alloc.clone());
3404 self.current = Some(pos);
3405 *self.length -= 1;
3406 if emptied_internal_root {
3407 // SAFETY: This is safe since current does not point within the now
3408 // empty root node.
3409 let root = unsafe { self.root.reborrow().as_mut().unwrap() };
3410 root.pop_internal_level(self.alloc.clone());
3411 }
3412 Some(kv)
3413 }
3414}
3415
3416impl<'a, K: Ord, V, A: Allocator + Clone> CursorMut<'a, K, V, A> {
3417 /// Inserts a new key-value pair into the map in the gap that the
3418 /// cursor is currently pointing to.
3419 ///
3420 /// After the insertion the cursor will be pointing at the gap after the
3421 /// newly inserted element.
3422 ///
3423 /// # Safety
3424 ///
3425 /// You must ensure that the `BTreeMap` invariants are maintained.
3426 /// Specifically:
3427 ///
3428 /// * The key of the newly inserted element must be unique in the tree.
3429 /// * All keys in the tree must remain in sorted order.
3430 #[unstable(feature = "btree_cursors", issue = "107540")]
3431 pub unsafe fn insert_after_unchecked(&mut self, key: K, value: V) {
3432 unsafe { self.inner.insert_after_unchecked(key, value) }
3433 }
3434
3435 /// Inserts a new key-value pair into the map in the gap that the
3436 /// cursor is currently pointing to.
3437 ///
3438 /// After the insertion the cursor will be pointing at the gap after the
3439 /// newly inserted element.
3440 ///
3441 /// # Safety
3442 ///
3443 /// You must ensure that the `BTreeMap` invariants are maintained.
3444 /// Specifically:
3445 ///
3446 /// * The key of the newly inserted element must be unique in the tree.
3447 /// * All keys in the tree must remain in sorted order.
3448 #[unstable(feature = "btree_cursors", issue = "107540")]
3449 pub unsafe fn insert_before_unchecked(&mut self, key: K, value: V) {
3450 unsafe { self.inner.insert_before_unchecked(key, value) }
3451 }
3452
3453 /// Inserts a new key-value pair into the map in the gap that the
3454 /// cursor is currently pointing to.
3455 ///
3456 /// After the insertion the cursor will be pointing at the gap before the
3457 /// newly inserted element.
3458 ///
3459 /// If the inserted key is not greater than the key before the cursor
3460 /// (if any), or if it not less than the key after the cursor (if any),
3461 /// then an [`UnorderedKeyError`] is returned since this would
3462 /// invalidate the [`Ord`] invariant between the keys of the map.
3463 #[unstable(feature = "btree_cursors", issue = "107540")]
3464 pub fn insert_after(&mut self, key: K, value: V) -> Result<(), UnorderedKeyError> {
3465 self.inner.insert_after(key, value)
3466 }
3467
3468 /// Inserts a new key-value pair into the map in the gap that the
3469 /// cursor is currently pointing to.
3470 ///
3471 /// After the insertion the cursor will be pointing at the gap after the
3472 /// newly inserted element.
3473 ///
3474 /// If the inserted key is not greater than the key before the cursor
3475 /// (if any), or if it not less than the key after the cursor (if any),
3476 /// then an [`UnorderedKeyError`] is returned since this would
3477 /// invalidate the [`Ord`] invariant between the keys of the map.
3478 #[unstable(feature = "btree_cursors", issue = "107540")]
3479 pub fn insert_before(&mut self, key: K, value: V) -> Result<(), UnorderedKeyError> {
3480 self.inner.insert_before(key, value)
3481 }
3482
3483 /// Removes the next element from the `BTreeMap`.
3484 ///
3485 /// The element that was removed is returned. The cursor position is
3486 /// unchanged (before the removed element).
3487 #[unstable(feature = "btree_cursors", issue = "107540")]
3488 pub fn remove_next(&mut self) -> Option<(K, V)> {
3489 self.inner.remove_next()
3490 }
3491
3492 /// Removes the preceding element from the `BTreeMap`.
3493 ///
3494 /// The element that was removed is returned. The cursor position is
3495 /// unchanged (after the removed element).
3496 #[unstable(feature = "btree_cursors", issue = "107540")]
3497 pub fn remove_prev(&mut self) -> Option<(K, V)> {
3498 self.inner.remove_prev()
3499 }
3500}
3501
3502/// Error type returned by [`CursorMut::insert_before`] and
3503/// [`CursorMut::insert_after`] if the key being inserted is not properly
3504/// ordered with regards to adjacent keys.
3505#[derive(Clone, PartialEq, Eq, Debug)]
3506#[unstable(feature = "btree_cursors", issue = "107540")]
3507pub struct UnorderedKeyError {}
3508
3509#[unstable(feature = "btree_cursors", issue = "107540")]
3510impl fmt::Display for UnorderedKeyError {
3511 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
3512 write!(f, "key is not properly ordered relative to neighbors")
3513 }
3514}
3515
3516#[unstable(feature = "btree_cursors", issue = "107540")]
3517impl Error for UnorderedKeyError {}
3518
3519#[cfg(test)]
3520mod tests;