diff options
Diffstat (limited to 'library/alloc/src/collections/binary_heap')
-rw-r--r-- | library/alloc/src/collections/binary_heap/mod.rs | 91 |
1 files changed, 35 insertions, 56 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) { |