Add VecDeque::extend from vec::IntoIter and slice::Iter specializations

[rust.git] / library / alloc / src / collections / vec_deque / mod.rs

diff --git a/library/alloc/src/collections/vec_deque/mod.rs b/library/alloc/src/collections/vec_deque/mod.rs
index 488671d8d8d19b7fbf1ab6129ec934969e37dc41..5f1a6848ae62a324c2f410e58b15797ecb808653 100644 (file)
--- a/library/alloc/src/collections/vec_deque/mod.rs
+++ b/library/alloc/src/collections/vec_deque/mod.rs
@@ -54,6 +54,10 @@
 
 mod ring_slices;
 
+use self::spec_extend::SpecExtend;
+
+mod spec_extend;
+
 #[cfg(test)]
 mod tests;
 
@@ -1342,6 +1346,12 @@ pub fn clear(&mut self) {
     /// Returns `true` if the deque contains an element equal to the
     /// given value.
     ///
+    /// This operation is *O*(*n*).
+    ///
+    /// Note that if you have a sorted `VecDeque`, [`binary_search`] may be faster.
+    ///
+    /// [`binary_search`]: VecDeque::binary_search
+    ///
     /// # Examples
     ///
     /// ```
@@ -2560,7 +2570,8 @@ unsafe fn rotate_right_inner(&mut self, k: usize) {
         }
     }
 
-    /// Binary searches the sorted deque for a given element.
+    /// Binary searches this `VecDeque` for a given element.
+    /// This behaves similarly to [`contains`] if this `VecDeque` is sorted.
     ///
     /// If the value is found then [`Result::Ok`] is returned, containing the
     /// index of the matching element. If there are multiple matches, then any
@@ -2570,6 +2581,7 @@ unsafe fn rotate_right_inner(&mut self, k: usize) {
     ///
     /// 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
@@ -2614,7 +2626,8 @@ pub fn binary_search(&self, x: &T) -> Result<usize, usize>
         self.binary_search_by(|e| e.cmp(x))
     }
 
-    /// Binary searches the sorted deque with a comparator function.
+    /// 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
@@ -2629,6 +2642,7 @@ pub fn binary_search(&self, x: &T) -> Result<usize, usize>
     ///
     /// 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
@@ -2667,7 +2681,8 @@ pub fn binary_search_by<'a, F>(&'a self, mut f: F) -> Result<usize, usize>
         }
     }
 
-    /// Binary searches the sorted deque with a key extraction function.
+    /// 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.
@@ -2680,6 +2695,7 @@ pub fn binary_search_by<'a, F>(&'a self, mut f: F) -> Result<usize, usize>
     ///
     /// 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
@@ -2958,24 +2974,7 @@ fn into_iter(self) -> IterMut<'a, T> {
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<T, A: Allocator> Extend<T> for VecDeque<T, A> {
     fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
-        // This function should be the moral equivalent of:
-        //
-        //      for item in iter.into_iter() {
-        //          self.push_back(item);
-        //      }
-        let mut iter = iter.into_iter();
-        while let Some(element) = iter.next() {
-            if self.len() == self.capacity() {
-                let (lower, _) = iter.size_hint();
-                self.reserve(lower.saturating_add(1));
-            }
-
-            let head = self.head;
-            self.head = self.wrap_add(self.head, 1);
-            unsafe {
-                self.buffer_write(head, element);
-            }
-        }
+        <Self as SpecExtend<T, I::IntoIter>>::spec_extend(self, iter.into_iter());
     }
 
     #[inline]
@@ -2992,7 +2991,7 @@ fn extend_reserve(&mut self, additional: usize) {
 #[stable(feature = "extend_ref", since = "1.2.0")]
 impl<'a, T: 'a + Copy, A: Allocator> Extend<&'a T> for VecDeque<T, A> {
     fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
-        self.extend(iter.into_iter().cloned());
+        self.spec_extend(iter.into_iter());
     }
 
     #[inline]