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

Provided by KDAB

Privacy Policy
Learn Rust with the experts
Find out more