diff options
| author | Matthias Krüger <matthias.krueger@famsik.de> | 2022-11-29 05:24:23 +0100 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2022-11-29 05:24:23 +0100 |
| commit | d5d79ac67bbe359e3a3c8ca841450afd37cd1187 (patch) | |
| tree | 2ef9e72c04ef4c63e9e541213f7907049e9b6964 /compiler/rustc_data_structures/src | |
| parent | cea2e14ba266ab80bc679c59dd07ebfa03811952 (diff) | |
| parent | 11525e506e2e469d5b13981420cd9702eddeb2e9 (diff) | |
| download | rust-d5d79ac67bbe359e3a3c8ca841450afd37cd1187.tar.gz rust-d5d79ac67bbe359e3a3c8ca841450afd37cd1187.zip | |
Rollup merge of #105010 - Neutron3529:patch-2, r=jyn514
Fix documentation of asymptotic complexity for rustc_data_structures::SortedMap https://users.rust-lang.org/t/is-the-document-in-sortedmap-in-rustc-data-structures-sorted-map-correct/84939 SortedMap have `O(n)` insertions and removal rather than `O(log(n))`
Diffstat (limited to 'compiler/rustc_data_structures/src')
| -rw-r--r-- | compiler/rustc_data_structures/src/sorted_map.rs | 4 |
1 files changed, 2 insertions, 2 deletions
diff --git a/compiler/rustc_data_structures/src/sorted_map.rs b/compiler/rustc_data_structures/src/sorted_map.rs index fe257e10205..d607a5c8314 100644 --- a/compiler/rustc_data_structures/src/sorted_map.rs +++ b/compiler/rustc_data_structures/src/sorted_map.rs @@ -10,8 +10,8 @@ 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*)) -/// and elements can be iterated in order cheaply. +/// slightly different trade-offs: lookup is *O*(log(*n*)), insertion and removal +/// are *O*(*n*) but elements can be iterated in order cheaply. /// /// `SortedMap` can be faster than a `BTreeMap` for small sizes (<50) since it /// stores data in a more compact way. It also supports accessing contiguous |