diff options
| -rw-r--r-- | library/alloc/src/collections/linked_list.rs | 10 | ||||
| -rw-r--r-- | library/alloc/src/collections/vec_deque/mod.rs | 18 | ||||
| -rw-r--r-- | library/core/src/slice/mod.rs | 18 |
3 files changed, 35 insertions, 11 deletions
diff --git a/library/alloc/src/collections/linked_list.rs b/library/alloc/src/collections/linked_list.rs index d81f24e7202..736b38370ab 100644 --- a/library/alloc/src/collections/linked_list.rs +++ b/library/alloc/src/collections/linked_list.rs @@ -645,7 +645,7 @@ impl<T> LinkedList<T> { /// Returns `true` if the `LinkedList` contains an element equal to the /// given value. /// - /// This operation should compute in *O*(*n*) time. + /// This operation should compute linearly in *O*(*n*) time. /// /// # Examples /// @@ -1569,7 +1569,7 @@ impl<'a, T> CursorMut<'a, T> { /// Appends an element to the front of the cursor's parent list. The node /// that the cursor points to is unchanged, even if it is the "ghost" node. /// - /// This operation should compute in O(1) time. + /// This operation should compute in *O*(1) time. // `push_front` continues to point to "ghost" when it addes a node to mimic // the behavior of `insert_before` on an empty list. #[unstable(feature = "linked_list_cursors", issue = "58533")] @@ -1584,7 +1584,7 @@ impl<'a, T> CursorMut<'a, T> { /// Appends an element to the back of the cursor's parent list. The node /// that the cursor points to is unchanged, even if it is the "ghost" node. /// - /// This operation should compute in O(1) time. + /// This operation should compute in *O*(1) time. #[unstable(feature = "linked_list_cursors", issue = "58533")] pub fn push_back(&mut self, elt: T) { // Safety: We know that `push_back` does not change the position in @@ -1603,7 +1603,7 @@ impl<'a, T> CursorMut<'a, T> { /// unchanged, unless it was pointing to the front element. In that case, it /// points to the new front element. /// - /// This operation should compute in O(1) time. + /// This operation should compute in *O*(1) time. #[unstable(feature = "linked_list_cursors", issue = "58533")] pub fn pop_front(&mut self) -> Option<T> { // We can't check if current is empty, we must check the list directly. @@ -1630,7 +1630,7 @@ impl<'a, T> CursorMut<'a, T> { /// unchanged, unless it was pointing to the back element. In that case, it /// points to the "ghost" element. /// - /// This operation should compute in O(1) time. + /// This operation should compute in *O*(1) time. #[unstable(feature = "linked_list_cursors", issue = "58533")] pub fn pop_back(&mut self) -> Option<T> { if self.list.is_empty() { diff --git a/library/alloc/src/collections/vec_deque/mod.rs b/library/alloc/src/collections/vec_deque/mod.rs index 488671d8d8d..ab14a43fb93 100644 --- a/library/alloc/src/collections/vec_deque/mod.rs +++ b/library/alloc/src/collections/vec_deque/mod.rs @@ -1342,6 +1342,12 @@ impl<T, A: Allocator> VecDeque<T, A> { /// 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 +2566,8 @@ impl<T, A: Allocator> VecDeque<T, A> { } } - /// 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 +2577,7 @@ 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 @@ -2614,7 +2622,8 @@ impl<T, A: Allocator> VecDeque<T, A> { 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 +2638,7 @@ 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 @@ -2667,7 +2677,8 @@ impl<T, A: Allocator> VecDeque<T, A> { } } - /// 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 +2691,7 @@ 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 diff --git a/library/core/src/slice/mod.rs b/library/core/src/slice/mod.rs index 2a4030de00b..a226dea54a4 100644 --- a/library/core/src/slice/mod.rs +++ b/library/core/src/slice/mod.rs @@ -2139,6 +2139,12 @@ impl<T> [T] { /// Returns `true` if the slice contains an element with the given value. /// + /// This operation is *O*(*n*). + /// + /// Note that if you have a sorted slice, [`binary_search`] may be faster. + /// + /// [`binary_search`]: slice::binary_search + /// /// # Examples /// /// ``` @@ -2298,7 +2304,8 @@ impl<T> [T] { None } - /// Binary searches this sorted slice for a given element. + /// Binary searches this slice for a given element. + /// This behaves similary to [`contains`] if this slice 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 @@ -2310,6 +2317,7 @@ impl<T> [T] { /// /// See also [`binary_search_by`], [`binary_search_by_key`], and [`partition_point`]. /// + /// [`contains`]: slice::contains /// [`binary_search_by`]: slice::binary_search_by /// [`binary_search_by_key`]: slice::binary_search_by_key /// [`partition_point`]: slice::partition_point @@ -2349,7 +2357,8 @@ impl<T> [T] { self.binary_search_by(|p| p.cmp(x)) } - /// Binary searches this sorted slice with a comparator function. + /// Binary searches this slice with a comparator function. + /// This behaves similarly to [`contains`] if this slice is sorted. /// /// The comparator function should implement an order consistent /// with the sort order of the underlying slice, returning an @@ -2366,6 +2375,7 @@ impl<T> [T] { /// /// See also [`binary_search`], [`binary_search_by_key`], and [`partition_point`]. /// + /// [`contains`]: slice::contains /// [`binary_search`]: slice::binary_search /// [`binary_search_by_key`]: slice::binary_search_by_key /// [`partition_point`]: slice::partition_point @@ -2424,7 +2434,8 @@ impl<T> [T] { Err(left) } - /// Binary searches this sorted slice with a key extraction function. + /// Binary searches this slice with a key extraction function. + /// This behaves similarly to [`contains`] if this slice is sorted. /// /// Assumes that the slice is sorted by the key, for instance with /// [`sort_by_key`] using the same key extraction function. @@ -2439,6 +2450,7 @@ impl<T> [T] { /// /// See also [`binary_search`], [`binary_search_by`], and [`partition_point`]. /// + /// [`contains`]: slice::contains /// [`sort_by_key`]: slice::sort_by_key /// [`binary_search`]: slice::binary_search /// [`binary_search_by`]: slice::binary_search_by |