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`] and [`BTreeSet::into_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, source: &Self) {
120 self.map.clone_from(&source.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` in ascending order.
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 #[rustc_confusables("front")]
794 pub fn first(&self) -> Option<&T>
795 where
796 T: Ord,
797 {
798 self.map.first_key_value().map(|(k, _)| k)
799 }
800
801 /// Returns a reference to the last element in the set, if any.
802 /// This element is always the maximum of all elements in the set.
803 ///
804 /// # Examples
805 ///
806 /// Basic usage:
807 ///
808 /// ```
809 /// use std::collections::BTreeSet;
810 ///
811 /// let mut set = BTreeSet::new();
812 /// assert_eq!(set.last(), None);
813 /// set.insert(1);
814 /// assert_eq!(set.last(), Some(&1));
815 /// set.insert(2);
816 /// assert_eq!(set.last(), Some(&2));
817 /// ```
818 #[must_use]
819 #[stable(feature = "map_first_last", since = "1.66.0")]
820 #[rustc_confusables("back")]
821 pub fn last(&self) -> Option<&T>
822 where
823 T: Ord,
824 {
825 self.map.last_key_value().map(|(k, _)| k)
826 }
827
828 /// Removes the first element from the set and returns it, if any.
829 /// The first element is always the minimum element in the set.
830 ///
831 /// # Examples
832 ///
833 /// ```
834 /// use std::collections::BTreeSet;
835 ///
836 /// let mut set = BTreeSet::new();
837 ///
838 /// set.insert(1);
839 /// while let Some(n) = set.pop_first() {
840 /// assert_eq!(n, 1);
841 /// }
842 /// assert!(set.is_empty());
843 /// ```
844 #[stable(feature = "map_first_last", since = "1.66.0")]
845 pub fn pop_first(&mut self) -> Option<T>
846 where
847 T: Ord,
848 {
849 self.map.pop_first().map(|kv| kv.0)
850 }
851
852 /// Removes the last element from the set and returns it, if any.
853 /// The last element is always the maximum element in the set.
854 ///
855 /// # Examples
856 ///
857 /// ```
858 /// use std::collections::BTreeSet;
859 ///
860 /// let mut set = BTreeSet::new();
861 ///
862 /// set.insert(1);
863 /// while let Some(n) = set.pop_last() {
864 /// assert_eq!(n, 1);
865 /// }
866 /// assert!(set.is_empty());
867 /// ```
868 #[stable(feature = "map_first_last", since = "1.66.0")]
869 pub fn pop_last(&mut self) -> Option<T>
870 where
871 T: Ord,
872 {
873 self.map.pop_last().map(|kv| kv.0)
874 }
875
876 /// Adds a value to the set.
877 ///
878 /// Returns whether the value was newly inserted. That is:
879 ///
880 /// - If the set did not previously contain an equal value, `true` is
881 /// returned.
882 /// - If the set already contained an equal value, `false` is returned, and
883 /// the entry is not updated.
884 ///
885 /// See the [module-level documentation] for more.
886 ///
887 /// [module-level documentation]: index.html#insert-and-complex-keys
888 ///
889 /// # Examples
890 ///
891 /// ```
892 /// use std::collections::BTreeSet;
893 ///
894 /// let mut set = BTreeSet::new();
895 ///
896 /// assert_eq!(set.insert(2), true);
897 /// assert_eq!(set.insert(2), false);
898 /// assert_eq!(set.len(), 1);
899 /// ```
900 #[stable(feature = "rust1", since = "1.0.0")]
901 #[rustc_confusables("push", "put")]
902 pub fn insert(&mut self, value: T) -> bool
903 where
904 T: Ord,
905 {
906 self.map.insert(value, SetValZST::default()).is_none()
907 }
908
909 /// Adds a value to the set, replacing the existing element, if any, that is
910 /// equal to the value. Returns the replaced element.
911 ///
912 /// # Examples
913 ///
914 /// ```
915 /// use std::collections::BTreeSet;
916 ///
917 /// let mut set = BTreeSet::new();
918 /// set.insert(Vec::<i32>::new());
919 ///
920 /// assert_eq!(set.get(&[][..]).unwrap().capacity(), 0);
921 /// set.replace(Vec::with_capacity(10));
922 /// assert_eq!(set.get(&[][..]).unwrap().capacity(), 10);
923 /// ```
924 #[stable(feature = "set_recovery", since = "1.9.0")]
925 #[rustc_confusables("swap")]
926 pub fn replace(&mut self, value: T) -> Option<T>
927 where
928 T: Ord,
929 {
930 Recover::replace(&mut self.map, value)
931 }
932
933 /// If the set contains an element equal to the value, removes it from the
934 /// set and drops it. Returns whether such an element was present.
935 ///
936 /// The value may be any borrowed form of the set's element type,
937 /// but the ordering on the borrowed form *must* match the
938 /// ordering on the element type.
939 ///
940 /// # Examples
941 ///
942 /// ```
943 /// use std::collections::BTreeSet;
944 ///
945 /// let mut set = BTreeSet::new();
946 ///
947 /// set.insert(2);
948 /// assert_eq!(set.remove(&2), true);
949 /// assert_eq!(set.remove(&2), false);
950 /// ```
951 #[stable(feature = "rust1", since = "1.0.0")]
952 pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool
953 where
954 T: Borrow<Q> + Ord,
955 Q: Ord,
956 {
957 self.map.remove(value).is_some()
958 }
959
960 /// Removes and returns the element in the set, if any, that is equal to
961 /// the value.
962 ///
963 /// The value may be any borrowed form of the set's element type,
964 /// but the ordering on the borrowed form *must* match the
965 /// ordering on the element type.
966 ///
967 /// # Examples
968 ///
969 /// ```
970 /// use std::collections::BTreeSet;
971 ///
972 /// let mut set = BTreeSet::from([1, 2, 3]);
973 /// assert_eq!(set.take(&2), Some(2));
974 /// assert_eq!(set.take(&2), None);
975 /// ```
976 #[stable(feature = "set_recovery", since = "1.9.0")]
977 pub fn take<Q: ?Sized>(&mut self, value: &Q) -> Option<T>
978 where
979 T: Borrow<Q> + Ord,
980 Q: Ord,
981 {
982 Recover::take(&mut self.map, value)
983 }
984
985 /// Retains only the elements specified by the predicate.
986 ///
987 /// In other words, remove all elements `e` for which `f(&e)` returns `false`.
988 /// The elements are visited in ascending order.
989 ///
990 /// # Examples
991 ///
992 /// ```
993 /// use std::collections::BTreeSet;
994 ///
995 /// let mut set = BTreeSet::from([1, 2, 3, 4, 5, 6]);
996 /// // Keep only the even numbers.
997 /// set.retain(|&k| k % 2 == 0);
998 /// assert!(set.iter().eq([2, 4, 6].iter()));
999 /// ```
1000 #[stable(feature = "btree_retain", since = "1.53.0")]
1001 pub fn retain<F>(&mut self, mut f: F)
1002 where
1003 T: Ord,
1004 F: FnMut(&T) -> bool,
1005 {
1006 self.extract_if(|v| !f(v)).for_each(drop);
1007 }
1008
1009 /// Moves all elements from `other` into `self`, leaving `other` empty.
1010 ///
1011 /// # Examples
1012 ///
1013 /// ```
1014 /// use std::collections::BTreeSet;
1015 ///
1016 /// let mut a = BTreeSet::new();
1017 /// a.insert(1);
1018 /// a.insert(2);
1019 /// a.insert(3);
1020 ///
1021 /// let mut b = BTreeSet::new();
1022 /// b.insert(3);
1023 /// b.insert(4);
1024 /// b.insert(5);
1025 ///
1026 /// a.append(&mut b);
1027 ///
1028 /// assert_eq!(a.len(), 5);
1029 /// assert_eq!(b.len(), 0);
1030 ///
1031 /// assert!(a.contains(&1));
1032 /// assert!(a.contains(&2));
1033 /// assert!(a.contains(&3));
1034 /// assert!(a.contains(&4));
1035 /// assert!(a.contains(&5));
1036 /// ```
1037 #[stable(feature = "btree_append", since = "1.11.0")]
1038 pub fn append(&mut self, other: &mut Self)
1039 where
1040 T: Ord,
1041 A: Clone,
1042 {
1043 self.map.append(&mut other.map);
1044 }
1045
1046 /// Splits the collection into two at the value. Returns a new collection
1047 /// with all elements greater than or equal to the value.
1048 ///
1049 /// # Examples
1050 ///
1051 /// Basic usage:
1052 ///
1053 /// ```
1054 /// use std::collections::BTreeSet;
1055 ///
1056 /// let mut a = BTreeSet::new();
1057 /// a.insert(1);
1058 /// a.insert(2);
1059 /// a.insert(3);
1060 /// a.insert(17);
1061 /// a.insert(41);
1062 ///
1063 /// let b = a.split_off(&3);
1064 ///
1065 /// assert_eq!(a.len(), 2);
1066 /// assert_eq!(b.len(), 3);
1067 ///
1068 /// assert!(a.contains(&1));
1069 /// assert!(a.contains(&2));
1070 ///
1071 /// assert!(b.contains(&3));
1072 /// assert!(b.contains(&17));
1073 /// assert!(b.contains(&41));
1074 /// ```
1075 #[stable(feature = "btree_split_off", since = "1.11.0")]
1076 pub fn split_off<Q: ?Sized + Ord>(&mut self, value: &Q) -> Self
1077 where
1078 T: Borrow<Q> + Ord,
1079 A: Clone,
1080 {
1081 BTreeSet { map: self.map.split_off(value) }
1082 }
1083
1084 /// Creates an iterator that visits all elements in ascending order and
1085 /// uses a closure to determine if an element should be removed.
1086 ///
1087 /// If the closure returns `true`, the element is removed from the set and
1088 /// yielded. If the closure returns `false`, or panics, the element remains
1089 /// in the set and will not be yielded.
1090 ///
1091 /// If the returned `ExtractIf` is not exhausted, e.g. because it is dropped without iterating
1092 /// or the iteration short-circuits, then the remaining elements will be retained.
1093 /// Use [`retain`] with a negated predicate if you do not need the returned iterator.
1094 ///
1095 /// [`retain`]: BTreeSet::retain
1096 /// # Examples
1097 ///
1098 /// Splitting a set into even and odd values, reusing the original set:
1099 ///
1100 /// ```
1101 /// #![feature(btree_extract_if)]
1102 /// use std::collections::BTreeSet;
1103 ///
1104 /// let mut set: BTreeSet<i32> = (0..8).collect();
1105 /// let evens: BTreeSet<_> = set.extract_if(|v| v % 2 == 0).collect();
1106 /// let odds = set;
1107 /// assert_eq!(evens.into_iter().collect::<Vec<_>>(), vec![0, 2, 4, 6]);
1108 /// assert_eq!(odds.into_iter().collect::<Vec<_>>(), vec![1, 3, 5, 7]);
1109 /// ```
1110 #[unstable(feature = "btree_extract_if", issue = "70530")]
1111 pub fn extract_if<'a, F>(&'a mut self, pred: F) -> ExtractIf<'a, T, F, A>
1112 where
1113 T: Ord,
1114 F: 'a + FnMut(&T) -> bool,
1115 {
1116 let (inner, alloc) = self.map.extract_if_inner();
1117 ExtractIf { pred, inner, alloc }
1118 }
1119
1120 /// Gets an iterator that visits the elements in the `BTreeSet` in ascending
1121 /// order.
1122 ///
1123 /// # Examples
1124 ///
1125 /// ```
1126 /// use std::collections::BTreeSet;
1127 ///
1128 /// let set = BTreeSet::from([3, 1, 2]);
1129 /// let mut set_iter = set.iter();
1130 /// assert_eq!(set_iter.next(), Some(&1));
1131 /// assert_eq!(set_iter.next(), Some(&2));
1132 /// assert_eq!(set_iter.next(), Some(&3));
1133 /// assert_eq!(set_iter.next(), None);
1134 /// ```
1135 #[stable(feature = "rust1", since = "1.0.0")]
1136 pub fn iter(&self) -> Iter<'_, T> {
1137 Iter { iter: self.map.keys() }
1138 }
1139
1140 /// Returns the number of elements in the set.
1141 ///
1142 /// # Examples
1143 ///
1144 /// ```
1145 /// use std::collections::BTreeSet;
1146 ///
1147 /// let mut v = BTreeSet::new();
1148 /// assert_eq!(v.len(), 0);
1149 /// v.insert(1);
1150 /// assert_eq!(v.len(), 1);
1151 /// ```
1152 #[must_use]
1153 #[stable(feature = "rust1", since = "1.0.0")]
1154 #[rustc_const_unstable(
1155 feature = "const_btree_len",
1156 issue = "71835",
1157 implied_by = "const_btree_new"
1158 )]
1159 #[rustc_confusables("length", "size")]
1160 pub const fn len(&self) -> usize {
1161 self.map.len()
1162 }
1163
1164 /// Returns `true` if the set contains no elements.
1165 ///
1166 /// # Examples
1167 ///
1168 /// ```
1169 /// use std::collections::BTreeSet;
1170 ///
1171 /// let mut v = BTreeSet::new();
1172 /// assert!(v.is_empty());
1173 /// v.insert(1);
1174 /// assert!(!v.is_empty());
1175 /// ```
1176 #[must_use]
1177 #[stable(feature = "rust1", since = "1.0.0")]
1178 #[rustc_const_unstable(
1179 feature = "const_btree_len",
1180 issue = "71835",
1181 implied_by = "const_btree_new"
1182 )]
1183 pub const fn is_empty(&self) -> bool {
1184 self.len() == 0
1185 }
1186}
1187
1188#[stable(feature = "rust1", since = "1.0.0")]
1189impl<T: Ord> FromIterator<T> for BTreeSet<T> {
1190 fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> BTreeSet<T> {
1191 let mut inputs: Vec<_> = iter.into_iter().collect();
1192
1193 if inputs.is_empty() {
1194 return BTreeSet::new();
1195 }
1196
1197 // use stable sort to preserve the insertion order.
1198 inputs.sort();
1199 BTreeSet::from_sorted_iter(inputs.into_iter(), alloc:Global)
1200 }
1201}
1202
1203impl<T: Ord, A: Allocator + Clone> BTreeSet<T, A> {
1204 fn from_sorted_iter<I: Iterator<Item = T>>(iter: I, alloc: A) -> BTreeSet<T, A> {
1205 let iter: impl Iterator = iter.map(|k: T| (k, SetValZST::default()));
1206 let map: BTreeMap = BTreeMap::bulk_build_from_sorted_iter(iter, alloc);
1207 BTreeSet { map }
1208 }
1209}
1210
1211#[stable(feature = "std_collections_from_array", since = "1.56.0")]
1212impl<T: Ord, const N: usize> From<[T; N]> for BTreeSet<T> {
1213 /// Converts a `[T; N]` into a `BTreeSet<T>`.
1214 ///
1215 /// ```
1216 /// use std::collections::BTreeSet;
1217 ///
1218 /// let set1 = BTreeSet::from([1, 2, 3, 4]);
1219 /// let set2: BTreeSet<_> = [1, 2, 3, 4].into();
1220 /// assert_eq!(set1, set2);
1221 /// ```
1222 fn from(mut arr: [T; N]) -> Self {
1223 if N == 0 {
1224 return BTreeSet::new();
1225 }
1226
1227 // use stable sort to preserve the insertion order.
1228 arr.sort();
1229 let iter: impl Iterator = IntoIterator::into_iter(self:arr).map(|k: T| (k, SetValZST::default()));
1230 let map: BTreeMap = BTreeMap::bulk_build_from_sorted_iter(iter, alloc:Global);
1231 BTreeSet { map }
1232 }
1233}
1234
1235#[stable(feature = "rust1", since = "1.0.0")]
1236impl<T, A: Allocator + Clone> IntoIterator for BTreeSet<T, A> {
1237 type Item = T;
1238 type IntoIter = IntoIter<T, A>;
1239
1240 /// Gets an iterator for moving out the `BTreeSet`'s contents in ascending order.
1241 ///
1242 /// # Examples
1243 ///
1244 /// ```
1245 /// use std::collections::BTreeSet;
1246 ///
1247 /// let set = BTreeSet::from([1, 2, 3, 4]);
1248 ///
1249 /// let v: Vec<_> = set.into_iter().collect();
1250 /// assert_eq!(v, [1, 2, 3, 4]);
1251 /// ```
1252 fn into_iter(self) -> IntoIter<T, A> {
1253 IntoIter { iter: self.map.into_iter() }
1254 }
1255}
1256
1257#[stable(feature = "rust1", since = "1.0.0")]
1258impl<'a, T, A: Allocator + Clone> IntoIterator for &'a BTreeSet<T, A> {
1259 type Item = &'a T;
1260 type IntoIter = Iter<'a, T>;
1261
1262 fn into_iter(self) -> Iter<'a, T> {
1263 self.iter()
1264 }
1265}
1266
1267/// An iterator produced by calling `extract_if` on BTreeSet.
1268#[unstable(feature = "btree_extract_if", issue = "70530")]
1269#[must_use = "iterators are lazy and do nothing unless consumed"]
1270pub struct ExtractIf<
1271 'a,
1272 T,
1273 F,
1274 #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + Clone = Global,
1275> where
1276 T: 'a,
1277 F: 'a + FnMut(&T) -> bool,
1278{
1279 pred: F,
1280 inner: super::map::ExtractIfInner<'a, T, SetValZST>,
1281 /// The BTreeMap will outlive this IntoIter so we don't care about drop order for `alloc`.
1282 alloc: A,
1283}
1284
1285#[unstable(feature = "btree_extract_if", issue = "70530")]
1286impl<T, F, A: Allocator + Clone> fmt::Debug for ExtractIf<'_, T, F, A>
1287where
1288 T: fmt::Debug,
1289 F: FnMut(&T) -> bool,
1290{
1291 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1292 f.debug_tuple(name:"ExtractIf").field(&self.inner.peek().map(|(k: &T, _)| k)).finish()
1293 }
1294}
1295
1296#[unstable(feature = "btree_extract_if", issue = "70530")]
1297impl<'a, T, F, A: Allocator + Clone> Iterator for ExtractIf<'_, T, F, A>
1298where
1299 F: 'a + FnMut(&T) -> bool,
1300{
1301 type Item = T;
1302
1303 fn next(&mut self) -> Option<T> {
1304 let pred: &mut F = &mut self.pred;
1305 let mut mapped_pred: impl FnMut(&T, &mut SetValZST) -> … = |k: &T, _v: &mut SetValZST| pred(k);
1306 self.inner.next(&mut mapped_pred, self.alloc.clone()).map(|(k: T, _)| k)
1307 }
1308
1309 fn size_hint(&self) -> (usize, Option<usize>) {
1310 self.inner.size_hint()
1311 }
1312}
1313
1314#[unstable(feature = "btree_extract_if", issue = "70530")]
1315impl<T, F, A: Allocator + Clone> FusedIterator for ExtractIf<'_, T, F, A> where F: FnMut(&T) -> bool {}
1316
1317#[stable(feature = "rust1", since = "1.0.0")]
1318impl<T: Ord, A: Allocator + Clone> Extend<T> for BTreeSet<T, A> {
1319 #[inline]
1320 fn extend<Iter: IntoIterator<Item = T>>(&mut self, iter: Iter) {
1321 iter.into_iter().for_each(move |elem: T| {
1322 self.insert(elem);
1323 });
1324 }
1325
1326 #[inline]
1327 fn extend_one(&mut self, elem: T) {
1328 self.insert(elem);
1329 }
1330}
1331
1332#[stable(feature = "extend_ref", since = "1.2.0")]
1333impl<'a, T: 'a + Ord + Copy, A: Allocator + Clone> Extend<&'a T> for BTreeSet<T, A> {
1334 fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
1335 self.extend(iter:iter.into_iter().cloned());
1336 }
1337
1338 #[inline]
1339 fn extend_one(&mut self, &elem: T: &'a T) {
1340 self.insert(elem);
1341 }
1342}
1343
1344#[stable(feature = "rust1", since = "1.0.0")]
1345impl<T> Default for BTreeSet<T> {
1346 /// Creates an empty `BTreeSet`.
1347 fn default() -> BTreeSet<T> {
1348 BTreeSet::new()
1349 }
1350}
1351
1352#[stable(feature = "rust1", since = "1.0.0")]
1353impl<T: Ord + Clone, A: Allocator + Clone> Sub<&BTreeSet<T, A>> for &BTreeSet<T, A> {
1354 type Output = BTreeSet<T, A>;
1355
1356 /// Returns the difference of `self` and `rhs` as a new `BTreeSet<T>`.
1357 ///
1358 /// # Examples
1359 ///
1360 /// ```
1361 /// use std::collections::BTreeSet;
1362 ///
1363 /// let a = BTreeSet::from([1, 2, 3]);
1364 /// let b = BTreeSet::from([3, 4, 5]);
1365 ///
1366 /// let result = &a - &b;
1367 /// assert_eq!(result, BTreeSet::from([1, 2]));
1368 /// ```
1369 fn sub(self, rhs: &BTreeSet<T, A>) -> BTreeSet<T, A> {
1370 BTreeSet::from_sorted_iter(
1371 self.difference(rhs).cloned(),
1372 alloc:ManuallyDrop::into_inner(self.map.alloc.clone()),
1373 )
1374 }
1375}
1376
1377#[stable(feature = "rust1", since = "1.0.0")]
1378impl<T: Ord + Clone, A: Allocator + Clone> BitXor<&BTreeSet<T, A>> for &BTreeSet<T, A> {
1379 type Output = BTreeSet<T, A>;
1380
1381 /// Returns the symmetric difference of `self` and `rhs` as a new `BTreeSet<T>`.
1382 ///
1383 /// # Examples
1384 ///
1385 /// ```
1386 /// use std::collections::BTreeSet;
1387 ///
1388 /// let a = BTreeSet::from([1, 2, 3]);
1389 /// let b = BTreeSet::from([2, 3, 4]);
1390 ///
1391 /// let result = &a ^ &b;
1392 /// assert_eq!(result, BTreeSet::from([1, 4]));
1393 /// ```
1394 fn bitxor(self, rhs: &BTreeSet<T, A>) -> BTreeSet<T, A> {
1395 BTreeSet::from_sorted_iter(
1396 self.symmetric_difference(rhs).cloned(),
1397 alloc:ManuallyDrop::into_inner(self.map.alloc.clone()),
1398 )
1399 }
1400}
1401
1402#[stable(feature = "rust1", since = "1.0.0")]
1403impl<T: Ord + Clone, A: Allocator + Clone> BitAnd<&BTreeSet<T, A>> for &BTreeSet<T, A> {
1404 type Output = BTreeSet<T, A>;
1405
1406 /// Returns the intersection of `self` and `rhs` as a new `BTreeSet<T>`.
1407 ///
1408 /// # Examples
1409 ///
1410 /// ```
1411 /// use std::collections::BTreeSet;
1412 ///
1413 /// let a = BTreeSet::from([1, 2, 3]);
1414 /// let b = BTreeSet::from([2, 3, 4]);
1415 ///
1416 /// let result = &a & &b;
1417 /// assert_eq!(result, BTreeSet::from([2, 3]));
1418 /// ```
1419 fn bitand(self, rhs: &BTreeSet<T, A>) -> BTreeSet<T, A> {
1420 BTreeSet::from_sorted_iter(
1421 self.intersection(rhs).cloned(),
1422 alloc:ManuallyDrop::into_inner(self.map.alloc.clone()),
1423 )
1424 }
1425}
1426
1427#[stable(feature = "rust1", since = "1.0.0")]
1428impl<T: Ord + Clone, A: Allocator + Clone> BitOr<&BTreeSet<T, A>> for &BTreeSet<T, A> {
1429 type Output = BTreeSet<T, A>;
1430
1431 /// Returns the union of `self` and `rhs` as a new `BTreeSet<T>`.
1432 ///
1433 /// # Examples
1434 ///
1435 /// ```
1436 /// use std::collections::BTreeSet;
1437 ///
1438 /// let a = BTreeSet::from([1, 2, 3]);
1439 /// let b = BTreeSet::from([3, 4, 5]);
1440 ///
1441 /// let result = &a | &b;
1442 /// assert_eq!(result, BTreeSet::from([1, 2, 3, 4, 5]));
1443 /// ```
1444 fn bitor(self, rhs: &BTreeSet<T, A>) -> BTreeSet<T, A> {
1445 BTreeSet::from_sorted_iter(
1446 self.union(rhs).cloned(),
1447 alloc:ManuallyDrop::into_inner(self.map.alloc.clone()),
1448 )
1449 }
1450}
1451
1452#[stable(feature = "rust1", since = "1.0.0")]
1453impl<T: Debug, A: Allocator + Clone> Debug for BTreeSet<T, A> {
1454 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1455 f.debug_set().entries(self.iter()).finish()
1456 }
1457}
1458
1459#[stable(feature = "rust1", since = "1.0.0")]
1460impl<T> Clone for Iter<'_, T> {
1461 fn clone(&self) -> Self {
1462 Iter { iter: self.iter.clone() }
1463 }
1464}
1465#[stable(feature = "rust1", since = "1.0.0")]
1466impl<'a, T> Iterator for Iter<'a, T> {
1467 type Item = &'a T;
1468
1469 fn next(&mut self) -> Option<&'a T> {
1470 self.iter.next()
1471 }
1472
1473 fn size_hint(&self) -> (usize, Option<usize>) {
1474 self.iter.size_hint()
1475 }
1476
1477 fn last(mut self) -> Option<&'a T> {
1478 self.next_back()
1479 }
1480
1481 fn min(mut self) -> Option<&'a T>
1482 where
1483 &'a T: Ord,
1484 {
1485 self.next()
1486 }
1487
1488 fn max(mut self) -> Option<&'a T>
1489 where
1490 &'a T: Ord,
1491 {
1492 self.next_back()
1493 }
1494}
1495#[stable(feature = "rust1", since = "1.0.0")]
1496impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
1497 fn next_back(&mut self) -> Option<&'a T> {
1498 self.iter.next_back()
1499 }
1500}
1501#[stable(feature = "rust1", since = "1.0.0")]
1502impl<T> ExactSizeIterator for Iter<'_, T> {
1503 fn len(&self) -> usize {
1504 self.iter.len()
1505 }
1506}
1507
1508#[stable(feature = "fused", since = "1.26.0")]
1509impl<T> FusedIterator for Iter<'_, T> {}
1510
1511#[stable(feature = "rust1", since = "1.0.0")]
1512impl<T, A: Allocator + Clone> Iterator for IntoIter<T, A> {
1513 type Item = T;
1514
1515 fn next(&mut self) -> Option<T> {
1516 self.iter.next().map(|(k: T, _)| k)
1517 }
1518
1519 fn size_hint(&self) -> (usize, Option<usize>) {
1520 self.iter.size_hint()
1521 }
1522}
1523
1524#[stable(feature = "default_iters", since = "1.70.0")]
1525impl<T> Default for Iter<'_, T> {
1526 /// Creates an empty `btree_set::Iter`.
1527 ///
1528 /// ```
1529 /// # use std::collections::btree_set;
1530 /// let iter: btree_set::Iter<'_, u8> = Default::default();
1531 /// assert_eq!(iter.len(), 0);
1532 /// ```
1533 fn default() -> Self {
1534 Iter { iter: Default::default() }
1535 }
1536}
1537
1538#[stable(feature = "rust1", since = "1.0.0")]
1539impl<T, A: Allocator + Clone> DoubleEndedIterator for IntoIter<T, A> {
1540 fn next_back(&mut self) -> Option<T> {
1541 self.iter.next_back().map(|(k: T, _)| k)
1542 }
1543}
1544#[stable(feature = "rust1", since = "1.0.0")]
1545impl<T, A: Allocator + Clone> ExactSizeIterator for IntoIter<T, A> {
1546 fn len(&self) -> usize {
1547 self.iter.len()
1548 }
1549}
1550
1551#[stable(feature = "fused", since = "1.26.0")]
1552impl<T, A: Allocator + Clone> FusedIterator for IntoIter<T, A> {}
1553
1554#[stable(feature = "default_iters", since = "1.70.0")]
1555impl<T, A> Default for IntoIter<T, A>
1556where
1557 A: Allocator + Default + Clone,
1558{
1559 /// Creates an empty `btree_set::IntoIter`.
1560 ///
1561 /// ```
1562 /// # use std::collections::btree_set;
1563 /// let iter: btree_set::IntoIter<u8> = Default::default();
1564 /// assert_eq!(iter.len(), 0);
1565 /// ```
1566 fn default() -> Self {
1567 IntoIter { iter: Default::default() }
1568 }
1569}
1570
1571#[stable(feature = "btree_range", since = "1.17.0")]
1572impl<T> Clone for Range<'_, T> {
1573 fn clone(&self) -> Self {
1574 Range { iter: self.iter.clone() }
1575 }
1576}
1577
1578#[stable(feature = "btree_range", since = "1.17.0")]
1579impl<'a, T> Iterator for Range<'a, T> {
1580 type Item = &'a T;
1581
1582 fn next(&mut self) -> Option<&'a T> {
1583 self.iter.next().map(|(k, _)| k)
1584 }
1585
1586 fn last(mut self) -> Option<&'a T> {
1587 self.next_back()
1588 }
1589
1590 fn min(mut self) -> Option<&'a T>
1591 where
1592 &'a T: Ord,
1593 {
1594 self.next()
1595 }
1596
1597 fn max(mut self) -> Option<&'a T>
1598 where
1599 &'a T: Ord,
1600 {
1601 self.next_back()
1602 }
1603}
1604
1605#[stable(feature = "btree_range", since = "1.17.0")]
1606impl<'a, T> DoubleEndedIterator for Range<'a, T> {
1607 fn next_back(&mut self) -> Option<&'a T> {
1608 self.iter.next_back().map(|(k: &T, _)| k)
1609 }
1610}
1611
1612#[stable(feature = "fused", since = "1.26.0")]
1613impl<T> FusedIterator for Range<'_, T> {}
1614
1615#[stable(feature = "default_iters", since = "1.70.0")]
1616impl<T> Default for Range<'_, T> {
1617 /// Creates an empty `btree_set::Range`.
1618 ///
1619 /// ```
1620 /// # use std::collections::btree_set;
1621 /// let iter: btree_set::Range<'_, u8> = Default::default();
1622 /// assert_eq!(iter.count(), 0);
1623 /// ```
1624 fn default() -> Self {
1625 Range { iter: Default::default() }
1626 }
1627}
1628
1629#[stable(feature = "rust1", since = "1.0.0")]
1630impl<T, A: Allocator + Clone> Clone for Difference<'_, T, A> {
1631 fn clone(&self) -> Self {
1632 Difference {
1633 inner: match &self.inner {
1634 DifferenceInner::Stitch { self_iter: &Iter<'_, T>, other_iter: &Peekable> } => DifferenceInner::Stitch {
1635 self_iter: self_iter.clone(),
1636 other_iter: other_iter.clone(),
1637 },
1638 DifferenceInner::Search { self_iter: &Iter<'_, T>, other_set: &&BTreeSet } => {
1639 DifferenceInner::Search { self_iter: self_iter.clone(), other_set }
1640 }
1641 DifferenceInner::Iterate(iter: &Iter<'_, T>) => DifferenceInner::Iterate(iter.clone()),
1642 },
1643 }
1644 }
1645}
1646#[stable(feature = "rust1", since = "1.0.0")]
1647impl<'a, T: Ord, A: Allocator + Clone> Iterator for Difference<'a, T, A> {
1648 type Item = &'a T;
1649
1650 fn next(&mut self) -> Option<&'a T> {
1651 match &mut self.inner {
1652 DifferenceInner::Stitch { self_iter, other_iter } => {
1653 let mut self_next = self_iter.next()?;
1654 loop {
1655 match other_iter.peek().map_or(Less, |other_next| self_next.cmp(other_next)) {
1656 Less => return Some(self_next),
1657 Equal => {
1658 self_next = self_iter.next()?;
1659 other_iter.next();
1660 }
1661 Greater => {
1662 other_iter.next();
1663 }
1664 }
1665 }
1666 }
1667 DifferenceInner::Search { self_iter, other_set } => loop {
1668 let self_next = self_iter.next()?;
1669 if !other_set.contains(&self_next) {
1670 return Some(self_next);
1671 }
1672 },
1673 DifferenceInner::Iterate(iter) => iter.next(),
1674 }
1675 }
1676
1677 fn size_hint(&self) -> (usize, Option<usize>) {
1678 let (self_len, other_len) = match &self.inner {
1679 DifferenceInner::Stitch { self_iter, other_iter } => {
1680 (self_iter.len(), other_iter.len())
1681 }
1682 DifferenceInner::Search { self_iter, other_set } => (self_iter.len(), other_set.len()),
1683 DifferenceInner::Iterate(iter) => (iter.len(), 0),
1684 };
1685 (self_len.saturating_sub(other_len), Some(self_len))
1686 }
1687
1688 fn min(mut self) -> Option<&'a T> {
1689 self.next()
1690 }
1691}
1692
1693#[stable(feature = "fused", since = "1.26.0")]
1694impl<T: Ord, A: Allocator + Clone> FusedIterator for Difference<'_, T, A> {}
1695
1696#[stable(feature = "rust1", since = "1.0.0")]
1697impl<T> Clone for SymmetricDifference<'_, T> {
1698 fn clone(&self) -> Self {
1699 SymmetricDifference(self.0.clone())
1700 }
1701}
1702#[stable(feature = "rust1", since = "1.0.0")]
1703impl<'a, T: Ord> Iterator for SymmetricDifference<'a, T> {
1704 type Item = &'a T;
1705
1706 fn next(&mut self) -> Option<&'a T> {
1707 loop {
1708 let (a_next: Option<&T>, b_next: Option<&T>) = self.0.nexts(Self::Item::cmp);
1709 if a_next.and(optb:b_next).is_none() {
1710 return a_next.or(optb:b_next);
1711 }
1712 }
1713 }
1714
1715 fn size_hint(&self) -> (usize, Option<usize>) {
1716 let (a_len: usize, b_len: usize) = self.0.lens();
1717 // No checked_add, because even if a and b refer to the same set,
1718 // and T is a zero-sized type, the storage overhead of sets limits
1719 // the number of elements to less than half the range of usize.
1720 (0, Some(a_len + b_len))
1721 }
1722
1723 fn min(mut self) -> Option<&'a T> {
1724 self.next()
1725 }
1726}
1727
1728#[stable(feature = "fused", since = "1.26.0")]
1729impl<T: Ord> FusedIterator for SymmetricDifference<'_, T> {}
1730
1731#[stable(feature = "rust1", since = "1.0.0")]
1732impl<T, A: Allocator + Clone> Clone for Intersection<'_, T, A> {
1733 fn clone(&self) -> Self {
1734 Intersection {
1735 inner: match &self.inner {
1736 IntersectionInner::Stitch { a: &Iter<'_, T>, b: &Iter<'_, T> } => {
1737 IntersectionInner::Stitch { a: a.clone(), b: b.clone() }
1738 }
1739 IntersectionInner::Search { small_iter: &Iter<'_, T>, large_set: &&BTreeSet } => {
1740 IntersectionInner::Search { small_iter: small_iter.clone(), large_set }
1741 }
1742 IntersectionInner::Answer(answer: &Option<&T>) => IntersectionInner::Answer(*answer),
1743 },
1744 }
1745 }
1746}
1747#[stable(feature = "rust1", since = "1.0.0")]
1748impl<'a, T: Ord, A: Allocator + Clone> Iterator for Intersection<'a, T, A> {
1749 type Item = &'a T;
1750
1751 fn next(&mut self) -> Option<&'a T> {
1752 match &mut self.inner {
1753 IntersectionInner::Stitch { a, b } => {
1754 let mut a_next = a.next()?;
1755 let mut b_next = b.next()?;
1756 loop {
1757 match a_next.cmp(b_next) {
1758 Less => a_next = a.next()?,
1759 Greater => b_next = b.next()?,
1760 Equal => return Some(a_next),
1761 }
1762 }
1763 }
1764 IntersectionInner::Search { small_iter, large_set } => loop {
1765 let small_next = small_iter.next()?;
1766 if large_set.contains(&small_next) {
1767 return Some(small_next);
1768 }
1769 },
1770 IntersectionInner::Answer(answer) => answer.take(),
1771 }
1772 }
1773
1774 fn size_hint(&self) -> (usize, Option<usize>) {
1775 match &self.inner {
1776 IntersectionInner::Stitch { a, b } => (0, Some(min(a.len(), b.len()))),
1777 IntersectionInner::Search { small_iter, .. } => (0, Some(small_iter.len())),
1778 IntersectionInner::Answer(None) => (0, Some(0)),
1779 IntersectionInner::Answer(Some(_)) => (1, Some(1)),
1780 }
1781 }
1782
1783 fn min(mut self) -> Option<&'a T> {
1784 self.next()
1785 }
1786}
1787
1788#[stable(feature = "fused", since = "1.26.0")]
1789impl<T: Ord, A: Allocator + Clone> FusedIterator for Intersection<'_, T, A> {}
1790
1791#[stable(feature = "rust1", since = "1.0.0")]
1792impl<T> Clone for Union<'_, T> {
1793 fn clone(&self) -> Self {
1794 Union(self.0.clone())
1795 }
1796}
1797#[stable(feature = "rust1", since = "1.0.0")]
1798impl<'a, T: Ord> Iterator for Union<'a, T> {
1799 type Item = &'a T;
1800
1801 fn next(&mut self) -> Option<&'a T> {
1802 let (a_next: Option<&T>, b_next: Option<&T>) = self.0.nexts(Self::Item::cmp);
1803 a_next.or(optb:b_next)
1804 }
1805
1806 fn size_hint(&self) -> (usize, Option<usize>) {
1807 let (a_len: usize, b_len: usize) = self.0.lens();
1808 // No checked_add - see SymmetricDifference::size_hint.
1809 (max(v1:a_len, v2:b_len), Some(a_len + b_len))
1810 }
1811
1812 fn min(mut self) -> Option<&'a T> {
1813 self.next()
1814 }
1815}
1816
1817#[stable(feature = "fused", since = "1.26.0")]
1818impl<T: Ord> FusedIterator for Union<'_, T> {}
1819
1820#[cfg(test)]
1821mod tests;
1822