map.rs source code [crates/alloc/src/collections/btree/map.rs]

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