From 52ab3e8e76afde6c6b5059816f641e49ef008c30 Mon Sep 17 00:00:00 2001 From: est31 Date: Thu, 16 Sep 2021 13:20:36 +0200 Subject: Add intra-doc-links to LinkedList rustdoc --- library/alloc/src/collections/linked_list.rs | 5 ++++- 1 file changed, 4 insertions(+), 1 deletion(-) (limited to 'library/alloc/src') diff --git a/library/alloc/src/collections/linked_list.rs b/library/alloc/src/collections/linked_list.rs index 9d45c5082db..a3729617aeb 100644 --- a/library/alloc/src/collections/linked_list.rs +++ b/library/alloc/src/collections/linked_list.rs @@ -38,9 +38,12 @@ mod tests; /// let list = LinkedList::from([1, 2, 3]); /// ``` /// -/// NOTE: It is almost always better to use `Vec` or `VecDeque` because +/// NOTE: It is almost always better to use [`Vec`] or [`VecDeque`] because /// array-based containers are generally faster, /// more memory efficient, and make better use of CPU cache. +/// +/// [`Vec`]: crate::vec::Vec +/// [`VecDeque`]: super::vec_deque::VecDeque #[stable(feature = "rust1", since = "1.0.0")] #[cfg_attr(not(test), rustc_diagnostic_item = "LinkedList")] pub struct LinkedList { -- cgit 1.4.1-3-g733a5 From a8a829deb491db3b87bbe715eece7a7dd5cd288c Mon Sep 17 00:00:00 2001 From: est31 Date: Thu, 16 Sep 2021 13:35:54 +0200 Subject: Add intra-doc-links to BinaryHeap rustdoc --- library/alloc/src/collections/binary_heap.rs | 10 +++++++--- 1 file changed, 7 insertions(+), 3 deletions(-) (limited to 'library/alloc/src') diff --git a/library/alloc/src/collections/binary_heap.rs b/library/alloc/src/collections/binary_heap.rs index 28e4f8bba05..ca289502379 100644 --- a/library/alloc/src/collections/binary_heap.rs +++ b/library/alloc/src/collections/binary_heap.rs @@ -159,9 +159,9 @@ use super::SpecExtend; /// This will be a max-heap. /// /// It is a logic error for an item to be modified in such a way that the -/// item's ordering relative to any other item, as determined by the `Ord` +/// item's ordering relative to any other item, as determined by the [`Ord`] /// trait, changes while it is in the heap. This is normally only possible -/// through `Cell`, `RefCell`, global state, I/O, or unsafe code. The +/// through [`Cell`], [`RefCell`], global state, I/O, or unsafe code. The /// behavior resulting from such a logic error is not specified, but will /// not result in undefined behavior. This could include panics, incorrect /// results, aborts, memory leaks, and non-termination. @@ -219,7 +219,7 @@ use super::SpecExtend; /// /// ## Min-heap /// -/// Either `std::cmp::Reverse` or a custom `Ord` implementation can be used to +/// Either [`core::cmp::Reverse`] or a custom [`Ord`] implementation can be used to /// make `BinaryHeap` a min-heap. This makes `heap.pop()` return the smallest /// value instead of the greatest one. /// @@ -250,6 +250,10 @@ use super::SpecExtend; /// The value for `push` is an expected cost; the method documentation gives a /// more detailed analysis. /// +/// [`core::cmp::Reverse`]: core::cmp::Reverse +/// [`Ord`]: core::cmp::Ord +/// [`Cell`]: core::cell::Cell +/// [`RefCell`]: core::cell::RefCell /// [push]: BinaryHeap::push /// [pop]: BinaryHeap::pop /// [peek]: BinaryHeap::peek -- cgit 1.4.1-3-g733a5 From 372711906b95f3008bca52869a5bd923767062d0 Mon Sep 17 00:00:00 2001 From: est31 Date: Thu, 16 Sep 2021 13:54:05 +0200 Subject: Add IntoIterator intra doc link to various collections --- library/alloc/src/collections/binary_heap.rs | 3 ++- library/alloc/src/collections/btree/map.rs | 3 ++- library/alloc/src/collections/btree/set.rs | 3 ++- library/alloc/src/collections/linked_list.rs | 3 ++- library/alloc/src/collections/vec_deque/into_iter.rs | 3 ++- library/std/src/collections/hash/map.rs | 3 ++- library/std/src/collections/hash/set.rs | 3 ++- 7 files changed, 14 insertions(+), 7 deletions(-) (limited to 'library/alloc/src') diff --git a/library/alloc/src/collections/binary_heap.rs b/library/alloc/src/collections/binary_heap.rs index ca289502379..31355387224 100644 --- a/library/alloc/src/collections/binary_heap.rs +++ b/library/alloc/src/collections/binary_heap.rs @@ -1259,9 +1259,10 @@ impl FusedIterator for Iter<'_, T> {} /// An owning iterator over the elements of a `BinaryHeap`. /// /// This `struct` is created by [`BinaryHeap::into_iter()`] -/// (provided by the `IntoIterator` trait). See its documentation for more. +/// (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 { diff --git a/library/alloc/src/collections/btree/map.rs b/library/alloc/src/collections/btree/map.rs index 501a604e7f7..2a7e1ef351b 100644 --- a/library/alloc/src/collections/btree/map.rs +++ b/library/alloc/src/collections/btree/map.rs @@ -326,9 +326,10 @@ impl fmt::Debug for IterMut<'_, K, V> { /// 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. +/// (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")] pub struct IntoIter { range: LazyLeafRange, diff --git a/library/alloc/src/collections/btree/set.rs b/library/alloc/src/collections/btree/set.rs index c664e201aec..16150ceeb62 100644 --- a/library/alloc/src/collections/btree/set.rs +++ b/library/alloc/src/collections/btree/set.rs @@ -107,9 +107,10 @@ impl fmt::Debug for Iter<'_, T> { /// An owning iterator over the items of a `BTreeSet`. /// /// This `struct` is created by the [`into_iter`] method on [`BTreeSet`] -/// (provided by the `IntoIterator` trait). See its documentation for more. +/// (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 { diff --git a/library/alloc/src/collections/linked_list.rs b/library/alloc/src/collections/linked_list.rs index a3729617aeb..b483a091925 100644 --- a/library/alloc/src/collections/linked_list.rs +++ b/library/alloc/src/collections/linked_list.rs @@ -124,9 +124,10 @@ impl fmt::Debug for IterMut<'_, T> { /// An owning iterator over the elements of a `LinkedList`. /// /// This `struct` is created by the [`into_iter`] method on [`LinkedList`] -/// (provided by the `IntoIterator` trait). See its documentation for more. +/// (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 { diff --git a/library/alloc/src/collections/vec_deque/into_iter.rs b/library/alloc/src/collections/vec_deque/into_iter.rs index 5f13c3bf303..946d3aa8064 100644 --- a/library/alloc/src/collections/vec_deque/into_iter.rs +++ b/library/alloc/src/collections/vec_deque/into_iter.rs @@ -8,9 +8,10 @@ use super::VecDeque; /// An owning iterator over the elements of a `VecDeque`. /// /// This `struct` is created by the [`into_iter`] method on [`VecDeque`] -/// (provided by the `IntoIterator` trait). See its documentation for more. +/// (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< diff --git a/library/std/src/collections/hash/map.rs b/library/std/src/collections/hash/map.rs index 36077a42b48..862f411ebe0 100644 --- a/library/std/src/collections/hash/map.rs +++ b/library/std/src/collections/hash/map.rs @@ -1257,9 +1257,10 @@ impl<'a, K, V> IterMut<'a, K, V> { /// An owning iterator over the entries of a `HashMap`. /// /// This `struct` is created by the [`into_iter`] method on [`HashMap`] -/// (provided by the `IntoIterator` trait). See its documentation for more. +/// (provided by the [`IntoIterator`] trait). See its documentation for more. /// /// [`into_iter`]: IntoIterator::into_iter +/// [`IntoIterator`]: crate::iter::IntoIterator /// /// # Example /// diff --git a/library/std/src/collections/hash/set.rs b/library/std/src/collections/hash/set.rs index 3b61acd122e..941981e3b00 100644 --- a/library/std/src/collections/hash/set.rs +++ b/library/std/src/collections/hash/set.rs @@ -1237,9 +1237,10 @@ pub struct Iter<'a, K: 'a> { /// An owning iterator over the items of a `HashSet`. /// /// This `struct` is created by the [`into_iter`] method on [`HashSet`] -/// (provided by the `IntoIterator` trait). See its documentation for more. +/// (provided by the [`IntoIterator`] trait). See its documentation for more. /// /// [`into_iter`]: IntoIterator::into_iter +/// [`IntoIterator`]: crate::iter::IntoIterator /// /// # Examples /// -- cgit 1.4.1-3-g733a5 From 956f87fb04f589ac2fbe262a043c9f3cad6b2ac0 Mon Sep 17 00:00:00 2001 From: r00ster91 Date: Fri, 24 Sep 2021 12:44:28 +0200 Subject: consistent big O notation --- RELEASES.md | 6 +++--- compiler/rustc_data_structures/src/graph/scc/mod.rs | 2 +- compiler/rustc_data_structures/src/sorted_map.rs | 2 +- library/alloc/src/collections/binary_heap.rs | 8 ++++---- library/alloc/src/vec/mod.rs | 6 +++--- library/core/src/iter/traits/iterator.rs | 3 ++- library/std/src/collections/mod.rs | 18 +++++++++--------- library/std/src/ffi/mod.rs | 4 ++-- src/tools/clippy/clippy_lints/src/methods/mod.rs | 2 +- 9 files changed, 26 insertions(+), 25 deletions(-) (limited to 'library/alloc/src') diff --git a/RELEASES.md b/RELEASES.md index c0851a1506e..12f949be478 100644 --- a/RELEASES.md +++ b/RELEASES.md @@ -4985,7 +4985,7 @@ Libraries - [Upgrade to Unicode 10.0.0][42999] - [Reimplemented `{f32, f64}::{min, max}` in Rust instead of using CMath.][42430] - [Skip the main thread's manual stack guard on Linux][43072] -- [Iterator::nth for `ops::{Range, RangeFrom}` is now done in O(1) time][43077] +- [Iterator::nth for `ops::{Range, RangeFrom}` is now done in *O*(1) time][43077] - [`#[repr(align(N))]` attribute max number is now 2^31 - 1.][43097] This was previously 2^15. - [`{OsStr, Path}::Display` now avoids allocations where possible][42613] @@ -8288,7 +8288,7 @@ Libraries algorithm][s]. * [`std::io::copy` allows `?Sized` arguments][cc]. * The `Windows`, `Chunks`, and `ChunksMut` iterators over slices all - [override `count`, `nth` and `last` with an O(1) + [override `count`, `nth` and `last` with an *O*(1) implementation][it]. * [`Default` is implemented for arrays up to `[T; 32]`][d]. * [`IntoRawFd` has been added to the Unix-specific prelude, @@ -8810,7 +8810,7 @@ Libraries * The `Default` implementation for `Arc` [no longer requires `Sync + Send`][arc]. * [The `Iterator` methods `count`, `nth`, and `last` have been - overridden for slices to have O(1) performance instead of O(n)][si]. + overridden for slices to have *O*(1) performance instead of *O*(*n*)][si]. * Incorrect handling of paths on Windows has been improved in both the compiler and the standard library. * [`AtomicPtr` gained a `Default` implementation][ap]. diff --git a/compiler/rustc_data_structures/src/graph/scc/mod.rs b/compiler/rustc_data_structures/src/graph/scc/mod.rs index e2cbb09ce5e..d8ac815a158 100644 --- a/compiler/rustc_data_structures/src/graph/scc/mod.rs +++ b/compiler/rustc_data_structures/src/graph/scc/mod.rs @@ -3,7 +3,7 @@ //! Also computes as the resulting DAG if each SCC is replaced with a //! node in the graph. This uses [Tarjan's algorithm]( //! https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm) -//! that completes in *O(n)* time. +//! that completes in *O*(*n*) time. use crate::fx::FxHashSet; use crate::graph::vec_graph::VecGraph; diff --git a/compiler/rustc_data_structures/src/sorted_map.rs b/compiler/rustc_data_structures/src/sorted_map.rs index 9a28f8f4e21..20e2a3b9696 100644 --- a/compiler/rustc_data_structures/src/sorted_map.rs +++ b/compiler/rustc_data_structures/src/sorted_map.rs @@ -9,7 +9,7 @@ mod index_map; pub use index_map::SortedIndexMultiMap; /// `SortedMap` is a data structure with similar characteristics as BTreeMap but -/// slightly different trade-offs: lookup, insertion, and removal are O(log(N)) +/// slightly different trade-offs: lookup, insertion, and removal are *O*(log(*n*)) /// and elements can be iterated in order cheaply. /// /// `SortedMap` can be faster than a `BTreeMap` for small sizes (<50) since it diff --git a/library/alloc/src/collections/binary_heap.rs b/library/alloc/src/collections/binary_heap.rs index 28e4f8bba05..be807d733e8 100644 --- a/library/alloc/src/collections/binary_heap.rs +++ b/library/alloc/src/collections/binary_heap.rs @@ -3,7 +3,7 @@ //! Insertion and popping the largest element have *O*(log(*n*)) time complexity. //! Checking the largest element is *O*(1). Converting a vector to a binary heap //! can be done in-place, and has *O*(*n*) complexity. A binary heap can also be -//! converted to a sorted vector in-place, allowing it to be used for an *O*(*n* \* log(*n*)) +//! converted to a sorted vector in-place, allowing it to be used for an *O*(*n* * log(*n*)) //! in-place heapsort. //! //! # Examples @@ -243,9 +243,9 @@ use super::SpecExtend; /// /// # Time complexity /// -/// | [push] | [pop] | [peek]/[peek\_mut] | -/// |--------|-----------|--------------------| -/// | O(1)~ | *O*(log(*n*)) | *O*(1) | +/// | [push] | [pop] | [peek]/[peek\_mut] | +/// |---------|---------------|--------------------| +/// | *O*(1)~ | *O*(log(*n*)) | *O*(1) | /// /// The value for `push` is an expected cost; the method documentation gives a /// more detailed analysis. diff --git a/library/alloc/src/vec/mod.rs b/library/alloc/src/vec/mod.rs index 2f6887229e7..04d369257d8 100644 --- a/library/alloc/src/vec/mod.rs +++ b/library/alloc/src/vec/mod.rs @@ -1,8 +1,8 @@ //! A contiguous growable array type with heap-allocated contents, written //! `Vec`. //! -//! Vectors have `O(1)` indexing, amortized `O(1)` push (to the end) and -//! `O(1)` pop (from the end). +//! Vectors have *O*(1) indexing, amortized *O*(1) push (to the end) and +//! *O*(1) pop (from the end). //! //! Vectors ensure they never allocate more than `isize::MAX` bytes. //! @@ -1268,7 +1268,7 @@ impl Vec { /// /// The removed element is replaced by the last element of the vector. /// - /// This does not preserve ordering, but is O(1). + /// This does not preserve ordering, but is *O*(1). /// /// # Panics /// diff --git a/library/core/src/iter/traits/iterator.rs b/library/core/src/iter/traits/iterator.rs index f884340f4e0..2c499f6fe44 100644 --- a/library/core/src/iter/traits/iterator.rs +++ b/library/core/src/iter/traits/iterator.rs @@ -1798,10 +1798,11 @@ pub trait Iterator { /// The relative order of partitioned items is not maintained. /// /// # Current implementation + /// /// Current algorithms tries finding the first element for which the predicate evaluates /// to false, and the last element for which it evaluates to true and repeatedly swaps them. /// - /// Time Complexity: *O*(*N*) + /// Time complexity: *O*(*n*) /// /// See also [`is_partitioned()`] and [`partition()`]. /// diff --git a/library/std/src/collections/mod.rs b/library/std/src/collections/mod.rs index 71645aadb1d..23f38ff7e15 100644 --- a/library/std/src/collections/mod.rs +++ b/library/std/src/collections/mod.rs @@ -97,11 +97,11 @@ //! //! ## Sequences //! -//! | | get(i) | insert(i) | remove(i) | append | split_off(i) | -//! |----------------|----------------|-----------------|----------------|--------|----------------| -//! | [`Vec`] | O(1) | O(n-i)* | O(n-i) | O(m)* | O(n-i) | -//! | [`VecDeque`] | O(1) | O(min(i, n-i))* | O(min(i, n-i)) | O(m)* | O(min(i, n-i)) | -//! | [`LinkedList`] | O(min(i, n-i)) | O(min(i, n-i)) | O(min(i, n-i)) | O(1) | O(min(i, n-i)) | +//! | | get(i) | insert(i) | remove(i) | append | split_off(i) | +//! |----------------|------------------------|-------------------------|------------------------|-----------|------------------------| +//! | [`Vec`] | *O*(1) | *O*(*n*-*i*)* | *O*(*n*-*i*) | *O*(*m*)* | *O*(*n*-*i*) | +//! | [`VecDeque`] | *O*(1) | *O*(min(*i*, *n*-*i*))* | *O*(min(*i*, *n*-*i*)) | *O*(*m*)* | *O*(min(*i*, *n*-*i*)) | +//! | [`LinkedList`] | *O*(min(*i*, *n*-*i*)) | *O*(min(*i*, *n*-*i*)) | *O*(min(*i*, *n*-*i*)) | *O*(1) | *O*(min(*i*, *n*-*i*)) | //! //! Note that where ties occur, [`Vec`] is generally going to be faster than [`VecDeque`], and //! [`VecDeque`] is generally going to be faster than [`LinkedList`]. @@ -110,10 +110,10 @@ //! //! For Sets, all operations have the cost of the equivalent Map operation. //! -//! | | get | insert | remove | range | append | -//! |--------------|-----------|-----------|-----------|-----------|--------| -//! | [`HashMap`] | O(1)~ | O(1)~* | O(1)~ | N/A | N/A | -//! | [`BTreeMap`] | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n+m) | +//! | | get | insert | remove | range | append | +//! |--------------|---------------|---------------|---------------|---------------|--------------| +//! | [`HashMap`] | *O*(1)~ | *O*(1)~* | *O*(1)~ | N/A | N/A | +//! | [`BTreeMap`] | *O*(log(*n*)) | *O*(log(*n*)) | *O*(log(*n*)) | *O*(log(*n*)) | *O*(*n*+*m*) | //! //! # Correct and Efficient Usage of Collections //! diff --git a/library/std/src/ffi/mod.rs b/library/std/src/ffi/mod.rs index fe4e3af91ad..84d65bb3df4 100644 --- a/library/std/src/ffi/mod.rs +++ b/library/std/src/ffi/mod.rs @@ -43,8 +43,8 @@ //! terminator, so the buffer length is really `len+1` characters. //! Rust strings don't have a nul terminator; their length is always //! stored and does not need to be calculated. While in Rust -//! accessing a string's length is a `O(1)` operation (because the -//! length is stored); in C it is an `O(length)` operation because the +//! accessing a string's length is an *O*(1) operation (because the +//! length is stored); in C it is an *O*(*n*) operation because the //! length needs to be computed by scanning the string for the nul //! terminator. //! diff --git a/src/tools/clippy/clippy_lints/src/methods/mod.rs b/src/tools/clippy/clippy_lints/src/methods/mod.rs index e89b2d295b9..e4d34524f72 100644 --- a/src/tools/clippy/clippy_lints/src/methods/mod.rs +++ b/src/tools/clippy/clippy_lints/src/methods/mod.rs @@ -995,7 +995,7 @@ declare_clippy_lint! { declare_clippy_lint! { /// ### What it does /// Checks for use of `.iter().nth()` (and the related - /// `.iter_mut().nth()`) on standard library types with O(1) element access. + /// `.iter_mut().nth()`) on standard library types with *O*(1) element access. /// /// ### Why is this bad? /// `.get()` and `.get_mut()` are more efficient and more -- cgit 1.4.1-3-g733a5