Merging upstream version 1.70.0+dfsg1.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

13 files changed, 412 insertions, 165 deletions

diff --git a/library/alloc/src/collections/binary_heap/mod.rs b/library/alloc/src/collections/binary_heap/mod.rs
index f1d0a305d..2c089bb31 100644
--- a/library/alloc/src/collections/binary_heap/mod.rs
+++ b/library/alloc/src/collections/binary_heap/mod.rs
@@ -144,7 +144,7 @@
 #![stable(feature = "rust1", since = "1.0.0")]
 
 use core::fmt;
-use core::iter::{FromIterator, FusedIterator, InPlaceIterable, SourceIter, TrustedLen};
+use core::iter::{FusedIterator, InPlaceIterable, SourceIter, TrustedLen};
 use core::mem::{self, swap, ManuallyDrop};
 use core::num::NonZeroUsize;
 use core::ops::{Deref, DerefMut};
@@ -154,8 +154,6 @@ use crate::collections::TryReserveError;
 use crate::slice;
 use crate::vec::{self, AsVecIntoIter, Vec};
 
-use super::SpecExtend;
-
 #[cfg(test)]
 mod tests;
 
@@ -265,7 +263,6 @@ mod tests;
 /// more detailed analysis.
 ///
 /// [`core::cmp::Reverse`]: core::cmp::Reverse
-/// [`Ord`]: core::cmp::Ord
 /// [`Cell`]: core::cell::Cell
 /// [`RefCell`]: core::cell::RefCell
 /// [push]: BinaryHeap::push
@@ -400,6 +397,17 @@ impl<T: fmt::Debug> fmt::Debug for BinaryHeap<T> {
     }
 }
 
+struct RebuildOnDrop<'a, T: Ord> {
+    heap: &'a mut BinaryHeap<T>,
+    rebuild_from: usize,
+}
+
+impl<'a, T: Ord> Drop for RebuildOnDrop<'a, T> {
+    fn drop(&mut self) {
+        self.heap.rebuild_tail(self.rebuild_from);
+    }
+}
+
 impl<T: Ord> BinaryHeap<T> {
     /// Creates an empty `BinaryHeap` as a max-heap.
     ///
@@ -837,7 +845,6 @@ impl<T: Ord> BinaryHeap<T> {
     /// Basic usage:
     ///
     /// ```
-    /// #![feature(binary_heap_retain)]
     /// use std::collections::BinaryHeap;
     ///
     /// let mut heap = BinaryHeap::from([-10, -5, 1, 2, 4, 13]);
@@ -846,35 +853,24 @@ impl<T: Ord> BinaryHeap<T> {
     ///
     /// assert_eq!(heap.into_sorted_vec(), [-10, 2, 4])
     /// ```
-    #[unstable(feature = "binary_heap_retain", issue = "71503")]
+    #[stable(feature = "binary_heap_retain", since = "1.70.0")]
     pub fn retain<F>(&mut self, mut f: F)
     where
         F: FnMut(&T) -> bool,
     {
-        struct RebuildOnDrop<'a, T: Ord> {
-            heap: &'a mut BinaryHeap<T>,
-            first_removed: usize,
-        }
-
-        let mut guard = RebuildOnDrop { first_removed: self.len(), heap: self };
-
+        // rebuild_start will be updated to the first touched element below, and the rebuild will
+        // only be done for the tail.
+        let mut guard = RebuildOnDrop { rebuild_from: self.len(), heap: self };
         let mut i = 0;
+
         guard.heap.data.retain(|e| {
             let keep = f(e);
-            if !keep && i < guard.first_removed {
-                guard.first_removed = i;
+            if !keep && i < guard.rebuild_from {
+                guard.rebuild_from = i;
             }
             i += 1;
             keep
         });
-
-        impl<'a, T: Ord> Drop for RebuildOnDrop<'a, T> {
-            fn drop(&mut self) {
-                // data[..first_removed] is untouched, so we only need to
-                // rebuild the tail:
-                self.heap.rebuild_tail(self.first_removed);
-            }
-        }
     }
 }
 
@@ -1421,7 +1417,6 @@ impl<T> FusedIterator for Iter<'_, T> {}
 /// (provided by the [`IntoIterator`] trait). See its documentation for more.
 ///
 /// [`into_iter`]: BinaryHeap::into_iter
-/// [`IntoIterator`]: core::iter::IntoIterator
 #[stable(feature = "rust1", since = "1.0.0")]
 #[derive(Clone)]
 pub struct IntoIter<T> {
@@ -1468,6 +1463,20 @@ impl<T> ExactSizeIterator for IntoIter<T> {
 #[stable(feature = "fused", since = "1.26.0")]
 impl<T> FusedIterator for IntoIter<T> {}
 
+#[stable(feature = "default_iters", since = "1.70.0")]
+impl<T> Default for IntoIter<T> {
+    /// Creates an empty `binary_heap::IntoIter`.
+    ///
+    /// ```
+    /// # use std::collections::binary_heap;
+    /// let iter: binary_heap::IntoIter<u8> = Default::default();
+    /// assert_eq!(iter.len(), 0);
+    /// ```
+    fn default() -> Self {
+        IntoIter { iter: Default::default() }
+    }
+}
+
 // In addition to the SAFETY invariants of the following three unsafe traits
 // also refer to the vec::in_place_collect module documentation to get an overview
 #[unstable(issue = "none", feature = "inplace_iteration")]
@@ -1715,7 +1724,8 @@ impl<'a, T> IntoIterator for &'a BinaryHeap<T> {
 impl<T: Ord> Extend<T> for BinaryHeap<T> {
     #[inline]
     fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
-        <Self as SpecExtend<I>>::spec_extend(self, iter);
+        let guard = RebuildOnDrop { rebuild_from: self.len(), heap: self };
+        guard.heap.data.extend(iter);
     }
 
     #[inline]
@@ -1729,37 +1739,6 @@ impl<T: Ord> Extend<T> for BinaryHeap<T> {
     }
 }
 
-impl<T: Ord, I: IntoIterator<Item = T>> SpecExtend<I> for BinaryHeap<T> {
-    default fn spec_extend(&mut self, iter: I) {
-        self.extend_desugared(iter.into_iter());
-    }
-}
-
-impl<T: Ord> SpecExtend<Vec<T>> for BinaryHeap<T> {
-    fn spec_extend(&mut self, ref mut other: Vec<T>) {
-        let start = self.data.len();
-        self.data.append(other);
-        self.rebuild_tail(start);
-    }
-}
-
-impl<T: Ord> SpecExtend<BinaryHeap<T>> for BinaryHeap<T> {
-    fn spec_extend(&mut self, ref mut other: BinaryHeap<T>) {
-        self.append(other);
-    }
-}
-
-impl<T: Ord> BinaryHeap<T> {
-    fn extend_desugared<I: IntoIterator<Item = T>>(&mut self, iter: I) {
-        let iterator = iter.into_iter();
-        let (lower, _) = iterator.size_hint();
-
-        self.reserve(lower);
-
-        iterator.for_each(move |elem| self.push(elem));
-    }
-}
-
 #[stable(feature = "extend_ref", since = "1.2.0")]
 impl<'a, T: 'a + Ord + Copy> Extend<&'a T> for BinaryHeap<T> {
     fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
diff --git a/library/alloc/src/collections/btree/map.rs b/library/alloc/src/collections/btree/map.rs
index 386cd1a16..afdc99817 100644
--- a/library/alloc/src/collections/btree/map.rs
+++ b/library/alloc/src/collections/btree/map.rs
@@ -3,7 +3,7 @@ use core::borrow::Borrow;
 use core::cmp::Ordering;
 use core::fmt::{self, Debug};
 use core::hash::{Hash, Hasher};
-use core::iter::{FromIterator, FusedIterator};
+use core::iter::FusedIterator;
 use core::marker::PhantomData;
 use core::mem::{self, ManuallyDrop};
 use core::ops::{Bound, Index, RangeBounds};
@@ -362,6 +362,20 @@ impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Iter<'_, K, V> {
     }
 }
 
+#[stable(feature = "default_iters", since = "1.70.0")]
+impl<'a, K: 'a, V: 'a> Default for Iter<'a, K, V> {
+    /// Creates an empty `btree_map::Iter`.
+    ///
+    /// ```
+    /// # use std::collections::btree_map;
+    /// let iter: btree_map::Iter<'_, u8, u8> = Default::default();
+    /// assert_eq!(iter.len(), 0);
+    /// ```
+    fn default() -> Self {
+        Iter { range: Default::default(), length: 0 }
+    }
+}
+
 /// A mutable iterator over the entries of a `BTreeMap`.
 ///
 /// This `struct` is created by the [`iter_mut`] method on [`BTreeMap`]. See its
@@ -386,13 +400,26 @@ impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IterMut<'_, K, V> {
     }
 }
 
