summary refs log tree commit diff
path: root/library/alloc/src/collections
AgeCommit message (Collapse)AuthorLines
2024-01-25Rollup merge of #118208 - Amanieu:btree_cursor2, r=dtolnayMatthias Krüger-392/+549
Rewrite the BTreeMap cursor API using gaps Tracking issue: #107540 Currently, a `Cursor` points to a single element in the tree, and allows moving to the next or previous element while mutating the tree. However this was found to be confusing and hard to use. This PR completely refactors cursors to instead point to a gap between two elements in the tree. This eliminates the need for a "ghost" element that exists after the last element and before the first one. Additionally, `upper_bound` and `lower_bound` now have a much clearer meaning. The ability to mutate keys is also factored out into a separate `CursorMutKey` type which is unsafe to create. This makes the API easier to use since it avoids duplicated versions of each method with and without key mutation. API summary: ```rust impl<K, V> BTreeMap<K, V> { fn lower_bound<Q>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V> where K: Borrow<Q> + Ord, Q: Ord; fn lower_bound_mut<Q>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V> where K: Borrow<Q> + Ord, Q: Ord; fn upper_bound<Q>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V> where K: Borrow<Q> + Ord, Q: Ord; fn upper_bound_mut<Q>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V> where K: Borrow<Q> + Ord, Q: Ord; } struct Cursor<'a, K: 'a, V: 'a>; impl<'a, K, V> Cursor<'a, K, V> { fn next(&mut self) -> Option<(&'a K, &'a V)>; fn prev(&mut self) -> Option<(&'a K, &'a V)>; fn peek_next(&self) -> Option<(&'a K, &'a V)>; fn peek_prev(&self) -> Option<(&'a K, &'a V)>; } struct CursorMut<'a, K: 'a, V: 'a>; impl<'a, K, V> CursorMut<'a, K, V> { fn next(&mut self) -> Option<(&K, &mut V)>; fn prev(&mut self) -> Option<(&K, &mut V)>; fn peek_next(&mut self) -> Option<(&K, &mut V)>; fn peek_prev(&mut self) -> Option<(&K, &mut V)>; unsafe fn insert_after_unchecked(&mut self, key: K, value: V); unsafe fn insert_before_unchecked(&mut self, key: K, value: V); fn insert_after(&mut self, key: K, value: V) -> Result<(), UnorderedKeyError>; fn insert_before(&mut self, key: K, value: V) -> Result<(), UnorderedKeyError>; fn remove_next(&mut self) -> Option<(K, V)>; fn remove_prev(&mut self) -> Option<(K, V)>; fn as_cursor(&self) -> Cursor<'_, K, V>; unsafe fn with_mutable_key(self) -> CursorMutKey<'a, K, V, A>; } struct CursorMutKey<'a, K: 'a, V: 'a>; impl<'a, K, V> CursorMut<'a, K, V> { fn next(&mut self) -> Option<(&mut K, &mut V)>; fn prev(&mut self) -> Option<(&mut K, &mut V)>; fn peek_next(&mut self) -> Option<(&mut K, &mut V)>; fn peek_prev(&mut self) -> Option<(&mut K, &mut V)>; unsafe fn insert_after_unchecked(&mut self, key: K, value: V); unsafe fn insert_before_unchecked(&mut self, key: K, value: V); fn insert_after(&mut self, key: K, value: V) -> Result<(), UnorderedKeyError>; fn insert_before(&mut self, key: K, value: V) -> Result<(), UnorderedKeyError>; fn remove_next(&mut self) -> Option<(K, V)>; fn remove_prev(&mut self) -> Option<(K, V)>; fn as_cursor(&self) -> Cursor<'_, K, V>; unsafe fn with_mutable_key(self) -> CursorMutKey<'a, K, V, A>; } struct UnorderedKeyError; ```
2024-01-02Adjust library tests for unused_tuple_struct_fields -> dead_codeJake Goulding-2/+2
2023-12-21fix minor mistake in comments describing VecDeque resizingKent Ross-4/+4
2023-12-10remove redundant importssurechen-11/+1
detects redundant imports that can be eliminated. for #117772 : In order to facilitate review and modification, split the checking code and removing redundant imports code into two PR.
2023-12-09Auto merge of #114136 - TennyZhuang:linked-list-retain, r=thomccbors-0/+93
add LinkedList::{retain,retain_mut} Implement #114135 The API is consistent with other collections.
2023-11-29Rollup merge of #118398 - mu001999:std/add_cfgs, r=thomccMatthias Krüger-0/+1
Add proper cfgs in std Detected by #118257
2023-11-28Auto merge of #110353 - the8472:in-place-flatten-chunks, r=cuviperbors-2/+9
Expand in-place iteration specialization to Flatten, FlatMap and ArrayChunks This enables the following cases to collect in-place: ```rust let v = vec![[0u8; 4]; 1024] let v: Vec<_> = v.into_iter().flatten().collect(); let v: Vec<Option<NonZeroUsize>> = vec![NonZeroUsize::new(0); 1024]; let v: Vec<_> = v.into_iter().flatten().collect(); let v = vec![u8; 4096]; let v: Vec<_> = v.into_iter().array_chunks::<4>().collect(); ``` Especially the nicheful-option-flattening should be useful in real code.
2023-11-28Add proper cfgsr0cky-0/+1
2023-11-23Add UnorderedKeyErrorAmanieu d'Antras-31/+43
2023-11-23Update library/alloc/src/collections/btree/map.rsAmanieu d'Antras-1/+1
Co-authored-by: Joe ST <joe@fbstj.net>
2023-11-23Rewrite the BTreeMap cursor API using gapsAmanieu d'Antras-374/+519
Tracking issue: #107540 Currently, a `Cursor` points to a single element in the tree, and allows moving to the next or previous element while mutating the tree. However this was found to be confusing and hard to use. This PR completely refactors cursors to instead point to a gap between two elements in the tree. This eliminates the need for a "ghost" element that exists after the last element and before the first one. Additionally, `upper_bound` and `lower_bound` now have a much clearer meaning. The ability to mutate keys is also factored out into a separate `CursorMutKey` type which is unsafe to create. This makes the API easier to use since it avoids duplicated versions of each method with and without key mutation. API summary: ```rust impl<K, V> BTreeMap<K, V> { fn lower_bound<Q>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V> where K: Borrow<Q> + Ord, Q: Ord; fn lower_bound_mut<Q>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V> where K: Borrow<Q> + Ord, Q: Ord; fn upper_bound<Q>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V> where K: Borrow<Q> + Ord, Q: Ord; fn upper_bound_mut<Q>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V> where K: Borrow<Q> + Ord, Q: Ord; } struct Cursor<'a, K: 'a, V: 'a>; impl<'a, K, V> Cursor<'a, K, V> { fn next(&mut self) -> Option<(&'a K, &'a V)>; fn prev(&mut self) -> Option<(&'a K, &'a V)>; fn peek_next(&self) -> Option<(&'a K, &'a V)>; fn peek_prev(&self) -> Option<(&'a K, &'a V)>; } struct CursorMut<'a, K: 'a, V: 'a>; impl<'a, K, V> CursorMut<'a, K, V> { fn next(&mut self) -> Option<(&K, &mut V)>; fn prev(&mut self) -> Option<(&K, &mut V)>; fn peek_next(&mut self) -> Option<(&K, &mut V)>; fn peek_prev(&mut self) -> Option<(&K, &mut V)>; unsafe fn insert_after_unchecked(&mut self, key: K, value: V); unsafe fn insert_before_unchecked(&mut self, key: K, value: V); fn insert_after(&mut self, key: K, value: V); fn insert_before(&mut self, key: K, value: V); fn remove_next(&mut self) -> Option<(K, V)>; fn remove_prev(&mut self) -> Option<(K, V)>; fn as_cursor(&self) -> Cursor<'_, K, V>; unsafe fn with_mutable_key(self) -> CursorMutKey<'a, K, V, A>; } struct CursorMutKey<'a, K: 'a, V: 'a>; impl<'a, K, V> CursorMut<'a, K, V> { fn next(&mut self) -> Option<(&mut K, &mut V)>; fn prev(&mut self) -> Option<(&mut K, &mut V)>; fn peek_next(&mut self) -> Option<(&mut K, &mut V)>; fn peek_prev(&mut self) -> Option<(&mut K, &mut V)>; unsafe fn insert_after_unchecked(&mut self, key: K, value: V); unsafe fn insert_before_unchecked(&mut self, key: K, value: V); fn insert_after(&mut self, key: K, value: V); fn insert_before(&mut self, key: K, value: V); fn remove_next(&mut self) -> Option<(K, V)>; fn remove_prev(&mut self) -> Option<(K, V)>; fn as_cursor(&self) -> Cursor<'_, K, V>; unsafe fn with_mutable_key(self) -> CursorMutKey<'a, K, V, A>; } ```
2023-10-28mark constructor of `BinaryHeap` as const fncoekjan-2/+4
2023-10-09Make BTreeSet::new_in constSven Bartscher-1/+1
2023-10-09Make BTreeMap::new_in constSven Bartscher-1/+1
Closes rust-lang/wg-allocators#118
2023-10-04Fix misuses of a vs ancui fliter-1/+1
Signed-off-by: cui fliter <imcusg@gmail.com>
2023-09-16edit `std::collections::VecDeque` docsmxnkarou-2/+2
2023-09-03Expand in-place iteration specialization to Flatten, FlatMap and ArrayChunksThe 8472-2/+9
2023-07-30Avoid using ptr::Unique in LinkedList codeRyan Lowe-11/+13
2023-07-30Auto merge of #114236 - fee1-dead-contrib:rollup-m92j7q1, r=fee1-deadbors-0/+8
Rollup of 3 pull requests Successful merges: - #112151 (Clarify behavior of inclusive bounds in BTreeMap::{lower,upper}_bound) - #113512 (Updated lines doc to include trailing carriage return note) - #114203 (Effects: don't print `host` param in diagnostics) r? `@ghost` `@rustbot` modify labels: rollup
2023-07-30Rollup merge of #112151 - chloekek:patch-1, r=workingjubileefee1-dead-0/+8
Clarify behavior of inclusive bounds in BTreeMap::{lower,upper}_bound It wasn’t quite clear to me how these methods would interpret inclusive bounds so I added examples for those.
2023-07-30Auto merge of #112280 - zica87:master, r=workingjubileebors-13/+0
Remove redundant example of `BTreeSet::iter` The usage and that `Values returned by the iterator are returned in ascending order` are already demonstrated by the other example and the description, so I removed the useless one.
2023-07-28btree/map.rs: remove "Basic usage" textTshepang Mbambo-54/+0
Not useful, for there is just a single example
2023-07-28add LinkedList::{retain,retain_mut}TennyZhuang-0/+93
Signed-off-by: TennyZhuang <zty0826@gmail.com>
2023-07-13Fix VecDeque's rotate_left and rotate_right panic testsPedro Lobo-2/+2
2023-07-13Rename VecDeque's rotate_left and rotate_right parametersPedro Lobo-23/+23
2023-06-14s/drain_filter/extract_if/ for Vec, Btree{Map,Set} and LinkedListThe 8472-129/+124
2023-06-14remove drain-on-drop behavior from linked_list::DrainFilter and add #[must_use]The 8472-30/+14
2023-06-14remove drain-on-drop behavior from BTree{Set,Map}::DrainFilter and add ↵The 8472-58/+40
#[must_use]
2023-06-13Auto merge of #112314 - ferrocene:pa-core-alloc-abort, r=bjorn3bors-0/+17
Ignore `core`, `alloc` and `test` tests that require unwinding on `-C panic=abort` Some of the tests for `core` and `alloc` require unwinding through their use of `catch_unwind`. These tests fail when testing using `-C panic=abort` (in my case through a target without unwinding support, and `-Z panic-abort-tests`), while they should be ignored as they don't indicate a failure. This PR marks all of these tests with this attribute: ```rust #[cfg_attr(not(panic = "unwind"), ignore = "test requires unwinding support")] ``` I'm not aware of a way to test this on rust-lang/rust's CI, as we don't test any target with `-C panic=abort`, but I tested this locally on a Ferrocene target and it does indeed make the test suite pass.
2023-06-13ignore core, alloc and test tests that require unwinding on panic=abortPietro Albini-0/+17
2023-06-11Impl allocator function for iteratorsyanchith-0/+32
2023-06-11Remove explicit lifetimesyanchith-20/+20
2023-06-09Don't explicitly name Globalyanchith-1/+1
2023-06-09Pass tidy againyanchith-5/+1
2023-06-09Add allocator functionyanchith-0/+7
2023-06-09Reallocatorize after mergeyanchith-12/+16
2023-06-09Merge branch 'master' into binary-heap-tayanchith-1941/+3225
2023-06-04Remove redundant example of `BTreeSet::iter`zica-13/+0
2023-05-31Clarify behavior of inclusive bounds in BTreeMap::{lower,upper}_boundchloekek-0/+8
2023-05-15Fixed typoBenjamin Atelsek-1/+1
2023-05-04btree_map: `Cursor{,Mut}::peek_prev` must agreeJubilee Young-2/+21
Our `Cursor::peek_prev` and `CursorMut::peek_prev` must agree on how to behave when they are called on the "null element".
2023-04-29Rollup merge of #110958 - compiler-errors:stdlib-refinement, r=cuviperDylan DPC-17/+65
Make sure that some stdlib method signatures aren't accidental refinements In the process of implementing https://rust-lang.github.io/rfcs/3245-refined-impls.html, I found a bunch of stdlib implementations that accidentally "refined" their method signatures by dropping (unnecessary) bounds. This isn't currently a problem, but may become one if/when method signature refining is stabilized in the future. Shouldn't hurt to make these signatures a bit more accurate anyways. NOTE (just to be clear lol): This does not affect behavior at all, since we don't actually take advantage of refined implementations yet!
2023-04-28Make sure that signatures aren't accidental refinementsMichael Goulet-17/+65
2023-04-28replace version placeholdersPietro Albini-16/+16
2023-04-26Rollup merge of #110419 - jsoref:spelling-library, r=jyn514Matthias Krüger-1/+1
Spelling library Split per https://github.com/rust-lang/rust/pull/110392 I can squash once people are happy w/ the changes. It's really uncommon for large sets of changes to be perfectly acceptable w/o at least some changes. I probably won't have time to respond until tomorrow or the next day
2023-04-26Spelling library/Josh Soref-1/+1
* advance * aligned * borrowed * calculate * debugable * debuggable * declarations * desugaring * documentation * enclave * ignorable * initialized * iterator * kaboom * monomorphization * nonexistent * optimizer * panicking * process * reentrant * rustonomicon * the * uninitialized Signed-off-by: Josh Soref <2119212+jsoref@users.noreply.github.com>
2023-04-25Auto merge of #103093 - rytheo:linked-list-alloc-api, r=Mark-Simulacrumbors-135/+224
Add support for allocators in `LinkedList` Allows `LinkedList` to use a custom allocator
2023-04-24Add support for allocators in LinkedListRyan Lowe-135/+224
2023-04-14Rollup merge of #110244 - kadiwa4:unnecessary_imports, r=JohnTitorMatthias Krüger-16/+7
Remove some unneeded imports / qualified paths Continuation of #105537.
2023-04-12remove some unneeded importsKaDiWa-16/+7
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-02-28 21:25:20 +0000