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