+#[stable(feature = "default_iters", since = "1.70.0")]
+impl<'a, K: 'a, V: 'a> Default for IterMut<'a, K, V> {
+    /// Creates an empty `btree_map::IterMut`.
+    ///
+    /// ```
+    /// # use std::collections::btree_map;
+    /// let iter: btree_map::IterMut<'_, u8, u8> = Default::default();
+    /// assert_eq!(iter.len(), 0);
+    /// ```
+    fn default() -> Self {
+        IterMut { range: Default::default(), length: 0, _marker: PhantomData {} }
+    }
+}
+
 /// An owning iterator over the entries of a `BTreeMap`.
 ///
 /// This `struct` is created by the [`into_iter`] method on [`BTreeMap`]
 /// (provided by the [`IntoIterator`] trait). See its documentation for more.
 ///
 /// [`into_iter`]: IntoIterator::into_iter
-/// [`IntoIterator`]: core::iter::IntoIterator
 #[stable(feature = "rust1", since = "1.0.0")]
 #[rustc_insignificant_dtor]
 pub struct IntoIter<
@@ -421,6 +448,23 @@ impl<K: Debug, V: Debug, A: Allocator + Clone> Debug for IntoIter<K, V, A> {
     }
 }
 
+#[stable(feature = "default_iters", since = "1.70.0")]
+impl<K, V, A> Default for IntoIter<K, V, A>
+where
+    A: Allocator + Default + Clone,
+{
+    /// Creates an empty `btree_map::IntoIter`.
+    ///
+    /// ```
+    /// # use std::collections::btree_map;
+    /// let iter: btree_map::IntoIter<u8, u8> = Default::default();
+    /// assert_eq!(iter.len(), 0);
+    /// ```
+    fn default() -> Self {
+        IntoIter { range: Default::default(), length: 0, alloc: Default::default() }
+    }
+}
+
 /// An iterator over the keys of a `BTreeMap`.
 ///
 /// This `struct` is created by the [`keys`] method on [`BTreeMap`]. See its
@@ -605,7 +649,7 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> {
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn clear(&mut self) {
         // avoid moving the allocator
-        mem::drop(BTreeMap {
+        drop(BTreeMap {
             root: mem::replace(&mut self.root, None),
             length: mem::replace(&mut self.length, 0),
             alloc: self.alloc.clone(),
@@ -1768,6 +1812,20 @@ impl<K, V> Clone for Keys<'_, K, V> {
     }
 }
 
+#[stable(feature = "default_iters", since = "1.70.0")]
+impl<K, V> Default for Keys<'_, K, V> {
+    /// Creates an empty `btree_map::Keys`.
+    ///
+    /// ```
+    /// # use std::collections::btree_map;
+    /// let iter: btree_map::Keys<'_, u8, u8> = Default::default();
+    /// assert_eq!(iter.len(), 0);
+    /// ```
+    fn default() -> Self {
+        Keys { inner: Default::default() }
+    }
+}
+
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<'a, K, V> Iterator for Values<'a, K, V> {
     type Item = &'a V;
@@ -1809,6 +1867,20 @@ impl<K, V> Clone for Values<'_, K, V> {
     }
 }
 
+#[stable(feature = "default_iters", since = "1.70.0")]
+impl<K, V> Default for Values<'_, K, V> {
+    /// Creates an empty `btree_map::Values`.
+    ///
+    /// ```
+    /// # use std::collections::btree_map;
+    /// let iter: btree_map::Values<'_, u8, u8> = Default::default();
+    /// assert_eq!(iter.len(), 0);
+    /// ```
+    fn default() -> Self {
+        Values { inner: Default::default() }
+    }
+}
+
 /// An iterator produced by calling `drain_filter` on BTreeMap.
 #[unstable(feature = "btree_drain_filter", issue = "70530")]
 pub struct DrainFilter<
@@ -1945,6 +2017,20 @@ impl<'a, K, V> Iterator for Range<'a, K, V> {
     }
 }
 
