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

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