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