+#[stable(feature = "default_iters", since = "1.70.0")]
+impl<K, V> Default for Range<'_, K, V> {
+    /// Creates an empty `btree_map::Range`.
+    ///
+    /// ```
+    /// # use std::collections::btree_map;
+    /// let iter: btree_map::Range<'_, u8, u8> = Default::default();
+    /// assert_eq!(iter.count(), 0);
+    /// ```
+    fn default() -> Self {
+        Range { inner: Default::default() }
+    }
+}
+
 #[stable(feature = "map_values_mut", since = "1.10.0")]
 impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
     type Item = &'a mut V;
@@ -2021,6 +2107,23 @@ impl<K, V, A: Allocator + Clone> ExactSizeIterator for IntoKeys<K, V, A> {
 #[stable(feature = "map_into_keys_values", since = "1.54.0")]
 impl<K, V, A: Allocator + Clone> FusedIterator for IntoKeys<K, V, A> {}
 
+#[stable(feature = "default_iters", since = "1.70.0")]
+impl<K, V, A> Default for IntoKeys<K, V, A>
+where
+    A: Allocator + Default + Clone,
+{
+    /// Creates an empty `btree_map::IntoKeys`.
+    ///
+    /// ```
+    /// # use std::collections::btree_map;
+    /// let iter: btree_map::IntoKeys<u8, u8> = Default::default();
+    /// assert_eq!(iter.len(), 0);
+    /// ```
+    fn default() -> Self {
+        IntoKeys { inner: Default::default() }
+    }
+}
+
 #[stable(feature = "map_into_keys_values", since = "1.54.0")]
 impl<K, V, A: Allocator + Clone> Iterator for IntoValues<K, V, A> {
     type Item = V;
@@ -2055,6 +2158,23 @@ impl<K, V, A: Allocator + Clone> ExactSizeIterator for IntoValues<K, V, A> {
 #[stable(feature = "map_into_keys_values", since = "1.54.0")]
 impl<K, V, A: Allocator + Clone> FusedIterator for IntoValues<K, V, A> {}
 
+#[stable(feature = "default_iters", since = "1.70.0")]
+impl<K, V, A> Default for IntoValues<K, V, A>
+where
+    A: Allocator + Default + Clone,
+{
+    /// Creates an empty `btree_map::IntoValues`.
+    ///
+    /// ```
+    /// # use std::collections::btree_map;
+    /// let iter: btree_map::IntoValues<u8, u8> = Default::default();
+    /// assert_eq!(iter.len(), 0);
+    /// ```
+    fn default() -> Self {
+        IntoValues { inner: Default::default() }
+    }
+}
+
 #[stable(feature = "btree_range", since = "1.17.0")]
 impl<'a, K, V> DoubleEndedIterator for Range<'a, K, V> {
     fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
@@ -3062,7 +3182,7 @@ impl<'a, K: Ord, V, A: Allocator + Clone> CursorMut<'a, K, V, A> {
                 panic!("key must be ordered above the current element");
             }
         }
-        if let Some((next, _)) = self.peek_prev() {
+        if let Some((next, _)) = self.peek_next() {
             if &key >= next {
                 panic!("key must be ordered below the next element");
             }
diff --git a/library/alloc/src/collections/btree/map/tests.rs b/library/alloc/src/collections/btree/map/tests.rs
index 76c2f27b4..da00d83bd 100644
--- a/library/alloc/src/collections/btree/map/tests.rs
+++ b/library/alloc/src/collections/btree/map/tests.rs
@@ -9,8 +9,7 @@ use crate::testing::ord_chaos::{Cyclic3, Governed, Governor};
 use crate::testing::rng::DeterministicRng;
 use crate::vec::Vec;
 use std::cmp::Ordering;
-use std::convert::TryFrom;
-use std::iter::{self, FromIterator};
+use std::iter;
 use std::mem;
 use std::ops::Bound::{self, Excluded, Included, Unbounded};
 use std::ops::RangeBounds;
@@ -2385,3 +2384,67 @@ fn test_cursor_mut() {
     assert_eq!(cur.key(), Some(&4));
     assert_eq!(map, BTreeMap::from([(0, '?'), (1, 'a'), (3, 'c'), (4, 'd')]));
 }
+
+#[should_panic(expected = "key must be ordered above the previous element")]
+#[test]
+fn test_cursor_mut_insert_before_1() {
+    let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]);
+    let mut cur = map.upper_bound_mut(Bound::Included(&2));
+    cur.insert_before(0, 'd');
+}
+
+#[should_panic(expected = "key must be ordered above the previous element")]
+#[test]
+fn test_cursor_mut_insert_before_2() {
+    let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]);
+    let mut cur = map.upper_bound_mut(Bound::Included(&2));
+    cur.insert_before(1, 'd');
+}
+
+#[should_panic(expected = "key must be ordered below the current element")]
+#[test]
+fn test_cursor_mut_insert_before_3() {
+    let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]);
+    let mut cur = map.upper_bound_mut(Bound::Included(&2));
+    cur.insert_before(2, 'd');
+}
+
+#[should_panic(expected = "key must be ordered below the current element")]
+#[test]
+fn test_cursor_mut_insert_before_4() {
+    let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]);
+    let mut cur = map.upper_bound_mut(Bound::Included(&2));
+    cur.insert_before(3, 'd');
+}
+
+#[should_panic(expected = "key must be ordered above the current element")]
+#[test]
+fn test_cursor_mut_insert_after_1() {
+    let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]);
+    let mut cur = map.upper_bound_mut(Bound::Included(&2));
+    cur.insert_after(1, 'd');
+}
+
+#[should_panic(expected = "key must be ordered above the current element")]
+#[test]
+fn test_cursor_mut_insert_after_2() {
+    let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]);
+    let mut cur = map.upper_bound_mut(Bound::Included(&2));
+    cur.insert_after(2, 'd');
+}
+
+#[should_panic(expected = "key must be ordered below the next element")]
+#[test]
+fn test_cursor_mut_insert_after_3() {
+    let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]);
+    let mut cur = map.upper_bound_mut(Bound::Included(&2));
+    cur.insert_after(3, 'd');
+}
+
+#[should_panic(expected = "key must be ordered below the next element")]
+#[test]
+fn test_cursor_mut_insert_after_4() {
+    let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]);
+    let mut cur = map.upper_bound_mut(Bound::Included(&2));
+    cur.insert_after(4, 'd');
+}
diff --git a/library/alloc/src/collections/btree/mod.rs b/library/alloc/src/collections/btree/mod.rs
index 7552f2fc0..c7d0144de 100644
--- a/library/alloc/src/collections/btree/mod.rs
+++ b/library/alloc/src/collections/btree/mod.rs
@@ -13,7 +13,6 @@ pub mod set;
 mod set_val;
 mod split;
 
