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

1	use core::borrow::Borrow;
2	use core::cmp::Ordering::{self, Equal, Greater, Less};
3	use core::cmp::{max, min};
4	use core::fmt::{self, Debug};
5	use core::hash::{Hash, Hasher};
6	use core::iter::{FusedIterator, Peekable};
7	use core::mem::ManuallyDrop;
8	use core::ops::{BitAnd, BitOr, BitXor, Bound, RangeBounds, Sub};
9
10	use super::map::{self, BTreeMap, Keys};
11	use super::merge_iter::MergeIterInner;
12	use super::set_val::SetValZST;
13	use crate::alloc::{Allocator, Global};
14	use crate::vec::Vec;
15
16	mod entry;
17
18	#[unstable(feature = "btree_set_entry", issue = "133549")]
19	pub use self::entry::{Entry, OccupiedEntry, VacantEntry};
20
21	/// An ordered set based on a B-Tree.
22	///
23	/// See [`BTreeMap`]'s documentation for a detailed discussion of this collection's performance
24	/// benefits and drawbacks.
25	///
26	/// It is a logic error for an item to be modified in such a way that the item's ordering relative
27	/// to any other item, as determined by the [`Ord`] trait, changes while it is in the set. This is
28	/// normally only possible through [`Cell`], [`RefCell`], global state, I/O, or unsafe code.
29	/// The behavior resulting from such a logic error is not specified, but will be encapsulated to the
30	/// `BTreeSet` that observed the logic error and not result in undefined behavior. This could
31	/// include panics, incorrect results, aborts, memory leaks, and non-termination.
32	///
33	/// Iterators returned by [`BTreeSet::iter`] and [`BTreeSet::into_iter`] produce their items in order, and take worst-case
34	/// logarithmic and amortized constant time per item returned.
35	///
36	/// [`Cell`]: core::cell::Cell
37	/// [`RefCell`]: core::cell::RefCell
38	///
39	/// # Examples
40	///
41	/// ```
42	/// use std::collections::BTreeSet;
43	///
44	/// // Type inference lets us omit an explicit type signature (which
45	/// // would be `BTreeSet<&str>` in this example).
46	/// let mut books = BTreeSet::new();
47	///
48	/// // Add some books.
49	/// books.insert("A Dance With Dragons");
50	/// books.insert("To Kill a Mockingbird");
51	/// books.insert("The Odyssey");
52	/// books.insert("The Great Gatsby");
53	///
54	/// // Check for a specific one.
55	/// if !books.contains("The Winds of Winter") {
56	/// println!("We have {} books, but The Winds of Winter ain't one.",
57	/// books.len());
58	/// }
59	///
60	/// // Remove a book.
61	/// books.remove("The Odyssey");
62	///
63	/// // Iterate over everything.
64	/// for book in &books {
65	/// println!("{book}");
66	/// }
67	/// ```
68	///
69	/// A `BTreeSet` with a known list of items can be initialized from an array:
70	///
71	/// ```
72	/// use std::collections::BTreeSet;
73	///
74	/// let set = BTreeSet::from([`1`, `2`, `3`]);
75	/// ```
76	#[stable(feature = "rust1", since = "1.0.0")]
77	#[cfg_attr(not(test), rustc_diagnostic_item = "BTreeSet")]
78	pub struct BTreeSet<
79	T,
80	#[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + Clone = Global,
81	> {
82	map: BTreeMap<T, SetValZST, A>,
83	}
84
85	#[stable(feature = "rust1", since = "1.0.0")]
86	impl<T: Hash, A: Allocator + Clone> Hash for BTreeSet<T, A> {
87	fn hash<H: Hasher>(&self, state: &mut H) {
88	self.map.hash(state)
89	}
90	}
91
92	#[stable(feature = "rust1", since = "1.0.0")]
93	impl<T: PartialEq, A: Allocator + Clone> PartialEq for BTreeSet<T, A> {
94	fn eq(&self, other: &BTreeSet<T, A>) -> bool {
95	self.map.eq(&other.map)
96	}
97	}
98
99	#[stable(feature = "rust1", since = "1.0.0")]
100	impl<T: Eq, A: Allocator + Clone> Eq for BTreeSet<T, A> {}
101
102	#[stable(feature = "rust1", since = "1.0.0")]
103	impl<T: PartialOrd, A: Allocator + Clone> PartialOrd for BTreeSet<T, A> {
104	fn partial_cmp(&self, other: &BTreeSet<T, A>) -> Option<Ordering> {
105	self.map.partial_cmp(&other.map)
106	}
107	}
108
109	#[stable(feature = "rust1", since = "1.0.0")]
110	impl<T: Ord, A: Allocator + Clone> Ord for BTreeSet<T, A> {
111	fn cmp(&self, other: &BTreeSet<T, A>) -> Ordering {
112	self.map.cmp(&other.map)
113	}
114	}
115
116	#[stable(feature = "rust1", since = "1.0.0")]
117	impl<T: Clone, A: Allocator + Clone> Clone for BTreeSet<T, A> {
118	fn clone(&self) -> Self {
119	BTreeSet { map: self.map.clone() }
120	}
121
122	fn clone_from(&mut self, source: &Self) {
123	self.map.clone_from(&source.map);
124	}
125	}
126
127	/// An iterator over the items of a `BTreeSet`.
128	///
129	/// This `struct` is created by the [`iter`] method on [`BTreeSet`].
130	/// See its documentation for more.
131	///
132	/// [`iter`]: BTreeSet::iter
133	#[must_use = "iterators are lazy and do nothing unless consumed"]
134	#[stable(feature = "rust1", since = "1.0.0")]
135	pub struct Iter<'a, T: 'a> {
136	iter: Keys<'a, T, SetValZST>,
137	}
138
139	#[stable(feature = "collection_debug", since = "1.17.0")]
140	impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> {
141	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
142	f.debug_tuple(name:"Iter").field(&self.iter).finish()
143	}
144	}
145
146	/// An owning iterator over the items of a `BTreeSet` in ascending order.
147	///
148	/// This `struct` is created by the [`into_iter`] method on [`BTreeSet`]
149	/// (provided by the [`IntoIterator`] trait). See its documentation for more.
150	///
151	/// [`into_iter`]: BTreeSet#method.into_iter
152	#[stable(feature = "rust1", since = "1.0.0")]
153	#[derive(Debug)]
154	pub struct IntoIter<
155	T,
156	#[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + Clone = Global,
157	> {
158	iter: super::map::IntoIter<T, SetValZST, A>,
159	}
160
161	/// An iterator over a sub-range of items in a `BTreeSet`.
162	///
163	/// This `struct` is created by the [`range`] method on [`BTreeSet`].
164	/// See its documentation for more.
165	///
166	/// [`range`]: BTreeSet::range
167	#[must_use = "iterators are lazy and do nothing unless consumed"]
168	#[derive(Debug)]
169	#[stable(feature = "btree_range", since = "1.17.0")]
170	pub struct Range<'a, T: 'a> {
171	iter: super::map::Range<'a, T, SetValZST>,
172	}
173
174	/// A lazy iterator producing elements in the difference of `BTreeSet`s.
175	///
176	/// This `struct` is created by the [`difference`] method on [`BTreeSet`].
177	/// See its documentation for more.
178	///
179	/// [`difference`]: BTreeSet::difference
180	#[must_use = "this returns the difference as an iterator, \
181	without modifying either input set"]
182	#[stable(feature = "rust1", since = "1.0.0")]
183	pub struct Difference<
184	'a,
185	T: 'a,
186	#[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + Clone = Global,
187	> {
188	inner: DifferenceInner<'a, T, A>,
189	}
190	enum DifferenceInner<'a, T: 'a, A: Allocator + Clone> {
191	Stitch {
192	// iterate all of `self` and some of `other`, spotting matches along the way
193	self_iter: Iter<'a, T>,
194	other_iter: Peekable<Iter<'a, T>>,
195	},
196	Search {
197	// iterate `self`, look up in `other`
198	self_iter: Iter<'a, T>,
199	other_set: &'a BTreeSet<T, A>,
200	},
201	Iterate(Iter<'a, T>), // simply produce all elements in `self`
202	}
203
204	// Explicit Debug impl necessary because of issue #26925
205	impl<T: Debug, A: Allocator + Clone> Debug for DifferenceInner<'_, T, A> {
206	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
207	match self {
208	DifferenceInner::Stitch { self_iter: &Iter<'_, T>, other_iter: &Peekable> } => f&mut DebugStruct<'_, '_>
209	.debug_struct("Stitch")
210	.field("self_iter", self_iter)
211	.field(name:"other_iter", value:other_iter)
212	.finish(),
213	DifferenceInner::Search { self_iter: &Iter<'_, T>, other_set: &&BTreeSet } => f&mut DebugStruct<'_, '_>
214	.debug_struct("Search")
215	.field("self_iter", self_iter)
216	.field(name:"other_iter", value:other_set)
217	.finish(),
218	DifferenceInner::Iterate(x: &Iter<'_, T>) => f.debug_tuple(name:"Iterate").field(x).finish(),
219	}
220	}
221	}
222
223	#[stable(feature = "collection_debug", since = "1.17.0")]
224	impl<T: fmt::Debug, A: Allocator + Clone> fmt::Debug for Difference<'_, T, A> {
225	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
226	f.debug_tuple(name:"Difference").field(&self.inner).finish()
227	}
228	}
229
230	/// A lazy iterator producing elements in the symmetric difference of `BTreeSet`s.
231	///
232	/// This `struct` is created by the [`symmetric_difference`] method on
233	/// [`BTreeSet`]. See its documentation for more.
234	///
235	/// [`symmetric_difference`]: BTreeSet::symmetric_difference
236	#[must_use = "this returns the difference as an iterator, \
237	without modifying either input set"]
238	#[stable(feature = "rust1", since = "1.0.0")]
239	pub struct SymmetricDifference<'a, T: 'a>(MergeIterInner<Iter<'a, T>>);
240
241	#[stable(feature = "collection_debug", since = "1.17.0")]
242	impl<T: fmt::Debug> fmt::Debug for SymmetricDifference<'_, T> {
243	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
244	f.debug_tuple(name:"SymmetricDifference").field(&self.0).finish()
245	}
246	}
247
248	/// A lazy iterator producing elements in the intersection of `BTreeSet`s.
249	///
250	/// This `struct` is created by the [`intersection`] method on [`BTreeSet`].
251	/// See its documentation for more.
252	///
253	/// [`intersection`]: BTreeSet::intersection
254	#[must_use = "this returns the intersection as an iterator, \
255	without modifying either input set"]
256	#[stable(feature = "rust1", since = "1.0.0")]
257	pub struct Intersection<
258	'a,
259	T: 'a,
260	#[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + Clone = Global,
261	> {
262	inner: IntersectionInner<'a, T, A>,
263	}
264	enum IntersectionInner<'a, T: 'a, A: Allocator + Clone> {
265	Stitch {
266	// iterate similarly sized sets jointly, spotting matches along the way
267	a: Iter<'a, T>,
268	b: Iter<'a, T>,
269	},
270	Search {
271	// iterate a small set, look up in the large set
272	small_iter: Iter<'a, T>,
273	large_set: &'a BTreeSet<T, A>,
274	},
275	Answer(Option<&'a T>), // return a specific element or emptiness
276	}
277
278	// Explicit Debug impl necessary because of issue #26925
279	impl<T: Debug, A: Allocator + Clone> Debug for IntersectionInner<'_, T, A> {
280	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
281	match self {
282	IntersectionInner::Stitch { a: &Iter<'_, T>, b: &Iter<'_, T> } => {
283	f.debug_struct("Stitch").field("a", a).field(name:"b", value:b).finish()
284	}
285	IntersectionInner::Search { small_iter: &Iter<'_, T>, large_set: &&BTreeSet } => f&mut DebugStruct<'_, '_>
286	.debug_struct("Search")
287	.field("small_iter", small_iter)
288	.field(name:"large_set", value:large_set)
289	.finish(),
290	IntersectionInner::Answer(x: &Option<&T>) => f.debug_tuple(name:"Answer").field(x).finish(),
291	}
292	}
293	}
294
295	#[stable(feature = "collection_debug", since = "1.17.0")]
296	impl<T: Debug, A: Allocator + Clone> Debug for Intersection<'_, T, A> {
297	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
298	f.debug_tuple(name:"Intersection").field(&self.inner).finish()
299	}
300	}
301
302	/// A lazy iterator producing elements in the union of `BTreeSet`s.
303	///
304	/// This `struct` is created by the [`union`] method on [`BTreeSet`].
305	/// See its documentation for more.
306	///
307	/// [`union`]: BTreeSet::union
308	#[must_use = "this returns the union as an iterator, \
309	without modifying either input set"]
310	#[stable(feature = "rust1", since = "1.0.0")]
311	pub struct Union<'a, T: 'a>(MergeIterInner<Iter<'a, T>>);
312
313	#[stable(feature = "collection_debug", since = "1.17.0")]
314	impl<T: fmt::Debug> fmt::Debug for Union<'_, T> {
315	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
316	f.debug_tuple(name:"Union").field(&self.0).finish()
317	}
318	}
319
320	// This constant is used by functions that compare two sets.
321	// It estimates the relative size at which searching performs better
322	// than iterating, based on the benchmarks in
323	// https://github.com/ssomers/rust_bench_btreeset_intersection.
324	// It's used to divide rather than multiply sizes, to rule out overflow,
325	// and it's a power of two to make that division cheap.
326	const ITER_PERFORMANCE_TIPPING_SIZE_DIFF: usize = `16`;
327
328	impl<T> BTreeSet<T> {
329	/// Makes a new, empty `BTreeSet`.
330	///
331	/// Does not allocate anything on its own.
332	///
333	/// # Examples
334	///
335	/// ```
336	/// # #![allow(unused_mut)]
337	/// use std::collections::BTreeSet;
338	///
339	/// let mut set: BTreeSet<i32> = BTreeSet::new();
340	/// ```
341	#[stable(feature = "rust1", since = "1.0.0")]
342	#[rustc_const_stable(feature = "const_btree_new", since = "1.66.0")]
343	#[must_use]
344	pub const fn new() -> BTreeSet<T> {
345	BTreeSet { map: BTreeMap::new() }
346	}
347	}
348
349	impl<T, A: Allocator + Clone> BTreeSet<T, A> {
350	/// Makes a new `BTreeSet` with a reasonable choice of B.
351	///
352	/// # Examples
353	///
354	/// ```
355	/// # #![allow(unused_mut)]
356	/// # #![feature(allocator_api)]
357	/// # #![feature(btreemap_alloc)]
358	/// use std::collections::BTreeSet;
359	/// use std::alloc::Global;
360	///
361	/// let mut set: BTreeSet<i32> = BTreeSet::new_in(Global);
362	/// ```
363	#[unstable(feature = "btreemap_alloc", issue = "32838")]
364	pub const fn new_in(alloc: A) -> BTreeSet<T, A> {
365	BTreeSet { map: BTreeMap::new_in(alloc) }
366	}
367
368	/// Constructs a double-ended iterator over a sub-range of elements in the set.
369	/// The simplest way is to use the range syntax `min..max`, thus `range(min..max)` will
370	/// yield elements from min (inclusive) to max (exclusive).
371	/// The range may also be entered as `(Bound<T>, Bound<T>)`, so for example
372	/// `range((Excluded(4), Included(10)))` will yield a left-exclusive, right-inclusive
373	/// range from 4 to 10.
374	///
375	/// # Panics
376	///
377	/// Panics if range `start > end`.
378	/// Panics if range `start == end` and both bounds are `Excluded`.
379	///
380	/// # Examples
381	///
382	/// ```
383	/// use std::collections::BTreeSet;
384	/// use std::ops::Bound::Included;
385	///
386	/// let mut set = BTreeSet::new();
387	/// set.insert(`3`);
388	/// set.insert(`5`);
389	/// set.insert(`8`);
390	/// for &elem in set.range((Included(&`4`), Included(&`8`))) {
391	/// println!("{elem}");
392	/// }
393	/// assert_eq!(Some(&`5`), set.range(`4`..).next());
394	/// ```
395	#[stable(feature = "btree_range", since = "1.17.0")]
396	pub fn range<K: ?Sized, R>(&self, range: R) -> Range<'_, T>
397	where
398	K: Ord,
399	T: Borrow<K> + Ord,
400	R: RangeBounds<K>,
401	{
402	Range { iter: self.map.range(range) }
403	}
404
405	/// Visits the elements representing the difference,
406	/// i.e., the elements that are in `self` but not in `other`,
407	/// in ascending order.
408	///
409	/// # Examples
410	///
411	/// ```
412	/// use std::collections::BTreeSet;
413	///
414	/// let mut a = BTreeSet::new();
415	/// a.insert(`1`);
416	/// a.insert(`2`);
417	///
418	/// let mut b = BTreeSet::new();
419	/// b.insert(`2`);
420	/// b.insert(`3`);
421	///
422	/// let diff: Vec<_> = a.difference(&b).cloned().collect();
423	/// assert_eq!(diff, [`1`]);
424	/// ```
425	#[stable(feature = "rust1", since = "1.0.0")]
426	pub fn difference<'a>(&'a self, other: &'a BTreeSet<T, A>) -> Difference<'a, T, A>
427	where
428	T: Ord,
429	{
430	let (self_min, self_max) =
431	if let (Some(self_min), Some(self_max)) = (self.first(), self.last()) {
432	(self_min, self_max)
433	} else {
434	return Difference { inner: DifferenceInner::Iterate(self.iter()) };
435	};
436	let (other_min, other_max) =
437	if let (Some(other_min), Some(other_max)) = (other.first(), other.last()) {
438	(other_min, other_max)
439	} else {
440	return Difference { inner: DifferenceInner::Iterate(self.iter()) };
441	};
442	Difference {
443	inner: match (self_min.cmp(other_max), self_max.cmp(other_min)) {
444	(Greater, _) \| (_, Less) => DifferenceInner::Iterate(self.iter()),
445	(Equal, _) => {
446	let mut self_iter = self.iter();
447	self_iter.next();
448	DifferenceInner::Iterate(self_iter)
449	}
450	(_, Equal) => {
451	let mut self_iter = self.iter();
452	self_iter.next_back();
453	DifferenceInner::Iterate(self_iter)
454	}
455	_ if self.len() <= other.len() / ITER_PERFORMANCE_TIPPING_SIZE_DIFF => {
456	DifferenceInner::Search { self_iter: self.iter(), other_set: other }
457	}
458	_ => DifferenceInner::Stitch {
459	self_iter: self.iter(),
460	other_iter: other.iter().peekable(),
461	},
462	},
463	}
464	}
465
466	/// Visits the elements representing the symmetric difference,
467	/// i.e., the elements that are in `self` or in `other` but not in both,
468	/// in ascending order.
469	///
470	/// # Examples
471	///
472	/// ```
473	/// use std::collections::BTreeSet;
474	///
475	/// let mut a = BTreeSet::new();
476	/// a.insert(`1`);
477	/// a.insert(`2`);
478	///
479	/// let mut b = BTreeSet::new();
480	/// b.insert(`2`);
481	/// b.insert(`3`);
482	///
483	/// let sym_diff: Vec<_> = a.symmetric_difference(&b).cloned().collect();
484	/// assert_eq!(sym_diff, [`1`, `3`]);
485	/// ```
486	#[stable(feature = "rust1", since = "1.0.0")]
487	pub fn symmetric_difference<'a>(
488	&'a self,
489	other: &'a BTreeSet<T, A>,
490	) -> SymmetricDifference<'a, T>
491	where
492	T: Ord,
493	{
494	SymmetricDifference(MergeIterInner::new(self.iter(), other.iter()))
495	}
496
497	/// Visits the elements representing the intersection,
498	/// i.e., the elements that are both in `self` and `other`,
499	/// in ascending order.
500	///
501	/// # Examples
502	///
503	/// ```
504	/// use std::collections::BTreeSet;
505	///
506	/// let mut a = BTreeSet::new();
507	/// a.insert(`1`);
508	/// a.insert(`2`);
509	///
510	/// let mut b = BTreeSet::new();
511	/// b.insert(`2`);
512	/// b.insert(`3`);
513	///
514	/// let intersection: Vec<_> = a.intersection(&b).cloned().collect();
515	/// assert_eq!(intersection, [`2`]);
516	/// ```
517	#[stable(feature = "rust1", since = "1.0.0")]
518	pub fn intersection<'a>(&'a self, other: &'a BTreeSet<T, A>) -> Intersection<'a, T, A>
519	where
520	T: Ord,
521	{
522	let (self_min, self_max) =
523	if let (Some(self_min), Some(self_max)) = (self.first(), self.last()) {
524	(self_min, self_max)
525	} else {
526	return Intersection { inner: IntersectionInner::Answer(None) };
527	};
528	let (other_min, other_max) =
529	if let (Some(other_min), Some(other_max)) = (other.first(), other.last()) {
530	(other_min, other_max)
531	} else {
532	return Intersection { inner: IntersectionInner::Answer(None) };
533	};
534	Intersection {
535	inner: match (self_min.cmp(other_max), self_max.cmp(other_min)) {
536	(Greater, _) \| (_, Less) => IntersectionInner::Answer(None),
537	(Equal, _) => IntersectionInner::Answer(Some(self_min)),
538	(_, Equal) => IntersectionInner::Answer(Some(self_max)),
539	_ if self.len() <= other.len() / ITER_PERFORMANCE_TIPPING_SIZE_DIFF => {
540	IntersectionInner::Search { small_iter: self.iter(), large_set: other }
541	}
542	_ if other.len() <= self.len() / ITER_PERFORMANCE_TIPPING_SIZE_DIFF => {
543	IntersectionInner::Search { small_iter: other.iter(), large_set: self }
544	}
545	_ => IntersectionInner::Stitch { a: self.iter(), b: other.iter() },
546	},
547	}
548	}
549
550	/// Visits the elements representing the union,
551	/// i.e., all the elements in `self` or `other`, without duplicates,
552	/// in ascending order.
553	///
554	/// # Examples
555	///
556	/// ```
557	/// use std::collections::BTreeSet;
558	///
559	/// let mut a = BTreeSet::new();
560	/// a.insert(`1`);
561	///
562	/// let mut b = BTreeSet::new();
563	/// b.insert(`2`);
564	///
565	/// let union: Vec<_> = a.union(&b).cloned().collect();
566	/// assert_eq!(union, [`1`, `2`]);
567	/// ```
568	#[stable(feature = "rust1", since = "1.0.0")]
569	pub fn union<'a>(&'a self, other: &'a BTreeSet<T, A>) -> Union<'a, T>
570	where
571	T: Ord,
572	{
573	Union(MergeIterInner::new(self.iter(), other.iter()))
574	}
575
576	/// Clears the set, removing all elements.
577	///
578	/// # Examples
579	///
580	/// ```
581	/// use std::collections::BTreeSet;
582	///
583	/// let mut v = BTreeSet::new();
584	/// v.insert(`1`);
585	/// v.clear();
586	/// assert!(v.is_empty());
587	/// ```
588	#[stable(feature = "rust1", since = "1.0.0")]
589	pub fn clear(&mut self)
590	where
591	A: Clone,
592	{
593	self.map.clear()
594	}
595
596	/// Returns `true` if the set contains an element equal to the value.
597	///
598	/// The value may be any borrowed form of the set's element type,
599	/// but the ordering on the borrowed form must* match the*
600	/// ordering on the element type.
601	///
602	/// # Examples
603	///
604	/// ```
605	/// use std::collections::BTreeSet;
606	///
607	/// let set = BTreeSet::from([`1`, `2`, `3`]);
608	/// assert_eq!(set.contains(&`1`), `true`);
609	/// assert_eq!(set.contains(&`4`), `false`);
610	/// ```
611	#[stable(feature = "rust1", since = "1.0.0")]
612	pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool
613	where
614	T: Borrow<Q> + Ord,
615	Q: Ord,
616	{
617	self.map.contains_key(value)
618	}
619
620	/// Returns a reference to the element in the set, if any, that is equal to
621	/// the value.
622	///
623	/// The value may be any borrowed form of the set's element type,
624	/// but the ordering on the borrowed form must* match the*
625	/// ordering on the element type.
626	///
627	/// # Examples
628	///
629	/// ```
630	/// use std::collections::BTreeSet;
631	///
632	/// let set = BTreeSet::from([`1`, `2`, `3`]);
633	/// assert_eq!(set.get(&`2`), Some(&`2`));
634	/// assert_eq!(set.get(&`4`), None);
635	/// ```
636	#[stable(feature = "set_recovery", since = "1.9.0")]
637	pub fn get<Q: ?Sized>(&self, value: &Q) -> Option<&T>
638	where
639	T: Borrow<Q> + Ord,
640	Q: Ord,
641	{
642	self.map.get_key_value(value).map(\|(k, _)\| k)
643	}
644
645	/// Returns `true` if `self` has no elements in common with `other`.
646	/// This is equivalent to checking for an empty intersection.
647	///
648	/// # Examples
649	///
650	/// ```
651	/// use std::collections::BTreeSet;
652	///
653	/// let a = BTreeSet::from([`1`, `2`, `3`]);
654	/// let mut b = BTreeSet::new();
655	///
656	/// assert_eq!(a.is_disjoint(&b), `true`);
657	/// b.insert(`4`);
658	/// assert_eq!(a.is_disjoint(&b), `true`);
659	/// b.insert(`1`);
660	/// assert_eq!(a.is_disjoint(&b), `false`);
661	/// ```
662	#[must_use]
663	#[stable(feature = "rust1", since = "1.0.0")]
664	pub fn is_disjoint(&self, other: &BTreeSet<T, A>) -> bool
665	where
666	T: Ord,
667	{
668	self.intersection(other).next().is_none()
669	}
670
671	/// Returns `true` if the set is a subset of another,
672	/// i.e., `other` contains at least all the elements in `self`.
673	///
674	/// # Examples
675	///
676	/// ```
677	/// use std::collections::BTreeSet;
678	///
679	/// let sup = BTreeSet::from([`1`, `2`, `3`]);
680	/// let mut set = BTreeSet::new();
681	///
682	/// assert_eq!(set.is_subset(&sup), `true`);
683	/// set.insert(`2`);
684	/// assert_eq!(set.is_subset(&sup), `true`);
685	/// set.insert(`4`);
686	/// assert_eq!(set.is_subset(&sup), `false`);
687	/// ```
688	#[must_use]
689	#[stable(feature = "rust1", since = "1.0.0")]
690	pub fn is_subset(&self, other: &BTreeSet<T, A>) -> bool
691	where
692	T: Ord,
693	{
694	// Same result as self.difference(other).next().is_none()
695	// but the code below is faster (hugely in some cases).
696	if self.len() > other.len() {
697	return `false`;
698	}
699	let (self_min, self_max) =
700	if let (Some(self_min), Some(self_max)) = (self.first(), self.last()) {
701	(self_min, self_max)
702	} else {
703	return `true`; // self is empty
704	};
705	let (other_min, other_max) =
706	if let (Some(other_min), Some(other_max)) = (other.first(), other.last()) {
707	(other_min, other_max)
708	} else {
709	return `false`; // other is empty
710	};
711	let mut self_iter = self.iter();
712	match self_min.cmp(other_min) {
713	Less => return `false`,
714	Equal => {
715	self_iter.next();
716	}
717	Greater => (),
718	}
719	match self_max.cmp(other_max) {
720	Greater => return `false`,
721	Equal => {
722	self_iter.next_back();
723	}
724	Less => (),
725	}
726	if self_iter.len() <= other.len() / ITER_PERFORMANCE_TIPPING_SIZE_DIFF {
727	for next in self_iter {
728	if !other.contains(next) {
729	return `false`;
730	}
731	}
732	} else {
733	let mut other_iter = other.iter();
734	other_iter.next();
735	other_iter.next_back();
736	let mut self_next = self_iter.next();
737	while let Some(self1) = self_next {
738	match other_iter.next().map_or(Less, \|other1\| self1.cmp(other1)) {
739	Less => return `false`,
740	Equal => self_next = self_iter.next(),
741	Greater => (),
742	}
743	}
744	}
745	`true`
746	}
747
748	/// Returns `true` if the set is a superset of another,
749	/// i.e., `self` contains at least all the elements in `other`.
750	///
751	/// # Examples
752	///
753	/// ```
754	/// use std::collections::BTreeSet;
755	///
756	/// let sub = BTreeSet::from([`1`, `2`]);
757	/// let mut set = BTreeSet::new();
758	///
759	/// assert_eq!(set.is_superset(&sub), `false`);
760	///
761	/// set.insert(`0`);
762	/// set.insert(`1`);
763	/// assert_eq!(set.is_superset(&sub), `false`);
764	///
765	/// set.insert(`2`);
766	/// assert_eq!(set.is_superset(&sub), `true`);
767	/// ```
768	#[must_use]
769	#[stable(feature = "rust1", since = "1.0.0")]
770	pub fn is_superset(&self, other: &BTreeSet<T, A>) -> bool
771	where
772	T: Ord,
773	{
774	other.is_subset(self)
775	}
776
777	/// Returns a reference to the first element in the set, if any.
778	/// This element is always the minimum of all elements in the set.
779	///
780	/// # Examples
781	///
782	/// Basic usage:
783	///
784	/// ```
785	/// use std::collections::BTreeSet;
786	///
787	/// let mut set = BTreeSet::new();
788	/// assert_eq!(set.first(), None);
789	/// set.insert(`1`);
790	/// assert_eq!(set.first(), Some(&`1`));
791	/// set.insert(`2`);
792	/// assert_eq!(set.first(), Some(&`1`));
793	/// ```
794	#[must_use]
795	#[stable(feature = "map_first_last", since = "1.66.0")]
796	#[rustc_confusables("front")]
797	pub fn first(&self) -> Option<&T>
798	where
799	T: Ord,
800	{
801	self.map.first_key_value().map(\|(k, _)\| k)
802	}
803
804	/// Returns a reference to the last element in the set, if any.
805	/// This element is always the maximum of all elements in the set.
806	///
807	/// # Examples
808	///
809	/// Basic usage:
810	///
811	/// ```
812	/// use std::collections::BTreeSet;
813	///
814	/// let mut set = BTreeSet::new();
815	/// assert_eq!(set.last(), None);
816	/// set.insert(`1`);
817	/// assert_eq!(set.last(), Some(&`1`));
818	/// set.insert(`2`);
819	/// assert_eq!(set.last(), Some(&`2`));
820	/// ```
821	#[must_use]
822	#[stable(feature = "map_first_last", since = "1.66.0")]
823	#[rustc_confusables("back")]
824	pub fn last(&self) -> Option<&T>
825	where
826	T: Ord,
827	{
828	self.map.last_key_value().map(\|(k, _)\| k)
829	}
830
831	/// Removes the first element from the set and returns it, if any.
832	/// The first element is always the minimum element in the set.
833	///
834	/// # Examples
835	///
836	/// ```
837	/// use std::collections::BTreeSet;
838	///
839	/// let mut set = BTreeSet::new();
840	///
841	/// set.insert(`1`);
842	/// while let Some(n) = set.pop_first() {
843	/// assert_eq!(n, `1`);
844	/// }
845	/// assert!(set.is_empty());
846	/// ```
847	#[stable(feature = "map_first_last", since = "1.66.0")]
848	pub fn pop_first(&mut self) -> Option<T>
849	where
850	T: Ord,
851	{
852	self.map.pop_first().map(\|kv\| kv.0)
853	}
854
855	/// Removes the last element from the set and returns it, if any.
856	/// The last element is always the maximum element in the set.
857	///
858	/// # Examples
859	///
860	/// ```
861	/// use std::collections::BTreeSet;
862	///
863	/// let mut set = BTreeSet::new();
864	///
865	/// set.insert(`1`);
866	/// while let Some(n) = set.pop_last() {
867	/// assert_eq!(n, `1`);
868	/// }
869	/// assert!(set.is_empty());
870	/// ```
871	#[stable(feature = "map_first_last", since = "1.66.0")]
872	pub fn pop_last(&mut self) -> Option<T>
873	where
874	T: Ord,
875	{
876	self.map.pop_last().map(\|kv\| kv.0)
877	}
878
879	/// Adds a value to the set.
880	///
881	/// Returns whether the value was newly inserted. That is:
882	///
883	/// - If the set did not previously contain an equal value, `true` is
884	/// returned.
885	/// - If the set already contained an equal value, `false` is returned, and
886	/// the entry is not updated.
887	///
888	/// See the [module-level documentation] for more.
889	///
890	/// [module-level documentation]: index.html#insert-and-complex-keys
891	///
892	/// # Examples
893	///
894	/// ```
895	/// use std::collections::BTreeSet;
896	///
897	/// let mut set = BTreeSet::new();
898	///
899	/// assert_eq!(set.insert(`2`), `true`);
900	/// assert_eq!(set.insert(`2`), `false`);
901	/// assert_eq!(set.len(), `1`);
902	/// ```
903	#[stable(feature = "rust1", since = "1.0.0")]
904	#[rustc_confusables("push", "put")]
905	pub fn insert(&mut self, value: T) -> bool
906	where
907	T: Ord,
908	{
909	self.map.insert(value, SetValZST::default()).is_none()
910	}
911
912	/// Adds a value to the set, replacing the existing element, if any, that is
913	/// equal to the value. Returns the replaced element.
914	///
915	/// # Examples
916	///
917	/// ```
918	/// use std::collections::BTreeSet;
919	///
920	/// let mut set = BTreeSet::new();
921	/// set.insert(Vec::<i32>::new());
922	///
923	/// assert_eq!(set.get(&[][..]).unwrap().capacity(), `0`);
924	/// set.replace(Vec::with_capacity(`10`));
925	/// assert_eq!(set.get(&[][..]).unwrap().capacity(), `10`);
926	/// ```
927	#[stable(feature = "set_recovery", since = "1.9.0")]
928	#[rustc_confusables("swap")]
929	pub fn replace(&mut self, value: T) -> Option<T>
930	where
931	T: Ord,
932	{
933	self.map.replace(value)
934	}
935
936	/// Inserts the given `value` into the set if it is not present, then
937	/// returns a reference to the value in the set.
938	///
939	/// # Examples
940	///
941	/// ```
942	/// #![feature(btree_set_entry)]
943	///
944	/// use std::collections::BTreeSet;
945	///
946	/// let mut set = BTreeSet::from([`1`, `2`, `3`]);
947	/// assert_eq!(set.len(), `3`);
948	/// assert_eq!(set.get_or_insert(`2`), &`2`);
949	/// assert_eq!(set.get_or_insert(`100`), &`100`);
950	/// assert_eq!(set.len(), `4`); // 100 was inserted
951	/// ```
952	#[inline]
953	#[unstable(feature = "btree_set_entry", issue = "133549")]
954	pub fn get_or_insert(&mut self, value: T) -> &T
955	where
956	T: Ord,
957	{
958	self.map.entry(value).insert_entry(SetValZST).into_key()
959	}
960
961	/// Inserts a value computed from `f` into the set if the given `value` is
962	/// not present, then returns a reference to the value in the set.
963	///
964	/// # Examples
965	///
966	/// ```
967	/// #![feature(btree_set_entry)]
968	///
969	/// use std::collections::BTreeSet;
970	///
971	/// let mut set: BTreeSet<String> = ["cat", "dog", "horse"]
972	/// .iter().map(\|&pet\| pet.to_owned()).collect();
973	///
974	/// assert_eq!(set.len(), `3`);
975	/// for &pet in &["cat", "dog", "fish"] {
976	/// let value = set.get_or_insert_with(pet, str::to_owned);
977	/// assert_eq!(value, pet);
978	/// }
979	/// assert_eq!(set.len(), `4`); // a new "fish" was inserted
980	/// ```
981	#[inline]
982	#[unstable(feature = "btree_set_entry", issue = "133549")]
983	pub fn get_or_insert_with<Q: ?Sized, F>(&mut self, value: &Q, f: F) -> &T
984	where
985	T: Borrow<Q> + Ord,
986	Q: Ord,
987	F: FnOnce(&Q) -> T,
988	{
989	self.map.get_or_insert_with(value, f)
990	}
991
992	/// Gets the given value's corresponding entry in the set for in-place manipulation.
993	///
994	/// # Examples
995	///
996	/// ```
997	/// #![feature(btree_set_entry)]
998	///
999	/// use std::collections::BTreeSet;
1000	/// use std::collections::btree_set::Entry::*;
1001	///
1002	/// let mut singles = BTreeSet::new();
1003	/// let mut dupes = BTreeSet::new();
1004	///
1005	/// for ch in "a short treatise on fungi".chars() {
1006	/// if let Vacant(dupe_entry) = dupes.entry(ch) {
1007	/// // We haven't already seen a duplicate, so
1008	/// // check if we've at least seen it once.
1009	/// match singles.entry(ch) {
1010	/// Vacant(single_entry) => {
1011	/// // We found a new character for the first time.
1012	/// single_entry.insert()
1013	/// }
1014	/// Occupied(single_entry) => {
1015	/// // We've already seen this once, "move" it to dupes.
1016	/// single_entry.remove();
1017	/// dupe_entry.insert();
1018	/// }
1019	/// }
1020	/// }
1021	/// }
1022	///
1023	/// assert!(!singles.contains(&'t') && dupes.contains(&'t'));
1024	/// assert!(singles.contains(&'u') && !dupes.contains(&'u'));
1025	/// assert!(!singles.contains(&'v') && !dupes.contains(&'v'));
1026	/// ```
1027	#[inline]
1028	#[unstable(feature = "btree_set_entry", issue = "133549")]
1029	pub fn entry(&mut self, value: T) -> Entry<'_, T, A>
1030	where
1031	T: Ord,
1032	{
1033	match self.map.entry(value) {
1034	map::Entry::Occupied(entry) => Entry::Occupied(OccupiedEntry { inner: entry }),
1035	map::Entry::Vacant(entry) => Entry::Vacant(VacantEntry { inner: entry }),
1036	}
1037	}
1038
1039	/// If the set contains an element equal to the value, removes it from the
1040	/// set and drops it. Returns whether such an element was present.
1041	///
1042	/// The value may be any borrowed form of the set's element type,
1043	/// but the ordering on the borrowed form must* match the*
1044	/// ordering on the element type.
1045	///
1046	/// # Examples
1047	///
1048	/// ```
1049	/// use std::collections::BTreeSet;
1050	///
1051	/// let mut set = BTreeSet::new();
1052	///
1053	/// set.insert(`2`);
1054	/// assert_eq!(set.remove(&`2`), `true`);
1055	/// assert_eq!(set.remove(&`2`), `false`);
1056	/// ```
1057	#[stable(feature = "rust1", since = "1.0.0")]
1058	pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool
1059	where
1060	T: Borrow<Q> + Ord,
1061	Q: Ord,
1062	{
1063	self.map.remove(value).is_some()
1064	}
1065
1066	/// Removes and returns the element in the set, if any, that is equal to
1067	/// the value.
1068	///
1069	/// The value may be any borrowed form of the set's element type,
1070	/// but the ordering on the borrowed form must* match the*
1071	/// ordering on the element type.
1072	///
1073	/// # Examples
1074	///
1075	/// ```
1076	/// use std::collections::BTreeSet;
1077	///
1078	/// let mut set = BTreeSet::from([`1`, `2`, `3`]);
1079	/// assert_eq!(set.take(&`2`), Some(`2`));
1080	/// assert_eq!(set.take(&`2`), None);
1081	/// ```
1082	#[stable(feature = "set_recovery", since = "1.9.0")]
1083	pub fn take<Q: ?Sized>(&mut self, value: &Q) -> Option<T>
1084	where
1085	T: Borrow<Q> + Ord,
1086	Q: Ord,
1087	{
1088	self.map.remove_entry(value).map(\|(k, _)\| k)
1089	}
1090
1091	/// Retains only the elements specified by the predicate.
1092	///
1093	/// In other words, remove all elements `e` for which `f(&e)` returns `false`.
1094	/// The elements are visited in ascending order.
1095	///
1096	/// # Examples
1097	///
1098	/// ```
1099	/// use std::collections::BTreeSet;
1100	///
1101	/// let mut set = BTreeSet::from([`1`, `2`, `3`, `4`, `5`, `6`]);
1102	/// // Keep only the even numbers.
1103	/// set.retain(\|&k\| k % `2` == `0`);
1104	/// assert!(set.iter().eq([`2`, `4`, `6`].iter()));
1105	/// ```
1106	#[stable(feature = "btree_retain", since = "1.53.0")]
1107	pub fn retain<F>(&mut self, mut f: F)
1108	where
1109	T: Ord,
1110	F: FnMut(&T) -> bool,
1111	{
1112	self.extract_if(.., \|v\| !f(v)).for_each(drop);
1113	}
1114
1115	/// Moves all elements from `other` into `self`, leaving `other` empty.
1116	///
1117	/// # Examples
1118	///
1119	/// ```
1120	/// use std::collections::BTreeSet;
1121	///
1122	/// let mut a = BTreeSet::new();
1123	/// a.insert(`1`);
1124	/// a.insert(`2`);
1125	/// a.insert(`3`);
1126	///
1127	/// let mut b = BTreeSet::new();
1128	/// b.insert(`3`);
1129	/// b.insert(`4`);
1130	/// b.insert(`5`);
1131	///
1132	/// a.append(&mut b);
1133	///
1134	/// assert_eq!(a.len(), `5`);
1135	/// assert_eq!(b.len(), `0`);
1136	///
1137	/// assert!(a.contains(&`1`));
1138	/// assert!(a.contains(&`2`));
1139	/// assert!(a.contains(&`3`));
1140	/// assert!(a.contains(&`4`));
1141	/// assert!(a.contains(&`5`));
1142	/// ```
1143	#[stable(feature = "btree_append", since = "1.11.0")]
1144	pub fn append(&mut self, other: &mut Self)
1145	where
1146	T: Ord,
1147	A: Clone,
1148	{
1149	self.map.append(&mut other.map);
1150	}
1151
1152	/// Splits the collection into two at the value. Returns a new collection
1153	/// with all elements greater than or equal to the value.
1154	///
1155	/// # Examples
1156	///
1157	/// Basic usage:
1158	///
1159	/// ```
1160	/// use std::collections::BTreeSet;
1161	///
1162	/// let mut a = BTreeSet::new();
1163	/// a.insert(`1`);
1164	/// a.insert(`2`);
1165	/// a.insert(`3`);
1166	/// a.insert(`17`);
1167	/// a.insert(`41`);
1168	///
1169	/// let b = a.split_off(&`3`);
1170	///
1171	/// assert_eq!(a.len(), `2`);
1172	/// assert_eq!(b.len(), `3`);
1173	///
1174	/// assert!(a.contains(&`1`));
1175	/// assert!(a.contains(&`2`));
1176	///
1177	/// assert!(b.contains(&`3`));
1178	/// assert!(b.contains(&`17`));
1179	/// assert!(b.contains(&`41`));
1180	/// ```
1181	#[stable(feature = "btree_split_off", since = "1.11.0")]
1182	pub fn split_off<Q: ?Sized + Ord>(&mut self, value: &Q) -> Self
1183	where
1184	T: Borrow<Q> + Ord,
1185	A: Clone,
1186	{
1187	BTreeSet { map: self.map.split_off(value) }
1188	}
1189
1190	/// Creates an iterator that visits elements in the specified range in ascending order and
1191	/// uses a closure to determine if an element should be removed.
1192	///
1193	/// If the closure returns `true`, the element is removed from the set and
1194	/// yielded. If the closure returns `false`, or panics, the element remains
1195	/// in the set and will not be yielded.
1196	///
1197	/// If the returned `ExtractIf` is not exhausted, e.g. because it is dropped without iterating
1198	/// or the iteration short-circuits, then the remaining elements will be retained.
1199	/// Use [`retain`] with a negated predicate if you do not need the returned iterator.
1200	///
1201	/// [`retain`]: BTreeSet::retain
1202	/// # Examples
1203	///
1204	/// ```
1205	/// #![feature(btree_extract_if)]
1206	/// use std::collections::BTreeSet;
1207	///
1208	/// // Splitting a set into even and odd values, reusing the original set:
1209	/// let mut set: BTreeSet<i32> = (`0`..`8`).collect();
1210	/// let evens: BTreeSet<_> = set.extract_if(.., \|v\| v % `2` == `0`).collect();
1211	/// let odds = set;
1212	/// assert_eq!(evens.into_iter().collect::<Vec<_>>(), vec![`0`, `2`, `4`, `6`]);
1213	/// assert_eq!(odds.into_iter().collect::<Vec<_>>(), vec![`1`, `3`, `5`, `7`]);
1214	///
1215	/// // Splitting a set into low and high halves, reusing the original set:
1216	/// let mut set: BTreeSet<i32> = (`0`..`8`).collect();
1217	/// let low: BTreeSet<_> = set.extract_if(`0`..`4`, \|_v\| `true`).collect();
1218	/// let high = set;
1219	/// assert_eq!(low.into_iter().collect::<Vec<_>>(), [`0`, `1`, `2`, `3`]);
1220	/// assert_eq!(high.into_iter().collect::<Vec<_>>(), [`4`, `5`, `6`, `7`]);
1221	/// ```
1222	#[unstable(feature = "btree_extract_if", issue = "70530")]
1223	pub fn extract_if<'a, F, R>(&'a mut self, range: R, pred: F) -> ExtractIf<'a, T, R, F, A>
1224	where
1225	T: Ord,
1226	R: RangeBounds<T>,
1227	F: 'a + FnMut(&T) -> bool,
1228	{
1229	let (inner, alloc) = self.map.extract_if_inner(range);
1230	ExtractIf { pred, inner, alloc }
1231	}
1232
1233	/// Gets an iterator that visits the elements in the `BTreeSet` in ascending
1234	/// order.
1235	///
1236	/// # Examples
1237	///
1238	/// ```
1239	/// use std::collections::BTreeSet;
1240	///
1241	/// let set = BTreeSet::from([`3`, `1`, `2`]);
1242	/// let mut set_iter = set.iter();
1243	/// assert_eq!(set_iter.next(), Some(&`1`));
1244	/// assert_eq!(set_iter.next(), Some(&`2`));
1245	/// assert_eq!(set_iter.next(), Some(&`3`));
1246	/// assert_eq!(set_iter.next(), None);
1247	/// ```
1248	#[stable(feature = "rust1", since = "1.0.0")]
1249	#[cfg_attr(not(test), rustc_diagnostic_item = "btreeset_iter")]
1250	pub fn iter(&self) -> Iter<'_, T> {
1251	Iter { iter: self.map.keys() }
1252	}
1253
1254	/// Returns the number of elements in the set.
1255	///
1256	/// # Examples
1257	///
1258	/// ```
1259	/// use std::collections::BTreeSet;
1260	///
1261	/// let mut v = BTreeSet::new();
1262	/// assert_eq!(v.len(), `0`);
1263	/// v.insert(`1`);
1264	/// assert_eq!(v.len(), `1`);
1265	/// ```
1266	#[must_use]
1267	#[stable(feature = "rust1", since = "1.0.0")]
1268	#[rustc_const_unstable(
1269	feature = "const_btree_len",
1270	issue = "71835",
1271	implied_by = "const_btree_new"
1272	)]
1273	#[rustc_confusables("length", "size")]
1274	pub const fn len(&self) -> usize {
1275	self.map.len()
1276	}
1277
1278	/// Returns `true` if the set contains no elements.
1279	///
1280	/// # Examples
1281	///
1282	/// ```
1283	/// use std::collections::BTreeSet;
1284	///
1285	/// let mut v = BTreeSet::new();
1286	/// assert!(v.is_empty());
1287	/// v.insert(`1`);
1288	/// assert!(!v.is_empty());
1289	/// ```
1290	#[must_use]
1291	#[stable(feature = "rust1", since = "1.0.0")]
1292	#[rustc_const_unstable(
1293	feature = "const_btree_len",
1294	issue = "71835",
1295	implied_by = "const_btree_new"
1296	)]
1297	pub const fn is_empty(&self) -> bool {
1298	self.len() == `0`
1299	}
1300
1301	/// Returns a [`Cursor`] pointing at the gap before the smallest element
1302	/// greater than the given bound.
1303	///
1304	/// Passing `Bound::Included(x)` will return a cursor pointing to the
1305	/// gap before the smallest element greater than or equal to `x`.
1306	///
1307	/// Passing `Bound::Excluded(x)` will return a cursor pointing to the
1308	/// gap before the smallest element greater than `x`.
1309	///
1310	/// Passing `Bound::Unbounded` will return a cursor pointing to the
1311	/// gap before the smallest element in the set.
1312	///
1313	/// # Examples
1314	///
1315	/// ```
1316	/// #![feature(btree_cursors)]
1317	///
1318	/// use std::collections::BTreeSet;
1319	/// use std::ops::Bound;
1320	///
1321	/// let set = BTreeSet::from([`1`, `2`, `3`, `4`]);
1322	///
1323	/// let cursor = set.lower_bound(Bound::Included(&`2`));
1324	/// assert_eq!(cursor.peek_prev(), Some(&`1`));
1325	/// assert_eq!(cursor.peek_next(), Some(&`2`));
1326	///
1327	/// let cursor = set.lower_bound(Bound::Excluded(&`2`));
1328	/// assert_eq!(cursor.peek_prev(), Some(&`2`));
1329	/// assert_eq!(cursor.peek_next(), Some(&`3`));
1330	///
1331	/// let cursor = set.lower_bound(Bound::Unbounded);
1332	/// assert_eq!(cursor.peek_prev(), None);
1333	/// assert_eq!(cursor.peek_next(), Some(&`1`));
1334	/// ```
1335	#[unstable(feature = "btree_cursors", issue = "107540")]
1336	pub fn lower_bound<Q: ?Sized>(&self, bound: Bound<&Q>) -> Cursor<'_, T>
1337	where
1338	T: Borrow<Q> + Ord,
1339	Q: Ord,
1340	{
1341	Cursor { inner: self.map.lower_bound(bound) }
1342	}
1343
1344	/// Returns a [`CursorMut`] pointing at the gap before the smallest element
1345	/// greater than the given bound.
1346	///
1347	/// Passing `Bound::Included(x)` will return a cursor pointing to the
1348	/// gap before the smallest element greater than or equal to `x`.
1349	///
1350	/// Passing `Bound::Excluded(x)` will return a cursor pointing to the
1351	/// gap before the smallest element greater than `x`.
1352	///
1353	/// Passing `Bound::Unbounded` will return a cursor pointing to the
1354	/// gap before the smallest element in the set.
1355	///
1356	/// # Examples
1357	///
1358	/// ```
1359	/// #![feature(btree_cursors)]
1360	///
1361	/// use std::collections::BTreeSet;
1362	/// use std::ops::Bound;
1363	///
1364	/// let mut set = BTreeSet::from([`1`, `2`, `3`, `4`]);
1365	///
1366	/// let mut cursor = set.lower_bound_mut(Bound::Included(&`2`));
1367	/// assert_eq!(cursor.peek_prev(), Some(&`1`));
1368	/// assert_eq!(cursor.peek_next(), Some(&`2`));
1369	///
1370	/// let mut cursor = set.lower_bound_mut(Bound::Excluded(&`2`));
1371	/// assert_eq!(cursor.peek_prev(), Some(&`2`));
1372	/// assert_eq!(cursor.peek_next(), Some(&`3`));
1373	///
1374	/// let mut cursor = set.lower_bound_mut(Bound::Unbounded);
1375	/// assert_eq!(cursor.peek_prev(), None);
1376	/// assert_eq!(cursor.peek_next(), Some(&`1`));
1377	/// ```
1378	#[unstable(feature = "btree_cursors", issue = "107540")]
1379	pub fn lower_bound_mut<Q: ?Sized>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, T, A>
1380	where
1381	T: Borrow<Q> + Ord,
1382	Q: Ord,
1383	{
1384	CursorMut { inner: self.map.lower_bound_mut(bound) }
1385	}
1386
1387	/// Returns a [`Cursor`] pointing at the gap after the greatest element
1388	/// smaller than the given bound.
1389	///
1390	/// Passing `Bound::Included(x)` will return a cursor pointing to the
1391	/// gap after the greatest element smaller than or equal to `x`.
1392	///
1393	/// Passing `Bound::Excluded(x)` will return a cursor pointing to the
1394	/// gap after the greatest element smaller than `x`.
1395	///
1396	/// Passing `Bound::Unbounded` will return a cursor pointing to the
1397	/// gap after the greatest element in the set.
1398	///
1399	/// # Examples
1400	///
1401	/// ```
1402	/// #![feature(btree_cursors)]
1403	///
1404	/// use std::collections::BTreeSet;
1405	/// use std::ops::Bound;
1406	///
1407	/// let set = BTreeSet::from([`1`, `2`, `3`, `4`]);
1408	///
1409	/// let cursor = set.upper_bound(Bound::Included(&`3`));
1410	/// assert_eq!(cursor.peek_prev(), Some(&`3`));
1411	/// assert_eq!(cursor.peek_next(), Some(&`4`));
1412	///
1413	/// let cursor = set.upper_bound(Bound::Excluded(&`3`));
1414	/// assert_eq!(cursor.peek_prev(), Some(&`2`));
1415	/// assert_eq!(cursor.peek_next(), Some(&`3`));
1416	///
1417	/// let cursor = set.upper_bound(Bound::Unbounded);
1418	/// assert_eq!(cursor.peek_prev(), Some(&`4`));
1419	/// assert_eq!(cursor.peek_next(), None);
1420	/// ```
1421	#[unstable(feature = "btree_cursors", issue = "107540")]
1422	pub fn upper_bound<Q: ?Sized>(&self, bound: Bound<&Q>) -> Cursor<'_, T>
1423	where
1424	T: Borrow<Q> + Ord,
1425	Q: Ord,
1426	{
1427	Cursor { inner: self.map.upper_bound(bound) }
1428	}
1429
1430	/// Returns a [`CursorMut`] pointing at the gap after the greatest element
1431	/// smaller than the given bound.
1432	///
1433	/// Passing `Bound::Included(x)` will return a cursor pointing to the
1434	/// gap after the greatest element smaller than or equal to `x`.
1435	///
1436	/// Passing `Bound::Excluded(x)` will return a cursor pointing to the
1437	/// gap after the greatest element smaller than `x`.
1438	///
1439	/// Passing `Bound::Unbounded` will return a cursor pointing to the
1440	/// gap after the greatest element in the set.
1441	///
1442	/// # Examples
1443	///
1444	/// ```
1445	/// #![feature(btree_cursors)]
1446	///
1447	/// use std::collections::BTreeSet;
1448	/// use std::ops::Bound;
1449	///
1450	/// let mut set = BTreeSet::from([`1`, `2`, `3`, `4`]);
1451	///
1452	/// let mut cursor = set.upper_bound_mut(Bound::Included(&`3`));
1453	/// assert_eq!(cursor.peek_prev(), Some(&`3`));
1454	/// assert_eq!(cursor.peek_next(), Some(&`4`));
1455	///
1456	/// let mut cursor = set.upper_bound_mut(Bound::Excluded(&`3`));
1457	/// assert_eq!(cursor.peek_prev(), Some(&`2`));
1458	/// assert_eq!(cursor.peek_next(), Some(&`3`));
1459	///
1460	/// let mut cursor = set.upper_bound_mut(Bound::Unbounded);
1461	/// assert_eq!(cursor.peek_prev(), Some(&`4`));
1462	/// assert_eq!(cursor.peek_next(), None);
1463	/// ```
1464	#[unstable(feature = "btree_cursors", issue = "107540")]
1465	pub fn upper_bound_mut<Q: ?Sized>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, T, A>
1466	where
1467	T: Borrow<Q> + Ord,
1468	Q: Ord,
1469	{
1470	CursorMut { inner: self.map.upper_bound_mut(bound) }
1471	}
1472	}
1473
1474	#[stable(feature = "rust1", since = "1.0.0")]
1475	impl<T: Ord> FromIterator<T> for BTreeSet<T> {
1476	fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> BTreeSet<T> {
1477	let mut inputs: Vec<_> = iter.into_iter().collect();
1478
1479	if inputs.is_empty() {
1480	return BTreeSet::new();
1481	}
1482
1483	// use stable sort to preserve the insertion order.
1484	inputs.sort();
1485	BTreeSet::from_sorted_iter(inputs.into_iter(), alloc:Global)
1486	}
1487	}
1488
1489	impl<T: Ord, A: Allocator + Clone> BTreeSet<T, A> {
1490	fn from_sorted_iter<I: Iterator<Item = T>>(iter: I, alloc: A) -> BTreeSet<T, A> {
1491	let iter: impl Iterator = iter.map(\|k: T\| (k, SetValZST::default()));
1492	let map: BTreeMap = BTreeMap::bulk_build_from_sorted_iter(iter, alloc);
1493	BTreeSet { map }
1494	}
1495	}
1496
1497	#[stable(feature = "std_collections_from_array", since = "1.56.0")]
1498	impl<T: Ord, const N: usize> From<[T; N]> for BTreeSet<T> {
1499	/// Converts a `[T; N]` into a `BTreeSet<T>`.
1500	///
1501	/// If the array contains any equal values,
1502	/// all but one will be dropped.
1503	///
1504	/// # Examples
1505	///
1506	/// ```
1507	/// use std::collections::BTreeSet;
1508	///
1509	/// let set1 = BTreeSet::from([`1`, `2`, `3`, `4`]);
1510	/// let set2: BTreeSet<_> = [`1`, `2`, `3`, `4`].into();
1511	/// assert_eq!(set1, set2);
1512	/// ```
1513	fn from(mut arr: [T; N]) -> Self {
1514	if N == `0` {
1515	return BTreeSet::new();
1516	}
1517
1518	// use stable sort to preserve the insertion order.
1519	arr.sort();
1520	let iter = IntoIterator::into_iter(arr).map(\|k\| (k, SetValZST::default()));
1521	let map = BTreeMap::bulk_build_from_sorted_iter(iter, Global);
1522	BTreeSet { map }
1523	}
1524	}
1525
1526	#[stable(feature = "rust1", since = "1.0.0")]
1527	impl<T, A: Allocator + Clone> IntoIterator for BTreeSet<T, A> {
1528	type Item = T;
1529	type IntoIter = IntoIter<T, A>;
1530
1531	/// Gets an iterator for moving out the `BTreeSet`'s contents in ascending order.
1532	///
1533	/// # Examples
1534	///
1535	/// ```
1536	/// use std::collections::BTreeSet;
1537	///
1538	/// let set = BTreeSet::from([`1`, `2`, `3`, `4`]);
1539	///
1540	/// let v: Vec<_> = set.into_iter().collect();
1541	/// assert_eq!(v, [`1`, `2`, `3`, `4`]);
1542	/// ```
1543	fn into_iter(self) -> IntoIter<T, A> {
1544	IntoIter { iter: self.map.into_iter() }
1545	}
1546	}
1547
1548	#[stable(feature = "rust1", since = "1.0.0")]
1549	impl<'a, T, A: Allocator + Clone> IntoIterator for &'a BTreeSet<T, A> {
1550	type Item = &'a T;
1551	type IntoIter = Iter<'a, T>;
1552
1553	fn into_iter(self) -> Iter<'a, T> {
1554	self.iter()
1555	}
1556	}
1557
1558	/// An iterator produced by calling `extract_if` on BTreeSet.
1559	#[unstable(feature = "btree_extract_if", issue = "70530")]
1560	#[must_use = "iterators are lazy and do nothing unless consumed"]
1561	pub struct ExtractIf<
1562	'a,
1563	T,
1564	R,
1565	F,
1566	#[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + Clone = Global,
1567	> {
1568	pred: F,
1569	inner: super::map::ExtractIfInner<'a, T, SetValZST, R>,
1570	/// The BTreeMap will outlive this IntoIter so we don't care about drop order for `alloc`.
1571	alloc: A,
1572	}
1573
1574	#[unstable(feature = "btree_extract_if", issue = "70530")]
1575	impl<T, R, F, A> fmt::Debug for ExtractIf<'_, T, R, F, A>
1576	where
1577	T: fmt::Debug,
1578	A: Allocator + Clone,
1579	{
1580	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1581	f&mut DebugStruct<'_, '_>.debug_struct("ExtractIf")
1582	.field(name:"peek", &self.inner.peek().map(\|(k: &T, _)\| k))
1583	.finish_non_exhaustive()
1584	}
1585	}
1586
1587	#[unstable(feature = "btree_extract_if", issue = "70530")]
1588	impl<'a, T, R, F, A: Allocator + Clone> Iterator for ExtractIf<'_, T, R, F, A>
1589	where
1590	T: PartialOrd,
1591	R: RangeBounds<T>,
1592	F: 'a + FnMut(&T) -> bool,
1593	{
1594	type Item = T;
1595
1596	fn next(&mut self) -> Option<T> {
1597	let pred: &mut F = &mut self.pred;
1598	let mut mapped_pred: impl FnMut(&T, &mut SetValZST) -> … = \|k: &T, _v: &mut SetValZST\| pred(k);
1599	self.inner.next(&mut mapped_pred, self.alloc.clone()).map(\|(k: T, _)\| k)
1600	}
1601
1602	fn size_hint(&self) -> (usize, Option<usize>) {
1603	self.inner.size_hint()
1604	}
1605	}
1606
1607	#[unstable(feature = "btree_extract_if", issue = "70530")]
1608	impl<T, R, F, A: Allocator + Clone> FusedIterator for ExtractIf<'_, T, R, F, A>
1609	where
1610	T: PartialOrd,
1611	R: RangeBounds<T>,
1612	F: FnMut(&T) -> bool,
1613	{
1614	}
1615
1616	#[stable(feature = "rust1", since = "1.0.0")]
1617	impl<T: Ord, A: Allocator + Clone> Extend<T> for BTreeSet<T, A> {
1618	#[inline]
1619	fn extend<Iter: IntoIterator<Item = T>>(&mut self, iter: Iter) {
1620	iter.into_iter().for_each(move \|elem: T\| {
1621	self.insert(elem);
1622	});
1623	}
1624
1625	#[inline]
1626	fn extend_one(&mut self, elem: T) {
1627	self.insert(elem);
1628	}
1629	}
1630
1631	#[stable(feature = "extend_ref", since = "1.2.0")]
1632	impl<'a, T: 'a + Ord + Copy, A: Allocator + Clone> Extend<&'a T> for BTreeSet<T, A> {
1633	fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
1634	self.extend(iter.into_iter().cloned());
1635	}
1636
1637	#[inline]
1638	fn extend_one(&mut self, &elem: T: &'a T) {
1639	self.insert(elem);
1640	}
1641	}
1642
1643	#[stable(feature = "rust1", since = "1.0.0")]
1644	impl<T> Default for BTreeSet<T> {
1645	/// Creates an empty `BTreeSet`.
1646	fn default() -> BTreeSet<T> {
1647	BTreeSet::new()
1648	}
1649	}
1650
1651	#[stable(feature = "rust1", since = "1.0.0")]
1652	impl<T: Ord + Clone, A: Allocator + Clone> Sub<&BTreeSet<T, A>> for &BTreeSet<T, A> {
1653	type Output = BTreeSet<T, A>;
1654
1655	/// Returns the difference of `self` and `rhs` as a new `BTreeSet<T>`.
1656	///
1657	/// # Examples
1658	///
1659	/// ```
1660	/// use std::collections::BTreeSet;
1661	///
1662	/// let a = BTreeSet::from([`1`, `2`, `3`]);
1663	/// let b = BTreeSet::from([`3`, `4`, `5`]);
1664	///
1665	/// let result = &a - &b;
1666	/// assert_eq!(result, BTreeSet::from([`1`, `2`]));
1667	/// ```
1668	fn sub(self, rhs: &BTreeSet<T, A>) -> BTreeSet<T, A> {
1669	BTreeSet::from_sorted_iter(
1670	self.difference(rhs).cloned(),
1671	alloc:ManuallyDrop::into_inner(self.map.alloc.clone()),
1672	)
1673	}
1674	}
1675
1676	#[stable(feature = "rust1", since = "1.0.0")]
1677	impl<T: Ord + Clone, A: Allocator + Clone> BitXor<&BTreeSet<T, A>> for &BTreeSet<T, A> {
1678	type Output = BTreeSet<T, A>;
1679
1680	/// Returns the symmetric difference of `self` and `rhs` as a new `BTreeSet<T>`.
1681	///
1682	/// # Examples
1683	///
1684	/// ```
1685	/// use std::collections::BTreeSet;
1686	///
1687	/// let a = BTreeSet::from([`1`, `2`, `3`]);
1688	/// let b = BTreeSet::from([`2`, `3`, `4`]);
1689	///
1690	/// let result = &a ^ &b;
1691	/// assert_eq!(result, BTreeSet::from([`1`, `4`]));
1692	/// ```
1693	fn bitxor(self, rhs: &BTreeSet<T, A>) -> BTreeSet<T, A> {
1694	BTreeSet::from_sorted_iter(
1695	self.symmetric_difference(rhs).cloned(),
1696	alloc:ManuallyDrop::into_inner(self.map.alloc.clone()),
1697	)
1698	}
1699	}
1700
1701	#[stable(feature = "rust1", since = "1.0.0")]
1702	impl<T: Ord + Clone, A: Allocator + Clone> BitAnd<&BTreeSet<T, A>> for &BTreeSet<T, A> {
1703	type Output = BTreeSet<T, A>;
1704
1705	/// Returns the intersection of `self` and `rhs` as a new `BTreeSet<T>`.
1706	///
1707	/// # Examples
1708	///
1709	/// ```
1710	/// use std::collections::BTreeSet;
1711	///
1712	/// let a = BTreeSet::from([`1`, `2`, `3`]);
1713	/// let b = BTreeSet::from([`2`, `3`, `4`]);
1714	///
1715	/// let result = &a & &b;
1716	/// assert_eq!(result, BTreeSet::from([`2`, `3`]));
1717	/// ```
1718	fn bitand(self, rhs: &BTreeSet<T, A>) -> BTreeSet<T, A> {
1719	BTreeSet::from_sorted_iter(
1720	self.intersection(rhs).cloned(),
1721	alloc:ManuallyDrop::into_inner(self.map.alloc.clone()),
1722	)
1723	}
1724	}
1725
1726	#[stable(feature = "rust1", since = "1.0.0")]
1727	impl<T: Ord + Clone, A: Allocator + Clone> BitOr<&BTreeSet<T, A>> for &BTreeSet<T, A> {
1728	type Output = BTreeSet<T, A>;
1729
1730	/// Returns the union of `self` and `rhs` as a new `BTreeSet<T>`.
1731	///
1732	/// # Examples
1733	///
1734	/// ```
1735	/// use std::collections::BTreeSet;
1736	///
1737	/// let a = BTreeSet::from([`1`, `2`, `3`]);
1738	/// let b = BTreeSet::from([`3`, `4`, `5`]);
1739	///
1740	/// let result = &a \| &b;
1741	/// assert_eq!(result, BTreeSet::from([`1`, `2`, `3`, `4`, `5`]));
1742	/// ```
1743	fn bitor(self, rhs: &BTreeSet<T, A>) -> BTreeSet<T, A> {
1744	BTreeSet::from_sorted_iter(
1745	self.union(rhs).cloned(),
1746	alloc:ManuallyDrop::into_inner(self.map.alloc.clone()),
1747	)
1748	}
1749	}
1750
1751	#[stable(feature = "rust1", since = "1.0.0")]
1752	impl<T: Debug, A: Allocator + Clone> Debug for BTreeSet<T, A> {
1753	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1754	f.debug_set().entries(self.iter()).finish()
1755	}
1756	}
1757
1758	#[stable(feature = "rust1", since = "1.0.0")]
1759	impl<T> Clone for Iter<'_, T> {
1760	fn clone(&self) -> Self {
1761	Iter { iter: self.iter.clone() }
1762	}
1763	}
1764	#[stable(feature = "rust1", since = "1.0.0")]
1765	impl<'a, T> Iterator for Iter<'a, T> {
1766	type Item = &'a T;
1767
1768	fn next(&mut self) -> Option<&'a T> {
1769	self.iter.next()
1770	}
1771
1772	fn size_hint(&self) -> (usize, Option<usize>) {
1773	self.iter.size_hint()
1774	}
1775
1776	fn last(mut self) -> Option<&'a T> {
1777	self.next_back()
1778	}
1779
1780	fn min(mut self) -> Option<&'a T>
1781	where
1782	&'a T: Ord,
1783	{
1784	self.next()
1785	}
1786
1787	fn max(mut self) -> Option<&'a T>
1788	where
1789	&'a T: Ord,
1790	{
1791	self.next_back()
1792	}
1793	}
1794	#[stable(feature = "rust1", since = "1.0.0")]
1795	impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
1796	fn next_back(&mut self) -> Option<&'a T> {
1797	self.iter.next_back()
1798	}
1799	}
1800	#[stable(feature = "rust1", since = "1.0.0")]
1801	impl<T> ExactSizeIterator for Iter<'_, T> {
1802	fn len(&self) -> usize {
1803	self.iter.len()
1804	}
1805	}
1806
1807	#[stable(feature = "fused", since = "1.26.0")]
1808	impl<T> FusedIterator for Iter<'_, T> {}
1809
1810	#[stable(feature = "rust1", since = "1.0.0")]
1811	impl<T, A: Allocator + Clone> Iterator for IntoIter<T, A> {
1812	type Item = T;
1813
1814	fn next(&mut self) -> Option<T> {
1815	self.iter.next().map(\|(k: T, _)\| k)
1816	}
1817
1818	fn size_hint(&self) -> (usize, Option<usize>) {
1819	self.iter.size_hint()
1820	}
1821	}
1822
1823	#[stable(feature = "default_iters", since = "1.70.0")]
1824	impl<T> Default for Iter<'_, T> {
1825	/// Creates an empty `btree_set::Iter`.
1826	///
1827	/// ```
1828	/// # use std::collections::btree_set;
1829	/// let iter: btree_set::Iter<'_, u8> = Default::default();
1830	/// assert_eq!(iter.len(), `0`);
1831	/// ```
1832	fn default() -> Self {
1833	Iter { iter: Default::default() }
1834	}
1835	}
1836
1837	#[stable(feature = "rust1", since = "1.0.0")]
1838	impl<T, A: Allocator + Clone> DoubleEndedIterator for IntoIter<T, A> {
1839	fn next_back(&mut self) -> Option<T> {
1840	self.iter.next_back().map(\|(k: T, _)\| k)
1841	}
1842	}
1843	#[stable(feature = "rust1", since = "1.0.0")]
1844	impl<T, A: Allocator + Clone> ExactSizeIterator for IntoIter<T, A> {
1845	fn len(&self) -> usize {
1846	self.iter.len()
1847	}
1848	}
1849
1850	#[stable(feature = "fused", since = "1.26.0")]
1851	impl<T, A: Allocator + Clone> FusedIterator for IntoIter<T, A> {}
1852
1853	#[stable(feature = "default_iters", since = "1.70.0")]
1854	impl<T, A> Default for IntoIter<T, A>
1855	where
1856	A: Allocator + Default + Clone,
1857	{
1858	/// Creates an empty `btree_set::IntoIter`.
1859	///
1860	/// ```
1861	/// # use std::collections::btree_set;
1862	/// let iter: btree_set::IntoIter<u8> = Default::default();
1863	/// assert_eq!(iter.len(), `0`);
1864	/// ```
1865	fn default() -> Self {
1866	IntoIter { iter: Default::default() }
1867	}
1868	}
1869
1870	#[stable(feature = "btree_range", since = "1.17.0")]
1871	impl<T> Clone for Range<'_, T> {
1872	fn clone(&self) -> Self {
1873	Range { iter: self.iter.clone() }
1874	}
1875	}
1876
1877	#[stable(feature = "btree_range", since = "1.17.0")]
1878	impl<'a, T> Iterator for Range<'a, T> {
1879	type Item = &'a T;
1880
1881	fn next(&mut self) -> Option<&'a T> {
1882	self.iter.next().map(\|(k, _)\| k)
1883	}
1884
1885	fn last(mut self) -> Option<&'a T> {
1886	self.next_back()
1887	}
1888
1889	fn min(mut self) -> Option<&'a T>
1890	where
1891	&'a T: Ord,
1892	{
1893	self.next()
1894	}
1895
1896	fn max(mut self) -> Option<&'a T>
1897	where
1898	&'a T: Ord,
1899	{
1900	self.next_back()
1901	}
1902	}
1903
1904	#[stable(feature = "btree_range", since = "1.17.0")]
1905	impl<'a, T> DoubleEndedIterator for Range<'a, T> {
1906	fn next_back(&mut self) -> Option<&'a T> {
1907	self.iter.next_back().map(\|(k: &'a T, _)\| k)
1908	}
1909	}
1910
1911	#[stable(feature = "fused", since = "1.26.0")]
1912	impl<T> FusedIterator for Range<'_, T> {}
1913
1914	#[stable(feature = "default_iters", since = "1.70.0")]
1915	impl<T> Default for Range<'_, T> {
1916	/// Creates an empty `btree_set::Range`.
1917	///
1918	/// ```
1919	/// # use std::collections::btree_set;
1920	/// let iter: btree_set::Range<'_, u8> = Default::default();
1921	/// assert_eq!(iter.count(), `0`);
1922	/// ```
1923	fn default() -> Self {
1924	Range { iter: Default::default() }
1925	}
1926	}
1927
1928	#[stable(feature = "rust1", since = "1.0.0")]
1929	impl<T, A: Allocator + Clone> Clone for Difference<'_, T, A> {
1930	fn clone(&self) -> Self {
1931	Difference {
1932	inner: match &self.inner {
1933	DifferenceInner::Stitch { self_iter: &Iter<'_, T>, other_iter: &Peekable> } => DifferenceInner::Stitch {
1934	self_iter: self_iter.clone(),
1935	other_iter: other_iter.clone(),
1936	},
1937	DifferenceInner::Search { self_iter: &Iter<'_, T>, other_set: &&BTreeSet } => {
1938	DifferenceInner::Search { self_iter: self_iter.clone(), other_set }
1939	}
1940	DifferenceInner::Iterate(iter: &Iter<'_, T>) => DifferenceInner::Iterate(iter.clone()),
1941	},
1942	}
1943	}
1944	}
1945	#[stable(feature = "rust1", since = "1.0.0")]
1946	impl<'a, T: Ord, A: Allocator + Clone> Iterator for Difference<'a, T, A> {
1947	type Item = &'a T;
1948
1949	fn next(&mut self) -> Option<&'a T> {
1950	match &mut self.inner {
1951	DifferenceInner::Stitch { self_iter, other_iter } => {
1952	let mut self_next = self_iter.next()?;
1953	loop {
1954	match other_iter.peek().map_or(Less, \|other_next\| self_next.cmp(other_next)) {
1955	Less => return Some(self_next),
1956	Equal => {
1957	self_next = self_iter.next()?;
1958	other_iter.next();
1959	}
1960	Greater => {
1961	other_iter.next();
1962	}
1963	}
1964	}
1965	}
1966	DifferenceInner::Search { self_iter, other_set } => loop {
1967	let self_next = self_iter.next()?;
1968	if !other_set.contains(&self_next) {
1969	return Some(self_next);
1970	}
1971	},
1972	DifferenceInner::Iterate(iter) => iter.next(),
1973	}
1974	}
1975
1976	fn size_hint(&self) -> (usize, Option<usize>) {
1977	let (self_len, other_len) = match &self.inner {
1978	DifferenceInner::Stitch { self_iter, other_iter } => {
1979	(self_iter.len(), other_iter.len())
1980	}
1981	DifferenceInner::Search { self_iter, other_set } => (self_iter.len(), other_set.len()),
1982	DifferenceInner::Iterate(iter) => (iter.len(), `0`),
1983	};
1984	(self_len.saturating_sub(other_len), Some(self_len))
1985	}
1986
1987	fn min(mut self) -> Option<&'a T> {
1988	self.next()
1989	}
1990	}
1991
1992	#[stable(feature = "fused", since = "1.26.0")]
1993	impl<T: Ord, A: Allocator + Clone> FusedIterator for Difference<'_, T, A> {}
1994
1995	#[stable(feature = "rust1", since = "1.0.0")]
1996	impl<T> Clone for SymmetricDifference<'_, T> {
1997	fn clone(&self) -> Self {
1998	SymmetricDifference(self.0.clone())
1999	}
2000	}
2001	#[stable(feature = "rust1", since = "1.0.0")]
2002	impl<'a, T: Ord> Iterator for SymmetricDifference<'a, T> {
2003	type Item = &'a T;
2004
2005	fn next(&mut self) -> Option<&'a T> {
2006	loop {
2007	let (a_next: Option<&'a T>, b_next: Option<&'a T>) = self.0.nexts(Self::Item::cmp);
2008	if a_next.and(optb:b_next).is_none() {
2009	return a_next.or(optb:b_next);
2010	}
2011	}
2012	}
2013
2014	fn size_hint(&self) -> (usize, Option<usize>) {
2015	let (a_len: usize, b_len: usize) = self.0.lens();
2016	// No checked_add, because even if a and b refer to the same set,
2017	// and T is a zero-sized type, the storage overhead of sets limits
2018	// the number of elements to less than half the range of usize.
2019	(`0`, Some(a_len + b_len))
2020	}
2021
2022	fn min(mut self) -> Option<&'a T> {
2023	self.next()
2024	}
2025	}
2026
2027	#[stable(feature = "fused", since = "1.26.0")]
2028	impl<T: Ord> FusedIterator for SymmetricDifference<'_, T> {}
2029
2030	#[stable(feature = "rust1", since = "1.0.0")]
2031	impl<T, A: Allocator + Clone> Clone for Intersection<'_, T, A> {
2032	fn clone(&self) -> Self {
2033	Intersection {
2034	inner: match &self.inner {
2035	IntersectionInner::Stitch { a: &Iter<'_, T>, b: &Iter<'_, T> } => {
2036	IntersectionInner::Stitch { a: a.clone(), b: b.clone() }
2037	}
2038	IntersectionInner::Search { small_iter: &Iter<'_, T>, large_set: &&BTreeSet } => {
2039	IntersectionInner::Search { small_iter: small_iter.clone(), large_set }
2040	}
2041	IntersectionInner::Answer(answer: &Option<&T>) => IntersectionInner::Answer(*answer),
2042	},
2043	}
2044	}
2045	}
2046	#[stable(feature = "rust1", since = "1.0.0")]
2047	impl<'a, T: Ord, A: Allocator + Clone> Iterator for Intersection<'a, T, A> {
2048	type Item = &'a T;
2049
2050	fn next(&mut self) -> Option<&'a T> {
2051	match &mut self.inner {
2052	IntersectionInner::Stitch { a, b } => {
2053	let mut a_next = a.next()?;
2054	let mut b_next = b.next()?;
2055	loop {
2056	match a_next.cmp(b_next) {
2057	Less => a_next = a.next()?,
2058	Greater => b_next = b.next()?,
2059	Equal => return Some(a_next),
2060	}
2061	}
2062	}
2063	IntersectionInner::Search { small_iter, large_set } => loop {
2064	let small_next = small_iter.next()?;
2065	if large_set.contains(&small_next) {
2066	return Some(small_next);
2067	}
2068	},
2069	IntersectionInner::Answer(answer) => answer.take(),
2070	}
2071	}
2072
2073	fn size_hint(&self) -> (usize, Option<usize>) {
2074	match &self.inner {
2075	IntersectionInner::Stitch { a, b } => (`0`, Some(min(a.len(), b.len()))),
2076	IntersectionInner::Search { small_iter, .. } => (`0`, Some(small_iter.len())),
2077	IntersectionInner::Answer(None) => (`0`, Some(`0`)),
2078	IntersectionInner::Answer(Some(_)) => (`1`, Some(`1`)),
2079	}
2080	}
2081
2082	fn min(mut self) -> Option<&'a T> {
2083	self.next()
2084	}
2085	}
2086
2087	#[stable(feature = "fused", since = "1.26.0")]
2088	impl<T: Ord, A: Allocator + Clone> FusedIterator for Intersection<'_, T, A> {}
2089
2090	#[stable(feature = "rust1", since = "1.0.0")]
2091	impl<T> Clone for Union<'_, T> {
2092	fn clone(&self) -> Self {
2093	Union(self.0.clone())
2094	}
2095	}
2096	#[stable(feature = "rust1", since = "1.0.0")]
2097	impl<'a, T: Ord> Iterator for Union<'a, T> {
2098	type Item = &'a T;
2099
2100	fn next(&mut self) -> Option<&'a T> {
2101	let (a_next: Option<&'a T>, b_next: Option<&'a T>) = self.0.nexts(Self::Item::cmp);
2102	a_next.or(optb:b_next)
2103	}
2104
2105	fn size_hint(&self) -> (usize, Option<usize>) {
2106	let (a_len: usize, b_len: usize) = self.0.lens();
2107	// No checked_add - see SymmetricDifference::size_hint.
2108	(max(v1:a_len, v2:b_len), Some(a_len + b_len))
2109	}
2110
2111	fn min(mut self) -> Option<&'a T> {
2112	self.next()
2113	}
2114	}
2115
2116	#[stable(feature = "fused", since = "1.26.0")]
2117	impl<T: Ord> FusedIterator for Union<'_, T> {}
2118
2119	/// A cursor over a `BTreeSet`.
2120	///
2121	/// A `Cursor` is like an iterator, except that it can freely seek back-and-forth.
2122	///
2123	/// Cursors always point to a gap between two elements in the set, and can
2124	/// operate on the two immediately adjacent elements.
2125	///
2126	/// A `Cursor` is created with the [`BTreeSet::lower_bound`] and [`BTreeSet::upper_bound`] methods.
2127	#[derive(Clone)]
2128	#[unstable(feature = "btree_cursors", issue = "107540")]
2129	pub struct Cursor<'a, K: 'a> {
2130	inner: super::map::Cursor<'a, K, SetValZST>,
2131	}
2132
2133	#[unstable(feature = "btree_cursors", issue = "107540")]
2134	impl<K: Debug> Debug for Cursor<'_, K> {
2135	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2136	f.write_str(data:"Cursor")
2137	}
2138	}
2139
2140	/// A cursor over a `BTreeSet` with editing operations.
2141	///
2142	/// A `Cursor` is like an iterator, except that it can freely seek back-and-forth, and can
2143	/// safely mutate the set during iteration. This is because the lifetime of its yielded
2144	/// references is tied to its own lifetime, instead of just the underlying map. This means
2145	/// cursors cannot yield multiple elements at once.
2146	///
2147	/// Cursors always point to a gap between two elements in the set, and can
2148	/// operate on the two immediately adjacent elements.
2149	///
2150	/// A `CursorMut` is created with the [`BTreeSet::lower_bound_mut`] and [`BTreeSet::upper_bound_mut`]
2151	/// methods.
2152	#[unstable(feature = "btree_cursors", issue = "107540")]
2153	pub struct CursorMut<'a, K: 'a, #[unstable(feature = "allocator_api", issue = "32838")] A = Global>
2154	{
2155	inner: super::map::CursorMut<'a, K, SetValZST, A>,
2156	}
2157
2158	#[unstable(feature = "btree_cursors", issue = "107540")]
2159	impl<K: Debug, A> Debug for CursorMut<'_, K, A> {
2160	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2161	f.write_str(data:"CursorMut")
2162	}
2163	}
2164
2165	/// A cursor over a `BTreeSet` with editing operations, and which allows
2166	/// mutating elements.
2167	///
2168	/// A `Cursor` is like an iterator, except that it can freely seek back-and-forth, and can
2169	/// safely mutate the set during iteration. This is because the lifetime of its yielded
2170	/// references is tied to its own lifetime, instead of just the underlying set. This means
2171	/// cursors cannot yield multiple elements at once.
2172	///
2173	/// Cursors always point to a gap between two elements in the set, and can
2174	/// operate on the two immediately adjacent elements.
2175	///
2176	/// A `CursorMutKey` is created from a [`CursorMut`] with the
2177	/// [`CursorMut::with_mutable_key`] method.
2178	///
2179	/// # Safety
2180	///
2181	/// Since this cursor allows mutating elements, you must ensure that the
2182	/// `BTreeSet` invariants are maintained. Specifically:
2183	///
2184	/// The newly inserted element must be unique in the tree.*
2185	/// All elements in the tree must remain in sorted order.*
2186	#[unstable(feature = "btree_cursors", issue = "107540")]
2187	pub struct CursorMutKey<
2188	'a,
2189	K: 'a,
2190	#[unstable(feature = "allocator_api", issue = "32838")] A = Global,
2191	> {
2192	inner: super::map::CursorMutKey<'a, K, SetValZST, A>,
2193	}
2194
2195	#[unstable(feature = "btree_cursors", issue = "107540")]
2196	impl<K: Debug, A> Debug for CursorMutKey<'_, K, A> {
2197	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2198	f.write_str(data:"CursorMutKey")
2199	}
2200	}
2201
2202	impl<'a, K> Cursor<'a, K> {
2203	/// Advances the cursor to the next gap, returning the element that it
2204	/// moved over.
2205	///
2206	/// If the cursor is already at the end of the set then `None` is returned
2207	/// and the cursor is not moved.
2208	#[unstable(feature = "btree_cursors", issue = "107540")]
2209	pub fn next(&mut self) -> Option<&'a K> {
2210	self.inner.next().map(\|(k, _)\| k)
2211	}
2212
2213	/// Advances the cursor to the previous gap, returning the element that it
2214	/// moved over.
2215	///
2216	/// If the cursor is already at the start of the set then `None` is returned
2217	/// and the cursor is not moved.
2218	#[unstable(feature = "btree_cursors", issue = "107540")]
2219	pub fn prev(&mut self) -> Option<&'a K> {
2220	self.inner.prev().map(\|(k, _)\| k)
2221	}
2222
2223	/// Returns a reference to next element without moving the cursor.
2224	///
2225	/// If the cursor is at the end of the set then `None` is returned
2226	#[unstable(feature = "btree_cursors", issue = "107540")]
2227	pub fn peek_next(&self) -> Option<&'a K> {
2228	self.inner.peek_next().map(\|(k, _)\| k)
2229	}
2230
2231	/// Returns a reference to the previous element without moving the cursor.
2232	///
2233	/// If the cursor is at the start of the set then `None` is returned.
2234	#[unstable(feature = "btree_cursors", issue = "107540")]
2235	pub fn peek_prev(&self) -> Option<&'a K> {
2236	self.inner.peek_prev().map(\|(k, _)\| k)
2237	}
2238	}
2239
2240	impl<'a, T, A> CursorMut<'a, T, A> {
2241	/// Advances the cursor to the next gap, returning the element that it
2242	/// moved over.
2243	///
2244	/// If the cursor is already at the end of the set then `None` is returned
2245	/// and the cursor is not moved.
2246	#[unstable(feature = "btree_cursors", issue = "107540")]
2247	pub fn next(&mut self) -> Option<&T> {
2248	self.inner.next().map(\|(k, _)\| k)
2249	}
2250
2251	/// Advances the cursor to the previous gap, returning the element that it
2252	/// moved over.
2253	///
2254	/// If the cursor is already at the start of the set then `None` is returned
2255	/// and the cursor is not moved.
2256	#[unstable(feature = "btree_cursors", issue = "107540")]
2257	pub fn prev(&mut self) -> Option<&T> {
2258	self.inner.prev().map(\|(k, _)\| k)
2259	}
2260
2261	/// Returns a reference to the next element without moving the cursor.
2262	///
2263	/// If the cursor is at the end of the set then `None` is returned.
2264	#[unstable(feature = "btree_cursors", issue = "107540")]
2265	pub fn peek_next(&mut self) -> Option<&T> {
2266	self.inner.peek_next().map(\|(k, _)\| k)
2267	}
2268
2269	/// Returns a reference to the previous element without moving the cursor.
2270	///
2271	/// If the cursor is at the start of the set then `None` is returned.
2272	#[unstable(feature = "btree_cursors", issue = "107540")]
2273	pub fn peek_prev(&mut self) -> Option<&T> {
2274	self.inner.peek_prev().map(\|(k, _)\| k)
2275	}
2276
2277	/// Returns a read-only cursor pointing to the same location as the
2278	/// `CursorMut`.
2279	///
2280	/// The lifetime of the returned `Cursor` is bound to that of the
2281	/// `CursorMut`, which means it cannot outlive the `CursorMut` and that the
2282	/// `CursorMut` is frozen for the lifetime of the `Cursor`.
2283	#[unstable(feature = "btree_cursors", issue = "107540")]
2284	pub fn as_cursor(&self) -> Cursor<'_, T> {
2285	Cursor { inner: self.inner.as_cursor() }
2286	}
2287
2288	/// Converts the cursor into a [`CursorMutKey`], which allows mutating
2289	/// elements in the tree.
2290	///
2291	/// # Safety
2292	///
2293	/// Since this cursor allows mutating elements, you must ensure that the
2294	/// `BTreeSet` invariants are maintained. Specifically:
2295	///
2296	/// The newly inserted element must be unique in the tree.*
2297	/// All elements in the tree must remain in sorted order.*
2298	#[unstable(feature = "btree_cursors", issue = "107540")]
2299	pub unsafe fn with_mutable_key(self) -> CursorMutKey<'a, T, A> {
2300	CursorMutKey { inner: unsafe { self.inner.with_mutable_key() } }
2301	}
2302	}
2303
2304	impl<'a, T, A> CursorMutKey<'a, T, A> {
2305	/// Advances the cursor to the next gap, returning the element that it
2306	/// moved over.
2307	///
2308	/// If the cursor is already at the end of the set then `None` is returned
2309	/// and the cursor is not moved.
2310	#[unstable(feature = "btree_cursors", issue = "107540")]
2311	pub fn next(&mut self) -> Option<&mut T> {
2312	self.inner.next().map(\|(k, _)\| k)
2313	}
2314
2315	/// Advances the cursor to the previous gap, returning the element that it
2316	/// moved over.
2317	///
2318	/// If the cursor is already at the start of the set then `None` is returned
2319	/// and the cursor is not moved.
2320	#[unstable(feature = "btree_cursors", issue = "107540")]
2321	pub fn prev(&mut self) -> Option<&mut T> {
2322	self.inner.prev().map(\|(k, _)\| k)
2323	}
2324
2325	/// Returns a reference to the next element without moving the cursor.
2326	///
2327	/// If the cursor is at the end of the set then `None` is returned
2328	#[unstable(feature = "btree_cursors", issue = "107540")]
2329	pub fn peek_next(&mut self) -> Option<&mut T> {
2330	self.inner.peek_next().map(\|(k, _)\| k)
2331	}
2332
2333	/// Returns a reference to the previous element without moving the cursor.
2334	///
2335	/// If the cursor is at the start of the set then `None` is returned.
2336	#[unstable(feature = "btree_cursors", issue = "107540")]
2337	pub fn peek_prev(&mut self) -> Option<&mut T> {
2338	self.inner.peek_prev().map(\|(k, _)\| k)
2339	}
2340
2341	/// Returns a read-only cursor pointing to the same location as the
2342	/// `CursorMutKey`.
2343	///
2344	/// The lifetime of the returned `Cursor` is bound to that of the
2345	/// `CursorMutKey`, which means it cannot outlive the `CursorMutKey` and that the
2346	/// `CursorMutKey` is frozen for the lifetime of the `Cursor`.
2347	#[unstable(feature = "btree_cursors", issue = "107540")]
2348	pub fn as_cursor(&self) -> Cursor<'_, T> {
2349	Cursor { inner: self.inner.as_cursor() }
2350	}
2351	}
2352
2353	impl<'a, T: Ord, A: Allocator + Clone> CursorMut<'a, T, A> {
2354	/// Inserts a new element into the set in the gap that the
2355	/// cursor is currently pointing to.
2356	///
2357	/// After the insertion the cursor will be pointing at the gap before the
2358	/// newly inserted element.
2359	///
2360	/// # Safety
2361	///
2362	/// You must ensure that the `BTreeSet` invariants are maintained.
2363	/// Specifically:
2364	///
2365	/// The newly inserted element must be unique in the tree.*
2366	/// All elements in the tree must remain in sorted order.*
2367	#[unstable(feature = "btree_cursors", issue = "107540")]
2368	pub unsafe fn insert_after_unchecked(&mut self, value: T) {
2369	unsafe { self.inner.insert_after_unchecked(value, SetValZST) }
2370	}
2371
2372	/// Inserts a new element into the set in the gap that the
2373	/// cursor is currently pointing to.
2374	///
2375	/// After the insertion the cursor will be pointing at the gap after the
2376	/// newly inserted element.
2377	///
2378	/// # Safety
2379	///
2380	/// You must ensure that the `BTreeSet` invariants are maintained.
2381	/// Specifically:
2382	///
2383	/// The newly inserted element must be unique in the tree.*
2384	/// All elements in the tree must remain in sorted order.*
2385	#[unstable(feature = "btree_cursors", issue = "107540")]
2386	pub unsafe fn insert_before_unchecked(&mut self, value: T) {
2387	unsafe { self.inner.insert_before_unchecked(value, SetValZST) }
2388	}
2389
2390	/// Inserts a new element into the set in the gap that the
2391	/// cursor is currently pointing to.
2392	///
2393	/// After the insertion the cursor will be pointing at the gap before the
2394	/// newly inserted element.
2395	///
2396	/// If the inserted element is not greater than the element before the
2397	/// cursor (if any), or if it not less than the element after the cursor (if
2398	/// any), then an [`UnorderedKeyError`] is returned since this would
2399	/// invalidate the [`Ord`] invariant between the elements of the set.
2400	#[unstable(feature = "btree_cursors", issue = "107540")]
2401	pub fn insert_after(&mut self, value: T) -> Result<(), UnorderedKeyError> {
2402	self.inner.insert_after(value, SetValZST)
2403	}
2404
2405	/// Inserts a new element into the set in the gap that the
2406	/// cursor is currently pointing to.
2407	///
2408	/// After the insertion the cursor will be pointing at the gap after the
2409	/// newly inserted element.
2410	///
2411	/// If the inserted element is not greater than the element before the
2412	/// cursor (if any), or if it not less than the element after the cursor (if
2413	/// any), then an [`UnorderedKeyError`] is returned since this would
2414	/// invalidate the [`Ord`] invariant between the elements of the set.
2415	#[unstable(feature = "btree_cursors", issue = "107540")]
2416	pub fn insert_before(&mut self, value: T) -> Result<(), UnorderedKeyError> {
2417	self.inner.insert_before(value, SetValZST)
2418	}
2419
2420	/// Removes the next element from the `BTreeSet`.
2421	///
2422	/// The element that was removed is returned. The cursor position is
2423	/// unchanged (before the removed element).
2424	#[unstable(feature = "btree_cursors", issue = "107540")]
2425	pub fn remove_next(&mut self) -> Option<T> {
2426	self.inner.remove_next().map(\|(k, _)\| k)
2427	}
2428
2429	/// Removes the preceding element from the `BTreeSet`.
2430	///
2431	/// The element that was removed is returned. The cursor position is
2432	/// unchanged (after the removed element).
2433	#[unstable(feature = "btree_cursors", issue = "107540")]
2434	pub fn remove_prev(&mut self) -> Option<T> {
2435	self.inner.remove_prev().map(\|(k, _)\| k)
2436	}
2437	}
2438
2439	impl<'a, T: Ord, A: Allocator + Clone> CursorMutKey<'a, T, A> {
2440	/// Inserts a new element into the set in the gap that the
2441	/// cursor is currently pointing to.
2442	///
2443	/// After the insertion the cursor will be pointing at the gap before the
2444	/// newly inserted element.
2445	///
2446	/// # Safety
2447	///
2448	/// You must ensure that the `BTreeSet` invariants are maintained.
2449	/// Specifically:
2450	///
2451	/// The key of the newly inserted element must be unique in the tree.*
2452	/// All elements in the tree must remain in sorted order.*
2453	#[unstable(feature = "btree_cursors", issue = "107540")]
2454	pub unsafe fn insert_after_unchecked(&mut self, value: T) {
2455	unsafe { self.inner.insert_after_unchecked(value, SetValZST) }
2456	}
2457
2458	/// Inserts a new element into the set in the gap that the
2459	/// cursor is currently pointing to.
2460	///
2461	/// After the insertion the cursor will be pointing at the gap after the
2462	/// newly inserted element.
2463	///
2464	/// # Safety
2465	///
2466	/// You must ensure that the `BTreeSet` invariants are maintained.
2467	/// Specifically:
2468	///
2469	/// The newly inserted element must be unique in the tree.*
2470	/// All elements in the tree must remain in sorted order.*
2471	#[unstable(feature = "btree_cursors", issue = "107540")]
2472	pub unsafe fn insert_before_unchecked(&mut self, value: T) {
2473	unsafe { self.inner.insert_before_unchecked(value, SetValZST) }
2474	}
2475
2476	/// Inserts a new element into the set in the gap that the
2477	/// cursor is currently pointing to.
2478	///
2479	/// After the insertion the cursor will be pointing at the gap before the
2480	/// newly inserted element.
2481	///
2482	/// If the inserted element is not greater than the element before the
2483	/// cursor (if any), or if it not less than the element after the cursor (if
2484	/// any), then an [`UnorderedKeyError`] is returned since this would
2485	/// invalidate the [`Ord`] invariant between the elements of the set.
2486	#[unstable(feature = "btree_cursors", issue = "107540")]
2487	pub fn insert_after(&mut self, value: T) -> Result<(), UnorderedKeyError> {
2488	self.inner.insert_after(value, SetValZST)
2489	}
2490
2491	/// Inserts a new element into the set in the gap that the
2492	/// cursor is currently pointing to.
2493	///
2494	/// After the insertion the cursor will be pointing at the gap after the
2495	/// newly inserted element.
2496	///
2497	/// If the inserted element is not greater than the element before the
2498	/// cursor (if any), or if it not less than the element after the cursor (if
2499	/// any), then an [`UnorderedKeyError`] is returned since this would
2500	/// invalidate the [`Ord`] invariant between the elements of the set.
2501	#[unstable(feature = "btree_cursors", issue = "107540")]
2502	pub fn insert_before(&mut self, value: T) -> Result<(), UnorderedKeyError> {
2503	self.inner.insert_before(value, SetValZST)
2504	}
2505
2506	/// Removes the next element from the `BTreeSet`.
2507	///
2508	/// The element that was removed is returned. The cursor position is
2509	/// unchanged (before the removed element).
2510	#[unstable(feature = "btree_cursors", issue = "107540")]
2511	pub fn remove_next(&mut self) -> Option<T> {
2512	self.inner.remove_next().map(\|(k, _)\| k)
2513	}
2514
2515	/// Removes the preceding element from the `BTreeSet`.
2516	///
2517	/// The element that was removed is returned. The cursor position is
2518	/// unchanged (after the removed element).
2519	#[unstable(feature = "btree_cursors", issue = "107540")]
2520	pub fn remove_prev(&mut self) -> Option<T> {
2521	self.inner.remove_prev().map(\|(k, _)\| k)
2522	}
2523	}
2524
2525	#[unstable(feature = "btree_cursors", issue = "107540")]
2526	pub use super::map::UnorderedKeyError;
2527
2528	#[cfg(test)]
2529	mod tests;
2530