1use crate::vec::Vec;
2use core::borrow::Borrow;
3use core::cmp::Ordering::{self, Equal, Greater, Less};
4use core::cmp::{max, min};
5use core::fmt::{self, Debug};
6use core::hash::{Hash, Hasher};
7use core::iter::{FusedIterator, Peekable};
8use core::mem::ManuallyDrop;
9use core::ops::{BitAnd, BitOr, BitXor, RangeBounds, Sub};
10
11use super::map::{BTreeMap, Keys};
12use super::merge_iter::MergeIterInner;
13use super::set_val::SetValZST;
14use super::Recover;
15
16use crate::alloc::{Allocator, Global};
17
18/// An ordered set based on a B-Tree.
19///
20/// See [`BTreeMap`]'s documentation for a detailed discussion of this collection's performance
21/// benefits and drawbacks.
22///
23/// It is a logic error for an item to be modified in such a way that the item's ordering relative
24/// to any other item, as determined by the [`Ord`] trait, changes while it is in the set. This is
25/// normally only possible through [`Cell`], [`RefCell`], global state, I/O, or unsafe code.
26/// The behavior resulting from such a logic error is not specified, but will be encapsulated to the
27/// `BTreeSet` that observed the logic error and not result in undefined behavior. This could
28/// include panics, incorrect results, aborts, memory leaks, and non-termination.
29///
30/// Iterators returned by [`BTreeSet::iter`] produce their items in order, and take worst-case
31/// logarithmic and amortized constant time per item returned.
32///
33/// [`Cell`]: core::cell::Cell
34/// [`RefCell`]: core::cell::RefCell
35///
36/// # Examples
37///
38/// ```
39/// use std::collections::BTreeSet;
40///
41/// // Type inference lets us omit an explicit type signature (which
42/// // would be `BTreeSet<&str>` in this example).
43/// let mut books = BTreeSet::new();
44///
45/// // Add some books.
46/// books.insert("A Dance With Dragons");
47/// books.insert("To Kill a Mockingbird");
48/// books.insert("The Odyssey");
49/// books.insert("The Great Gatsby");
50///
51/// // Check for a specific one.
52/// if !books.contains("The Winds of Winter") {
53/// println!("We have {} books, but The Winds of Winter ain't one.",
54/// books.len());
55/// }
56///
57/// // Remove a book.
58/// books.remove("The Odyssey");
59///
60/// // Iterate over everything.
61/// for book in &books {
62/// println!("{book}");
63/// }
64/// ```
65///
66/// A `BTreeSet` with a known list of items can be initialized from an array:
67///
68/// ```
69/// use std::collections::BTreeSet;
70///
71/// let set = BTreeSet::from([1, 2, 3]);
72/// ```
73#[stable(feature = "rust1", since = "1.0.0")]
74#[cfg_attr(not(test), rustc_diagnostic_item = "BTreeSet")]
75pub struct BTreeSet<
76 T,
77 #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + Clone = Global,
78> {
79 map: BTreeMap<T, SetValZST, A>,
80}
81
82#[stable(feature = "rust1", since = "1.0.0")]
83impl<T: Hash, A: Allocator + Clone> Hash for BTreeSet<T, A> {
84 fn hash<H: Hasher>(&self, state: &mut H) {
85 self.map.hash(state)
86 }
87}
88
89#[stable(feature = "rust1", since = "1.0.0")]
90impl<T: PartialEq, A: Allocator + Clone> PartialEq for BTreeSet<T, A> {
91 fn eq(&self, other: &BTreeSet<T, A>) -> bool {
92 self.map.eq(&other.map)
93 }
94}
95
96#[stable(feature = "rust1", since = "1.0.0")]
97impl<T: Eq, A: Allocator + Clone> Eq for BTreeSet<T, A> {}
98
99#[stable(feature = "rust1", since = "1.0.0")]
100impl<T: PartialOrd, A: Allocator + Clone> PartialOrd for BTreeSet<T, A> {
101 fn partial_cmp(&self, other: &BTreeSet<T, A>) -> Option<Ordering> {
102 self.map.partial_cmp(&other.map)
103 }
104}
105
106#[stable(feature = "rust1", since = "1.0.0")]
107impl<T: Ord, A: Allocator + Clone> Ord for BTreeSet<T, A> {
108 fn cmp(&self, other: &BTreeSet<T, A>) -> Ordering {
109 self.map.cmp(&other.map)
110 }
111}
112
113#[stable(feature = "rust1", since = "1.0.0")]
114impl<T: Clone, A: Allocator + Clone> Clone for BTreeSet<T, A> {
115 fn clone(&self) -> Self {
116 BTreeSet { map: self.map.clone() }
117 }
118
119 fn clone_from(&mut self, other: &Self) {
120 self.map.clone_from(&other.map);
121 }
122}
123
124/// An iterator over the items of a `BTreeSet`.
125///
126/// This `struct` is created by the [`iter`] method on [`BTreeSet`].
127/// See its documentation for more.
128///
129/// [`iter`]: BTreeSet::iter
130#[must_use = "iterators are lazy and do nothing unless consumed"]
131#[stable(feature = "rust1", since = "1.0.0")]
132pub struct Iter<'a, T: 'a> {
133 iter: Keys<'a, T, SetValZST>,
134}
135
136#[stable(feature = "collection_debug", since = "1.17.0")]
137impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> {
138 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
139 f.debug_tuple(name:"Iter").field(&self.iter.clone()).finish()
140 }
141}
142
143/// An owning iterator over the items of a `BTreeSet`.
144///
145/// This `struct` is created by the [`into_iter`] method on [`BTreeSet`]
146/// (provided by the [`IntoIterator`] trait). See its documentation for more.
147///
148/// [`into_iter`]: BTreeSet#method.into_iter
149#[stable(feature = "rust1", since = "1.0.0")]
150#[derive(Debug)]
151pub struct IntoIter<
152 T,
153 #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + Clone = Global,
154> {
155 iter: super::map::IntoIter<T, SetValZST, A>,
156}
157
158/// An iterator over a sub-range of items in a `BTreeSet`.
159///
160/// This `struct` is created by the [`range`] method on [`BTreeSet`].
161/// See its documentation for more.
162///
163/// [`range`]: BTreeSet::range
164#[must_use = "iterators are lazy and do nothing unless consumed"]
165#[derive(Debug)]
166#[stable(feature = "btree_range", since = "1.17.0")]
167pub struct Range<'a, T: 'a> {
168 iter: super::map::Range<'a, T, SetValZST>,
169}
170
171/// A lazy iterator producing elements in the difference of `BTreeSet`s.
172///
173/// This `struct` is created by the [`difference`] method on [`BTreeSet`].
174/// See its documentation for more.
175///
176/// [`difference`]: BTreeSet::difference
177#[must_use = "this returns the difference as an iterator, \
178 without modifying either input set"]
179#[stable(feature = "rust1", since = "1.0.0")]
180pub struct Difference<
181 'a,
182 T: 'a,
183 #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + Clone = Global,
184> {
185 inner: DifferenceInner<'a, T, A>,
186}
187enum DifferenceInner<'a, T: 'a, A: Allocator + Clone> {
188 Stitch {
189 // iterate all of `self` and some of `other`, spotting matches along the way
190 self_iter: Iter<'a, T>,
191 other_iter: Peekable<Iter<'a, T>>,
192 },
193 Search {
194 // iterate `self`, look up in `other`
195 self_iter: Iter<'a, T>,
196 other_set: &'a BTreeSet<T, A>,
197 },
198 Iterate(Iter<'a, T>), // simply produce all elements in `self`
199}
200
201// Explicit Debug impl necessary because of issue #26925
202impl<T: Debug, A: Allocator + Clone> Debug for DifferenceInner<'_, T, A> {
203 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
204 match self {
205 DifferenceInner::Stitch { self_iter: &Iter<'_, T>, other_iter: &Peekable> } => f&mut DebugStruct<'_, '_>
206 .debug_struct("Stitch")
207 .field("self_iter", self_iter)
208 .field(name:"other_iter", value:other_iter)
209 .finish(),
210 DifferenceInner::Search { self_iter: &Iter<'_, T>, other_set: &&BTreeSet } => f&mut DebugStruct<'_, '_>
211 .debug_struct("Search")
212 .field("self_iter", self_iter)
213 .field(name:"other_iter", value:other_set)
214 .finish(),
215 DifferenceInner::Iterate(x: &Iter<'_, T>) => f.debug_tuple(name:"Iterate").field(x).finish(),
216 }
217 }
218}
219
220#[stable(feature = "collection_debug", since = "1.17.0")]
221impl<T: fmt::Debug, A: Allocator + Clone> fmt::Debug for Difference<'_, T, A> {
222 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
223 f.debug_tuple(name:"Difference").field(&self.inner).finish()
224 }
225}
226
227/// A lazy iterator producing elements in the symmetric difference of `BTreeSet`s.
228///
229/// This `struct` is created by the [`symmetric_difference`] method on
230/// [`BTreeSet`]. See its documentation for more.
231///
232/// [`symmetric_difference`]: BTreeSet::symmetric_difference
233#[must_use = "this returns the difference as an iterator, \
234 without modifying either input set"]
235#[stable(feature = "rust1", since = "1.0.0")]
236pub struct SymmetricDifference<'a, T: 'a>(MergeIterInner<Iter<'a, T>>);
237
238#[stable(feature = "collection_debug", since = "1.17.0")]
239impl<T: fmt::Debug> fmt::Debug for SymmetricDifference<'_, T> {
240 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
241 f.debug_tuple(name:"SymmetricDifference").field(&self.0).finish()
242 }
243}
244
245/// A lazy iterator producing elements in the intersection of `BTreeSet`s.
246///
247/// This `struct` is created by the [`intersection`] method on [`BTreeSet`].
248/// See its documentation for more.
249///
250/// [`intersection`]: BTreeSet::intersection
251#[must_use = "this returns the intersection as an iterator, \
252 without modifying either input set"]
253#[stable(feature = "rust1", since = "1.0.0")]
254pub struct Intersection<
255 'a,
256 T: 'a,
257 #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + Clone = Global,
258> {
259 inner: IntersectionInner<'a, T, A>,
260}
261enum IntersectionInner<'a, T: 'a, A: Allocator + Clone> {
262 Stitch {
263 // iterate similarly sized sets jointly, spotting matches along the way
264 a: Iter<'a, T>,
265 b: Iter<'a, T>,
266 },
267 Search {
268 // iterate a small set, look up in the large set
269 small_iter: Iter<'a, T>,
270 large_set: &'a BTreeSet<T, A>,
271 },
272 Answer(Option<&'a T>), // return a specific element or emptiness
273}
274
275// Explicit Debug impl necessary because of issue #26925
276impl<T: Debug, A: Allocator + Clone> Debug for IntersectionInner<'_, T, A> {
277 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
278 match self {
279 IntersectionInner::Stitch { a: &Iter<'_, T>, b: &Iter<'_, T> } => {
280 f.debug_struct("Stitch").field("a", a).field(name:"b", value:b).finish()
281 }
282 IntersectionInner::Search { small_iter: &Iter<'_, T>, large_set: &&BTreeSet } => f&mut DebugStruct<'_, '_>
283 .debug_struct("Search")
284 .field("small_iter", small_iter)
285 .field(name:"large_set", value:large_set)
286 .finish(),
287 IntersectionInner::Answer(x: &Option<&T>) => f.debug_tuple(name:"Answer").field(x).finish(),
288 }
289 }
290}
291
292#[stable(feature = "collection_debug", since = "1.17.0")]
293impl<T: Debug, A: Allocator + Clone> Debug for Intersection<'_, T, A> {
294 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
295 f.debug_tuple(name:"Intersection").field(&self.inner).finish()
296 }
297}
298
299/// A lazy iterator producing elements in the union of `BTreeSet`s.
300///
301/// This `struct` is created by the [`union`] method on [`BTreeSet`].
302/// See its documentation for more.
303///
304/// [`union`]: BTreeSet::union
305#[must_use = "this returns the union as an iterator, \
306 without modifying either input set"]
307#[stable(feature = "rust1", since = "1.0.0")]
308pub struct Union<'a, T: 'a>(MergeIterInner<Iter<'a, T>>);
309
310#[stable(feature = "collection_debug", since = "1.17.0")]
311impl<T: fmt::Debug> fmt::Debug for Union<'_, T> {
312 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
313 f.debug_tuple(name:"Union").field(&self.0).finish()
314 }
315}
316
317// This constant is used by functions that compare two sets.
318// It estimates the relative size at which searching performs better
319// than iterating, based on the benchmarks in
320// https://github.com/ssomers/rust_bench_btreeset_intersection.
321// It's used to divide rather than multiply sizes, to rule out overflow,
322// and it's a power of two to make that division cheap.
323const ITER_PERFORMANCE_TIPPING_SIZE_DIFF: usize = 16;
324
325impl<T> BTreeSet<T> {
326 /// Makes a new, empty `BTreeSet`.
327 ///
328 /// Does not allocate anything on its own.
329 ///
330 /// # Examples
331 ///
332 /// ```
333 /// # #![allow(unused_mut)]
334 /// use std::collections::BTreeSet;
335 ///
336 /// let mut set: BTreeSet<i32> = BTreeSet::new();
337 /// ```
338 #[stable(feature = "rust1", since = "1.0.0")]
339 #[rustc_const_stable(feature = "const_btree_new", since = "1.66.0")]
340 #[must_use]
341 pub const fn new() -> BTreeSet<T> {
342 BTreeSet { map: BTreeMap::new() }
343 }
344}
345
346impl<T, A: Allocator + Clone> BTreeSet<T, A> {
347 /// Makes a new `BTreeSet` with a reasonable choice of B.
348 ///
349 /// # Examples
350 ///
351 /// ```
352 /// # #![allow(unused_mut)]
353 /// # #![feature(allocator_api)]
354 /// # #![feature(btreemap_alloc)]
355 /// use std::collections::BTreeSet;
356 /// use std::alloc::Global;
357 ///
358 /// let mut set: BTreeSet<i32> = BTreeSet::new_in(Global);
359 /// ```
360 #[unstable(feature = "btreemap_alloc", issue = "32838")]
361 pub const fn new_in(alloc: A) -> BTreeSet<T, A> {
362 BTreeSet { map: BTreeMap::new_in(alloc) }
363 }
364
365 /// Constructs a double-ended iterator over a sub-range of elements in the set.
366 /// The simplest way is to use the range syntax `min..max`, thus `range(min..max)` will
367 /// yield elements from min (inclusive) to max (exclusive).
368 /// The range may also be entered as `(Bound<T>, Bound<T>)`, so for example
369 /// `range((Excluded(4), Included(10)))` will yield a left-exclusive, right-inclusive
370 /// range from 4 to 10.
371 ///
372 /// # Panics
373 ///
374 /// Panics if range `start > end`.
375 /// Panics if range `start == end` and both bounds are `Excluded`.
376 ///
377 /// # Examples
378 ///
379 /// ```
380 /// use std::collections::BTreeSet;
381 /// use std::ops::Bound::Included;
382 ///
383 /// let mut set = BTreeSet::new();
384 /// set.insert(3);
385 /// set.insert(5);
386 /// set.insert(8);
387 /// for &elem in set.range((Included(&4), Included(&8))) {
388 /// println!("{elem}");
389 /// }
390 /// assert_eq!(Some(&5), set.range(4..).next());
391 /// ```
392 #[stable(feature = "btree_range", since = "1.17.0")]
393 pub fn range<K: ?Sized, R>(&self, range: R) -> Range<'_, T>
394 where
395 K: Ord,
396 T: Borrow<K> + Ord,
397 R: RangeBounds<K>,
398 {
399 Range { iter: self.map.range(range) }
400 }
401
402 /// Visits the elements representing the difference,
403 /// i.e., the elements that are in `self` but not in `other`,
404 /// in ascending order.
405 ///
406 /// # Examples
407 ///
408 /// ```
409 /// use std::collections::BTreeSet;
410 ///
411 /// let mut a = BTreeSet::new();
412 /// a.insert(1);
413 /// a.insert(2);
414 ///
415 /// let mut b = BTreeSet::new();
416 /// b.insert(2);
417 /// b.insert(3);
418 ///
419 /// let diff: Vec<_> = a.difference(&b).cloned().collect();
420 /// assert_eq!(diff, [1]);
421 /// ```
422 #[stable(feature = "rust1", since = "1.0.0")]
423 pub fn difference<'a>(&'a self, other: &'a BTreeSet<T, A>) -> Difference<'a, T, A>
424 where
425 T: Ord,
426 {
427 let (self_min, self_max) =
428 if let (Some(self_min), Some(self_max)) = (self.first(), self.last()) {
429 (self_min, self_max)
430 } else {
431 return Difference { inner: DifferenceInner::Iterate(self.iter()) };
432 };
433 let (other_min, other_max) =
434 if let (Some(other_min), Some(other_max)) = (other.first(), other.last()) {
435 (other_min, other_max)
436 } else {
437 return Difference { inner: DifferenceInner::Iterate(self.iter()) };
438 };
439 Difference {
440 inner: match (self_min.cmp(other_max), self_max.cmp(other_min)) {
441 (Greater, _) | (_, Less) => DifferenceInner::Iterate(self.iter()),
442 (Equal, _) => {
443 let mut self_iter = self.iter();
444 self_iter.next();
445 DifferenceInner::Iterate(self_iter)
446 }
447 (_, Equal) => {
448 let mut self_iter = self.iter();
449 self_iter.next_back();
450 DifferenceInner::Iterate(self_iter)
451 }
452 _ if self.len() <= other.len() / ITER_PERFORMANCE_TIPPING_SIZE_DIFF => {
453 DifferenceInner::Search { self_iter: self.iter(), other_set: other }
454 }
455 _ => DifferenceInner::Stitch {
456 self_iter: self.iter(),
457 other_iter: other.iter().peekable(),
458 },
459 },
460 }
461 }
462
463 /// Visits the elements representing the symmetric difference,
464 /// i.e., the elements that are in `self` or in `other` but not in both,
465 /// in ascending order.
466 ///
467 /// # Examples
468 ///
469 /// ```
470 /// use std::collections::BTreeSet;
471 ///
472 /// let mut a = BTreeSet::new();
473 /// a.insert(1);
474 /// a.insert(2);
475 ///
476 /// let mut b = BTreeSet::new();
477 /// b.insert(2);
478 /// b.insert(3);
479 ///
480 /// let sym_diff: Vec<_> = a.symmetric_difference(&b).cloned().collect();
481 /// assert_eq!(sym_diff, [1, 3]);
482 /// ```
483 #[stable(feature = "rust1", since = "1.0.0")]
484 pub fn symmetric_difference<'a>(
485 &'a self,
486 other: &'a BTreeSet<T, A>,
487 ) -> SymmetricDifference<'a, T>
488 where
489 T: Ord,
490 {
491 SymmetricDifference(MergeIterInner::new(self.iter(), other.iter()))
492 }
493
494 /// Visits the elements representing the intersection,
495 /// i.e., the elements that are both in `self` and `other`,
496 /// in ascending order.
497 ///
498 /// # Examples
499 ///
500 /// ```
501 /// use std::collections::BTreeSet;
502 ///
503 /// let mut a = BTreeSet::new();
504 /// a.insert(1);
505 /// a.insert(2);
506 ///
507 /// let mut b = BTreeSet::new();
508 /// b.insert(2);
509 /// b.insert(3);
510 ///
511 /// let intersection: Vec<_> = a.intersection(&b).cloned().collect();
512 /// assert_eq!(intersection, [2]);
513 /// ```
514 #[stable(feature = "rust1", since = "1.0.0")]
515 pub fn intersection<'a>(&'a self, other: &'a BTreeSet<T, A>) -> Intersection<'a, T, A>
516 where
517 T: Ord,
518 {
519 let (self_min, self_max) =
520 if let (Some(self_min), Some(self_max)) = (self.first(), self.last()) {
521 (self_min, self_max)
522 } else {
523 return Intersection { inner: IntersectionInner::Answer(None) };
524 };
525 let (other_min, other_max) =
526 if let (Some(other_min), Some(other_max)) = (other.first(), other.last()) {
527 (other_min, other_max)
528 } else {
529 return Intersection { inner: IntersectionInner::Answer(None) };
530 };
531 Intersection {
532 inner: match (self_min.cmp(other_max), self_max.cmp(other_min)) {
533 (Greater, _) | (_, Less) => IntersectionInner::Answer(None),
534 (Equal, _) => IntersectionInner::Answer(Some(self_min)),
535 (_, Equal) => IntersectionInner::Answer(Some(self_max)),
536 _ if self.len() <= other.len() / ITER_PERFORMANCE_TIPPING_SIZE_DIFF => {
537 IntersectionInner::Search { small_iter: self.iter(), large_set: other }
538 }
539 _ if other.len() <= self.len() / ITER_PERFORMANCE_TIPPING_SIZE_DIFF => {
540 IntersectionInner::Search { small_iter: other.iter(), large_set: self }
541 }
542 _ => IntersectionInner::Stitch { a: self.iter(), b: other.iter() },
543 },
544 }
545 }
546
547 /// Visits the elements representing the union,
548 /// i.e., all the elements in `self` or `other`, without duplicates,
549 /// in ascending order.
550 ///
551 /// # Examples
552 ///
553 /// ```
554 /// use std::collections::BTreeSet;
555 ///
556 /// let mut a = BTreeSet::new();
557 /// a.insert(1);
558 ///
559 /// let mut b = BTreeSet::new();
560 /// b.insert(2);
561 ///
562 /// let union: Vec<_> = a.union(&b).cloned().collect();
563 /// assert_eq!(union, [1, 2]);
564 /// ```
565 #[stable(feature = "rust1", since = "1.0.0")]
566 pub fn union<'a>(&'a self, other: &'a BTreeSet<T, A>) -> Union<'a, T>
567 where
568 T: Ord,
569 {
570 Union(MergeIterInner::new(self.iter(), other.iter()))
571 }
572
573 /// Clears the set, removing all elements.
574 ///
575 /// # Examples
576 ///
577 /// ```
578 /// use std::collections::BTreeSet;
579 ///
580 /// let mut v = BTreeSet::new();
581 /// v.insert(1);
582 /// v.clear();
583 /// assert!(v.is_empty());
584 /// ```
585 #[stable(feature = "rust1", since = "1.0.0")]
586 pub fn clear(&mut self)
587 where
588 A: Clone,
589 {
590 self.map.clear()
591 }
592
593 /// Returns `true` if the set contains an element equal to the value.
594 ///
595 /// The value may be any borrowed form of the set's element type,
596 /// but the ordering on the borrowed form *must* match the
597 /// ordering on the element type.
598 ///
599 /// # Examples
600 ///
601 /// ```
602 /// use std::collections::BTreeSet;
603 ///
604 /// let set = BTreeSet::from([1, 2, 3]);
605 /// assert_eq!(set.contains(&1), true);
606 /// assert_eq!(set.contains(&4), false);
607 /// ```
608 #[stable(feature = "rust1", since = "1.0.0")]
609 pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool
610 where
611 T: Borrow<Q> + Ord,
612 Q: Ord,
613 {
614 self.map.contains_key(value)
615 }
616
617 /// Returns a reference to the element in the set, if any, that is equal to
618 /// the value.
619 ///
620 /// The value may be any borrowed form of the set's element type,
621 /// but the ordering on the borrowed form *must* match the
622 /// ordering on the element type.
623 ///
624 /// # Examples
625 ///
626 /// ```
627 /// use std::collections::BTreeSet;
628 ///
629 /// let set = BTreeSet::from([1, 2, 3]);
630 /// assert_eq!(set.get(&2), Some(&2));
631 /// assert_eq!(set.get(&4), None);
632 /// ```
633 #[stable(feature = "set_recovery", since = "1.9.0")]
634 pub fn get<Q: ?Sized>(&self, value: &Q) -> Option<&T>
635 where
636 T: Borrow<Q> + Ord,
637 Q: Ord,
638 {
639 Recover::get(&self.map, value)
640 }
641
642 /// Returns `true` if `self` has no elements in common with `other`.
643 /// This is equivalent to checking for an empty intersection.
644 ///
645 /// # Examples
646 ///
647 /// ```
648 /// use std::collections::BTreeSet;
649 ///
650 /// let a = BTreeSet::from([1, 2, 3]);
651 /// let mut b = BTreeSet::new();
652 ///
653 /// assert_eq!(a.is_disjoint(&b), true);
654 /// b.insert(4);
655 /// assert_eq!(a.is_disjoint(&b), true);
656 /// b.insert(1);
657 /// assert_eq!(a.is_disjoint(&b), false);
658 /// ```
659 #[must_use]
660 #[stable(feature = "rust1", since = "1.0.0")]
661 pub fn is_disjoint(&self, other: &BTreeSet<T, A>) -> bool
662 where
663 T: Ord,
664 {
665 self.intersection(other).next().is_none()
666 }
667
668 /// Returns `true` if the set is a subset of another,
669 /// i.e., `other` contains at least all the elements in `self`.
670 ///
671 /// # Examples
672 ///
673 /// ```
674 /// use std::collections::BTreeSet;
675 ///
676 /// let sup = BTreeSet::from([1, 2, 3]);
677 /// let mut set = BTreeSet::new();
678 ///
679 /// assert_eq!(set.is_subset(&sup), true);
680 /// set.insert(2);
681 /// assert_eq!(set.is_subset(&sup), true);
682 /// set.insert(4);
683 /// assert_eq!(set.is_subset(&sup), false);
684 /// ```
685 #[must_use]
686 #[stable(feature = "rust1", since = "1.0.0")]
687 pub fn is_subset(&self, other: &BTreeSet<T, A>) -> bool
688 where
689 T: Ord,
690 {
691 // Same result as self.difference(other).next().is_none()
692 // but the code below is faster (hugely in some cases).
693 if self.len() > other.len() {
694 return false;
695 }
696 let (self_min, self_max) =
697 if let (Some(self_min), Some(self_max)) = (self.first(), self.last()) {
698 (self_min, self_max)
699 } else {
700 return true; // self is empty
701 };
702 let (other_min, other_max) =
703 if let (Some(other_min), Some(other_max)) = (other.first(), other.last()) {
704 (other_min, other_max)
705 } else {
706 return false; // other is empty
707 };
708 let mut self_iter = self.iter();
709 match self_min.cmp(other_min) {
710 Less => return false,
711 Equal => {
712 self_iter.next();
713 }
714 Greater => (),
715 }
716 match self_max.cmp(other_max) {
717 Greater => return false,
718 Equal => {
719 self_iter.next_back();
720 }
721 Less => (),
722 }
723 if self_iter.len() <= other.len() / ITER_PERFORMANCE_TIPPING_SIZE_DIFF {
724 for next in self_iter {
725 if !other.contains(next) {
726 return false;
727 }
728 }
729 } else {
730 let mut other_iter = other.iter();
731 other_iter.next();
732 other_iter.next_back();
733 let mut self_next = self_iter.next();
734 while let Some(self1) = self_next {
735 match other_iter.next().map_or(Less, |other1| self1.cmp(other1)) {
736 Less => return false,
737 Equal => self_next = self_iter.next(),
738 Greater => (),
739 }
740 }
741 }
742 true
743 }
744
745 /// Returns `true` if the set is a superset of another,
746 /// i.e., `self` contains at least all the elements in `other`.
747 ///
748 /// # Examples
749 ///
750 /// ```
751 /// use std::collections::BTreeSet;
752 ///
753 /// let sub = BTreeSet::from([1, 2]);
754 /// let mut set = BTreeSet::new();
755 ///
756 /// assert_eq!(set.is_superset(&sub), false);
757 ///
758 /// set.insert(0);
759 /// set.insert(1);
760 /// assert_eq!(set.is_superset(&sub), false);
761 ///
762 /// set.insert(2);
763 /// assert_eq!(set.is_superset(&sub), true);
764 /// ```
765 #[must_use]
766 #[stable(feature = "rust1", since = "1.0.0")]
767 pub fn is_superset(&self, other: &BTreeSet<T, A>) -> bool
768 where
769 T: Ord,
770 {
771 other.is_subset(self)
772 }
773
774 /// Returns a reference to the first element in the set, if any.
775 /// This element is always the minimum of all elements in the set.
776 ///
777 /// # Examples
778 ///
779 /// Basic usage:
780 ///
781 /// ```
782 /// use std::collections::BTreeSet;
783 ///
784 /// let mut set = BTreeSet::new();
785 /// assert_eq!(set.first(), None);
786 /// set.insert(1);
787 /// assert_eq!(set.first(), Some(&1));
788 /// set.insert(2);
789 /// assert_eq!(set.first(), Some(&1));
790 /// ```
791 #[must_use]
792 #[stable(feature = "map_first_last", since = "1.66.0")]
793 pub fn first(&self) -> Option<&T>
794 where
795 T: Ord,
796 {
797 self.map.first_key_value().map(|(k, _)| k)
798 }
799
800 /// Returns a reference to the last element in the set, if any.
801 /// This element is always the maximum of all elements in the set.
802 ///
803 /// # Examples
804 ///
805 /// Basic usage:
806 ///
807 /// ```
808 /// use std::collections::BTreeSet;
809 ///
810 /// let mut set = BTreeSet::new();
811 /// assert_eq!(set.last(), None);
812 /// set.insert(1);
813 /// assert_eq!(set.last(), Some(&1));
814 /// set.insert(2);
815 /// assert_eq!(set.last(), Some(&2));
816 /// ```
817 #[must_use]
818 #[stable(feature = "map_first_last", since = "1.66.0")]
819 pub fn last(&self) -> Option<&T>
820 where
821 T: Ord,
822 {
823 self.map.last_key_value().map(|(k, _)| k)
824 }
825
826 /// Removes the first element from the set and returns it, if any.
827 /// The first element is always the minimum element in the set.
828 ///
829 /// # Examples
830 ///
831 /// ```
832 /// use std::collections::BTreeSet;
833 ///
834 /// let mut set = BTreeSet::new();
835 ///
836 /// set.insert(1);
837 /// while let Some(n) = set.pop_first() {
838 /// assert_eq!(n, 1);
839 /// }
840 /// assert!(set.is_empty());
841 /// ```
842 #[stable(feature = "map_first_last", since = "1.66.0")]
843 pub fn pop_first(&mut self) -> Option<T>
844 where
845 T: Ord,
846 {
847 self.map.pop_first().map(|kv| kv.0)
848 }
849
850 /// Removes the last element from the set and returns it, if any.
851 /// The last element is always the maximum element in the set.
852 ///
853 /// # Examples
854 ///
855 /// ```
856 /// use std::collections::BTreeSet;
857 ///
858 /// let mut set = BTreeSet::new();
859 ///
860 /// set.insert(1);
861 /// while let Some(n) = set.pop_last() {
862 /// assert_eq!(n, 1);
863 /// }
864 /// assert!(set.is_empty());
865 /// ```
866 #[stable(feature = "map_first_last", since = "1.66.0")]
867 pub fn pop_last(&mut self) -> Option<T>
868 where
869 T: Ord,
870 {
871 self.map.pop_last().map(|kv| kv.0)
872 }
873
874 /// Adds a value to the set.
875 ///
876 /// Returns whether the value was newly inserted. That is:
877 ///
878 /// - If the set did not previously contain an equal value, `true` is
879 /// returned.
880 /// - If the set already contained an equal value, `false` is returned, and
881 /// the entry is not updated.
882 ///
883 /// See the [module-level documentation] for more.
884 ///
885 /// [module-level documentation]: index.html#insert-and-complex-keys
886 ///
887 /// # Examples
888 ///
889 /// ```
890 /// use std::collections::BTreeSet;
891 ///
892 /// let mut set = BTreeSet::new();
893 ///
894 /// assert_eq!(set.insert(2), true);
895 /// assert_eq!(set.insert(2), false);
896 /// assert_eq!(set.len(), 1);
897 /// ```
898 #[stable(feature = "rust1", since = "1.0.0")]
899 pub fn insert(&mut self, value: T) -> bool
900 where
901 T: Ord,
902 {
903 self.map.insert(value, SetValZST::default()).is_none()
904 }
905
906 /// Adds a value to the set, replacing the existing element, if any, that is
907 /// equal to the value. Returns the replaced element.
908 ///
909 /// # Examples
910 ///
911 /// ```
912 /// use std::collections::BTreeSet;
913 ///
914 /// let mut set = BTreeSet::new();
915 /// set.insert(Vec::<i32>::new());
916 ///
917 /// assert_eq!(set.get(&[][..]).unwrap().capacity(), 0);
918 /// set.replace(Vec::with_capacity(10));
919 /// assert_eq!(set.get(&[][..]).unwrap().capacity(), 10);
920 /// ```
921 #[stable(feature = "set_recovery", since = "1.9.0")]
922 pub fn replace(&mut self, value: T) -> Option<T>
923 where
924 T: Ord,
925 {
926 Recover::replace(&mut self.map, value)
927 }
928
929 /// If the set contains an element equal to the value, removes it from the
930 /// set and drops it. Returns whether such an element was present.
931 ///
932 /// The value may be any borrowed form of the set's element type,
933 /// but the ordering on the borrowed form *must* match the
934 /// ordering on the element type.
935 ///
936 /// # Examples
937 ///
938 /// ```
939 /// use std::collections::BTreeSet;
940 ///
941 /// let mut set = BTreeSet::new();
942 ///
943 /// set.insert(2);
944 /// assert_eq!(set.remove(&2), true);
945 /// assert_eq!(set.remove(&2), false);
946 /// ```
947 #[stable(feature = "rust1", since = "1.0.0")]
948 pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool
949 where
950 T: Borrow<Q> + Ord,
951 Q: Ord,
952 {
953 self.map.remove(value).is_some()
954 }
955
956 /// Removes and returns the element in the set, if any, that is equal to
957 /// the value.
958 ///
959 /// The value may be any borrowed form of the set's element type,
960 /// but the ordering on the borrowed form *must* match the
961 /// ordering on the element type.
962 ///
963 /// # Examples
964 ///
965 /// ```
966 /// use std::collections::BTreeSet;
967 ///
968 /// let mut set = BTreeSet::from([1, 2, 3]);
969 /// assert_eq!(set.take(&2), Some(2));
970 /// assert_eq!(set.take(&2), None);
971 /// ```
972 #[stable(feature = "set_recovery", since = "1.9.0")]
973 pub fn take<Q: ?Sized>(&mut self, value: &Q) -> Option<T>
974 where
975 T: Borrow<Q> + Ord,
976 Q: Ord,
977 {
978 Recover::take(&mut self.map, value)
979 }
980
981 /// Retains only the elements specified by the predicate.
982 ///
983 /// In other words, remove all elements `e` for which `f(&e)` returns `false`.
984 /// The elements are visited in ascending order.
985 ///
986 /// # Examples
987 ///
988 /// ```
989 /// use std::collections::BTreeSet;
990 ///
991 /// let mut set = BTreeSet::from([1, 2, 3, 4, 5, 6]);
992 /// // Keep only the even numbers.
993 /// set.retain(|&k| k % 2 == 0);
994 /// assert!(set.iter().eq([2, 4, 6].iter()));
995 /// ```
996 #[stable(feature = "btree_retain", since = "1.53.0")]
997 pub fn retain<F>(&mut self, mut f: F)
998 where
999 T: Ord,
1000 F: FnMut(&T) -> bool,
1001 {
1002 self.extract_if(|v| !f(v)).for_each(drop);
1003 }
1004
1005 /// Moves all elements from `other` into `self`, leaving `other` empty.
1006 ///
1007 /// # Examples
1008 ///
1009 /// ```
1010 /// use std::collections::BTreeSet;
1011 ///
1012 /// let mut a = BTreeSet::new();
1013 /// a.insert(1);
1014 /// a.insert(2);
1015 /// a.insert(3);
1016 ///
1017 /// let mut b = BTreeSet::new();
1018 /// b.insert(3);
1019 /// b.insert(4);
1020 /// b.insert(5);
1021 ///
1022 /// a.append(&mut b);
1023 ///
1024 /// assert_eq!(a.len(), 5);
1025 /// assert_eq!(b.len(), 0);
1026 ///
1027 /// assert!(a.contains(&1));
1028 /// assert!(a.contains(&2));
1029 /// assert!(a.contains(&3));
1030 /// assert!(a.contains(&4));
1031 /// assert!(a.contains(&5));
1032 /// ```
1033 #[stable(feature = "btree_append", since = "1.11.0")]
1034 pub fn append(&mut self, other: &mut Self)
1035 where
1036 T: Ord,
1037 A: Clone,
1038 {
1039 self.map.append(&mut other.map);
1040 }
1041
1042 /// Splits the collection into two at the value. Returns a new collection
1043 /// with all elements greater than or equal to the value.
1044 ///
1045 /// # Examples
1046 ///
1047 /// Basic usage:
1048 ///
1049 /// ```
1050 /// use std::collections::BTreeSet;
1051 ///
1052 /// let mut a = BTreeSet::new();
1053 /// a.insert(1);
1054 /// a.insert(2);
1055 /// a.insert(3);
1056 /// a.insert(17);
1057 /// a.insert(41);
1058 ///
1059 /// let b = a.split_off(&3);
1060 ///
1061 /// assert_eq!(a.len(), 2);
1062 /// assert_eq!(b.len(), 3);
1063 ///
1064 /// assert!(a.contains(&1));
1065 /// assert!(a.contains(&2));
1066 ///
1067 /// assert!(b.contains(&3));
1068 /// assert!(b.contains(&17));
1069 /// assert!(b.contains(&41));
1070 /// ```
1071 #[stable(feature = "btree_split_off", since = "1.11.0")]
1072 pub fn split_off<Q: ?Sized + Ord>(&mut self, value: &Q) -> Self
1073 where
1074 T: Borrow<Q> + Ord,
1075 A: Clone,
1076 {
1077 BTreeSet { map: self.map.split_off(value) }
1078 }
1079
1080 /// Creates an iterator that visits all elements in ascending order and
1081 /// uses a closure to determine if an element should be removed.
1082 ///
1083 /// If the closure returns `true`, the element is removed from the set and
1084 /// yielded. If the closure returns `false`, or panics, the element remains
1085 /// in the set and will not be yielded.
1086 ///
1087 /// If the returned `ExtractIf` is not exhausted, e.g. because it is dropped without iterating
1088 /// or the iteration short-circuits, then the remaining elements will be retained.
1089 /// Use [`retain`] with a negated predicate if you do not need the returned iterator.
1090 ///
1091 /// [`retain`]: BTreeSet::retain
1092 /// # Examples
1093 ///
1094 /// Splitting a set into even and odd values, reusing the original set:
1095 ///
1096 /// ```
1097 /// #![feature(btree_extract_if)]
1098 /// use std::collections::BTreeSet;
1099 ///
1100 /// let mut set: BTreeSet<i32> = (0..8).collect();
1101 /// let evens: BTreeSet<_> = set.extract_if(|v| v % 2 == 0).collect();
1102 /// let odds = set;
1103 /// assert_eq!(evens.into_iter().collect::<Vec<_>>(), vec![0, 2, 4, 6]);
1104 /// assert_eq!(odds.into_iter().collect::<Vec<_>>(), vec![1, 3, 5, 7]);
1105 /// ```
1106 #[unstable(feature = "btree_extract_if", issue = "70530")]
1107 pub fn extract_if<'a, F>(&'a mut self, pred: F) -> ExtractIf<'a, T, F, A>
1108 where
1109 T: Ord,
1110 F: 'a + FnMut(&T) -> bool,
1111 {
1112 let (inner, alloc) = self.map.extract_if_inner();
1113 ExtractIf { pred, inner, alloc }
1114 }
1115
1116 /// Gets an iterator that visits the elements in the `BTreeSet` in ascending
1117 /// order.
1118 ///
1119 /// # Examples
1120 ///
1121 /// ```
1122 /// use std::collections::BTreeSet;
1123 ///
1124 /// let set = BTreeSet::from([3, 1, 2]);
1125 /// let mut set_iter = set.iter();
1126 /// assert_eq!(set_iter.next(), Some(&1));
1127 /// assert_eq!(set_iter.next(), Some(&2));
1128 /// assert_eq!(set_iter.next(), Some(&3));
1129 /// assert_eq!(set_iter.next(), None);
1130 /// ```
1131 #[stable(feature = "rust1", since = "1.0.0")]
1132 pub fn iter(&self) -> Iter<'_, T> {
1133 Iter { iter: self.map.keys() }
1134 }
1135
1136 /// Returns the number of elements in the set.
1137 ///
1138 /// # Examples
1139 ///
1140 /// ```
1141 /// use std::collections::BTreeSet;
1142 ///
1143 /// let mut v = BTreeSet::new();
1144 /// assert_eq!(v.len(), 0);
1145 /// v.insert(1);
1146 /// assert_eq!(v.len(), 1);
1147 /// ```
1148 #[must_use]
1149 #[stable(feature = "rust1", since = "1.0.0")]
1150 #[rustc_const_unstable(
1151 feature = "const_btree_len",
1152 issue = "71835",
1153 implied_by = "const_btree_new"
1154 )]
1155 pub const fn len(&self) -> usize {
1156 self.map.len()
1157 }
1158
1159 /// Returns `true` if the set contains no elements.
1160 ///
1161 /// # Examples
1162 ///
1163 /// ```
1164 /// use std::collections::BTreeSet;
1165 ///
1166 /// let mut v = BTreeSet::new();
1167 /// assert!(v.is_empty());
1168 /// v.insert(1);
1169 /// assert!(!v.is_empty());
1170 /// ```
1171 #[must_use]
1172 #[stable(feature = "rust1", since = "1.0.0")]
1173 #[rustc_const_unstable(
1174 feature = "const_btree_len",
1175 issue = "71835",
1176 implied_by = "const_btree_new"
1177 )]
1178 pub const fn is_empty(&self) -> bool {
1179 self.len() == 0
1180 }
1181}
1182
1183#[stable(feature = "rust1", since = "1.0.0")]
1184impl<T: Ord> FromIterator<T> for BTreeSet<T> {
1185 fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> BTreeSet<T> {
1186 let mut inputs: Vec<_> = iter.into_iter().collect();
1187
1188 if inputs.is_empty() {
1189 return BTreeSet::new();
1190 }
1191
1192 // use stable sort to preserve the insertion order.
1193 inputs.sort();
1194 BTreeSet::from_sorted_iter(inputs.into_iter(), alloc:Global)
1195 }
1196}
1197
1198impl<T: Ord, A: Allocator + Clone> BTreeSet<T, A> {
1199 fn from_sorted_iter<I: Iterator<Item = T>>(iter: I, alloc: A) -> BTreeSet<T, A> {
1200 let iter: impl Iterator = iter.map(|k: T| (k, SetValZST::default()));
1201 let map: BTreeMap = BTreeMap::bulk_build_from_sorted_iter(iter, alloc);
1202 BTreeSet { map }
1203 }
1204}
1205
1206#[stable(feature = "std_collections_from_array", since = "1.56.0")]
1207impl<T: Ord, const N: usize> From<[T; N]> for BTreeSet<T> {
1208 /// Converts a `[T; N]` into a `BTreeSet<T>`.
1209 ///
1210 /// ```
1211 /// use std::collections::BTreeSet;
1212 ///
1213 /// let set1 = BTreeSet::from([1, 2, 3, 4]);
1214 /// let set2: BTreeSet<_> = [1, 2, 3, 4].into();
1215 /// assert_eq!(set1, set2);
1216 /// ```
1217 fn from(mut arr: [T; N]) -> Self {
1218 if N == 0 {
1219 return BTreeSet::new();
1220 }
1221
1222 // use stable sort to preserve the insertion order.
1223 arr.sort();
1224 let iter: impl Iterator = IntoIterator::into_iter(self:arr).map(|k: T| (k, SetValZST::default()));
1225 let map: BTreeMap = BTreeMap::bulk_build_from_sorted_iter(iter, alloc:Global);
1226 BTreeSet { map }
1227 }
1228}
1229
1230#[stable(feature = "rust1", since = "1.0.0")]
1231impl<T, A: Allocator + Clone> IntoIterator for BTreeSet<T, A> {
1232 type Item = T;
1233 type IntoIter = IntoIter<T, A>;
1234
1235 /// Gets an iterator for moving out the `BTreeSet`'s contents.
1236 ///
1237 /// # Examples
1238 ///
1239 /// ```
1240 /// use std::collections::BTreeSet;
1241 ///
1242 /// let set = BTreeSet::from([1, 2, 3, 4]);
1243 ///
1244 /// let v: Vec<_> = set.into_iter().collect();
1245 /// assert_eq!(v, [1, 2, 3, 4]);
1246 /// ```
1247 fn into_iter(self) -> IntoIter<T, A> {
1248 IntoIter { iter: self.map.into_iter() }
1249 }
1250}
1251
1252#[stable(feature = "rust1", since = "1.0.0")]
1253impl<'a, T, A: Allocator + Clone> IntoIterator for &'a BTreeSet<T, A> {
1254 type Item = &'a T;
1255 type IntoIter = Iter<'a, T>;
1256
1257 fn into_iter(self) -> Iter<'a, T> {
1258 self.iter()
1259 }
1260}
1261
1262/// An iterator produced by calling `extract_if` on BTreeSet.
1263#[unstable(feature = "btree_extract_if", issue = "70530")]
1264#[must_use = "iterators are lazy and do nothing unless consumed"]
1265pub struct ExtractIf<
1266 'a,
1267 T,
1268 F,
1269 #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + Clone = Global,
1270> where
1271 T: 'a,
1272 F: 'a + FnMut(&T) -> bool,
1273{
1274 pred: F,
1275 inner: super::map::ExtractIfInner<'a, T, SetValZST>,
1276 /// The BTreeMap will outlive this IntoIter so we don't care about drop order for `alloc`.
1277 alloc: A,
1278}
1279
1280#[unstable(feature = "btree_extract_if", issue = "70530")]
1281impl<T, F, A: Allocator + Clone> fmt::Debug for ExtractIf<'_, T, F, A>
1282where
1283 T: fmt::Debug,
1284 F: FnMut(&T) -> bool,
1285{
1286 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1287 f.debug_tuple(name:"ExtractIf").field(&self.inner.peek().map(|(k: &T, _)| k)).finish()
1288 }
1289}
1290
1291#[unstable(feature = "btree_extract_if", issue = "70530")]
1292impl<'a, T, F, A: Allocator + Clone> Iterator for ExtractIf<'_, T, F, A>
1293where
1294 F: 'a + FnMut(&T) -> bool,
1295{
1296 type Item = T;
1297
1298 fn next(&mut self) -> Option<T> {
1299 let pred: &mut F = &mut self.pred;
1300 let mut mapped_pred: impl FnMut(&T, &mut SetValZST) -> … = |k: &T, _v: &mut SetValZST| pred(k);
1301 self.inner.next(&mut mapped_pred, self.alloc.clone()).map(|(k: T, _)| k)
1302 }
1303
1304 fn size_hint(&self) -> (usize, Option<usize>) {
1305 self.inner.size_hint()
1306 }
1307}
1308
1309#[unstable(feature = "btree_extract_if", issue = "70530")]
1310impl<T, F, A: Allocator + Clone> FusedIterator for ExtractIf<'_, T, F, A> where F: FnMut(&T) -> bool {}
1311
1312#[stable(feature = "rust1", since = "1.0.0")]
1313impl<T: Ord, A: Allocator + Clone> Extend<T> for BTreeSet<T, A> {
1314 #[inline]
1315 fn extend<Iter: IntoIterator<Item = T>>(&mut self, iter: Iter) {
1316 iter.into_iter().for_each(move |elem: T| {
1317 self.insert(elem);
1318 });
1319 }
1320
1321 #[inline]
1322 fn extend_one(&mut self, elem: T) {
1323 self.insert(elem);
1324 }
1325}
1326
1327#[stable(feature = "extend_ref", since = "1.2.0")]
1328impl<'a, T: 'a + Ord + Copy, A: Allocator + Clone> Extend<&'a T> for BTreeSet<T, A> {
1329 fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
1330 self.extend(iter:iter.into_iter().cloned());
1331 }
1332
1333 #[inline]
1334 fn extend_one(&mut self, &elem: T: &'a T) {
1335 self.insert(elem);
1336 }
1337}
1338
1339#[stable(feature = "rust1", since = "1.0.0")]
1340impl<T> Default for BTreeSet<T> {
1341 /// Creates an empty `BTreeSet`.
1342 fn default() -> BTreeSet<T> {
1343 BTreeSet::new()
1344 }
1345}
1346
1347#[stable(feature = "rust1", since = "1.0.0")]
1348impl<T: Ord + Clone, A: Allocator + Clone> Sub<&BTreeSet<T, A>> for &BTreeSet<T, A> {
1349 type Output = BTreeSet<T, A>;
1350
1351 /// Returns the difference of `self` and `rhs` as a new `BTreeSet<T>`.
1352 ///
1353 /// # Examples
1354 ///
1355 /// ```
1356 /// use std::collections::BTreeSet;
1357 ///
1358 /// let a = BTreeSet::from([1, 2, 3]);
1359 /// let b = BTreeSet::from([3, 4, 5]);
1360 ///
1361 /// let result = &a - &b;
1362 /// assert_eq!(result, BTreeSet::from([1, 2]));
1363 /// ```
1364 fn sub(self, rhs: &BTreeSet<T, A>) -> BTreeSet<T, A> {
1365 BTreeSet::from_sorted_iter(
1366 self.difference(rhs).cloned(),
1367 alloc:ManuallyDrop::into_inner(self.map.alloc.clone()),
1368 )
1369 }
1370}
1371
1372#[stable(feature = "rust1", since = "1.0.0")]
1373impl<T: Ord + Clone, A: Allocator + Clone> BitXor<&BTreeSet<T, A>> for &BTreeSet<T, A> {
1374 type Output = BTreeSet<T, A>;
1375
1376 /// Returns the symmetric difference of `self` and `rhs` as a new `BTreeSet<T>`.
1377 ///
1378 /// # Examples
1379 ///
1380 /// ```
1381 /// use std::collections::BTreeSet;
1382 ///
1383 /// let a = BTreeSet::from([1, 2, 3]);
1384 /// let b = BTreeSet::from([2, 3, 4]);
1385 ///
1386 /// let result = &a ^ &b;
1387 /// assert_eq!(result, BTreeSet::from([1, 4]));
1388 /// ```
1389 fn bitxor(self, rhs: &BTreeSet<T, A>) -> BTreeSet<T, A> {
1390 BTreeSet::from_sorted_iter(
1391 self.symmetric_difference(rhs).cloned(),
1392 alloc:ManuallyDrop::into_inner(self.map.alloc.clone()),
1393 )
1394 }
1395}
1396
1397#[stable(feature = "rust1", since = "1.0.0")]
1398impl<T: Ord + Clone, A: Allocator + Clone> BitAnd<&BTreeSet<T, A>> for &BTreeSet<T, A> {
1399 type Output = BTreeSet<T, A>;
1400
1401 /// Returns the intersection of `self` and `rhs` as a new `BTreeSet<T>`.
1402 ///
1403 /// # Examples
1404 ///
1405 /// ```
1406 /// use std::collections::BTreeSet;
1407 ///
1408 /// let a = BTreeSet::from([1, 2, 3]);
1409 /// let b = BTreeSet::from([2, 3, 4]);
1410 ///
1411 /// let result = &a & &b;
1412 /// assert_eq!(result, BTreeSet::from([2, 3]));
1413 /// ```
1414 fn bitand(self, rhs: &BTreeSet<T, A>) -> BTreeSet<T, A> {
1415 BTreeSet::from_sorted_iter(
1416 self.intersection(rhs).cloned(),
1417 alloc:ManuallyDrop::into_inner(self.map.alloc.clone()),
1418 )
1419 }
1420}
1421
1422#[stable(feature = "rust1", since = "1.0.0")]
1423impl<T: Ord + Clone, A: Allocator + Clone> BitOr<&BTreeSet<T, A>> for &BTreeSet<T, A> {
1424 type Output = BTreeSet<T, A>;
1425
1426 /// Returns the union of `self` and `rhs` as a new `BTreeSet<T>`.
1427 ///
1428 /// # Examples
1429 ///
1430 /// ```
1431 /// use std::collections::BTreeSet;
1432 ///
1433 /// let a = BTreeSet::from([1, 2, 3]);
1434 /// let b = BTreeSet::from([3, 4, 5]);
1435 ///
1436 /// let result = &a | &b;
1437 /// assert_eq!(result, BTreeSet::from([1, 2, 3, 4, 5]));
1438 /// ```
1439 fn bitor(self, rhs: &BTreeSet<T, A>) -> BTreeSet<T, A> {
1440 BTreeSet::from_sorted_iter(
1441 self.union(rhs).cloned(),
1442 alloc:ManuallyDrop::into_inner(self.map.alloc.clone()),
1443 )
1444 }
1445}
1446
1447#[stable(feature = "rust1", since = "1.0.0")]
1448impl<T: Debug, A: Allocator + Clone> Debug for BTreeSet<T, A> {
1449 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1450 f.debug_set().entries(self.iter()).finish()
1451 }
1452}
1453
1454#[stable(feature = "rust1", since = "1.0.0")]
1455impl<T> Clone for Iter<'_, T> {
1456 fn clone(&self) -> Self {
1457 Iter { iter: self.iter.clone() }
1458 }
1459}
1460#[stable(feature = "rust1", since = "1.0.0")]
1461impl<'a, T> Iterator for Iter<'a, T> {
1462 type Item = &'a T;
1463
1464 fn next(&mut self) -> Option<&'a T> {
1465 self.iter.next()
1466 }
1467
1468 fn size_hint(&self) -> (usize, Option<usize>) {
1469 self.iter.size_hint()
1470 }
1471
1472 fn last(mut self) -> Option<&'a T> {
1473 self.next_back()
1474 }
1475
1476 fn min(mut self) -> Option<&'a T>
1477 where
1478 &'a T: Ord,
1479 {
1480 self.next()
1481 }
1482
1483 fn max(mut self) -> Option<&'a T>
1484 where
1485 &'a T: Ord,
1486 {
1487 self.next_back()
1488 }
1489}
1490#[stable(feature = "rust1", since = "1.0.0")]
1491impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
1492 fn next_back(&mut self) -> Option<&'a T> {
1493 self.iter.next_back()
1494 }
1495}
1496#[stable(feature = "rust1", since = "1.0.0")]
1497impl<T> ExactSizeIterator for Iter<'_, T> {
1498 fn len(&self) -> usize {
1499 self.iter.len()
1500 }
1501}
1502
1503#[stable(feature = "fused", since = "1.26.0")]
1504impl<T> FusedIterator for Iter<'_, T> {}
1505
1506#[stable(feature = "rust1", since = "1.0.0")]
1507impl<T, A: Allocator + Clone> Iterator for IntoIter<T, A> {
1508 type Item = T;
1509
1510 fn next(&mut self) -> Option<T> {
1511 self.iter.next().map(|(k: T, _)| k)
1512 }
1513
1514 fn size_hint(&self) -> (usize, Option<usize>) {
1515 self.iter.size_hint()
1516 }
1517}
1518
1519#[stable(feature = "default_iters", since = "1.70.0")]
1520impl<T> Default for Iter<'_, T> {
1521 /// Creates an empty `btree_set::Iter`.
1522 ///
1523 /// ```
1524 /// # use std::collections::btree_set;
1525 /// let iter: btree_set::Iter<'_, u8> = Default::default();
1526 /// assert_eq!(iter.len(), 0);
1527 /// ```
1528 fn default() -> Self {
1529 Iter { iter: Default::default() }
1530 }
1531}
1532
1533#[stable(feature = "rust1", since = "1.0.0")]
1534impl<T, A: Allocator + Clone> DoubleEndedIterator for IntoIter<T, A> {
1535 fn next_back(&mut self) -> Option<T> {
1536 self.iter.next_back().map(|(k: T, _)| k)
1537 }
1538}
1539#[stable(feature = "rust1", since = "1.0.0")]
1540impl<T, A: Allocator + Clone> ExactSizeIterator for IntoIter<T, A> {
1541 fn len(&self) -> usize {
1542 self.iter.len()
1543 }
1544}
1545
1546#[stable(feature = "fused", since = "1.26.0")]
1547impl<T, A: Allocator + Clone> FusedIterator for IntoIter<T, A> {}
1548
1549#[stable(feature = "default_iters", since = "1.70.0")]
1550impl<T, A> Default for IntoIter<T, A>
1551where
1552 A: Allocator + Default + Clone,
1553{
1554 /// Creates an empty `btree_set::IntoIter`.
1555 ///
1556 /// ```
1557 /// # use std::collections::btree_set;
1558 /// let iter: btree_set::IntoIter<u8> = Default::default();
1559 /// assert_eq!(iter.len(), 0);
1560 /// ```
1561 fn default() -> Self {
1562 IntoIter { iter: Default::default() }
1563 }
1564}
1565
1566#[stable(feature = "btree_range", since = "1.17.0")]
1567impl<T> Clone for Range<'_, T> {
1568 fn clone(&self) -> Self {
1569 Range { iter: self.iter.clone() }
1570 }
1571}
1572
1573#[stable(feature = "btree_range", since = "1.17.0")]
1574impl<'a, T> Iterator for Range<'a, T> {
1575 type Item = &'a T;
1576
1577 fn next(&mut self) -> Option<&'a T> {
1578 self.iter.next().map(|(k, _)| k)
1579 }
1580
1581 fn last(mut self) -> Option<&'a T> {
1582 self.next_back()
1583 }
1584
1585 fn min(mut self) -> Option<&'a T>
1586 where
1587 &'a T: Ord,
1588 {
1589 self.next()
1590 }
1591
1592 fn max(mut self) -> Option<&'a T>
1593 where
1594 &'a T: Ord,
1595 {
1596 self.next_back()
1597 }
1598}
1599
1600#[stable(feature = "btree_range", since = "1.17.0")]
1601impl<'a, T> DoubleEndedIterator for Range<'a, T> {
1602 fn next_back(&mut self) -> Option<&'a T> {
1603 self.iter.next_back().map(|(k: &T, _)| k)
1604 }
1605}
1606
1607#[stable(feature = "fused", since = "1.26.0")]
1608impl<T> FusedIterator for Range<'_, T> {}
1609
1610#[stable(feature = "default_iters", since = "1.70.0")]
1611impl<T> Default for Range<'_, T> {
1612 /// Creates an empty `btree_set::Range`.
1613 ///
1614 /// ```
1615 /// # use std::collections::btree_set;
1616 /// let iter: btree_set::Range<'_, u8> = Default::default();
1617 /// assert_eq!(iter.count(), 0);
1618 /// ```
1619 fn default() -> Self {
1620 Range { iter: Default::default() }
1621 }
1622}
1623
1624#[stable(feature = "rust1", since = "1.0.0")]
1625impl<T, A: Allocator + Clone> Clone for Difference<'_, T, A> {
1626 fn clone(&self) -> Self {
1627 Difference {
1628 inner: match &self.inner {
1629 DifferenceInner::Stitch { self_iter: &Iter<'_, T>, other_iter: &Peekable> } => DifferenceInner::Stitch {
1630 self_iter: self_iter.clone(),
1631 other_iter: other_iter.clone(),
1632 },
1633 DifferenceInner::Search { self_iter: &Iter<'_, T>, other_set: &&BTreeSet } => {
1634 DifferenceInner::Search { self_iter: self_iter.clone(), other_set }
1635 }
1636 DifferenceInner::Iterate(iter: &Iter<'_, T>) => DifferenceInner::Iterate(iter.clone()),
1637 },
1638 }
1639 }
1640}
1641#[stable(feature = "rust1", since = "1.0.0")]
1642impl<'a, T: Ord, A: Allocator + Clone> Iterator for Difference<'a, T, A> {
1643 type Item = &'a T;
1644
1645 fn next(&mut self) -> Option<&'a T> {
1646 match &mut self.inner {
1647 DifferenceInner::Stitch { self_iter, other_iter } => {
1648 let mut self_next = self_iter.next()?;
1649 loop {
1650 match other_iter.peek().map_or(Less, |other_next| self_next.cmp(other_next)) {
1651 Less => return Some(self_next),
1652 Equal => {
1653 self_next = self_iter.next()?;
1654 other_iter.next();
1655 }
1656 Greater => {
1657 other_iter.next();
1658 }
1659 }
1660 }
1661 }
1662 DifferenceInner::Search { self_iter, other_set } => loop {
1663 let self_next = self_iter.next()?;
1664 if !other_set.contains(&self_next) {
1665 return Some(self_next);
1666 }
1667 },
1668 DifferenceInner::Iterate(iter) => iter.next(),
1669 }
1670 }
1671
1672 fn size_hint(&self) -> (usize, Option<usize>) {
1673 let (self_len, other_len) = match &self.inner {
1674 DifferenceInner::Stitch { self_iter, other_iter } => {
1675 (self_iter.len(), other_iter.len())
1676 }
1677 DifferenceInner::Search { self_iter, other_set } => (self_iter.len(), other_set.len()),
1678 DifferenceInner::Iterate(iter) => (iter.len(), 0),
1679 };
1680 (self_len.saturating_sub(other_len), Some(self_len))
1681 }
1682
1683 fn min(mut self) -> Option<&'a T> {
1684 self.next()
1685 }
1686}
1687
1688#[stable(feature = "fused", since = "1.26.0")]
1689impl<T: Ord, A: Allocator + Clone> FusedIterator for Difference<'_, T, A> {}
1690
1691#[stable(feature = "rust1", since = "1.0.0")]
1692impl<T> Clone for SymmetricDifference<'_, T> {
1693 fn clone(&self) -> Self {
1694 SymmetricDifference(self.0.clone())
1695 }
1696}
1697#[stable(feature = "rust1", since = "1.0.0")]
1698impl<'a, T: Ord> Iterator for SymmetricDifference<'a, T> {
1699 type Item = &'a T;
1700
1701 fn next(&mut self) -> Option<&'a T> {
1702 loop {
1703 let (a_next: Option<&T>, b_next: Option<&T>) = self.0.nexts(Self::Item::cmp);
1704 if a_next.and(optb:b_next).is_none() {
1705 return a_next.or(optb:b_next);
1706 }
1707 }
1708 }
1709
1710 fn size_hint(&self) -> (usize, Option<usize>) {
1711 let (a_len: usize, b_len: usize) = self.0.lens();
1712 // No checked_add, because even if a and b refer to the same set,
1713 // and T is a zero-sized type, the storage overhead of sets limits
1714 // the number of elements to less than half the range of usize.
1715 (0, Some(a_len + b_len))
1716 }
1717
1718 fn min(mut self) -> Option<&'a T> {
1719 self.next()
1720 }
1721}
1722
1723#[stable(feature = "fused", since = "1.26.0")]
1724impl<T: Ord> FusedIterator for SymmetricDifference<'_, T> {}
1725
1726#[stable(feature = "rust1", since = "1.0.0")]
1727impl<T, A: Allocator + Clone> Clone for Intersection<'_, T, A> {
1728 fn clone(&self) -> Self {
1729 Intersection {
1730 inner: match &self.inner {
1731 IntersectionInner::Stitch { a: &Iter<'_, T>, b: &Iter<'_, T> } => {
1732 IntersectionInner::Stitch { a: a.clone(), b: b.clone() }
1733 }
1734 IntersectionInner::Search { small_iter: &Iter<'_, T>, large_set: &&BTreeSet } => {
1735 IntersectionInner::Search { small_iter: small_iter.clone(), large_set }
1736 }
1737 IntersectionInner::Answer(answer: &Option<&T>) => IntersectionInner::Answer(*answer),
1738 },
1739 }
1740 }
1741}
1742#[stable(feature = "rust1", since = "1.0.0")]
1743impl<'a, T: Ord, A: Allocator + Clone> Iterator for Intersection<'a, T, A> {
1744 type Item = &'a T;
1745
1746 fn next(&mut self) -> Option<&'a T> {
1747 match &mut self.inner {
1748 IntersectionInner::Stitch { a, b } => {
1749 let mut a_next = a.next()?;
1750 let mut b_next = b.next()?;
1751 loop {
1752 match a_next.cmp(b_next) {
1753 Less => a_next = a.next()?,
1754 Greater => b_next = b.next()?,
1755 Equal => return Some(a_next),
1756 }
1757 }
1758 }
1759 IntersectionInner::Search { small_iter, large_set } => loop {
1760 let small_next = small_iter.next()?;
1761 if large_set.contains(&small_next) {
1762 return Some(small_next);
1763 }
1764 },
1765 IntersectionInner::Answer(answer) => answer.take(),
1766 }
1767 }
1768
1769 fn size_hint(&self) -> (usize, Option<usize>) {
1770 match &self.inner {
1771 IntersectionInner::Stitch { a, b } => (0, Some(min(a.len(), b.len()))),
1772 IntersectionInner::Search { small_iter, .. } => (0, Some(small_iter.len())),
1773 IntersectionInner::Answer(None) => (0, Some(0)),
1774 IntersectionInner::Answer(Some(_)) => (1, Some(1)),
1775 }
1776 }
1777
1778 fn min(mut self) -> Option<&'a T> {
1779 self.next()
1780 }
1781}
1782
1783#[stable(feature = "fused", since = "1.26.0")]
1784impl<T: Ord, A: Allocator + Clone> FusedIterator for Intersection<'_, T, A> {}
1785
1786#[stable(feature = "rust1", since = "1.0.0")]
1787impl<T> Clone for Union<'_, T> {
1788 fn clone(&self) -> Self {
1789 Union(self.0.clone())
1790 }
1791}
1792#[stable(feature = "rust1", since = "1.0.0")]
1793impl<'a, T: Ord> Iterator for Union<'a, T> {
1794 type Item = &'a T;
1795
1796 fn next(&mut self) -> Option<&'a T> {
1797 let (a_next: Option<&T>, b_next: Option<&T>) = self.0.nexts(Self::Item::cmp);
1798 a_next.or(optb:b_next)
1799 }
1800
1801 fn size_hint(&self) -> (usize, Option<usize>) {
1802 let (a_len: usize, b_len: usize) = self.0.lens();
1803 // No checked_add - see SymmetricDifference::size_hint.
1804 (max(v1:a_len, v2:b_len), Some(a_len + b_len))
1805 }
1806
1807 fn min(mut self) -> Option<&'a T> {
1808 self.next()
1809 }
1810}
1811
1812#[stable(feature = "fused", since = "1.26.0")]
1813impl<T: Ord> FusedIterator for Union<'_, T> {}
1814
1815#[cfg(test)]
1816mod tests;
1817