-#[doc(hidden)]
 trait Recover<Q: ?Sized> {
     type Key;
 
diff --git a/library/alloc/src/collections/btree/navigate.rs b/library/alloc/src/collections/btree/navigate.rs
index b890717e5..a85a31624 100644
--- a/library/alloc/src/collections/btree/navigate.rs
+++ b/library/alloc/src/collections/btree/navigate.rs
@@ -19,6 +19,12 @@ impl<'a, K: 'a, V: 'a> Clone for LeafRange<marker::Immut<'a>, K, V> {
     }
 }
 
+impl<B, K, V> Default for LeafRange<B, K, V> {
+    fn default() -> Self {
+        LeafRange { front: None, back: None }
+    }
+}
+
 impl<BorrowType, K, V> LeafRange<BorrowType, K, V> {
     pub fn none() -> Self {
         LeafRange { front: None, back: None }
@@ -124,6 +130,12 @@ pub struct LazyLeafRange<BorrowType, K, V> {
     back: Option<LazyLeafHandle<BorrowType, K, V>>,
 }
 
+impl<B, K, V> Default for LazyLeafRange<B, K, V> {
+    fn default() -> Self {
+        LazyLeafRange { front: None, back: None }
+    }
+}
+
 impl<'a, K: 'a, V: 'a> Clone for LazyLeafRange<marker::Immut<'a>, K, V> {
     fn clone(&self) -> Self {
         LazyLeafRange { front: self.front.clone(), back: self.back.clone() }
diff --git a/library/alloc/src/collections/btree/set.rs b/library/alloc/src/collections/btree/set.rs
index 4ddb21192..da952a13f 100644
--- a/library/alloc/src/collections/btree/set.rs
+++ b/library/alloc/src/collections/btree/set.rs
@@ -1,13 +1,10 @@
-// This is pretty much entirely stolen from TreeSet, since BTreeMap has an identical interface
-// to TreeMap
-
 use crate::vec::Vec;
 use core::borrow::Borrow;
 use core::cmp::Ordering::{self, Equal, Greater, Less};
 use core::cmp::{max, min};
 use core::fmt::{self, Debug};
 use core::hash::{Hash, Hasher};
-use core::iter::{FromIterator, FusedIterator, Peekable};
+use core::iter::{FusedIterator, Peekable};
 use core::mem::ManuallyDrop;
 use core::ops::{BitAnd, BitOr, BitXor, RangeBounds, Sub};
 
@@ -18,8 +15,6 @@ use super::Recover;
 
 use crate::alloc::{Allocator, Global};
 
-// FIXME(conventions): implement bounded iterators
-
 /// An ordered set based on a B-Tree.
 ///
 /// See [`BTreeMap`]'s documentation for a detailed discussion of this collection's performance
@@ -35,7 +30,6 @@ use crate::alloc::{Allocator, Global};
 /// Iterators returned by [`BTreeSet::iter`] produce their items in order, and take worst-case
 /// logarithmic and amortized constant time per item returned.
 ///
-/// [`Ord`]: core::cmp::Ord
 /// [`Cell`]: core::cell::Cell
 /// [`RefCell`]: core::cell::RefCell
 ///
@@ -152,7 +146,6 @@ impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> {
 /// (provided by the [`IntoIterator`] trait). See its documentation for more.
 ///
 /// [`into_iter`]: BTreeSet#method.into_iter
-/// [`IntoIterator`]: core::iter::IntoIterator
 #[stable(feature = "rust1", since = "1.0.0")]
 #[derive(Debug)]
 pub struct IntoIter<
@@ -1544,6 +1537,21 @@ impl<T, A: Allocator + Clone> Iterator for IntoIter<T, A> {
         self.iter.size_hint()
     }
 }
+
+#[stable(feature = "default_iters", since = "1.70.0")]
+impl<T> Default for Iter<'_, T> {
+    /// Creates an empty `btree_set::Iter`.
+    ///
+    /// ```
+    /// # use std::collections::btree_set;
+    /// let iter: btree_set::Iter<'_, u8> = Default::default();
+    /// assert_eq!(iter.len(), 0);
+    /// ```
+    fn default() -> Self {
+        Iter { iter: Default::default() }
+    }
+}
+
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<T, A: Allocator + Clone> DoubleEndedIterator for IntoIter<T, A> {
     fn next_back(&mut self) -> Option<T> {
@@ -1560,6 +1568,23 @@ impl<T, A: Allocator + Clone> ExactSizeIterator for IntoIter<T, A> {
 #[stable(feature = "fused", since = "1.26.0")]
 impl<T, A: Allocator + Clone> FusedIterator for IntoIter<T, A> {}
 
+#[stable(feature = "default_iters", since = "1.70.0")]
+impl<T, A> Default for IntoIter<T, A>
+where
+    A: Allocator + Default + Clone,
+{
+    /// Creates an empty `btree_set::IntoIter`.
+    ///
+    /// ```
+    /// # use std::collections::btree_set;
+    /// let iter: btree_set::IntoIter<u8> = Default::default();
+    /// assert_eq!(iter.len(), 0);
+    /// ```
+    fn default() -> Self {
+        IntoIter { iter: Default::default() }
+    }
+}
+
 #[stable(feature = "btree_range", since = "1.17.0")]
 impl<T> Clone for Range<'_, T> {
     fn clone(&self) -> Self {
@@ -1598,6 +1623,20 @@ impl<'a, T> DoubleEndedIterator for Range<'a, T> {
 #[stable(feature = "fused", since = "1.26.0")]
 impl<T> FusedIterator for Range<'_, T> {}
 
+#[stable(feature = "default_iters", since = "1.70.0")]
+impl<T> Default for Range<'_, T> {
+    /// Creates an empty `btree_set::Range`.
+    ///
+    /// ```
+    /// # use std::collections::btree_set;
+    /// let iter: btree_set::Range<'_, u8> = Default::default();
+    /// assert_eq!(iter.count(), 0);
+    /// ```
+    fn default() -> Self {
+        Range { iter: Default::default() }
+    }
+}
+
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<T, A: Allocator + Clone> Clone for Difference<'_, T, A> {
     fn clone(&self) -> Self {
diff --git a/library/alloc/src/collections/btree/set/tests.rs b/library/alloc/src/collections/btree/set/tests.rs
index 7b8d41a60..a7c839d77 100644
--- a/library/alloc/src/collections/btree/set/tests.rs
+++ b/library/alloc/src/collections/btree/set/tests.rs
@@ -4,7 +4,6 @@ use crate::testing::rng::DeterministicRng;
 use crate::vec::Vec;
 use std::cmp::Ordering;
 use std::hash::{Hash, Hasher};
-use std::iter::FromIterator;
 use std::ops::Bound::{Excluded, Included};
 use std::panic::{catch_unwind, AssertUnwindSafe};
 
diff --git a/library/alloc/src/collections/linked_list.rs b/library/alloc/src/collections/linked_list.rs
index f2f5dffc2..106d05c57 100644
--- a/library/alloc/src/collections/linked_list.rs
+++ b/library/alloc/src/collections/linked_list.rs
@@ -15,7 +15,7 @@
 use core::cmp::Ordering;
 use core::fmt;
 use core::hash::{Hash, Hasher};
-use core::iter::{FromIterator, FusedIterator};
+use core::iter::FusedIterator;
 use core::marker::PhantomData;
 use core::mem;
 use core::ptr::NonNull;
@@ -130,7 +130,6 @@ impl<T: fmt::Debug> fmt::Debug for IterMut<'_, T> {
 /// (provided by the [`IntoIterator`] trait). See its documentation for more.
 ///
 /// [`into_iter`]: LinkedList::into_iter
-/// [`IntoIterator`]: core::iter::IntoIterator
 #[derive(Clone)]
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct IntoIter<T> {
@@ -1075,6 +1074,20 @@ impl<T> ExactSizeIterator for Iter<'_, T> {}
 #[stable(feature = "fused", since = "1.26.0")]
 impl<T> FusedIterator for Iter<'_, T> {}
 
+#[stable(feature = "default_iters", since = "1.70.0")]
+impl<T> Default for Iter<'_, T> {
+    /// Creates an empty `linked_list::Iter`.
+    ///
+    /// ```
+    /// # use std::collections::linked_list;
+    /// let iter: linked_list::Iter<'_, u8> = Default::default();
+    /// assert_eq!(iter.len(), 0);
+    /// ```
+    fn default() -> Self {
+        Iter { head: None, tail: None, len: 0, marker: Default::default() }
+    }
+}
+
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<'a, T> Iterator for IterMut<'a, T> {
     type Item = &'a mut T;
@@ -1129,6 +1142,13 @@ impl<T> ExactSizeIterator for IterMut<'_, T> {}
 #[stable(feature = "fused", since = "1.26.0")]
 impl<T> FusedIterator for IterMut<'_, T> {}
 
+#[stable(feature = "default_iters", since = "1.70.0")]
+impl<T> Default for IterMut<'_, T> {
+    fn default() -> Self {
+        IterMut { head: None, tail: None, len: 0, marker: Default::default() }
+    }
+}
+
 /// A cursor over a `LinkedList`.
 ///
 /// A `Cursor` is like an iterator, except that it can freely seek back-and-forth.
@@ -1808,6 +1828,20 @@ impl<T> ExactSizeIterator for IntoIter<T> {}
 #[stable(feature = "fused", since = "1.26.0")]
 impl<T> FusedIterator for IntoIter<T> {}
 
+#[stable(feature = "default_iters", since = "1.70.0")]
+impl<T> Default for IntoIter<T> {
+    /// Creates an empty `linked_list::IntoIter`.
+    ///
+    /// ```
+    /// # use std::collections::linked_list;
+    /// let iter: linked_list::IntoIter<u8> = Default::default();
+    /// assert_eq!(iter.len(), 0);
+    /// ```
+    fn default() -> Self {
+        LinkedList::new().into_iter()
+    }
+}
+
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<T> FromIterator<T> for LinkedList<T> {
     fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
diff --git a/library/alloc/src/collections/vec_deque/drain.rs b/library/alloc/src/collections/vec_deque/drain.rs
index 89feb361d..0be274a38 100644
--- a/library/alloc/src/collections/vec_deque/drain.rs
+++ b/library/alloc/src/collections/vec_deque/drain.rs
@@ -52,36 +52,22 @@ impl<'a, T, A: Allocator> Drain<'a, T, A> {
         }
     }
 
-    // Only returns pointers to the slices, as that's
-    // all we need to drop them. May only be called if `self.remaining != 0`.
+    // Only returns pointers to the slices, as that's all we need
+    // to drop them. May only be called if `self.remaining != 0`.
     unsafe fn as_slices(&self) -> (*mut [T], *mut [T]) {
         unsafe {
             let deque = self.deque.as_ref();
-            // FIXME: This is doing almost exactly the same thing as the else branch in `VecDeque::slice_ranges`.
-            // Unfortunately, we can't just call `slice_ranges` here, as the deque's `len` is currently
-            // just `drain_start`, so the range check would (almost) always panic. Between temporarily
-            // adjusting the deques `len` to call `slice_ranges`, and just copy pasting the `slice_ranges`
-            // implementation, this seemed like the less hacky solution, though it might be good to
-            // find a better one in the future.
-
-            // because `self.remaining != 0`, we know that `self.idx < deque.original_len`, so it's a valid
-            // logical index.
-            let wrapped_start = deque.to_physical_idx(self.idx);
-
-            let head_len = deque.capacity() - wrapped_start;
-
-            let (a_range, b_range) = if head_len >= self.remaining {
-                (wrapped_start..wrapped_start + self.remaining, 0..0)
-            } else {
-                let tail_len = self.remaining - head_len;
-                (wrapped_start..deque.capacity(), 0..tail_len)
-            };
-
-            // SAFETY: the range `self.idx..self.idx+self.remaining` lies strictly inside
-            // the range `0..deque.original_len`. because of this, and because of the fact
-            // that we acquire `a_range` and `b_range` exactly like `slice_ranges` would,
-            // it's guaranteed that `a_range` and `b_range` represent valid ranges into
-            // the deques buffer.
+
+            // We know that `self.idx + self.remaining <= deque.len <= usize::MAX`, so this won't overflow.
+            let logical_remaining_range = self.idx..self.idx + self.remaining;
+
+            // SAFETY: `logical_remaining_range` represents the
+            // range into the logical buffer of elements that
+            // haven't been drained yet, so they're all initialized,
+            // and `slice::range(start..end, end) == start..end`,
+            // so the preconditions for `slice_ranges` are met.
+            let (a_range, b_range) =
+                deque.slice_ranges(logical_remaining_range.clone(), logical_remaining_range.end);
             (deque.buffer_range(a_range), deque.buffer_range(b_range))
         }
     }
diff --git a/library/alloc/src/collections/vec_deque/into_iter.rs b/library/alloc/src/collections/vec_deque/into_iter.rs
index 34bc0ce91..d9e274df0 100644
--- a/library/alloc/src/collections/vec_deque/into_iter.rs
+++ b/library/alloc/src/collections/vec_deque/into_iter.rs
@@ -1,4 +1,5 @@
 use core::iter::{FusedIterator, TrustedLen};
+use core::num::NonZeroUsize;
 use core::{array, fmt, mem::MaybeUninit, ops::Try, ptr};
 
 use crate::alloc::{Allocator, Global};
@@ -11,7 +12,6 @@ use super::VecDeque;
 /// (provided by the [`IntoIterator`] trait). See its documentation for more.
 ///
 /// [`into_iter`]: VecDeque::into_iter
-/// [`IntoIterator`]: core::iter::IntoIterator
 #[derive(Clone)]
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct IntoIter<
@@ -54,15 +54,16 @@ impl<T, A: Allocator> Iterator for IntoIter<T, A> {
     }
 
     #[inline]
-    fn advance_by(&mut self, n: usize) -> Result<(), usize> {
-        if self.inner.len < n {
-            let len = self.inner.len;
+    fn advance_by(&mut self, n: usize) -> Result<(), NonZeroUsize> {
+        let len = self.inner.len;
+        let rem = if len < n {
             self.inner.clear();
-            Err(len)
+            n - len
         } else {
             self.inner.drain(..n);
-            Ok(())
-        }
+            0
+        };
+        NonZeroUsize::new(rem).map_or(Ok(()), Err)
     }
 
     #[inline]
@@ -182,15 +183,16 @@ impl<T, A: Allocator> DoubleEndedIterator for IntoIter<T, A> {
     }
 
     #[inline]
-    fn advance_back_by(&mut self, n: usize) -> Result<(), usize> {
+    fn advance_back_by(&mut self, n: usize) -> Result<(), NonZeroUsize> {
         let len = self.inner.len;
-        if len >= n {
-            self.inner.truncate(len - n);
-            Ok(())
-        } else {
+        let rem = if len < n {
             self.inner.clear();
-            Err(len)
-        }
+            n - len
+        } else {
+            self.inner.truncate(len - n);
+            0
+        };
+        NonZeroUsize::new(rem).map_or(Ok(()), Err)
     }
 
     fn try_rfold<B, F, R>(&mut self, mut init: B, mut f: F) -> R
diff --git a/library/alloc/src/collections/vec_deque/iter.rs b/library/alloc/src/collections/vec_deque/iter.rs
index d9f393714..646a2a991 100644
--- a/library/alloc/src/collections/vec_deque/iter.rs
+++ b/library/alloc/src/collections/vec_deque/iter.rs
@@ -1,4 +1,5 @@
 use core::iter::{FusedIterator, TrustedLen, TrustedRandomAccess, TrustedRandomAccessNoCoerce};
+use core::num::NonZeroUsize;
 use core::ops::Try;
 use core::{fmt, mem, slice};
 
@@ -55,13 +56,15 @@ impl<'a, T> Iterator for Iter<'a, T> {
         }
     }
 
-    fn advance_by(&mut self, n: usize) -> Result<(), usize> {
-        let m = match self.i1.advance_by(n) {
-            Ok(_) => return Ok(()),
-            Err(m) => m,
-        };
-        mem::swap(&mut self.i1, &mut self.i2);
-        self.i1.advance_by(n - m).map_err(|o| o + m)
+    fn advance_by(&mut self, n: usize) -> Result<(), NonZeroUsize> {
+        let remaining = self.i1.advance_by(n);
+        match remaining {
+            Ok(()) => return Ok(()),
+            Err(n) => {
+                mem::swap(&mut self.i1, &mut self.i2);
+                self.i1.advance_by(n.get())
+            }
+        }
     }
 
     #[inline]
@@ -125,14 +128,14 @@ impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
         }
     }
 
-    fn advance_back_by(&mut self, n: usize) -> Result<(), usize> {
-        let m = match self.i2.advance_back_by(n) {
-            Ok(_) => return Ok(()),
-            Err(m) => m,
-        };
-
-        mem::swap(&mut self.i1, &mut self.i2);
-        self.i2.advance_back_by(n - m).map_err(|o| m + o)
+    fn advance_back_by(&mut self, n: usize) -> Result<(), NonZeroUsize> {
+        match self.i2.advance_back_by(n) {
+            Ok(()) => return Ok(()),
+            Err(n) => {
+                mem::swap(&mut self.i1, &mut self.i2);
+                self.i2.advance_back_by(n.get())
+            }
+        }
     }
 
     fn rfold<Acc, F>(self, accum: Acc, mut f: F) -> Acc
diff --git a/library/alloc/src/collections/vec_deque/iter_mut.rs b/library/alloc/src/collections/vec_deque/iter_mut.rs
index 2c59d95cd..7defbb109 100644
--- a/library/alloc/src/collections/vec_deque/iter_mut.rs
+++ b/library/alloc/src/collections/vec_deque/iter_mut.rs
@@ -1,4 +1,5 @@
 use core::iter::{FusedIterator, TrustedLen, TrustedRandomAccess, TrustedRandomAccessNoCoerce};
+use core::num::NonZeroUsize;
 use core::ops::Try;
 use core::{fmt, mem, slice};
 
@@ -47,13 +48,14 @@ impl<'a, T> Iterator for IterMut<'a, T> {
         }
     }
 
-    fn advance_by(&mut self, n: usize) -> Result<(), usize> {
-        let m = match self.i1.advance_by(n) {
-            Ok(_) => return Ok(()),
-            Err(m) => m,
-        };
-        mem::swap(&mut self.i1, &mut self.i2);
-        self.i1.advance_by(n - m).map_err(|o| o + m)
+    fn advance_by(&mut self, n: usize) -> Result<(), NonZeroUsize> {
+        match self.i1.advance_by(n) {
+            Ok(()) => return Ok(()),
+            Err(remaining) => {
+                mem::swap(&mut self.i1, &mut self.i2);
+                self.i1.advance_by(remaining.get())
+            }
+        }
     }
 
     #[inline]
@@ -117,14 +119,14 @@ impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
         }
     }
 
-    fn advance_back_by(&mut self, n: usize) -> Result<(), usize> {
-        let m = match self.i2.advance_back_by(n) {
-            Ok(_) => return Ok(()),
-            Err(m) => m,
-        };
-
-        mem::swap(&mut self.i1, &mut self.i2);
-        self.i2.advance_back_by(n - m).map_err(|o| m + o)
+    fn advance_back_by(&mut self, n: usize) -> Result<(), NonZeroUsize> {
+        match self.i2.advance_back_by(n) {
+            Ok(()) => return Ok(()),
+            Err(remaining) => {
+                mem::swap(&mut self.i1, &mut self.i2);
+                self.i2.advance_back_by(remaining.get())
+            }
+        }
     }
 
     fn rfold<Acc, F>(self, accum: Acc, mut f: F) -> Acc
diff --git a/library/alloc/src/collections/vec_deque/mod.rs b/library/alloc/src/collections/vec_deque/mod.rs
index 8317ac431..8916b42ed 100644
--- a/library/alloc/src/collections/vec_deque/mod.rs
+++ b/library/alloc/src/collections/vec_deque/mod.rs
@@ -10,7 +10,7 @@
 use core::cmp::{self, Ordering};
 use core::fmt;
 use core::hash::{Hash, Hasher};
-use core::iter::{repeat_n, repeat_with, ByRefSized, FromIterator};
+use core::iter::{repeat_n, repeat_with, ByRefSized};
 use core::mem::{ManuallyDrop, SizedTypeProperties};
 use core::ops::{Index, IndexMut, Range, RangeBounds};
 use core::ptr;
@@ -1156,7 +1156,7 @@ impl<T, A: Allocator> VecDeque<T, A> {
     #[inline]
     #[stable(feature = "deque_extras_15", since = "1.5.0")]
     pub fn as_slices(&self) -> (&[T], &[T]) {
-        let (a_range, b_range) = self.slice_ranges(..);
+        let (a_range, b_range) = self.slice_ranges(.., self.len);
         // SAFETY: `slice_ranges` always returns valid ranges into
         // the physical buffer.
         unsafe { (&*self.buffer_range(a_range), &*self.buffer_range(b_range)) }
@@ -1190,7 +1190,7 @@ impl<T, A: Allocator> VecDeque<T, A> {
     #[inline]
     #[stable(feature = "deque_extras_15", since = "1.5.0")]
     pub fn as_mut_slices(&mut self) -> (&mut [T], &mut [T]) {
-        let (a_range, b_range) = self.slice_ranges(..);
+        let (a_range, b_range) = self.slice_ranges(.., self.len);
         // SAFETY: `slice_ranges` always returns valid ranges into
         // the physical buffer.
         unsafe { (&mut *self.buffer_range(a_range), &mut *self.buffer_range(b_range)) }
@@ -1232,19 +1232,28 @@ impl<T, A: Allocator> VecDeque<T, A> {
 
     /// Given a range into the logical buffer of the deque, this function
     /// return two ranges into the physical buffer that correspond to
-    /// the given range.
-    fn slice_ranges<R>(&self, range: R) -> (Range<usize>, Range<usize>)
+    /// the given range. The `len` parameter should usually just be `self.len`;
+    /// the reason it's passed explicitly is that if the deque is wrapped in
+    /// a `Drain`, then `self.len` is not actually the length of the deque.
+    ///
+    /// # Safety
+    ///
+    /// This function is always safe to call. For the resulting ranges to be valid
+    /// ranges into the physical buffer, the caller must ensure that the result of
+    /// calling `slice::range(range, ..len)` represents a valid range into the
+    /// logical buffer, and that all elements in that range are initialized.
+    fn slice_ranges<R>(&self, range: R, len: usize) -> (Range<usize>, Range<usize>)
     where
         R: RangeBounds<usize>,
     {
-        let Range { start, end } = slice::range(range, ..self.len);
+        let Range { start, end } = slice::range(range, ..len);
         let len = end - start;
 
         if len == 0 {
             (0..0, 0..0)
         } else {
-            // `slice::range` guarantees that `start <= end <= self.len`.
-            // because `len != 0`, we know that `start < end`, so `start < self.len`
+            // `slice::range` guarantees that `start <= end <= len`.
+            // because `len != 0`, we know that `start < end`, so `start < len`
             // and the indexing is valid.
             let wrapped_start = self.to_physical_idx(start);
 
@@ -1290,7 +1299,7 @@ impl<T, A: Allocator> VecDeque<T, A> {
     where
         R: RangeBounds<usize>,
     {
-        let (a_range, b_range) = self.slice_ranges(range);
+        let (a_range, b_range) = self.slice_ranges(range, self.len);
         // SAFETY: The ranges returned by `slice_ranges`
         // are valid ranges into the physical buffer, so
         // it's ok to pass them to `buffer_range` and
@@ -1330,7 +1339,7 @@ impl<T, A: Allocator> VecDeque<T, A> {
     where
         R: RangeBounds<usize>,
     {
-        let (a_range, b_range) = self.slice_ranges(range);
+        let (a_range, b_range) = self.slice_ranges(range, self.len);
         // SAFETY: The ranges returned by `slice_ranges`
         // are valid ranges into the physical buffer, so
         // it's ok to pass them to `buffer_range` and
@@ -2385,7 +2394,8 @@ impl<T, A: Allocator> VecDeque<T, A> {
     }
 
     /// Binary searches this `VecDeque` for a given element.
-    /// This behaves similarly to [`contains`] if this `VecDeque` is sorted.
+    /// If the `VecDeque` is not sorted, the returned result is unspecified and
+    /// meaningless.
     ///
     /// If the value is found then [`Result::Ok`] is returned, containing the
     /// index of the matching element. If there are multiple matches, then any
@@ -2395,7 +2405,6 @@ impl<T, A: Allocator> VecDeque<T, A> {
     ///
     /// See also [`binary_search_by`], [`binary_search_by_key`], and [`partition_point`].
     ///
-    /// [`contains`]: VecDeque::contains
     /// [`binary_search_by`]: VecDeque::binary_search_by
     /// [`binary_search_by_key`]: VecDeque::binary_search_by_key
     /// [`partition_point`]: VecDeque::partition_point
@@ -2441,12 +2450,13 @@ impl<T, A: Allocator> VecDeque<T, A> {
     }
 
     /// Binary searches this `VecDeque` with a comparator function.
-    /// This behaves similarly to [`contains`] if this `VecDeque` is sorted.
     ///
-    /// The comparator function should implement an order consistent
-    /// with the sort order of the deque, returning an order code that
-    /// indicates whether its argument is `Less`, `Equal` or `Greater`
-    /// than the desired target.
+    /// The comparator function should return an order code that indicates
+    /// whether its argument is `Less`, `Equal` or `Greater` the desired
+    /// target.
+    /// If the `VecDeque` is not sorted or if the comparator function does not
+    /// implement an order consistent with the sort order of the underlying
+    /// `VecDeque`, the returned result is unspecified and meaningless.
     ///
     /// If the value is found then [`Result::Ok`] is returned, containing the
     /// index of the matching element. If there are multiple matches, then any
@@ -2456,7 +2466,6 @@ impl<T, A: Allocator> VecDeque<T, A> {
     ///
     /// See also [`binary_search`], [`binary_search_by_key`], and [`partition_point`].
     ///
-    /// [`contains`]: VecDeque::contains
     /// [`binary_search`]: VecDeque::binary_search
     /// [`binary_search_by_key`]: VecDeque::binary_search_by_key
     /// [`partition_point`]: VecDeque::partition_point
@@ -2496,10 +2505,11 @@ impl<T, A: Allocator> VecDeque<T, A> {
     }
 
     /// Binary searches this `VecDeque` with a key extraction function.
-    /// This behaves similarly to [`contains`] if this `VecDeque` is sorted.
     ///
     /// Assumes that the deque is sorted by the key, for instance with
     /// [`make_contiguous().sort_by_key()`] using the same key extraction function.
+    /// If the deque is not sorted by the key, the returned result is
+    /// unspecified and meaningless.
     ///
     /// If the value is found then [`Result::Ok`] is returned, containing the
     /// index of the matching element. If there are multiple matches, then any
@@ -2509,7 +2519,6 @@ impl<T, A: Allocator> VecDeque<T, A> {
     ///
     /// See also [`binary_search`], [`binary_search_by`], and [`partition_point`].
     ///
-    /// [`contains`]: VecDeque::contains
     /// [`make_contiguous().sort_by_key()`]: VecDeque::make_contiguous
     /// [`binary_search`]: VecDeque::binary_search
     /// [`binary_search_by`]: VecDeque::binary_search_by