summary refs log tree commit diff
path: root/library/alloc/src/collections
AgeCommit message (Collapse)AuthorLines
2021-11-12provide a `SpecExtend` trait for `Vec<T>`Neutron3529-0/+8
The discussion is [here](https://internals.rust-lang.org/t/append-vec-to-binaryheap/15209/3)
2021-10-31Rollup merge of #89786 - jkugelman:must-use-len-and-is_empty, r=joshtriplettMatthias Krüger-2/+10
Add #[must_use] to len and is_empty Parent issue: #89692 r? `@joshtriplett`
2021-10-31Rollup merge of #89835 - jkugelman:must-use-expensive-computations, ↵Matthias Krüger-0/+8
r=joshtriplett Add #[must_use] to expensive computations The unifying theme for this commit is weak, admittedly. I put together a list of "expensive" functions when I originally proposed this whole effort, but nobody's cared about that criterion. Still, it's a decent way to bite off a not-too-big chunk of work. Given the grab bag nature of this commit, the messages I used vary quite a bit. I'm open to wording changes. For some reason clippy flagged four `BTreeSet` methods but didn't say boo about equivalent ones on `HashSet`. I stared at them for a while but I can't figure out the difference so I added the `HashSet` ones in. ```rust // Flagged by clippy. alloc::collections::btree_set::BTreeSet<T> fn difference<'a>(&'a self, other: &'a BTreeSet<T>) -> Difference<'a, T>; alloc::collections::btree_set::BTreeSet<T> fn symmetric_difference<'a>(&'a self, other: &'a BTreeSet<T>) -> SymmetricDifference<'a, T> alloc::collections::btree_set::BTreeSet<T> fn intersection<'a>(&'a self, other: &'a BTreeSet<T>) -> Intersection<'a, T>; alloc::collections::btree_set::BTreeSet<T> fn union<'a>(&'a self, other: &'a BTreeSet<T>) -> Union<'a, T>; // Ignored by clippy, but not by me. std::collections::HashSet<T, S> fn difference<'a>(&'a self, other: &'a HashSet<T, S>) -> Difference<'a, T, S>; std::collections::HashSet<T, S> fn symmetric_difference<'a>(&'a self, other: &'a HashSet<T, S>) -> SymmetricDifference<'a, T, S> std::collections::HashSet<T, S> fn intersection<'a>(&'a self, other: &'a HashSet<T, S>) -> Intersection<'a, T, S>; std::collections::HashSet<T, S> fn union<'a>(&'a self, other: &'a HashSet<T, S>) -> Union<'a, T, S>; ``` Parent issue: #89692 r? ```@joshtriplett```
2021-10-30Add #[must_use] to len and is_emptyJohn Kugelman-4/+12
2021-10-31Rollup merge of #89899 - jkugelman:must-use-alloc, r=joshtriplettMatthias Krüger-18/+57
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-9/+9
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-18Avoid overflow in `VecDeque::with_capacity_in()`.Hans Kratz-1/+1
2021-10-15Add #[must_use] to remaining alloc functionsJohn Kugelman-18/+57
2021-10-15Auto merge of #88717 - tabokie:vecdeque-fast-append, r=m-ou-sebors-2/+30
Optimize VecDeque::append Optimize `VecDeque::append` to do unsafe copy rather than iterating through each element. On my `Intel(R) Xeon(R) CPU E5-2630 v4 @ 2.20GHz`, the benchmark shows 37% improvements: ``` Master: custom-bench vec_deque_append 583164 ns/iter custom-bench vec_deque_append 550040 ns/iter Patched: custom-bench vec_deque_append 349204 ns/iter custom-bench vec_deque_append 368164 ns/iter ``` Additional notes on the context: this is the third attempt to implement a non-trivial version of `VecDeque::append`, the last two are reverted due to unsoundness or regression, see: - https://github.com/rust-lang/rust/pull/52553, reverted in https://github.com/rust-lang/rust/pull/53571 - https://github.com/rust-lang/rust/pull/53564, reverted in https://github.com/rust-lang/rust/pull/54851 Both cases are covered by existing tests. Signed-off-by: tabokie <xy.tao@outlook.com>
2021-10-12Add #[must_use] to expensive computationsJohn Kugelman-0/+8
The unifying theme for this commit is weak, admittedly. I put together a list of "expensive" functions when I originally proposed this whole effort, but nobody's cared about that criterion. Still, it's a decent way to bite off a not-too-big chunk of work. Given the grab bag nature of this commit, the messages I used vary quite a bit.
2021-10-12Rollup merge of #89778 - jkugelman:must-use-as_type-conversions, r=joshtriplettthe8472-0/+2
Add #[must_use] to as_type conversions Clippy missed these: ```rust alloc::string::String fn as_mut_str(&mut self) -> &mut str; core::mem::NonNull<T> unsafe fn as_uninit_mut<'a>(&mut self) -> &'a MaybeUninit<T>; str unsafe fn as_bytes_mut(&mut self) -> &mut [u8]; str fn as_mut_ptr(&mut self) -> *mut u8; ``` Parent issue: #89692 r? ````@joshtriplett````
2021-10-11Add #[must_use] to as_type conversionsJohn Kugelman-0/+2
2021-10-11Rollup merge of #89726 - jkugelman:must-use-alloc-constructors, r=joshtriplettGuillaume Gomez-0/+7
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-11Auto merge of #89755 - jkugelman:must-use-conversions-that-move-self, ↵bors-10/+15
r=joshtriplett Add #[must_use] to conversions that move self Everything here got the same message. Is the wording okay? ```rust #[must_use = "`self` will be dropped if the result is not used"] ``` I want to draw attention to these methods in particular: ```rust alloc::sync::Arc<MaybeUninit<T>> unsafe fn assume_init(self) -> Arc<T>; alloc::sync::Arc<[MaybeUninit<T>]> unsafe fn assume_init(self) -> Arc<[T]>; core::pin::Pin<&'a mut T> const fn into_ref(self) -> Pin<&'a T>; core::pin::Pin<&'a mut T> const fn get_mut(self) -> &'a mut T; core::pin::Pin<&'a mut T> const unsafe fn get_unchecked_mut(self) -> &'a mut T; core::pin::Pin<&'a mut T> unsafe fn map_unchecked_mut(self, func: F) -> Pin<&'a mut U>; core::pin::Pin<&'a mut Pin<P>> fn as_deref_mut(self) -> Pin<&'a mut P::Target>; ``` Parent issue: #89692 r? `@joshtriplett`
2021-10-10Add #[must_use] to conversions that move selfJohn Kugelman-10/+15
2021-10-10Add #[must_use] to alloc constructorsJohn Kugelman-0/+7
2021-10-09Add #[must_use] to is_condition testsJohn Kugelman-0/+3
There's nothing insightful to say about these so I didn't write any extra explanations.
2021-10-06Rollup merge of #89245 - DeveloperC286:iter_mut_fields_to_private, ↵Manish Goregaokar-16/+21
r=joshtriplett refactor: make VecDeque's IterMut fields module-private, not just crate-private Made the fields of VecDeque's IterMut private by creating a IterMut::new(...) function to create a new instance of IterMut and migrating usage to use IterMut::new(...).
2021-10-05refactor: VecDeques IterMut fields to privateDeveloperC-16/+21
Made the fields of VecDeque's IterMut private by creating a IterMut::new(...) function to create a new instance of IterMut and migrating usage to use IterMut::new(...).
2021-10-05refactor: VecDeques Drain fields to privateDeveloperC286-17/+26
2021-10-04Rollup merge of #89244 - DeveloperC286:pair_slices_fields_to_private, ↵Manish Goregaokar-4/+4
r=joshtriplett refactor: VecDeques PairSlices fields to private Reducing VecDeque's PairSlices fields to private, a `from(...)` method is already used to create PairSlices.
2021-10-04Rollup merge of #87993 - kornelski:try_reserve_stable, r=joshtriplettJubilee-6/+4
Stabilize try_reserve Stabilization PR for the [`try_reserve` feature](https://github.com/rust-lang/rust/issues/48043#issuecomment-898040475).
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-04Rollup merge of #88452 - xu-cheng:vecdeque-from-array, r=m-ou-seJubilee-1/+41
VecDeque: improve performance for From<[T; N]> Create `VecDeque` directly from the array instead of inserting items one-by-one. Benchmark ``` ./x.py bench library/alloc --test-args vec_deque::bench_from_array_1000 ``` * Before ``` test vec_deque::bench_from_array_1000 ... bench: 3,991 ns/iter (+/- 717) ``` * After ``` test vec_deque::bench_from_array_1000 ... bench: 268 ns/iter (+/- 37) ```
2021-10-04Stabilize try_reserveKornel-6/+4
2021-10-03Rollup merge of #87679 - ssomers:btree_comments, r=joshtriplettManish Goregaokar-10/+8
BTree: refine some comments
2021-10-04Update outdated commentXinye Tao-1/+1
2021-10-03Auto merge of #88086 - ssomers:btree_clone_testing, r=dtolnaybors-25/+32
BTree: toughen panicky test of clone() Test did not cover the second half of `clone_subtree` and why this clones key & value first.
2021-10-02Make diangostic item names consistentCameron Steffen-1/+1
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/+4
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-25Rollup merge of #89216 - r00ster91:bigo, r=dtolnayManish Goregaokar-4/+4
Consistent big O notation This makes the big O time complexity notation in places with markdown support more consistent. Inspired by #89210
2021-09-25Rollup merge of #89010 - est31:intra_doc_links, r=m-ou-seManish Goregaokar-9/+21
Add some intra doc links
2021-09-25refactor: VecDeques PairSlices fields to privateDeveloperC-4/+4
2021-09-24unitalicize O(1) complexitiesTakashi Idobe-4/+4
2021-09-24consistent big O notationr00ster91-4/+4
2021-09-23remove trailing whitespaceTakashi Idobe-4/+4
2021-09-23Add time complexities to linked_list.rsTakashi Idobe-0/+10
2021-09-22PR fixupAman Arora-4/+4
2021-09-212229: Annotate stdlib with insignficant dtorsAman Arora-0/+4
2021-09-17refactor: VecDeques IntoIter fields to privateDeveloperC286-2/+8
2021-09-16Add IntoIterator intra doc link to various collectionsest31-5/+10
2021-09-16Add intra-doc-links to BinaryHeap rustdocest31-3/+7
2021-09-16Add intra-doc-links to LinkedList rustdocest31-1/+4
2021-09-08rearrange to be panic safetabokie-10/+12
Signed-off-by: tabokie <xy.tao@outlook.com>
2021-09-07Optimize VecDeque::appendtabokie-2/+28
Signed-off-by: tabokie <xy.tao@outlook.com>
2021-09-07Auto merge of #88448 - xu-cheng:btree-blk-build, r=Mark-Simulacrumbors-10/+101
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-09-05Fix typo: needede -> neededYechan Bae-1/+1
2021-09-02Rollup merge of #88505 - ibraheemdev:use-unwrap-unchecked, r=kennytmMara Bos-1/+4
Use `unwrap_unchecked` where possible
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-07-04 10:18:37 +0000