about summary refs log tree commit diff
path: root/library/alloc/src/collections/vec_deque
AgeCommit message (Collapse)AuthorLines
2023-03-30Rollup merge of #106985 - jofas:106746-fix, r=ChrisDentonYuki Okushi-10/+10
Enhanced doucmentation of binary search methods for `slice` and `VecDeque` for unsorted instances Fixes #106746. Issue #106746 raises the concern that the binary search methods for slices and deques aren't explicit enough about the fact that they are only applicable to sorted slices/deques. I changed the explanation for these methods. I took the relatively harsh description of the behaviour of binary search on unsorted collections ("unspecified and meaningless") from the description of the [`partition_point`](https://doc.rust-lang.org/std/primitive.slice.html#method.partition_point) method: > If this slice is not partitioned, the returned result is unspecified and meaningless, as this method performs a kind of binary search.
2023-03-30removed deprecated markdown links from documentationjofas-3/+0
2023-03-29enhanced documentation of binary search methods for slice and VecDeque for ↵jofas-7/+10
unsorted instances
2023-03-27fix advance_by impl for vec_deque and add testsThe 8472-7/+7
2023-03-27replace advance_by returning usize with Result<(), NonZeroUsize>The 8472-29/+39
2023-03-27Change advance(_back)_by to return `usize` instead of `Result<(), usize>`The 8472-32/+30
A successful advance is now signalled by returning `0` and other values now represent the remaining number of steps that couldn't be advanced as opposed to the amount of steps that have been advanced during a partial advance_by. This simplifies adapters a bit, replacing some `match`/`if` with arithmetic. Whether this is beneficial overall depends on whether `advance_by` is mostly used as a building-block for other iterator methods and adapters or whether we also see uses by users where `Result` might be more useful.
2023-03-11Rollup merge of #106276 - Sp00ph:unify_slice_ranges, r=the8472Matthias Krüger-36/+31
Fix `vec_deque::Drain` FIXME In my original `VecDeque` rewrite, I didn't use `VecDeque::slice_ranges` in `Drain::as_slices`, even though that's basically the exact use case for `slice_ranges`. The reason for this was that a `VecDeque` wrapped in a `Drain` actually has its length set to `drain_start`, so that there's no potential use after free if you `mem::forget` the `Drain`. I modified `slice_ranges` to accept an explicit `len` parameter instead, which it now uses to bounds check the given range. This way, `Drain::as_slices` can use `slice_ranges` internally instead of having to basically just copy paste the `slice_ranges` code. Since `slice_ranges` is just an internal helper function, this shouldn't change the user facing behavior in any way.
2023-03-01Rollup merge of #108462 - pommicket:fix-vecdeque-zst-overflow, r=AmanieuDylan DPC-1/+1
Fix `VecDeque::append` capacity overflow for ZSTs Fixes #108454.
2023-02-26Disambiguate commentsMarkus Everling-2/+2
2023-02-26Fix `VecDeque::shrink_to` and add tests.Markus Everling-55/+104
This adds both a test specific to #108453 as well as an exhaustive test that goes through all possible combinations of head index, length and target capacity for a deque with capacity 16.
2023-02-25Use checked_add in VecDeque::append for ZSTs to avoid overflowpommicket-1/+1
2023-02-20Changes according to reviewMarkus Everling-11/+11
2023-02-18Auto merge of #106241 - Sp00ph:vec_deque_iter_methods, r=the8472bors-1/+184
Implement more methods for `vec_deque::IntoIter` This implements a couple `Iterator` methods on `vec_deque::IntoIter` (`(try_)fold`, `(try_)rfold` `advance_(back_)by`, `next_chunk`, `count` and `last`) to allow these to be more efficient than their default implementations, also allowing many other `Iterator` methods that use these under the hood to take advantage of these manual implementations. `vec::IntoIter` has similar implementations for many of these methods. This PR does not yet implement `TrustedRandomAccess` and friends, as I'm not very familiar with the required safety guarantees. r? `@the8472` (since you also took over my last PR)
2023-02-05Add `slice_ranges` safety commentMarkus Everling-5/+12
2023-01-31Fix `vec_deque::Drain` FIXMEMarkus Everling-31/+19
2023-01-25Set version placeholders to 1.68Mark Rousskov-1/+1
2023-01-08Rollup merge of #106562 - clubby789:vec-deque-example, r=Mark-SimulacrumYuki Okushi-1/+3
Clarify examples for `VecDeque::get/get_mut` Closes #106114 ``@rustbot`` label +A-docs
2023-01-07Rollup merge of #105128 - Sp00ph:vec_vec_deque_conversion, r=dtolnayMatthias Krüger-3/+3
Add O(1) `Vec -> VecDeque` conversion guarantee (See #105072)
2023-01-07Clarify examples for `VecDeque::get/get_mut`clubby789-1/+3
2022-12-29Implement more methods for `vec_deque::IntoIter`Markus Everling-1/+184
2022-12-20Auto merge of #105127 - Sp00ph:const_new, r=dtolnaybors-3/+4
Make `VecDeque::new` const (See #105072)
2022-12-15doc: Fix a few small issuesHannes Körber-1/+1
* A few typos around generic types (`;` vs `,`) * Use inline code formatting for code fragments * One instance of wrong wording
2022-12-08Apply review feedback; Fix no_global_oom_handling buildScott McMurray-0/+3
2022-12-08Make `VecDeque::from_iter` O(1) from `vec(_deque)::IntoIter`Scott McMurray-11/+71
2022-12-05Add O(1) `Vec -> VecDeque` conversion guaranteeMarkus Everling-3/+3
2022-12-05Auto merge of #105046 - scottmcm:vecdeque-vs-vec, r=Mark-Simulacrumbors-5/+12
Send `VecDeque::from_iter` via `Vec::from_iter` Since it's O(1) to convert between them now, might as well reuse the logic. Mostly for the various specializations it does, but might also save some monomorphization work if, say, people collect slice iterators into both `Vec`s and `VecDeque`s.
2022-12-01Fix typo in commentMarkus Everling-1/+1
2022-12-01Make `VecDeque::new` constMarkus Everling-3/+4
2022-12-01Make `VecDeque::new_in` unstably constMarkus Everling-2/+1
2022-11-29Send `VecDeque::from_iter` via `Vec::from_iter`Scott McMurray-5/+12
Since it's O(1) to convert between them now, might as well reuse the logic. Mostly for the various specializations it does, but might also save some monomorphization work if, say, people collect slice iterators into both `Vec`s and `VecDeque`s.
2022-11-26Add second test case in `make_contiguous_head_to_end`Markus Everling-10/+49
2022-11-26Improve slow path in `make_contiguous`Markus Everling-36/+76
2022-11-26Don't use `Take` in `SpecExtend` implMarkus Everling-21/+23
2022-11-25Changes according to code reviewMarkus Everling-144/+181
2022-11-20Update VecDeque implementationMarkus Everling-1230/+760
2022-11-15`VecDeque::resize` should re-use the buffer in the passed-in elementScott McMurray-2/+7
Today it always copies it for *every* appended element, but one of those clones is avoidable.
2022-11-07fmtRalf Jung-5/+5
2022-11-07run alloc benchmarks in Miri and fix UBRalf Jung-15/+19
2022-09-23Put back one of the `use`s for intra-doc mentionsScott McMurray-0/+6
2022-09-22Make ZST checks in core/alloc more readableScott McMurray-4/+4
There's a bunch of these checks because of special handing for ZSTs in various unsafe implementations of stuff. This lets them be `T::IS_ZST` instead of `mem::size_of::<T>() == 0` every time, making them both more readable and more terse. *Not* proposed for stabilization at this time. Would be `pub(crate)` except `alloc` wants to use it too. (And while it doesn't matter now, if we ever get something like 85836 making it a const can help codegen be simpler.)
2022-09-10Alternate approach; just modify DrainBen Kimock-52/+59
2022-09-10Remove &[T] from vec_deque::DrainBen Kimock-23/+41
2022-08-22Rollup merge of #100331 - lo48576:try-reserve-preserve-on-failure, r=thomccDylan DPC-1/+2
Guarantee `try_reserve` preserves the contents on error Update doc comments to make the guarantee explicit. However, some implementations does not have the statement though. * `HashMap`, `HashSet`: require guarantees on hashbrown side. * `PathBuf`: simply redirecting to `OsString`. Fixes #99606.
2022-08-21Replace most uses of `pointer::offset` with `add` and `sub`Maybe Waffle-2/+2
2022-08-10Guarantee `try_reserve` preserves the contents on errorYOSHIOKA Takuma-1/+2
Update doc comments to make the guarantee explicit. However, some implementations does not have the statement though. * `HashMap`, `HashSet`: require guarantees on hashbrown side. * `PathBuf`: simply redirecting to `OsString`. Fixes #99606.
2022-06-19Fix documentation for with_capacity and reserve families of methodsjmaargh-8/+8
Documentation for the following methods with_capacity with_capacity_in with_capacity_and_hasher reserve reserve_exact try_reserve try_reserve_exact was inconsistent and often not entirely correct where they existed on the following types Vec VecDeque String OsString PathBuf BinaryHeap HashSet HashMap BufWriter LineWriter since the allocator is allowed to allocate more than the requested capacity in all such cases, and will frequently "allocate" much more in the case of zero-sized types (I also checked BufReader, but there the docs appear to be accurate as it appears to actually allocate the exact capacity). Some effort was made to make the documentation more consistent between types as well. Fix with_capacity* methods for Vec Fix *reserve* methods for Vec Fix docs for *reserve* methods of VecDeque Fix docs for String::with_capacity Fix docs for *reserve* methods of String Fix docs for OsString::with_capacity Fix docs for *reserve* methods on OsString Fix docs for with_capacity* methods on HashSet Fix docs for *reserve methods of HashSet Fix docs for with_capacity* methods of HashMap Fix docs for *reserve methods on HashMap Fix expect messages about OOM in doctests Fix docs for BinaryHeap::with_capacity Fix docs for *reserve* methods of BinaryHeap Fix typos Fix docs for with_capacity on BufWriter and LineWriter Fix consistent use of `hasher` between `HashMap` and `HashSet` Fix warning in doc test Add test for capacity of vec with ZST Fix doc test error
2022-06-18Expose iter::ByRefSized as unstable feature and use itPaolo Barbolini-1/+1
2022-06-18Add VecDeque::extend from TrustedLen specializationPaolo Barbolini-0/+175
2022-05-30Rollup merge of #89685 - DeveloperC286:iter_fields_to_private, r=oli-obkMichael Goulet-16/+17
refactor: VecDeques Iter fields to private Made the fields of VecDeque's Iter private by creating a Iter::new(...) function to create a new instance of Iter and migrating usage to use Iter::new(...).
2022-05-08Warn on unused doc(hidden) on trait impl itemsLeón Orell Valerian Liehr-2/+0
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-02-26 16:40:26 +0000