Skip to main content

alloc/collections/btree/
set.rs

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