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

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