summary refs log tree commit diff
path: root/library/alloc/src/collections
AgeCommit message (Collapse)AuthorLines
2022-03-30Stabilize feature vec_retain_mut on Vec and VecDequeLinus Färnstrand-3/+1
2022-03-22rename internal helper trait AsIntoIter to AsVecIntoIterThe 8472-2/+2
2022-03-21add module-level documentation for vec's in-place iterationThe8472-0/+2
2022-03-21move AsIntoIter helper trait and mark it as unsafeThe8472-1/+1
2022-03-20Auto merge of #92962 - frank-king:btree_entry_no_insert, r=Amanieubors-41/+86
BTreeMap::entry: Avoid allocating if no insertion This PR allows the `VacantEntry` to borrow from an empty tree with no root, and to lazily allocate a new root node when the user calls `.insert(value)`.
2022-03-15fix typosDylan DPC-1/+1
2022-03-11Auto merge of #94472 - JmPotato:use_maybeuninit_for_vecdeque, r=m-ou-sebors-30/+95
Use MaybeUninit in VecDeque to remove the undefined behavior of slice Signed-off-by: JmPotato <ghzpotato@gmail.com> Ref https://github.com/rust-lang/rust/issues/74189. Adjust the code to follow the [doc.rust-lang.org/reference/behavior-considered-undefined.html](https://doc.rust-lang.org/reference/behavior-considered-undefined.html). * Change the return type of `buffer_as_slice` from `&[T]` to `&[MaybeUninit<T>]`. * Add some corresponding safety comments. Benchmark results: master 8d6f527530f4ba974d922269267fe89050188789 ```rust test collections::vec_deque::tests::bench_pop_back_100 ... bench: 47 ns/iter (+/- 1) test collections::vec_deque::tests::bench_pop_front_100 ... bench: 50 ns/iter (+/- 4) test collections::vec_deque::tests::bench_push_back_100 ... bench: 69 ns/iter (+/- 10) test collections::vec_deque::tests::bench_push_front_100 ... bench: 72 ns/iter (+/- 6) test collections::vec_deque::tests::bench_retain_half_10000 ... bench: 145,891 ns/iter (+/- 7,975) test collections::vec_deque::tests::bench_retain_odd_10000 ... bench: 141,647 ns/iter (+/- 3,711) test collections::vec_deque::tests::bench_retain_whole_10000 ... bench: 120,132 ns/iter (+/- 4,078) ``` This PR ```rust test collections::vec_deque::tests::bench_pop_back_100 ... bench: 48 ns/iter (+/- 2) test collections::vec_deque::tests::bench_pop_front_100 ... bench: 51 ns/iter (+/- 3) test collections::vec_deque::tests::bench_push_back_100 ... bench: 73 ns/iter (+/- 2) test collections::vec_deque::tests::bench_push_front_100 ... bench: 73 ns/iter (+/- 2) test collections::vec_deque::tests::bench_retain_half_10000 ... bench: 131,796 ns/iter (+/- 5,440) test collections::vec_deque::tests::bench_retain_odd_10000 ... bench: 137,563 ns/iter (+/- 3,349) test collections::vec_deque::tests::bench_retain_whole_10000 ... bench: 128,815 ns/iter (+/- 3,289) ```
2022-03-11Rollup merge of #94826 - allgoewer:fix-retain-documentation, r=yaahcDylan DPC-5/+5
Improve doc wording for retain on some collections I found the documentation wording on the various retain methods on many collections to be unusual. I tried to invert the relation by switching `such that` with `for which` .
2022-03-11Improve doc wording for retain on some collectionsMaik Allgöwer-5/+5
2022-03-10Use implicit capture syntax in format_argsT-O-R-U-S-17/+17
This updates the standard library's documentation to use the new syntax. The documentation is worthwhile to update as it should be more idiomatic (particularly for features like this, which are nice for users to get acquainted with). The general codebase is likely more hassle than benefit to update: it'll hurt git blame, and generally updates can be done by folks updating the code if (and when) that makes things more readable with the new format. A few places in the compiler and library code are updated (mostly just due to already having been done when this commit was first authored).
2022-03-10Use MaybeUninit in VecDeque to remove the undefined behavior of sliceJmPotato-30/+95
Signed-off-by: JmPotato <ghzpotato@gmail.com>
2022-03-09BTreeMap::entry: Avoid allocating if no insertionFrank King-41/+86
2022-03-07BTree: remove dead data needlessly complicating insertStein Somers-40/+19
2022-02-28Rollup merge of #92399 - Veeupup:fix_vec_typo, r=Dylan-DPCMatthias Krüger-2/+2
fix typo in btree/vec doc: Self -> self this pr fixes #92345 the documentation refers to the object the method is called for, not the type, so it should be using the lower case self.
2022-02-20BTree: simplify test codeStein Somers-138/+118
2022-02-19Collections: improve the documentation of drain membersStein Somers-13/+23
2022-02-17Rollup merge of #89869 - kpreid:from-doc, r=yaahcMatthias Krüger-0/+8
Add documentation to more `From::from` implementations. 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. * The new documentation for construction of maps and sets from arrays of keys mentions the handling of duplicates. Future work could be to do this for *all* code paths that convert an iterable to a map or set. * 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.
2022-02-14Describe VecDeque with more consistent namesStein Somers-110/+110
2022-01-18Replace iterator-based construction of collections by `Into<T>`Júnior Bassani-40/+35
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`.
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-07-08 22:07:36 +0000