about summary refs log tree commit diff
path: root/library/alloc/src/collections/btree/map.rs
AgeCommit message (Collapse)AuthorLines
2021-12-04Add documentation to more `From::from` implementations.Kevin Reid-0/+2
For users looking at documentation through IDE popups, this gives them relevant information rather than the generic trait documentation wording “Performs the conversion”. For users reading the documentation for a specific type for any reason, this informs them when the conversion may allocate or copy significant memory versus when it is always a move or cheap copy. Notes on specific cases: * The new documentation for `From<T> for T` explains that it is not a conversion at all. * Also documented `impl<T, U> Into<U> for T where U: From<T>`, the other central blanket implementation of conversion. * I did not add documentation to conversions of a specific error type to a more general error type. * I did not add documentation to unstable code. This change was prepared by searching for the text "From<... for" and so may have missed some cases that for whatever reason did not match. I also looked for `Into` impls but did not find any worth documenting by the above criteria.
2021-12-02Use `BTreeMap::from()` instead of using `BTreeMap::new()` with ↵Joseph T Lyons-4/+5
`BTreeMap::insert()`
2021-10-31Rollup merge of #89786 - jkugelman:must-use-len-and-is_empty, r=joshtriplettMatthias Krüger-0/+2
Add #[must_use] to len and is_empty Parent issue: #89692 r? `@joshtriplett`
2021-10-30Add #[must_use] to len and is_emptyJohn Kugelman-0/+2
2021-10-31Rollup merge of #89899 - jkugelman:must-use-alloc, r=joshtriplettMatthias Krüger-2/+9
Add #[must_use] to remaining alloc functions I've run out of compelling reasons to group functions together across crates so I'm just going to go module-by-module. This is everything remaining from the `alloc` crate. I ignored these because they might be used to purposefully leak memory... or other allocator shenanigans? I dunno. I'll add them if y'all tell me to. ```rust alloc::alloc unsafe fn alloc(layout: Layout) -> *mut u8; alloc::alloc unsafe fn alloc_zeroed(layout: Layout) -> *mut u8; alloc::sync::Arc<T> fn into_raw(this: Self) -> *const T; ``` I don't know why clippy ignored these. I added them myself: ```rust alloc::collections::btree_map::BTreeMap<K, V> fn range<T: ?Sized, R>(&self, range: R) -> Range<'_, K, V>; alloc::collections::btree_set::BTreeSet<T> fn range<K: ?Sized, R>(&self, range: R) -> Range<'_, T>; ``` I added these non-mutating `mut` functions: ```rust alloc::collections::btree_map::BTreeMap<K, V> fn range_mut<T: ?Sized, R>(&mut self, range: R) -> RangeMut<'_, K, V>; alloc::collections::btree_map::BTreeMap<K, V> fn iter_mut(&mut self) -> IterMut<'_, K, V>; alloc::collections::btree_map::BTreeMap<K, V> fn values_mut(&mut self) -> ValuesMut<'_, K, V>; alloc::collections::linked_list::LinkedList<T> fn iter_mut(&mut self) -> IterMut<'_, T>; alloc::collections::linked_list::LinkedList<T> fn cursor_front_mut(&mut self) -> CursorMut<'_, T>; alloc::collections::linked_list::LinkedList<T> fn cursor_back_mut(&mut self) -> CursorMut<'_, T>; alloc::collections::linked_list::LinkedList<T> fn front_mut(&mut self) -> Option<&mut T>; alloc::collections::linked_list::LinkedList<T> fn back_mut(&mut self) -> Option<&mut T>; alloc::collections::linked_list::CursorMut<'a, T> fn current(&mut self) -> Option<&mut T>; alloc::collections::linked_list::CursorMut<'a, T> fn peek_next(&mut self) -> Option<&mut T>; alloc::collections::linked_list::CursorMut<'a, T> fn peek_prev(&mut self) -> Option<&mut T>; alloc::collections::linked_list::CursorMut<'a, T> fn front_mut(&mut self) -> Option<&mut T>; alloc::collections::linked_list::CursorMut<'a, T> fn back_mut(&mut self) -> Option<&mut T>; ``` I moved a few existing `#[must_use]`s from functions onto the iterator types they return: `IntoIterSorted`, `IntoKeys`, `IntoValues`. Parent issue: #89692 r? `@joshtriplett`
2021-10-27Remove big O notationr00ster91-1/+1
2021-10-21Clarify undefined behaviour for binary heap, btree and hashsetWilfred Hughes-3/+3
Previously, it wasn't clear whether "This could include" was referring to logic errors, or undefined behaviour. Tweak wording to clarify this sentence does not relate to UB.
2021-10-15Add #[must_use] to remaining alloc functionsJohn Kugelman-2/+9
2021-10-11Rollup merge of #89726 - jkugelman:must-use-alloc-constructors, r=joshtriplettGuillaume Gomez-0/+1
Add #[must_use] to alloc constructors Added `#[must_use]`. to the various forms of `new`, `pin`, and `with_capacity` in the `alloc` crate. No extra explanations given as I couldn't think of anything useful to add. I figure this deserves extra scrutiny compared to the other PRs I've done so far. In particular: * The 4 `pin`/`pin_in` methods I touched. Are there legitimate use cases for pinning and not using the result? Pinning's a difficult concept I'm not very comfortable with. * `Box`'s constructors. Do people ever create boxes just for the side effects... allocating or zeroing out memory? Parent issue: #89692 r? ``@joshtriplett``
2021-10-10Add #[must_use] to conversions that move selfJohn Kugelman-0/+2
2021-10-10Add #[must_use] to alloc constructorsJohn Kugelman-0/+1
2021-10-04Rollup merge of #89443 - cuviper:btree-hash-len, r=dtolnayJubilee-0/+1
Include the length in BTree hashes This change makes it consistent with `Hash` for all other collections.
2021-10-03Rollup merge of #87679 - ssomers:btree_comments, r=joshtriplettManish Goregaokar-5/+5
BTree: refine some comments
2021-10-01Include the length in BTree hashesJosh Stone-0/+1
This change makes it consistent with `Hash` for all other collections.
2021-09-26Auto merge of #89144 - sexxi-goose:insig_stdlib, r=nikomatsakisbors-0/+2
2229: Mark insignificant dtor in stdlib I looked at all public [stdlib Drop implementations](https://doc.rust-lang.org/stable/std/ops/trait.Drop.html#implementors) and categorized them into Insigificant/Maybe/Significant Drop. Reasons are noted here: https://docs.google.com/spreadsheets/d/19edb9r5lo2UqMrCOVjV0fwcSdS-R7qvKNL76q7tO8VA/edit#gid=1838773501 One thing missing from this PR is tagging HashMap as insigificant destructor as that needs some discussion. r? `@Mark-Simulacrum` cc `@nikomatsakis`
2021-09-22PR fixupAman Arora-2/+2
2021-09-212229: Annotate stdlib with insignficant dtorsAman Arora-0/+2
2021-09-16Add IntoIterator intra doc link to various collectionsest31-1/+2
2021-09-07Auto merge of #88448 - xu-cheng:btree-blk-build, r=Mark-Simulacrumbors-5/+31
BTreeMap/BTreeSet::from_iter: use bulk building to improve the performance Bulk building is a common technique to increase the performance of building a fresh btree map. Instead of inserting items one-by-one, we sort all the items beforehand then create the BtreeMap in bulk. Benchmark ``` ./x.py bench library/alloc --test-args btree::map::from_iter ``` * Before ``` test btree::map::from_iter_rand_100 ... bench: 3,694 ns/iter (+/- 840) test btree::map::from_iter_rand_10_000 ... bench: 1,033,446 ns/iter (+/- 192,950) test btree::map::from_iter_seq_100 ... bench: 5,689 ns/iter (+/- 1,259) test btree::map::from_iter_seq_10_000 ... bench: 861,033 ns/iter (+/- 118,815) ``` * After ``` test btree::map::from_iter_rand_100 ... bench: 3,033 ns/iter (+/- 707) test btree::map::from_iter_rand_10_000 ... bench: 775,958 ns/iter (+/- 105,152) test btree::map::from_iter_seq_100 ... bench: 2,969 ns/iter (+/- 336) test btree::map::from_iter_seq_10_000 ... bench: 258,292 ns/iter (+/- 29,364) ```
2021-08-28BTreeMap::from_iter: use bulk building to improve the performanceCheng XU-5/+31
Bulk building is a common technique to increase the performance of building a fresh btree map. Instead of inserting items one-by-one, we sort all the items beforehand then create the BtreeMap in bulk.
2021-08-18BTree: remove Ord bound from newGary Guo-9/+4
2021-08-17BTree: refine some commentsStein Somers-5/+5
2021-08-02BTree: merge the complication introduced by #81486 and #86031Stein Somers-50/+40
2021-08-01Auto merge of #86031 - ssomers:btree_lazy_iterator, r=Mark-Simulacrumbors-31/+26
BTree: lazily locate leaves in rangeless iterators BTree iterators always locate both the first and last leaf edge and often only need either one, i.e., whenever they are traversed in a single direction, like in for-loops and in the common use of `iter().next()` or `iter().next_back()` to retrieve the first or last key/value-pair (#62924). It's fairly easy to avoid because the iterators with this disadvantage already are quite separate from other iterators. r? `@Mark-Simulacrum`
2021-07-24Auto merge of #84111 - bstrie:hashfrom, r=joshtriplettbors-1/+28
Stabilize `impl From<[(K, V); N]> for HashMap` (and friends) In addition to allowing HashMap to participate in Into/From conversion, this adds the long-requested ability to use constructor-like syntax for initializing a HashMap: ```rust let map = HashMap::from([ (1, 2), (3, 4), (5, 6) ]); ``` This addition is highly motivated by existing precedence, e.g. it is already possible to similarly construct a Vec from a fixed-size array: ```rust let vec = Vec::from([1, 2, 3]); ``` ...and it is already possible to collect a Vec of tuples into a HashMap (and vice-versa): ```rust let vec = Vec::from([(1, 2)]); let map: HashMap<_, _> = vec.into_iter().collect(); let vec: Vec<(_, _)> = map.into_iter().collect(); ``` ...and of course it is likewise possible to collect a fixed-size array of tuples into a HashMap ([but not vice-versa just yet](https://github.com/rust-lang/rust/issues/81615)): ```rust let arr = [(1, 2)]; let map: HashMap<_, _> = std::array::IntoIter::new(arr).collect(); ``` Therefore this addition seems like a no-brainer. As for any impl, this would be insta-stable.
2021-07-24Update std_collections_from_array stability versionbstrie-1/+1
2021-07-24Rollup merge of #86790 - janikrabe:retain-iter-order-doc, r=m-ou-seYuki Okushi-0/+1
Document iteration order of `retain` functions For `HashSet` and `HashMap`, this simply copies the comment from `BinaryHeap::retain`. For `BTreeSet` and `BTreeMap`, this adds an additional guarantee that wasn't previously documented. I think that because these data structures are inherently ordered and other functions guarantee ordered iteration, it makes sense to provide this guarantee for `retain` as well.
2021-07-08BTree: lazily locate leaves in rangeless iteratorsStein Somers-31/+26
2021-07-01Document iteration order of `retain` functionsJanik Rabe-0/+1
For `HashSet` and `HashMap`, this simply copies the comment from `BinaryHeap::retain`. For `BTreeSet` and `BTreeMap`, this adds an additional guarantee that wasn't previously documented. I think that because these data structures are inherently ordered and other functions guarantee ordered iteration, it makes sense to provide this guarantee for `retain` as well.
2021-06-30impl From<[(K, V); N]> for std::collectionsbstrie-1/+28
2021-06-30Remove "length" doc aliasesAmanieu d'Antras-1/+0
2021-06-30Remove "delete" doc aliasesAmanieu d'Antras-1/+0
2021-06-09BTree: encapsulate LeafRange better & some debug assertsStein Somers-36/+12
2021-05-07BTree: no longer copy keys and values before dropping themStein Somers-6/+15
2021-05-05Bump map_into_keys_values stable version to 1.54.0.Mara Bos-14/+14
2021-04-19Stablize {HashMap,BTreeMap}::into_{keys,values}Folyd-16/+14
2021-04-12Stabilize BTree{Map,Set}::retainJubilee Young-2/+1
2021-03-18Rollup merge of #82434 - jyn514:hash, r=JohnTitorDylan DPC-3/+4
Add more links between hash and btree collections - Link from `core::hash` to `HashMap` and `HashSet` - Link from HashMap and HashSet to the module-level documentation on when to use the collection - Link from several collections to Wikipedia articles on the general concept See also https://github.com/rust-lang/rust/pull/81989#issuecomment-783920840.
2021-03-04Add tracking issue for map_try_insert.Mara Bos-1/+1
2021-03-04Add BTreeMap::try_insert and btree_map::OccupiedError.Mara Bos-1/+35
2021-03-01Add diagnostic itemsCameron Steffen-0/+1
2021-02-23Add more links between hash and btree collectionsJoshua Nelson-3/+4
- Link from `core::hash` to `HashMap` and `HashSet` - Link from HashMap and HashSet to the module-level documentation on when to use the collection - Link from several collections to Wikipedia articles on the general concept
2021-02-15BTree: move more shared iterator code into navigate.rsStein Somers-56/+35
2021-02-14Auto merge of #81956 - ssomers:btree_post_75200, r=Mark-Simulacrumbors-19/+7
BTree: remove outdated traces of coercions The introduction of `marker::ValMut` (#75200) meant iterators no longer see mutable keys but their code still pretends it does. And settle on the majority style `Some(unsafe {…})` over `unsafe { Some(…) }`. r? `@Mark-Simulacrum`
2021-02-10BTree: remove outdated traces of coercionsStein Somers-19/+7
2021-02-09BTreeMap: disentangle Drop implementation from IntoIterStein Somers-26/+34
2021-02-08Auto merge of #81361 - ssomers:btree_drainy_refactor_7, r=Mark-Simulacrumbors-12/+12
BTreeMap: lightly refactor the split_off implementation r? `@Mark-Simulacrum`
2021-02-08Auto merge of #79245 - ssomers:btree_curb_ord_bound, r=dtolnaybors-13/+4
BTree: remove Ord bound where it is absent elsewhere Some btree methods don't really need an Ord bound and don't have one, while some methods that more obviously don't need it, do have one. An example of the former is `iter`, even though it explicitly exposes the work of the Ord implementation (["sorted by key"](https://doc.rust-lang.org/std/collections/struct.BTreeMap.html#method.iter) - but I'm not suggesting it should have the Ord bound). An example of the latter is `new`, which doesn't involve any keys whatsoever.
2021-02-07Rollup merge of #81526 - ojeda:btree-use-unwrap_unchecked, r=scottmcmGuillaume Gomez-6/+5
btree: use Option's unwrap_unchecked() Now that https://github.com/rust-lang/rust/issues/81383 is available, start using it.
2021-02-06Rollup merge of #81434 - ssomers:btree_drain_filter_doc_update, r=dtolnayJonas Schievink-15/+17
BTree: fix documentation of unstable public members As rightfully requested in #62924 & #70530. r? `@Mark-Simulacrum`
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-07-12 06:17:16 +0000