set.rs - source
Description: Source of the Rust file `library/alloc/src/collections/btree/set.rs`.

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