diff options
| author | Ralf Jung <post@ralfj.de> | 2021-05-20 00:19:02 +0200 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2021-05-20 00:19:02 +0200 |
| commit | c1c4cd57b3dbf8d151f0067994e5e120d4833f6d (patch) | |
| tree | 82566a4b544af7c335df972442481ef82653db8f | |
| parent | a552b5b04bcd546d788798a3bd94ded2dbba048e (diff) | |
| parent | 85e417718403cc0a8b058585fb8633b4698ea3e2 (diff) | |
| download | rust-c1c4cd57b3dbf8d151f0067994e5e120d4833f6d.tar.gz rust-c1c4cd57b3dbf8d151f0067994e5e120d4833f6d.zip | |
Rollup merge of #85315 - satylogin:master, r=yaahc
adding time complexity for partition_in_place iter method I feel that one thing missing from rust docs compared to cpp references is existence of time complexity for all methods and functions. While it would be humongous task to include it for everything in single go, it is still doable if we as community keep on adding it in relevant places as and when we find them. This PR adds the time complexity for partition_in_place method in iter.
| -rw-r--r-- | library/core/src/iter/traits/iterator.rs | 6 |
1 files changed, 6 insertions, 0 deletions
diff --git a/library/core/src/iter/traits/iterator.rs b/library/core/src/iter/traits/iterator.rs index 777e4bc2c89..c2e280ff07d 100644 --- a/library/core/src/iter/traits/iterator.rs +++ b/library/core/src/iter/traits/iterator.rs @@ -1849,6 +1849,12 @@ 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*) + /// /// See also [`is_partitioned()`] and [`partition()`]. /// /// [`is_partitioned()`]: Iterator::is_partitioned |