summary refs log tree commit diff
path: root/library/alloc/src/collections/vec_deque
AgeCommit message (Collapse)AuthorLines
2022-05-08Warn on unused doc(hidden) on trait impl itemsLeón Orell Valerian Liehr-2/+0
2022-05-06Add a dedicated length-prefixing method to `Hasher`Scott McMurray-1/+1
This accomplishes two main goals: - Make it clear who is responsible for prefix-freedom, including how they should do it - Make it feasible for a `Hasher` that *doesn't* care about Hash-DoS resistance to get better performance by not hashing lengths This does not change rustc-hash, since that's in an external crate, but that could potentially use it in future.
2022-04-28Add VecDeque::extend from vec::IntoIter and slice::Iter specializationsPaolo Barbolini-19/+79
2022-04-26Rollup merge of #90312 - r00ster91:search, r=Dylan-DPCDylan DPC-3/+15
Fix some confusing wording and improve slice-search-related docs This adds more links between `contains` and `binary_search` because I do think they have some relevant connections. If your (big) slice happens to be sorted and you know it, surely you should be using `[3; 100].binary_search(&5).is_ok()` over `[3; 100].contains(&5)`? This also fixes the confusing "searches this sorted X" wording which just sounds really weird because it doesn't know whether it's actually sorted. It should be but it may not be. The new wording should make it clearer that you will probably want to sort it and in the same sentence it also mentions the related function `contains`. Similarly, this mentions `binary_search` on `contains`' docs. This also fixes some other minor stuff and inconsistencies.
2022-04-24test: add test cases for VecDequeKeita Nonaka-0/+294
2022-04-06add necessary closure for partition_pointJane Lusby-2/+2
2022-04-06Update binary_search example to instead redirect to partition_pointJane Lusby-2/+16
2022-03-30Stabilize feature vec_retain_mut on Vec and VecDequeLinus Färnstrand-3/+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-11Improve doc wording for retain on some collectionsMaik Allgöwer-2/+2
2022-03-10Use MaybeUninit in VecDeque to remove the undefined behavior of sliceJmPotato-30/+95
Signed-off-by: JmPotato <ghzpotato@gmail.com>
2022-02-19Fix some confusing wording and improve slice-search-related docsr00ster91-3/+15
2022-02-19Collections: improve the documentation of drain membersStein Somers-8/+12
2022-02-17Rollup merge of #89869 - kpreid:from-doc, r=yaahcMatthias Krüger-0/+2
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-15/+15
2022-01-09eplace usages of vec![].into_iter with [].into_iterLucas Kent-8/+8
2021-12-12doc: fix typo in commentsjapm48-6/+6
dereferencable -> dereferenceable
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-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-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-10-18Avoid overflow in `VecDeque::with_capacity_in()`.Hans Kratz-1/+1
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-10Add #[must_use] to alloc constructorsJohn Kugelman-0/+2
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-4/+2
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 #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-4/+2
2021-10-04Update outdated commentXinye Tao-1/+1
2021-10-02Make diangostic item names consistentCameron Steffen-1/+1
2021-09-26Auto merge of #89144 - sexxi-goose:insig_stdlib, r=nikomatsakisbors-0/+1
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 #89010 - est31:intra_doc_links, r=m-ou-seManish Goregaokar-1/+2
Add some intra doc links
2021-09-25refactor: VecDeques PairSlices fields to privateDeveloperC-4/+4
2021-09-22PR fixupAman Arora-1/+1
2021-09-212229: Annotate stdlib with insignficant dtorsAman Arora-0/+1
2021-09-17refactor: VecDeques IntoIter fields to privateDeveloperC286-2/+8
2021-09-16Add IntoIterator intra doc link to various collectionsest31-1/+2
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-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-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-08Auto merge of #86879 - YohDeadfall:stabilize-vec-shrink-to, r=dtolnaybors-2/+1
Stabilize Vec<T>::shrink_to This PR stabilizes `shrink_to` feature and closes the corresponding issue. The second point was addressed already, and no `panic!` should occur. Closes #56431.
2021-08-08Bump shrink_to stabilization to Rust 1.56David Tolnay-1/+1
2021-08-07Auto merge of #87408 - kornelski:try_reserve_error, r=yaahcbors-1/+2
Hide allocator details from TryReserveError I think there's [no need for TryReserveError to carry detailed information](https://github.com/rust-lang/rust/issues/48043#issuecomment-825139280), but I wouldn't want that issue to delay stabilization of the `try_reserve` feature. So I'm proposing to stabilize `try_reserve` with a `TryReserveError` as an opaque structure, and if needed, expose error details later. This PR moves the `enum` to an unstable inner `TryReserveErrorKind` that lives under a separate feature flag. `TryReserveErrorKind` could possibly be left as an implementation detail forever, and the `TryReserveError` get methods such as `allocation_size() -> Option<usize>` or `layout() -> Option<Layout>` instead, or the details could be dropped completely to make try-reserve errors just a unit struct, and thus smaller and cheaper.
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-03-02 19:39:03 +0000