about summary refs log tree commit diff
path: root/library/alloc/src/collections
AgeCommit message (Collapse)AuthorLines
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-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-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
2021-09-01Rollup merge of #88040 - nbdd0121:btreemap, r=m-ou-seMara Bos-16/+20
BTree: remove Ord bound from new `K: Ord` bound is unnecessary on `BTree{Map,Set}::new` and their `Default` impl. No elements exist so there are nothing to compare anyway, so I don't think "future proof" would be a blocker here. This is analogous to `HashMap::new` not having a `K: Eq + Hash` bound. #79245 originally does this and for some reason drops the change to `new` and `Default`. I can see why changes to other methods like `entry` or `symmetric_difference` need to be careful but I couldn't find out any reason not to do it on `new`. Removing the bound also makes the stabilisation of `const fn new` not depending on const trait bounds. cc `@steffahn` who suggests me to make this PR. r? `@dtolnay`
2021-08-31add safety annotation to `LinkedList::detach_all_nodes`Ibraheem Ahmed-0/+3
Co-authored-by: kennytm <kennytm@gmail.com>
2021-08-30use `unwrap_unchecked` where possibleibraheemdev-1/+1
2021-08-28VecDeque: improve performance for From<[T; N]>Cheng XU-1/+41
Create VecDeque directly from the array instead of inserting items one-by-one.
2021-08-28BTreeSet::from_iter: use bulk building to improve the performanceCheng XU-5/+22
Apply the same optimization as BTreeMap::from_iter.
2021-08-28BTreeMap::from_iter: use bulk building to improve the performanceCheng XU-5/+79
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-26Rollup merge of #88216 - kornelski:from_layout_err, r=kennytmManish Goregaokar-3/+3
Don't stabilize creation of TryReserveError instances #48043 + https://github.com/rust-lang/rust/pull/87993#issuecomment-903189016
2021-08-22Fix typos “an”→“a” and a few different ones that appeared in the ↵Frank Steffahn-1/+1
same search
2021-08-21Auto merge of #88075 - Xuanwo:vec_deque_retain, r=dtolnaybors-8/+57
Optimize unnecessary check in VecDeque::retain This pr is highly inspired by https://github.com/rust-lang/rust/pull/88060 which shared the same idea: we can split the `for` loop into stages so that we can remove unnecessary checks like `del > 0`. ## Benchmarks Before ```rust test collections::vec_deque::tests::bench_retain_half_10000 ... bench: 290,125 ns/iter (+/- 8,717) test collections::vec_deque::tests::bench_retain_odd_10000 ... bench: 291,588 ns/iter (+/- 9,621) test collections::vec_deque::tests::bench_retain_whole_10000 ... bench: 287,426 ns/iter (+/- 9,009) ``` After ```rust test collections::vec_deque::tests::bench_retain_half_10000 ... bench: 243,940 ns/iter (+/- 8,563) test collections::vec_deque::tests::bench_retain_odd_10000 ... bench: 242,768 ns/iter (+/- 3,903) test collections::vec_deque::tests::bench_retain_whole_10000 ... bench: 202,926 ns/iter (+/- 6,332) ``` Based on the current benchmark, this PR will improve the perf of `VecDeque::retain` by around 16%. For special cases, the improvement will be up to 30%. Signed-off-by: Xuanwo <github@xuanwo.io>
2021-08-21Don't stabilize creation of TryReserveError instancesKornel-3/+3
2021-08-18BTree: remove Ord bound from newGary Guo-16/+20
2021-08-17BTree: refine some commentsStein Somers-11/+9
2021-08-16BTree: toughen panicky test of clone()Stein Somers-25/+32
2021-08-16Remove extra empty linesXuanwo-2/+0
Signed-off-by: Xuanwo <github@xuanwo.io>
2021-08-16Optimize unnecessary check in VecDeque::retainXuanwo-8/+59
Signed-off-by: Xuanwo <github@xuanwo.io>
2021-08-16Auto merge of #87696 - ssomers:btree_lazy_iterator_cleanup, r=Mark-Simulacrumbors-56/+56
BTree: merge the complication introduced by #81486 and #86031 Also: - Deallocate the last few tree nodes as soon as an `into_iter` iterator steps beyond the end, instead of waiting around for the drop of the iterator (just to share more code). - Symmetric code for backward iteration. - Mark unsafe the methods on dying handles, modelling dying handles after raw pointers: it's the caller's responsibility to use them safely. r? `@Mark-Simulacrum`
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-02-25 21:30:25 +0000