about summary refs log tree commit diff
path: root/library/alloc/src/collections
AgeCommit message (Collapse)AuthorLines
2022-01-16Rollup merge of #92706 - umanwizard:btree, r=dtolnayMatthias Krüger-4/+11
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.
2022-01-15Tweak btree iterator wording to not use 'yield'David Tolnay-4/+5
Yield means something else in the context of generators, which are sufficiently close to iterators that it's better to avoid the terminology collision here.
2022-01-11Address review commentsBrennan Vincent-4/+4
2022-01-11Auto merge of #92070 - rukai:replace_vec_into_iter_with_array_into_iter, ↵bors-10/+10
r=Mark-Simulacrum Replace usages of vec![].into_iter with [].into_iter `[].into_iter` is idiomatic over `vec![].into_iter` because its simpler and faster (unless the vec is optimized away in which case it would be the same) So we should change all the implementation, documentation and tests to use it. I skipped: * `src/tools` - Those are copied in from upstream * `src/test/ui` - Hard to tell if `vec![].into_iter` was used intentionally or not here and not much benefit to changing it. * any case where `vec![].into_iter` was used because we specifically needed a `Vec::IntoIter<T>` * any case where it looked like we were intentionally using `vec![].into_iter` to test it.
2022-01-09Clarify explicitly that BTree{Map,Set} are ordered.Brennan Vincent-4/+10
2022-01-09Compute most of Public/Exported access level in rustc_resolveLamb-0/+3
Mak DefId to AccessLevel map in resolve for export hir_id to accesslevel in resolve and applied in privacy using local def id removing tracing probes making function not recursive and adding comments Move most of Exported/Public res to rustc_resolve moving public/export res to resolve fix missing stability attributes in core, std and alloc move code to access_levels.rs return for some kinds instead of going through them Export correctness, macro changes, comments add comment for import binding add comment for import binding renmae to access level visitor, remove comments, move fn as closure, remove new_key fmt fix rebase fix rebase fmt fmt fix: move macro def to rustc_resolve fix: reachable AccessLevel for enum variants fmt fix: missing stability attributes for other architectures allow unreachable pub in rustfmt fix: missing impl access level + renaming export to reexport Missing impl access level was found thanks to a test in clippy
2022-01-09eplace usages of vec![].into_iter with [].into_iterLucas Kent-10/+10
2021-12-29fix typo in btree/vec doc: Self -> selfVeeupup-2/+2
2021-12-14Rollup merge of #91529 - TennyZhuang:try_reserve_binary_heap, r=yaahcMatthias Krüger-0/+79
add BinaryHeap::try_reserve and BinaryHeap::try_reserve_exact `try_reserve` of many collections were stablized in https://github.com/rust-lang/rust/pull/87993 in 1.57.0. Add `try_reserve` for the rest collections such as `BinaryHeap` should be not controversial.
2021-12-13Rollup merge of #91749 - ssomers:btree_comments, r=Mark-SimulacrumMatthias Krüger-55/+58
BTree: improve public descriptions and comments BTreeSet has always used the term "value" next to and meaning the same thing as "elements" (in the mathematical sense but also used for key-value pairs in BTreeMap), while in the BTreeMap sense these "values" are known as "keys" and definitely not "values". Today I had enough of that. r? `@Mark-Simulacrum`
2021-12-12Rollup merge of #91814 - japm48:spelling-fix, r=RalfJungMatthias Krüger-6/+6
doc: fix typo in comments `dereferencable -> dereferenceable` Fixes #91802.
2021-12-12Rollup merge of #91746 - ssomers:btree_tests, r=Mark-SimulacrumMatthias Krüger-6/+38
Btree: assert more API compatibility Introducing a member such as `BTreeSet::min()` would silently break compatibility if no code calls the existing `BTreeSet::min(set)`. `BTreeSet` is the only btree class silently bringing in stable members, apart from many occurrences of `#[derive(Debug)]` on iterators. r? `@Mark-Simulacrum`
2021-12-12doc: fix typo in commentsjapm48-6/+6
dereferencable -> dereferenceable
2021-12-11update feature gateTennyZhuang-4/+4
2021-12-11add BinaryHeap::try_reserve and BinaryHeap::try_reserve_exactTennyZhuang-0/+79
Signed-off-by: TennyZhuang <zty0826@gmail.com>
2021-12-11Auto merge of #91761 - matthiaskrgr:rollup-bjowmvz, r=matthiaskrgrbors-20/+19
Rollup of 11 pull requests Successful merges: - #91668 (Remove the match on `ErrorKind::Other`) - #91678 (Add tests fixed by #90023) - #91679 (Move core/stream/stream/mod.rs to core/stream/stream.rs) - #91681 (fix typo in `intrinsics::raw_eq` docs) - #91686 (Fix `Vec::reserve_exact` documentation) - #91697 (Delete Utf8Lossy::from_str) - #91706 (Add unstable book entries for parts of asm that are not being stabilized) - #91709 (Replace iterator-based set construction by *Set::From<[T; N]>) - #91716 (Improve x.py logging and defaults a bit more) - #91747 (Add pierwill to .mailmap) - #91755 (Fix since attribute for const_linked_list_new feature) Failed merges: r? `@ghost` `@rustbot` modify labels: rollup
2021-12-10Rollup merge of #91755 - not-my-profile:fix-const_linked_list_new-since, ↵Matthias Krüger-1/+1
r=dtolnay Fix since attribute for const_linked_list_new feature https://github.com/rust-lang/rust/pull/63684 was merged for 1.39 not 1.32
2021-12-10Rollup merge of #91482 - ↵Matthias Krüger-4/+5
JosephTLyons:update-HashMap-and-BTreeMap-documentation, r=yaahc Update documentation to use `from()` to initialize `HashMap`s and `BTreeMap`s As of Rust 1.56, `HashMap` and `BTreeMap` both have associated `from()` functions. I think using these in the documentation cleans things up a bit. It allows us to remove some of the `mut`s and avoids the Initialize-Then-Modify anti-pattern.
2021-12-10Fix since attribute for const_linked_list_new featureMartin Fischer-1/+1
https://github.com/rust-lang/rust/pull/63684 was merged for 1.39 not 1.32
2021-12-10BTree: improve public descriptions and commentsStein Somers-55/+58
2021-12-10BTree: assert presence of derived functionsStein Somers-0/+32
2021-12-10BTree: rename compile-time assertions to match library/alloc/testsStein Somers-6/+6
2021-12-09Replace iterator-based set construction by *Set::From<[T; N]>Júnior Bassani-19/+18
2021-12-07Rollup merge of #91547 - TennyZhuang:suggest_try_reserve, r=scottmcmMatthias Krüger-2/+2
Suggest try_reserve in try_reserve_exact During developing #91529 , I found that `try_reserve_exact` suggests `reserve` for further insertions. I think it's a mistake by copy&paste, `try_reserve` is better here.
2021-12-05Auto merge of #88611 - m-ou-se:array-into-iter-new-deprecate, r=joshtriplettbors-7/+7
Deprecate array::IntoIter::new.
2021-12-05doc: suggest try_reserve in try_reserve_exactTennyZhuang-2/+2
Signed-off-by: TennyZhuang <zty0826@gmail.com>
2021-12-05Rollup merge of #91215 - GuillaumeGomez:vec-deque-retain-mut, r=m-ou-seMatthias Krüger-3/+34
Implement VecDeque::retain_mut Part of https://github.com/rust-lang/rust/issues/90829. In https://github.com/rust-lang/rust/pull/90772, someone suggested that `retain_mut` should also be implemented on `VecDeque`. I think that it follows the same logic (coherency). So first: is it ok? Second: should I create a new feature for it or can we put it into the same one? r? `@joshtriplett`
2021-12-04Use IntoIterator for array impl everywhere.Mara Bos-7/+7
2021-12-04Add documentation to more `From::from` implementations.Kevin Reid-0/+8
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-11-29Remove unnecessary check in VecDeque::growCédric Barreteau-9/+11
All callers already check that the buffer is full before calling `grow()`. This is where it makes the most sense, since `grow()` is `inline(never)` and we don't want to pay for a function call just for that check. It could also be argued that it would be correct to call `grow()` even if the buffer wasn't full yet. This change breaks no code since `grow()` is not `pub`.
2021-11-25Implement VecDeque::retain_mutGuillaume Gomez-3/+34
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.
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-03-01 08:02:55 +0000