1 // This is pretty much entirely stolen from TreeSet, since BTreeMap has an identical interface
4 use core
::borrow
::Borrow
;
5 use core
::cmp
::Ordering
::{Equal, Greater, Less}
;
6 use core
::cmp
::{max, min}
;
7 use core
::fmt
::{self, Debug}
;
8 use core
::iter
::{FromIterator, FusedIterator, Peekable}
;
9 use core
::ops
::{BitAnd, BitOr, BitXor, RangeBounds, Sub}
;
11 use super::map
::{BTreeMap, Keys}
;
12 use super::merge_iter
::MergeIterInner
;
15 // FIXME(conventions): implement bounded iterators
17 /// A set based on a B-Tree.
19 /// See [`BTreeMap`]'s documentation for a detailed discussion of this collection's performance
20 /// benefits and drawbacks.
22 /// It is a logic error for an item to be modified in such a way that the item's ordering relative
23 /// to any other item, as determined by the [`Ord`] trait, changes while it is in the set. This is
24 /// normally only possible through [`Cell`], [`RefCell`], global state, I/O, or unsafe code.
26 /// [`Ord`]: core::cmp::Ord
27 /// [`Cell`]: core::cell::Cell
28 /// [`RefCell`]: core::cell::RefCell
33 /// use std::collections::BTreeSet;
35 /// // Type inference lets us omit an explicit type signature (which
36 /// // would be `BTreeSet<&str>` in this example).
37 /// let mut books = BTreeSet::new();
39 /// // Add some books.
40 /// books.insert("A Dance With Dragons");
41 /// books.insert("To Kill a Mockingbird");
42 /// books.insert("The Odyssey");
43 /// books.insert("The Great Gatsby");
45 /// // Check for a specific one.
46 /// if !books.contains("The Winds of Winter") {
47 /// println!("We have {} books, but The Winds of Winter ain't one.",
52 /// books.remove("The Odyssey");
54 /// // Iterate over everything.
55 /// for book in &books {
56 /// println!("{}", book);
59 #[derive(Hash, PartialEq, Eq, Ord, PartialOrd)]
60 #[stable(feature = "rust1", since = "1.0.0")]
61 pub struct BTreeSet
<T
> {
65 #[stable(feature = "rust1", since = "1.0.0")]
66 impl<T
: Clone
> Clone
for BTreeSet
<T
> {
67 fn clone(&self) -> Self {
68 BTreeSet { map: self.map.clone() }
71 fn clone_from(&mut self, other
: &Self) {
72 self.map
.clone_from(&other
.map
);
76 /// An iterator over the items of a `BTreeSet`.
78 /// This `struct` is created by the [`iter`] method on [`BTreeSet`].
79 /// See its documentation for more.
81 /// [`iter`]: BTreeSet::iter
82 #[stable(feature = "rust1", since = "1.0.0")]
83 pub struct Iter
<'a
, T
: 'a
> {
84 iter
: Keys
<'a
, T
, ()>,
87 #[stable(feature = "collection_debug", since = "1.17.0")]
88 impl<T
: fmt
::Debug
> fmt
::Debug
for Iter
<'_
, T
> {
89 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
90 f
.debug_tuple("Iter").field(&self.iter
.clone()).finish()
94 /// An owning iterator over the items of a `BTreeSet`.
96 /// This `struct` is created by the [`into_iter`] method on [`BTreeSet`]
97 /// (provided by the `IntoIterator` trait). See its documentation for more.
99 /// [`into_iter`]: BTreeSet#method.into_iter
100 #[stable(feature = "rust1", since = "1.0.0")]
102 pub struct IntoIter
<T
> {
103 iter
: super::map
::IntoIter
<T
, ()>,
106 /// An iterator over a sub-range of items in a `BTreeSet`.
108 /// This `struct` is created by the [`range`] method on [`BTreeSet`].
109 /// See its documentation for more.
111 /// [`range`]: BTreeSet::range
113 #[stable(feature = "btree_range", since = "1.17.0")]
114 pub struct Range
<'a
, T
: 'a
> {
115 iter
: super::map
::Range
<'a
, T
, ()>,
118 /// A lazy iterator producing elements in the difference of `BTreeSet`s.
120 /// This `struct` is created by the [`difference`] method on [`BTreeSet`].
121 /// See its documentation for more.
123 /// [`difference`]: BTreeSet::difference
124 #[stable(feature = "rust1", since = "1.0.0")]
125 pub struct Difference
<'a
, T
: 'a
> {
126 inner
: DifferenceInner
<'a
, T
>,
129 enum DifferenceInner
<'a
, T
: 'a
> {
131 // iterate all of `self` and some of `other`, spotting matches along the way
132 self_iter
: Iter
<'a
, T
>,
133 other_iter
: Peekable
<Iter
<'a
, T
>>,
136 // iterate `self`, look up in `other`
137 self_iter
: Iter
<'a
, T
>,
138 other_set
: &'a BTreeSet
<T
>,
140 Iterate(Iter
<'a
, T
>), // simply produce all values in `self`
143 #[stable(feature = "collection_debug", since = "1.17.0")]
144 impl<T
: fmt
::Debug
> fmt
::Debug
for Difference
<'_
, T
> {
145 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
146 f
.debug_tuple("Difference").field(&self.inner
).finish()
150 /// A lazy iterator producing elements in the symmetric difference of `BTreeSet`s.
152 /// This `struct` is created by the [`symmetric_difference`] method on
153 /// [`BTreeSet`]. See its documentation for more.
155 /// [`symmetric_difference`]: BTreeSet::symmetric_difference
156 #[stable(feature = "rust1", since = "1.0.0")]
157 pub struct SymmetricDifference
<'a
, T
: 'a
>(MergeIterInner
<Iter
<'a
, T
>>);
159 #[stable(feature = "collection_debug", since = "1.17.0")]
160 impl<T
: fmt
::Debug
> fmt
::Debug
for SymmetricDifference
<'_
, T
> {
161 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
162 f
.debug_tuple("SymmetricDifference").field(&self.0).finish()
166 /// A lazy iterator producing elements in the intersection of `BTreeSet`s.
168 /// This `struct` is created by the [`intersection`] method on [`BTreeSet`].
169 /// See its documentation for more.
171 /// [`intersection`]: BTreeSet::intersection
172 #[stable(feature = "rust1", since = "1.0.0")]
173 pub struct Intersection
<'a
, T
: 'a
> {
174 inner
: IntersectionInner
<'a
, T
>,
177 enum IntersectionInner
<'a
, T
: 'a
> {
179 // iterate similarly sized sets jointly, spotting matches along the way
184 // iterate a small set, look up in the large set
185 small_iter
: Iter
<'a
, T
>,
186 large_set
: &'a BTreeSet
<T
>,
188 Answer(Option
<&'a T
>), // return a specific value or emptiness
191 #[stable(feature = "collection_debug", since = "1.17.0")]
192 impl<T
: fmt
::Debug
> fmt
::Debug
for Intersection
<'_
, T
> {
193 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
194 f
.debug_tuple("Intersection").field(&self.inner
).finish()
198 /// A lazy iterator producing elements in the union of `BTreeSet`s.
200 /// This `struct` is created by the [`union`] method on [`BTreeSet`].
201 /// See its documentation for more.
203 /// [`union`]: BTreeSet::union
204 #[stable(feature = "rust1", since = "1.0.0")]
205 pub struct Union
<'a
, T
: 'a
>(MergeIterInner
<Iter
<'a
, T
>>);
207 #[stable(feature = "collection_debug", since = "1.17.0")]
208 impl<T
: fmt
::Debug
> fmt
::Debug
for Union
<'_
, T
> {
209 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
210 f
.debug_tuple("Union").field(&self.0).finish()
214 // This constant is used by functions that compare two sets.
215 // It estimates the relative size at which searching performs better
216 // than iterating, based on the benchmarks in
217 // https://github.com/ssomers/rust_bench_btreeset_intersection.
218 // It's used to divide rather than multiply sizes, to rule out overflow,
219 // and it's a power of two to make that division cheap.
220 const ITER_PERFORMANCE_TIPPING_SIZE_DIFF
: usize = 16;
222 impl<T
: Ord
> BTreeSet
<T
> {
223 /// Makes a new, empty `BTreeSet`.
225 /// Does not allocate anything on its own.
230 /// # #![allow(unused_mut)]
231 /// use std::collections::BTreeSet;
233 /// let mut set: BTreeSet<i32> = BTreeSet::new();
235 #[stable(feature = "rust1", since = "1.0.0")]
236 #[rustc_const_unstable(feature = "const_btree_new", issue = "71835")]
237 pub const fn new() -> BTreeSet
<T
> {
238 BTreeSet { map: BTreeMap::new() }
241 /// Constructs a double-ended iterator over a sub-range of elements in the set.
242 /// The simplest way is to use the range syntax `min..max`, thus `range(min..max)` will
243 /// yield elements from min (inclusive) to max (exclusive).
244 /// The range may also be entered as `(Bound<T>, Bound<T>)`, so for example
245 /// `range((Excluded(4), Included(10)))` will yield a left-exclusive, right-inclusive
246 /// range from 4 to 10.
251 /// use std::collections::BTreeSet;
252 /// use std::ops::Bound::Included;
254 /// let mut set = BTreeSet::new();
258 /// for &elem in set.range((Included(&4), Included(&8))) {
259 /// println!("{}", elem);
261 /// assert_eq!(Some(&5), set.range(4..).next());
263 #[stable(feature = "btree_range", since = "1.17.0")]
264 pub fn range
<K
: ?Sized
, R
>(&self, range
: R
) -> Range
<'_
, T
>
270 Range { iter: self.map.range(range) }
273 /// Visits the values representing the difference,
274 /// i.e., the values that are in `self` but not in `other`,
275 /// in ascending order.
280 /// use std::collections::BTreeSet;
282 /// let mut a = BTreeSet::new();
286 /// let mut b = BTreeSet::new();
290 /// let diff: Vec<_> = a.difference(&b).cloned().collect();
291 /// assert_eq!(diff, [1]);
293 #[stable(feature = "rust1", since = "1.0.0")]
294 pub fn difference
<'a
>(&'a
self, other
: &'a BTreeSet
<T
>) -> Difference
<'a
, T
> {
295 let (self_min
, self_max
) =
296 if let (Some(self_min
), Some(self_max
)) = (self.first(), self.last()) {
299 return Difference { inner: DifferenceInner::Iterate(self.iter()) }
;
301 let (other_min
, other_max
) =
302 if let (Some(other_min
), Some(other_max
)) = (other
.first(), other
.last()) {
303 (other_min
, other_max
)
305 return Difference { inner: DifferenceInner::Iterate(self.iter()) }
;
308 inner
: match (self_min
.cmp(other_max
), self_max
.cmp(other_min
)) {
309 (Greater
, _
) | (_
, Less
) => DifferenceInner
::Iterate(self.iter()),
311 let mut self_iter
= self.iter();
313 DifferenceInner
::Iterate(self_iter
)
316 let mut self_iter
= self.iter();
317 self_iter
.next_back();
318 DifferenceInner
::Iterate(self_iter
)
320 _
if self.len() <= other
.len() / ITER_PERFORMANCE_TIPPING_SIZE_DIFF
=> {
321 DifferenceInner
::Search { self_iter: self.iter(), other_set: other }
323 _
=> DifferenceInner
::Stitch
{
324 self_iter
: self.iter(),
325 other_iter
: other
.iter().peekable(),
331 /// Visits the values representing the symmetric difference,
332 /// i.e., the values that are in `self` or in `other` but not in both,
333 /// in ascending order.
338 /// use std::collections::BTreeSet;
340 /// let mut a = BTreeSet::new();
344 /// let mut b = BTreeSet::new();
348 /// let sym_diff: Vec<_> = a.symmetric_difference(&b).cloned().collect();
349 /// assert_eq!(sym_diff, [1, 3]);
351 #[stable(feature = "rust1", since = "1.0.0")]
352 pub fn symmetric_difference
<'a
>(
354 other
: &'a BTreeSet
<T
>,
355 ) -> SymmetricDifference
<'a
, T
> {
356 SymmetricDifference(MergeIterInner
::new(self.iter(), other
.iter()))
359 /// Visits the values representing the intersection,
360 /// i.e., the values that are both in `self` and `other`,
361 /// in ascending order.
366 /// use std::collections::BTreeSet;
368 /// let mut a = BTreeSet::new();
372 /// let mut b = BTreeSet::new();
376 /// let intersection: Vec<_> = a.intersection(&b).cloned().collect();
377 /// assert_eq!(intersection, [2]);
379 #[stable(feature = "rust1", since = "1.0.0")]
380 pub fn intersection
<'a
>(&'a
self, other
: &'a BTreeSet
<T
>) -> Intersection
<'a
, T
> {
381 let (self_min
, self_max
) =
382 if let (Some(self_min
), Some(self_max
)) = (self.first(), self.last()) {
385 return Intersection { inner: IntersectionInner::Answer(None) }
;
387 let (other_min
, other_max
) =
388 if let (Some(other_min
), Some(other_max
)) = (other
.first(), other
.last()) {
389 (other_min
, other_max
)
391 return Intersection { inner: IntersectionInner::Answer(None) }
;
394 inner
: match (self_min
.cmp(other_max
), self_max
.cmp(other_min
)) {
395 (Greater
, _
) | (_
, Less
) => IntersectionInner
::Answer(None
),
396 (Equal
, _
) => IntersectionInner
::Answer(Some(self_min
)),
397 (_
, Equal
) => IntersectionInner
::Answer(Some(self_max
)),
398 _
if self.len() <= other
.len() / ITER_PERFORMANCE_TIPPING_SIZE_DIFF
=> {
399 IntersectionInner
::Search { small_iter: self.iter(), large_set: other }
401 _
if other
.len() <= self.len() / ITER_PERFORMANCE_TIPPING_SIZE_DIFF
=> {
402 IntersectionInner
::Search { small_iter: other.iter(), large_set: self }
404 _
=> IntersectionInner
::Stitch { a: self.iter(), b: other.iter() }
,
409 /// Visits the values representing the union,
410 /// i.e., all the values in `self` or `other`, without duplicates,
411 /// in ascending order.
416 /// use std::collections::BTreeSet;
418 /// let mut a = BTreeSet::new();
421 /// let mut b = BTreeSet::new();
424 /// let union: Vec<_> = a.union(&b).cloned().collect();
425 /// assert_eq!(union, [1, 2]);
427 #[stable(feature = "rust1", since = "1.0.0")]
428 pub fn union<'a
>(&'a
self, other
: &'a BTreeSet
<T
>) -> Union
<'a
, T
> {
429 Union(MergeIterInner
::new(self.iter(), other
.iter()))
432 /// Clears the set, removing all values.
437 /// use std::collections::BTreeSet;
439 /// let mut v = BTreeSet::new();
442 /// assert!(v.is_empty());
444 #[stable(feature = "rust1", since = "1.0.0")]
445 pub fn clear(&mut self) {
449 /// Returns `true` if the set contains a value.
451 /// The value may be any borrowed form of the set's value type,
452 /// but the ordering on the borrowed form *must* match the
453 /// ordering on the value type.
458 /// use std::collections::BTreeSet;
460 /// let set: BTreeSet<_> = [1, 2, 3].iter().cloned().collect();
461 /// assert_eq!(set.contains(&1), true);
462 /// assert_eq!(set.contains(&4), false);
464 #[stable(feature = "rust1", since = "1.0.0")]
465 pub fn contains
<Q
: ?Sized
>(&self, value
: &Q
) -> bool
470 self.map
.contains_key(value
)
473 /// Returns a reference to the value in the set, if any, that is equal to the given value.
475 /// The value may be any borrowed form of the set's value type,
476 /// but the ordering on the borrowed form *must* match the
477 /// ordering on the value type.
482 /// use std::collections::BTreeSet;
484 /// let set: BTreeSet<_> = [1, 2, 3].iter().cloned().collect();
485 /// assert_eq!(set.get(&2), Some(&2));
486 /// assert_eq!(set.get(&4), None);
488 #[stable(feature = "set_recovery", since = "1.9.0")]
489 pub fn get
<Q
: ?Sized
>(&self, value
: &Q
) -> Option
<&T
>
494 Recover
::get(&self.map
, value
)
497 /// Returns `true` if `self` has no elements in common with `other`.
498 /// This is equivalent to checking for an empty intersection.
503 /// use std::collections::BTreeSet;
505 /// let a: BTreeSet<_> = [1, 2, 3].iter().cloned().collect();
506 /// let mut b = BTreeSet::new();
508 /// assert_eq!(a.is_disjoint(&b), true);
510 /// assert_eq!(a.is_disjoint(&b), true);
512 /// assert_eq!(a.is_disjoint(&b), false);
514 #[stable(feature = "rust1", since = "1.0.0")]
515 pub fn is_disjoint(&self, other
: &BTreeSet
<T
>) -> bool
{
516 self.intersection(other
).next().is_none()
519 /// Returns `true` if the set is a subset of another,
520 /// i.e., `other` contains at least all the values in `self`.
525 /// use std::collections::BTreeSet;
527 /// let sup: BTreeSet<_> = [1, 2, 3].iter().cloned().collect();
528 /// let mut set = BTreeSet::new();
530 /// assert_eq!(set.is_subset(&sup), true);
532 /// assert_eq!(set.is_subset(&sup), true);
534 /// assert_eq!(set.is_subset(&sup), false);
536 #[stable(feature = "rust1", since = "1.0.0")]
537 pub fn is_subset(&self, other
: &BTreeSet
<T
>) -> bool
{
538 // Same result as self.difference(other).next().is_none()
539 // but the code below is faster (hugely in some cases).
540 if self.len() > other
.len() {
543 let (self_min
, self_max
) =
544 if let (Some(self_min
), Some(self_max
)) = (self.first(), self.last()) {
547 return true; // self is empty
549 let (other_min
, other_max
) =
550 if let (Some(other_min
), Some(other_max
)) = (other
.first(), other
.last()) {
551 (other_min
, other_max
)
553 return false; // other is empty
555 let mut self_iter
= self.iter();
556 match self_min
.cmp(other_min
) {
557 Less
=> return false,
563 match self_max
.cmp(other_max
) {
564 Greater
=> return false,
566 self_iter
.next_back();
570 if self_iter
.len() <= other
.len() / ITER_PERFORMANCE_TIPPING_SIZE_DIFF
{
571 for next
in self_iter
{
572 if !other
.contains(next
) {
577 let mut other_iter
= other
.iter();
579 other_iter
.next_back();
580 let mut self_next
= self_iter
.next();
581 while let Some(self1
) = self_next
{
582 match other_iter
.next().map_or(Less
, |other1
| self1
.cmp(other1
)) {
583 Less
=> return false,
584 Equal
=> self_next
= self_iter
.next(),
592 /// Returns `true` if the set is a superset of another,
593 /// i.e., `self` contains at least all the values in `other`.
598 /// use std::collections::BTreeSet;
600 /// let sub: BTreeSet<_> = [1, 2].iter().cloned().collect();
601 /// let mut set = BTreeSet::new();
603 /// assert_eq!(set.is_superset(&sub), false);
607 /// assert_eq!(set.is_superset(&sub), false);
610 /// assert_eq!(set.is_superset(&sub), true);
612 #[stable(feature = "rust1", since = "1.0.0")]
613 pub fn is_superset(&self, other
: &BTreeSet
<T
>) -> bool
{
614 other
.is_subset(self)
617 /// Returns a reference to the first value in the set, if any.
618 /// This value is always the minimum of all values in the set.
625 /// #![feature(map_first_last)]
626 /// use std::collections::BTreeSet;
628 /// let mut map = BTreeSet::new();
629 /// assert_eq!(map.first(), None);
631 /// assert_eq!(map.first(), Some(&1));
633 /// assert_eq!(map.first(), Some(&1));
635 #[unstable(feature = "map_first_last", issue = "62924")]
636 pub fn first(&self) -> Option
<&T
> {
637 self.map
.first_key_value().map(|(k
, _
)| k
)
640 /// Returns a reference to the last value in the set, if any.
641 /// This value is always the maximum of all values in the set.
648 /// #![feature(map_first_last)]
649 /// use std::collections::BTreeSet;
651 /// let mut map = BTreeSet::new();
652 /// assert_eq!(map.first(), None);
654 /// assert_eq!(map.last(), Some(&1));
656 /// assert_eq!(map.last(), Some(&2));
658 #[unstable(feature = "map_first_last", issue = "62924")]
659 pub fn last(&self) -> Option
<&T
> {
660 self.map
.last_key_value().map(|(k
, _
)| k
)
663 /// Removes the first value from the set and returns it, if any.
664 /// The first value is always the minimum value in the set.
669 /// #![feature(map_first_last)]
670 /// use std::collections::BTreeSet;
672 /// let mut set = BTreeSet::new();
675 /// while let Some(n) = set.pop_first() {
676 /// assert_eq!(n, 1);
678 /// assert!(set.is_empty());
680 #[unstable(feature = "map_first_last", issue = "62924")]
681 pub fn pop_first(&mut self) -> Option
<T
> {
682 self.map
.pop_first().map(|kv
| kv
.0)
685 /// Removes the last value from the set and returns it, if any.
686 /// The last value is always the maximum value in the set.
691 /// #![feature(map_first_last)]
692 /// use std::collections::BTreeSet;
694 /// let mut set = BTreeSet::new();
697 /// while let Some(n) = set.pop_last() {
698 /// assert_eq!(n, 1);
700 /// assert!(set.is_empty());
702 #[unstable(feature = "map_first_last", issue = "62924")]
703 pub fn pop_last(&mut self) -> Option
<T
> {
704 self.map
.pop_last().map(|kv
| kv
.0)
707 /// Adds a value to the set.
709 /// If the set did not have this value present, `true` is returned.
711 /// If the set did have this value present, `false` is returned, and the
712 /// entry is not updated. See the [module-level documentation] for more.
714 /// [module-level documentation]: index.html#insert-and-complex-keys
719 /// use std::collections::BTreeSet;
721 /// let mut set = BTreeSet::new();
723 /// assert_eq!(set.insert(2), true);
724 /// assert_eq!(set.insert(2), false);
725 /// assert_eq!(set.len(), 1);
727 #[stable(feature = "rust1", since = "1.0.0")]
728 pub fn insert(&mut self, value
: T
) -> bool
{
729 self.map
.insert(value
, ()).is_none()
732 /// Adds a value to the set, replacing the existing value, if any, that is equal to the given
733 /// one. Returns the replaced value.
738 /// use std::collections::BTreeSet;
740 /// let mut set = BTreeSet::new();
741 /// set.insert(Vec::<i32>::new());
743 /// assert_eq!(set.get(&[][..]).unwrap().capacity(), 0);
744 /// set.replace(Vec::with_capacity(10));
745 /// assert_eq!(set.get(&[][..]).unwrap().capacity(), 10);
747 #[stable(feature = "set_recovery", since = "1.9.0")]
748 pub fn replace(&mut self, value
: T
) -> Option
<T
> {
749 Recover
::replace(&mut self.map
, value
)
752 /// Removes a value from the set. Returns whether the value was
753 /// present in the set.
755 /// The value may be any borrowed form of the set's value type,
756 /// but the ordering on the borrowed form *must* match the
757 /// ordering on the value type.
762 /// use std::collections::BTreeSet;
764 /// let mut set = BTreeSet::new();
767 /// assert_eq!(set.remove(&2), true);
768 /// assert_eq!(set.remove(&2), false);
770 #[stable(feature = "rust1", since = "1.0.0")]
771 pub fn remove
<Q
: ?Sized
>(&mut self, value
: &Q
) -> bool
776 self.map
.remove(value
).is_some()
779 /// Removes and returns the value in the set, if any, that is equal to the given one.
781 /// The value may be any borrowed form of the set's value type,
782 /// but the ordering on the borrowed form *must* match the
783 /// ordering on the value type.
788 /// use std::collections::BTreeSet;
790 /// let mut set: BTreeSet<_> = [1, 2, 3].iter().cloned().collect();
791 /// assert_eq!(set.take(&2), Some(2));
792 /// assert_eq!(set.take(&2), None);
794 #[stable(feature = "set_recovery", since = "1.9.0")]
795 pub fn take
<Q
: ?Sized
>(&mut self, value
: &Q
) -> Option
<T
>
800 Recover
::take(&mut self.map
, value
)
803 /// Retains only the elements specified by the predicate.
805 /// In other words, remove all elements `e` such that `f(&e)` returns `false`.
810 /// #![feature(btree_retain)]
811 /// use std::collections::BTreeSet;
813 /// let xs = [1, 2, 3, 4, 5, 6];
814 /// let mut set: BTreeSet<i32> = xs.iter().cloned().collect();
815 /// // Keep only the even numbers.
816 /// set.retain(|&k| k % 2 == 0);
817 /// assert!(set.iter().eq([2, 4, 6].iter()));
819 #[unstable(feature = "btree_retain", issue = "79025")]
820 pub fn retain
<F
>(&mut self, mut f
: F
)
822 F
: FnMut(&T
) -> bool
,
824 self.drain_filter(|v
| !f(v
));
827 /// Moves all elements from `other` into `Self`, leaving `other` empty.
832 /// use std::collections::BTreeSet;
834 /// let mut a = BTreeSet::new();
839 /// let mut b = BTreeSet::new();
844 /// a.append(&mut b);
846 /// assert_eq!(a.len(), 5);
847 /// assert_eq!(b.len(), 0);
849 /// assert!(a.contains(&1));
850 /// assert!(a.contains(&2));
851 /// assert!(a.contains(&3));
852 /// assert!(a.contains(&4));
853 /// assert!(a.contains(&5));
855 #[stable(feature = "btree_append", since = "1.11.0")]
856 pub fn append(&mut self, other
: &mut Self) {
857 self.map
.append(&mut other
.map
);
860 /// Splits the collection into two at the given key. Returns everything after the given key,
861 /// including the key.
868 /// use std::collections::BTreeSet;
870 /// let mut a = BTreeSet::new();
877 /// let b = a.split_off(&3);
879 /// assert_eq!(a.len(), 2);
880 /// assert_eq!(b.len(), 3);
882 /// assert!(a.contains(&1));
883 /// assert!(a.contains(&2));
885 /// assert!(b.contains(&3));
886 /// assert!(b.contains(&17));
887 /// assert!(b.contains(&41));
889 #[stable(feature = "btree_split_off", since = "1.11.0")]
890 pub fn split_off
<Q
: ?Sized
+ Ord
>(&mut self, key
: &Q
) -> Self
894 BTreeSet { map: self.map.split_off(key) }
897 /// Creates an iterator which uses a closure to determine if a value should be removed.
899 /// If the closure returns true, then the value is removed and yielded.
900 /// If the closure returns false, the value will remain in the list and will not be yielded
903 /// If the iterator is only partially consumed or not consumed at all, each of the remaining
904 /// values will still be subjected to the closure and removed and dropped if it returns true.
906 /// It is unspecified how many more values will be subjected to the closure
907 /// if a panic occurs in the closure, or if a panic occurs while dropping a value, or if the
908 /// `DrainFilter` itself is leaked.
912 /// Splitting a set into even and odd values, reusing the original set:
915 /// #![feature(btree_drain_filter)]
916 /// use std::collections::BTreeSet;
918 /// let mut set: BTreeSet<i32> = (0..8).collect();
919 /// let evens: BTreeSet<_> = set.drain_filter(|v| v % 2 == 0).collect();
921 /// assert_eq!(evens.into_iter().collect::<Vec<_>>(), vec![0, 2, 4, 6]);
922 /// assert_eq!(odds.into_iter().collect::<Vec<_>>(), vec![1, 3, 5, 7]);
924 #[unstable(feature = "btree_drain_filter", issue = "70530")]
925 pub fn drain_filter
<'a
, F
>(&'a
mut self, pred
: F
) -> DrainFilter
<'a
, T
, F
>
927 F
: 'a
+ FnMut(&T
) -> bool
,
929 DrainFilter { pred, inner: self.map.drain_filter_inner() }
933 impl<T
> BTreeSet
<T
> {
934 /// Gets an iterator that visits the values in the `BTreeSet` in ascending order.
939 /// use std::collections::BTreeSet;
941 /// let set: BTreeSet<usize> = [1, 2, 3].iter().cloned().collect();
942 /// let mut set_iter = set.iter();
943 /// assert_eq!(set_iter.next(), Some(&1));
944 /// assert_eq!(set_iter.next(), Some(&2));
945 /// assert_eq!(set_iter.next(), Some(&3));
946 /// assert_eq!(set_iter.next(), None);
949 /// Values returned by the iterator are returned in ascending order:
952 /// use std::collections::BTreeSet;
954 /// let set: BTreeSet<usize> = [3, 1, 2].iter().cloned().collect();
955 /// let mut set_iter = set.iter();
956 /// assert_eq!(set_iter.next(), Some(&1));
957 /// assert_eq!(set_iter.next(), Some(&2));
958 /// assert_eq!(set_iter.next(), Some(&3));
959 /// assert_eq!(set_iter.next(), None);
961 #[stable(feature = "rust1", since = "1.0.0")]
962 pub fn iter(&self) -> Iter
<'_
, T
> {
963 Iter { iter: self.map.keys() }
966 /// Returns the number of elements in the set.
971 /// use std::collections::BTreeSet;
973 /// let mut v = BTreeSet::new();
974 /// assert_eq!(v.len(), 0);
976 /// assert_eq!(v.len(), 1);
978 #[stable(feature = "rust1", since = "1.0.0")]
979 #[rustc_const_unstable(feature = "const_btree_new", issue = "71835")]
980 pub const fn len(&self) -> usize {
984 /// Returns `true` if the set contains no elements.
989 /// use std::collections::BTreeSet;
991 /// let mut v = BTreeSet::new();
992 /// assert!(v.is_empty());
994 /// assert!(!v.is_empty());
996 #[stable(feature = "rust1", since = "1.0.0")]
997 #[rustc_const_unstable(feature = "const_btree_new", issue = "71835")]
998 pub const fn is_empty(&self) -> bool
{
1003 #[stable(feature = "rust1", since = "1.0.0")]
1004 impl<T
: Ord
> FromIterator
<T
> for BTreeSet
<T
> {
1005 fn from_iter
<I
: IntoIterator
<Item
= T
>>(iter
: I
) -> BTreeSet
<T
> {
1006 let mut set
= BTreeSet
::new();
1012 #[stable(feature = "rust1", since = "1.0.0")]
1013 impl<T
> IntoIterator
for BTreeSet
<T
> {
1015 type IntoIter
= IntoIter
<T
>;
1017 /// Gets an iterator for moving out the `BTreeSet`'s contents.
1022 /// use std::collections::BTreeSet;
1024 /// let set: BTreeSet<usize> = [1, 2, 3, 4].iter().cloned().collect();
1026 /// let v: Vec<_> = set.into_iter().collect();
1027 /// assert_eq!(v, [1, 2, 3, 4]);
1029 fn into_iter(self) -> IntoIter
<T
> {
1030 IntoIter { iter: self.map.into_iter() }
1034 #[stable(feature = "rust1", since = "1.0.0")]
1035 impl<'a
, T
> IntoIterator
for &'a BTreeSet
<T
> {
1037 type IntoIter
= Iter
<'a
, T
>;
1039 fn into_iter(self) -> Iter
<'a
, T
> {
1044 /// An iterator produced by calling `drain_filter` on BTreeSet.
1045 #[unstable(feature = "btree_drain_filter", issue = "70530")]
1046 pub struct DrainFilter
<'a
, T
, F
>
1049 F
: 'a
+ FnMut(&T
) -> bool
,
1052 inner
: super::map
::DrainFilterInner
<'a
, T
, ()>,
1055 #[unstable(feature = "btree_drain_filter", issue = "70530")]
1056 impl<T
, F
> Drop
for DrainFilter
<'_
, T
, F
>
1058 F
: FnMut(&T
) -> bool
,
1060 fn drop(&mut self) {
1061 self.for_each(drop
);
1065 #[unstable(feature = "btree_drain_filter", issue = "70530")]
1066 impl<T
, F
> fmt
::Debug
for DrainFilter
<'_
, T
, F
>
1069 F
: FnMut(&T
) -> bool
,
1071 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
1072 f
.debug_tuple("DrainFilter").field(&self.inner
.peek().map(|(k
, _
)| k
)).finish()
1076 #[unstable(feature = "btree_drain_filter", issue = "70530")]
1077 impl<'a
, T
, F
> Iterator
for DrainFilter
<'_
, T
, F
>
1079 F
: 'a
+ FnMut(&T
) -> bool
,
1083 fn next(&mut self) -> Option
<T
> {
1084 let pred
= &mut self.pred
;
1085 let mut mapped_pred
= |k
: &T
, _v
: &mut ()| pred(k
);
1086 self.inner
.next(&mut mapped_pred
).map(|(k
, _
)| k
)
1089 fn size_hint(&self) -> (usize, Option
<usize>) {
1090 self.inner
.size_hint()
1094 #[unstable(feature = "btree_drain_filter", issue = "70530")]
1095 impl<T
, F
> FusedIterator
for DrainFilter
<'_
, T
, F
> where F
: FnMut(&T
) -> bool {}
1097 #[stable(feature = "rust1", since = "1.0.0")]
1098 impl<T
: Ord
> Extend
<T
> for BTreeSet
<T
> {
1100 fn extend
<Iter
: IntoIterator
<Item
= T
>>(&mut self, iter
: Iter
) {
1101 iter
.into_iter().for_each(move |elem
| {
1107 fn extend_one(&mut self, elem
: T
) {
1112 #[stable(feature = "extend_ref", since = "1.2.0")]
1113 impl<'a
, T
: 'a
+ Ord
+ Copy
> Extend
<&'a T
> for BTreeSet
<T
> {
1114 fn extend
<I
: IntoIterator
<Item
= &'a T
>>(&mut self, iter
: I
) {
1115 self.extend(iter
.into_iter().cloned());
1119 fn extend_one(&mut self, &elem
: &'a T
) {
1124 #[stable(feature = "rust1", since = "1.0.0")]
1125 impl<T
: Ord
> Default
for BTreeSet
<T
> {
1126 /// Creates an empty `BTreeSet`.
1127 fn default() -> BTreeSet
<T
> {
1132 #[stable(feature = "rust1", since = "1.0.0")]
1133 impl<T
: Ord
+ Clone
> Sub
<&BTreeSet
<T
>> for &BTreeSet
<T
> {
1134 type Output
= BTreeSet
<T
>;
1136 /// Returns the difference of `self` and `rhs` as a new `BTreeSet<T>`.
1141 /// use std::collections::BTreeSet;
1143 /// let a: BTreeSet<_> = vec![1, 2, 3].into_iter().collect();
1144 /// let b: BTreeSet<_> = vec![3, 4, 5].into_iter().collect();
1146 /// let result = &a - &b;
1147 /// let result_vec: Vec<_> = result.into_iter().collect();
1148 /// assert_eq!(result_vec, [1, 2]);
1150 fn sub(self, rhs
: &BTreeSet
<T
>) -> BTreeSet
<T
> {
1151 self.difference(rhs
).cloned().collect()
1155 #[stable(feature = "rust1", since = "1.0.0")]
1156 impl<T
: Ord
+ Clone
> BitXor
<&BTreeSet
<T
>> for &BTreeSet
<T
> {
1157 type Output
= BTreeSet
<T
>;
1159 /// Returns the symmetric difference of `self` and `rhs` as a new `BTreeSet<T>`.
1164 /// use std::collections::BTreeSet;
1166 /// let a: BTreeSet<_> = vec![1, 2, 3].into_iter().collect();
1167 /// let b: BTreeSet<_> = vec![2, 3, 4].into_iter().collect();
1169 /// let result = &a ^ &b;
1170 /// let result_vec: Vec<_> = result.into_iter().collect();
1171 /// assert_eq!(result_vec, [1, 4]);
1173 fn bitxor(self, rhs
: &BTreeSet
<T
>) -> BTreeSet
<T
> {
1174 self.symmetric_difference(rhs
).cloned().collect()
1178 #[stable(feature = "rust1", since = "1.0.0")]
1179 impl<T
: Ord
+ Clone
> BitAnd
<&BTreeSet
<T
>> for &BTreeSet
<T
> {
1180 type Output
= BTreeSet
<T
>;
1182 /// Returns the intersection of `self` and `rhs` as a new `BTreeSet<T>`.
1187 /// use std::collections::BTreeSet;
1189 /// let a: BTreeSet<_> = vec![1, 2, 3].into_iter().collect();
1190 /// let b: BTreeSet<_> = vec![2, 3, 4].into_iter().collect();
1192 /// let result = &a & &b;
1193 /// let result_vec: Vec<_> = result.into_iter().collect();
1194 /// assert_eq!(result_vec, [2, 3]);
1196 fn bitand(self, rhs
: &BTreeSet
<T
>) -> BTreeSet
<T
> {
1197 self.intersection(rhs
).cloned().collect()
1201 #[stable(feature = "rust1", since = "1.0.0")]
1202 impl<T
: Ord
+ Clone
> BitOr
<&BTreeSet
<T
>> for &BTreeSet
<T
> {
1203 type Output
= BTreeSet
<T
>;
1205 /// Returns the union of `self` and `rhs` as a new `BTreeSet<T>`.
1210 /// use std::collections::BTreeSet;
1212 /// let a: BTreeSet<_> = vec![1, 2, 3].into_iter().collect();
1213 /// let b: BTreeSet<_> = vec![3, 4, 5].into_iter().collect();
1215 /// let result = &a | &b;
1216 /// let result_vec: Vec<_> = result.into_iter().collect();
1217 /// assert_eq!(result_vec, [1, 2, 3, 4, 5]);
1219 fn bitor(self, rhs
: &BTreeSet
<T
>) -> BTreeSet
<T
> {
1220 self.union(rhs
).cloned().collect()
1224 #[stable(feature = "rust1", since = "1.0.0")]
1225 impl<T
: Debug
> Debug
for BTreeSet
<T
> {
1226 fn fmt(&self, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
1227 f
.debug_set().entries(self.iter()).finish()
1231 #[stable(feature = "rust1", since = "1.0.0")]
1232 impl<T
> Clone
for Iter
<'_
, T
> {
1233 fn clone(&self) -> Self {
1234 Iter { iter: self.iter.clone() }
1237 #[stable(feature = "rust1", since = "1.0.0")]
1238 impl<'a
, T
> Iterator
for Iter
<'a
, T
> {
1241 fn next(&mut self) -> Option
<&'a T
> {
1245 fn size_hint(&self) -> (usize, Option
<usize>) {
1246 self.iter
.size_hint()
1249 fn last(mut self) -> Option
<&'a T
> {
1253 fn min(mut self) -> Option
<&'a T
> {
1257 fn max(mut self) -> Option
<&'a T
> {
1261 #[stable(feature = "rust1", since = "1.0.0")]
1262 impl<'a
, T
> DoubleEndedIterator
for Iter
<'a
, T
> {
1263 fn next_back(&mut self) -> Option
<&'a T
> {
1264 self.iter
.next_back()
1267 #[stable(feature = "rust1", since = "1.0.0")]
1268 impl<T
> ExactSizeIterator
for Iter
<'_
, T
> {
1269 fn len(&self) -> usize {
1274 #[stable(feature = "fused", since = "1.26.0")]
1275 impl<T
> FusedIterator
for Iter
<'_
, T
> {}
1277 #[stable(feature = "rust1", since = "1.0.0")]
1278 impl<T
> Iterator
for IntoIter
<T
> {
1281 fn next(&mut self) -> Option
<T
> {
1282 self.iter
.next().map(|(k
, _
)| k
)
1285 fn size_hint(&self) -> (usize, Option
<usize>) {
1286 self.iter
.size_hint()
1289 #[stable(feature = "rust1", since = "1.0.0")]
1290 impl<T
> DoubleEndedIterator
for IntoIter
<T
> {
1291 fn next_back(&mut self) -> Option
<T
> {
1292 self.iter
.next_back().map(|(k
, _
)| k
)
1295 #[stable(feature = "rust1", since = "1.0.0")]
1296 impl<T
> ExactSizeIterator
for IntoIter
<T
> {
1297 fn len(&self) -> usize {
1302 #[stable(feature = "fused", since = "1.26.0")]
1303 impl<T
> FusedIterator
for IntoIter
<T
> {}
1305 #[stable(feature = "btree_range", since = "1.17.0")]
1306 impl<T
> Clone
for Range
<'_
, T
> {
1307 fn clone(&self) -> Self {
1308 Range { iter: self.iter.clone() }
1312 #[stable(feature = "btree_range", since = "1.17.0")]
1313 impl<'a
, T
> Iterator
for Range
<'a
, T
> {
1316 fn next(&mut self) -> Option
<&'a T
> {
1317 self.iter
.next().map(|(k
, _
)| k
)
1320 fn last(mut self) -> Option
<&'a T
> {
1324 fn min(mut self) -> Option
<&'a T
> {
1328 fn max(mut self) -> Option
<&'a T
> {
1333 #[stable(feature = "btree_range", since = "1.17.0")]
1334 impl<'a
, T
> DoubleEndedIterator
for Range
<'a
, T
> {
1335 fn next_back(&mut self) -> Option
<&'a T
> {
1336 self.iter
.next_back().map(|(k
, _
)| k
)
1340 #[stable(feature = "fused", since = "1.26.0")]
1341 impl<T
> FusedIterator
for Range
<'_
, T
> {}
1343 #[stable(feature = "rust1", since = "1.0.0")]
1344 impl<T
> Clone
for Difference
<'_
, T
> {
1345 fn clone(&self) -> Self {
1347 inner
: match &self.inner
{
1348 DifferenceInner
::Stitch { self_iter, other_iter }
=> DifferenceInner
::Stitch
{
1349 self_iter
: self_iter
.clone(),
1350 other_iter
: other_iter
.clone(),
1352 DifferenceInner
::Search { self_iter, other_set }
=> {
1353 DifferenceInner
::Search { self_iter: self_iter.clone(), other_set }
1355 DifferenceInner
::Iterate(iter
) => DifferenceInner
::Iterate(iter
.clone()),
1360 #[stable(feature = "rust1", since = "1.0.0")]
1361 impl<'a
, T
: Ord
> Iterator
for Difference
<'a
, T
> {
1364 fn next(&mut self) -> Option
<&'a T
> {
1365 match &mut self.inner
{
1366 DifferenceInner
::Stitch { self_iter, other_iter }
=> {
1367 let mut self_next
= self_iter
.next()?
;
1369 match other_iter
.peek().map_or(Less
, |other_next
| self_next
.cmp(other_next
)) {
1370 Less
=> return Some(self_next
),
1372 self_next
= self_iter
.next()?
;
1381 DifferenceInner
::Search { self_iter, other_set }
=> loop {
1382 let self_next
= self_iter
.next()?
;
1383 if !other_set
.contains(&self_next
) {
1384 return Some(self_next
);
1387 DifferenceInner
::Iterate(iter
) => iter
.next(),
1391 fn size_hint(&self) -> (usize, Option
<usize>) {
1392 let (self_len
, other_len
) = match &self.inner
{
1393 DifferenceInner
::Stitch { self_iter, other_iter }
=> {
1394 (self_iter
.len(), other_iter
.len())
1396 DifferenceInner
::Search { self_iter, other_set }
=> (self_iter
.len(), other_set
.len()),
1397 DifferenceInner
::Iterate(iter
) => (iter
.len(), 0),
1399 (self_len
.saturating_sub(other_len
), Some(self_len
))
1402 fn min(mut self) -> Option
<&'a T
> {
1407 #[stable(feature = "fused", since = "1.26.0")]
1408 impl<T
: Ord
> FusedIterator
for Difference
<'_
, T
> {}
1410 #[stable(feature = "rust1", since = "1.0.0")]
1411 impl<T
> Clone
for SymmetricDifference
<'_
, T
> {
1412 fn clone(&self) -> Self {
1413 SymmetricDifference(self.0.clone())
1416 #[stable(feature = "rust1", since = "1.0.0")]
1417 impl<'a
, T
: Ord
> Iterator
for SymmetricDifference
<'a
, T
> {
1420 fn next(&mut self) -> Option
<&'a T
> {
1422 let (a_next
, b_next
) = self.0.nexts(Self::Item
::cmp
);
1423 if a_next
.and(b_next
).is_none() {
1424 return a_next
.or(b_next
);
1429 fn size_hint(&self) -> (usize, Option
<usize>) {
1430 let (a_len
, b_len
) = self.0.lens();
1431 // No checked_add, because even if a and b refer to the same set,
1432 // and T is an empty type, the storage overhead of sets limits
1433 // the number of elements to less than half the range of usize.
1434 (0, Some(a_len
+ b_len
))
1437 fn min(mut self) -> Option
<&'a T
> {
1442 #[stable(feature = "fused", since = "1.26.0")]
1443 impl<T
: Ord
> FusedIterator
for SymmetricDifference
<'_
, T
> {}
1445 #[stable(feature = "rust1", since = "1.0.0")]
1446 impl<T
> Clone
for Intersection
<'_
, T
> {
1447 fn clone(&self) -> Self {
1449 inner
: match &self.inner
{
1450 IntersectionInner
::Stitch { a, b }
=> {
1451 IntersectionInner
::Stitch { a: a.clone(), b: b.clone() }
1453 IntersectionInner
::Search { small_iter, large_set }
=> {
1454 IntersectionInner
::Search { small_iter: small_iter.clone(), large_set }
1456 IntersectionInner
::Answer(answer
) => IntersectionInner
::Answer(*answer
),
1461 #[stable(feature = "rust1", since = "1.0.0")]
1462 impl<'a
, T
: Ord
> Iterator
for Intersection
<'a
, T
> {
1465 fn next(&mut self) -> Option
<&'a T
> {
1466 match &mut self.inner
{
1467 IntersectionInner
::Stitch { a, b }
=> {
1468 let mut a_next
= a
.next()?
;
1469 let mut b_next
= b
.next()?
;
1471 match a_next
.cmp(b_next
) {
1472 Less
=> a_next
= a
.next()?
,
1473 Greater
=> b_next
= b
.next()?
,
1474 Equal
=> return Some(a_next
),
1478 IntersectionInner
::Search { small_iter, large_set }
=> loop {
1479 let small_next
= small_iter
.next()?
;
1480 if large_set
.contains(&small_next
) {
1481 return Some(small_next
);
1484 IntersectionInner
::Answer(answer
) => answer
.take(),
1488 fn size_hint(&self) -> (usize, Option
<usize>) {
1490 IntersectionInner
::Stitch { a, b }
=> (0, Some(min(a
.len(), b
.len()))),
1491 IntersectionInner
::Search { small_iter, .. }
=> (0, Some(small_iter
.len())),
1492 IntersectionInner
::Answer(None
) => (0, Some(0)),
1493 IntersectionInner
::Answer(Some(_
)) => (1, Some(1)),
1497 fn min(mut self) -> Option
<&'a T
> {
1502 #[stable(feature = "fused", since = "1.26.0")]
1503 impl<T
: Ord
> FusedIterator
for Intersection
<'_
, T
> {}
1505 #[stable(feature = "rust1", since = "1.0.0")]
1506 impl<T
> Clone
for Union
<'_
, T
> {
1507 fn clone(&self) -> Self {
1508 Union(self.0.clone())
1511 #[stable(feature = "rust1", since = "1.0.0")]
1512 impl<'a
, T
: Ord
> Iterator
for Union
<'a
, T
> {
1515 fn next(&mut self) -> Option
<&'a T
> {
1516 let (a_next
, b_next
) = self.0.nexts(Self::Item
::cmp
);
1520 fn size_hint(&self) -> (usize, Option
<usize>) {
1521 let (a_len
, b_len
) = self.0.lens();
1522 // No checked_add - see SymmetricDifference::size_hint.
1523 (max(a_len
, b_len
), Some(a_len
+ b_len
))
1526 fn min(mut self) -> Option
<&'a T
> {
1531 #[stable(feature = "fused", since = "1.26.0")]
1532 impl<T
: Ord
> FusedIterator
for Union
<'_
, T
> {}