New upstream version 1.50.0+dfsg1

[rustc.git] / library / alloc / src / collections / btree / set.rs

diff --git a/library/alloc/src/collections/btree/set.rs b/library/alloc/src/collections/btree/set.rs
index 684019f8f5f5e02c6afa472a5a960686a1d46e59..f63c3dd58040866339c66f66ad4914a2c03899be 100644 (file)
--- a/library/alloc/src/collections/btree/set.rs
+++ b/library/alloc/src/collections/btree/set.rs
@@ -214,13 +214,15 @@ impl<T: fmt::Debug> fmt::Debug for Union<'_, T> {
 // This constant is used by functions that compare two sets.
 // It estimates the relative size at which searching performs better
 // than iterating, based on the benchmarks in
-// https://github.com/ssomers/rust_bench_btreeset_intersection;
+// https://github.com/ssomers/rust_bench_btreeset_intersection.
 // It's used to divide rather than multiply sizes, to rule out overflow,
 // and it's a power of two to make that division cheap.
 const ITER_PERFORMANCE_TIPPING_SIZE_DIFF: usize = 16;
 
 impl<T: Ord> BTreeSet<T> {
-    /// Makes a new `BTreeSet` with a reasonable choice of B.
+    /// Makes a new, empty `BTreeSet`.
+    ///
+    /// Does not allocate anything on its own.
     ///
     /// # Examples
     ///
@@ -677,7 +679,7 @@ impl<T: Ord> BTreeSet<T> {
     /// ```
     #[unstable(feature = "map_first_last", issue = "62924")]
     pub fn pop_first(&mut self) -> Option<T> {
-        self.map.first_entry().map(|entry| entry.remove_entry().0)
+        self.map.pop_first().map(|kv| kv.0)
     }
 
     /// Removes the last value from the set and returns it, if any.
@@ -699,7 +701,7 @@ impl<T: Ord> BTreeSet<T> {
     /// ```
     #[unstable(feature = "map_first_last", issue = "62924")]
     pub fn pop_last(&mut self) -> Option<T> {
-        self.map.last_entry().map(|entry| entry.remove_entry().0)
+        self.map.pop_last().map(|kv| kv.0)
     }
 
     /// Adds a value to the set.
@@ -798,6 +800,30 @@ impl<T: Ord> BTreeSet<T> {
         Recover::take(&mut self.map, value)
     }
 
+    /// Retains only the elements specified by the predicate.
+    ///
+    /// In other words, remove all elements `e` such that `f(&e)` returns `false`.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// #![feature(btree_retain)]
+    /// use std::collections::BTreeSet;
+    ///
+    /// let xs = [1, 2, 3, 4, 5, 6];
+    /// let mut set: BTreeSet<i32> = xs.iter().cloned().collect();
+    /// // Keep only the even numbers.
+    /// set.retain(|&k| k % 2 == 0);
+    /// assert!(set.iter().eq([2, 4, 6].iter()));
+    /// ```
+    #[unstable(feature = "btree_retain", issue = "79025")]
+    pub fn retain<F>(&mut self, mut f: F)
+    where
+        F: FnMut(&T) -> bool,
+    {
+        self.drain_filter(|v| !f(v));
+    }
+
     /// Moves all elements from `other` into `Self`, leaving `other` empty.
     ///
     /// # Examples
@@ -1097,7 +1123,7 @@ impl<'a, T: 'a + Ord + Copy> Extend<&'a T> for BTreeSet<T> {
 
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<T: Ord> Default for BTreeSet<T> {
-    /// Makes an empty `BTreeSet<T>` with a reasonable choice of B.
+    /// Creates an empty `BTreeSet`.
     fn default() -> BTreeSet<T> {
         BTreeSet::new()
     }