diff options
| author | Matthias Krüger <matthias.krueger@famsik.de> | 2022-01-16 16:58:16 +0100 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2022-01-16 16:58:16 +0100 |
| commit | 039d6dc2896366b45cb71cef61dcbbd6cfc518a4 (patch) | |
| tree | abeb1fdb1dd798bdb31a098f7c805d2278b814f7 /library/alloc/src/collections/btree | |
| parent | c5041f88ea6bb48379db3539e339e175534e4352 (diff) | |
| parent | ad6408dd7a786db603c2ed323894feb7110e8dea (diff) | |
| download | rust-039d6dc2896366b45cb71cef61dcbbd6cfc518a4.tar.gz rust-039d6dc2896366b45cb71cef61dcbbd6cfc518a4.zip | |
Rollup merge of #92706 - umanwizard:btree, r=dtolnay
Clarify explicitly that BTree{Map,Set} are ordered.
One of the main reasons one would want to use a BTree{Map,Set} rather than a Hash{Map,Set} is because they maintain their keys in sorted order; but this was never explicitly stated in the top-level docs (it was only indirectly alluded to there, and stated explicitly in the docs for `iter`, `values`, etc.)
This PR states the ordering guarantee more prominently.
Diffstat (limited to 'library/alloc/src/collections/btree')
| -rw-r--r-- | library/alloc/src/collections/btree/map.rs | 6 | ||||
| -rw-r--r-- | library/alloc/src/collections/btree/set.rs | 5 |
2 files changed, 9 insertions, 2 deletions
diff --git a/library/alloc/src/collections/btree/map.rs b/library/alloc/src/collections/btree/map.rs index 62153efbb39..794b9356e7c 100644 --- a/library/alloc/src/collections/btree/map.rs +++ b/library/alloc/src/collections/btree/map.rs @@ -34,7 +34,7 @@ pub(super) const MIN_LEN: usize = node::MIN_LEN_AFTER_SPLIT; // An empty map is represented either by the absence of a root node or by a // root node that is an empty leaf. -/// A map based on a [B-Tree]. +/// An ordered map based on a [B-Tree]. /// /// B-Trees represent a fundamental compromise between cache-efficiency and actually minimizing /// the amount of work performed in a search. In theory, a binary search tree (BST) is the optimal @@ -68,6 +68,10 @@ pub(super) const MIN_LEN: usize = node::MIN_LEN_AFTER_SPLIT; /// incorrect results, aborts, memory leaks, or non-termination) but will not be undefined /// behavior. /// +/// Iterators obtained from functions such as [`BTreeMap::iter`], [`BTreeMap::values`], or +/// [`BTreeMap::keys`] produce their items in order by key, and take worst-case logarithmic and +/// amortized constant time per item returned. +/// /// [B-Tree]: https://en.wikipedia.org/wiki/B-tree /// [`Cell`]: core::cell::Cell /// [`RefCell`]: core::cell::RefCell diff --git a/library/alloc/src/collections/btree/set.rs b/library/alloc/src/collections/btree/set.rs index 394c21bf51c..31df4e98ed7 100644 --- a/library/alloc/src/collections/btree/set.rs +++ b/library/alloc/src/collections/btree/set.rs @@ -15,7 +15,7 @@ use super::Recover; // FIXME(conventions): implement bounded iterators -/// A set based on a B-Tree. +/// An ordered set based on a B-Tree. /// /// See [`BTreeMap`]'s documentation for a detailed discussion of this collection's performance /// benefits and drawbacks. @@ -27,6 +27,9 @@ use super::Recover; /// incorrect results, aborts, memory leaks, or non-termination) but will not be undefined /// behavior. /// +/// Iterators returned by [`BTreeSet::iter`] produce their items in order, and take worst-case +/// logarithmic and amortized constant time per item returned. +/// /// [`Ord`]: core::cmp::Ord /// [`Cell`]: core::cell::Cell /// [`RefCell`]: core::cell::RefCell |