summary refs log tree commit diff
path: root/library/alloc/src/collections/btree/map.rs
AgeCommit message (Collapse)AuthorLines
2024-03-21document into_iter in top level docs iterator ordering guaranteesultrabear-1/+1
2024-03-21document iteration ordering on into_iter method instead of IntoIterator ↵ultrabear-1/+1
implementation
2024-03-21BTree(Set|Map): Guarantee that `IntoIter` will iterate in sorted by key orderultrabear-1/+2
2024-03-06Add #[inline] to BTreeMap::new constructorUrgau-0/+1
2024-03-01remove hidden use of GlobalAlexander-1/+1
2024-02-23remove repetitive wordscui fliter-6/+6
Signed-off-by: cui fliter <imcusg@gmail.com>
2024-02-22Add `rustc_confusables` annotations to some stdlib APIsEsteban Küber-0/+3
Help with common API confusion, like asking for `push` when the data structure really has `append`. ``` error[E0599]: no method named `size` found for struct `Vec<{integer}>` in the current scope --> $DIR/rustc_confusables_std_cases.rs:17:7 | LL | x.size(); | ^^^^ | help: you might have meant to use `len` | LL | x.len(); | ~~~ help: there is a method with a similar name | LL | x.resize(); | ~~~~~~ ``` #59450
2024-02-15Rollup merge of #120505 - Amanieu:fix-btreemap-cursor-remove, r=m-ou-seGuillaume Gomez-0/+12
Fix BTreeMap's Cursor::remove_{next,prev} These would incorrectly leave `current` as `None` after a failed attempt to remove an element (due to the cursor already being at the start/end).
2024-02-11fix intra-doc linksripytide-12/+12
2024-02-11fix incorrect doctestripytide-2/+2
2024-02-11improve `btree_cursors` functions documentationripytide-87/+130
2024-01-30Fix BTreeMap's Cursor::remove_{next,prev}Amanieu d'Antras-0/+12
These would incorrectly leave `current` as `None` after a failed attempt to remove an element (due to the cursor already being at the start/end).
2023-11-23Add UnorderedKeyErrorAmanieu d'Antras-10/+30
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-335/+414
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-09Make BTreeMap::new_in constSven Bartscher-1/+1
Closes rust-lang/wg-allocators#118
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-28btree/map.rs: remove "Basic usage" textTshepang Mbambo-54/+0
Not useful, for there is just a single example
2023-06-14s/drain_filter/extract_if/ for Vec, Btree{Map,Set} and LinkedListThe 8472-28/+28
2023-06-14remove drain-on-drop behavior from BTree{Set,Map}::DrainFilter and add ↵The 8472-18/+6
#[must_use]
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/+2
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-12/+48
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-12/+48
2023-04-28replace version placeholdersPietro Albini-8/+8
2023-04-14Rollup merge of #110244 - kadiwa4:unnecessary_imports, r=JohnTitorMatthias Krüger-3/+2
Remove some unneeded imports / qualified paths Continuation of #105537.
2023-04-12remove some unneeded importsKaDiWa-3/+2
2023-04-12Fix btree `CursorMut::insert_after` checkmarc0246-1/+1
2023-02-28Support allocators in various Default for IntoIter implsThe 8472-4/+13
Global implements Default so we can use that as bound for all allocators
2023-02-28rewrite iterator `Default` tests as doctestsThe 8472-0/+56
2023-02-28Implement Default for some alloc/core iteratorsThe 8472-0/+56
This way one can `mem::take()` them out of structs or #[derive(Default)] on structs containing them. These changes will be insta-stable.
2023-02-01BTreeMap: Add Cursor and CursorMutAmanieu d'Antras-2/+728
2022-11-20replace unusual grammarTshepang Mbambo-2/+2
2022-11-06Bump version placeholders to releaseMark Rousskov-7/+7
2022-10-15Documentation BTreeMap::append's behavior for already existing keysphilipp-3/+6
2022-10-11Rollup merge of #101727 - est31:stabilize_map_first_last, r=m-ou-seMatthias Krüger-12/+6
Stabilize map_first_last Stabilizes the following functions: ```Rust impl<T> BTreeSet<T> { pub fn first(&self) -> Option<&T> where T: Ord; pub fn last(&self) -> Option<&T> where T: Ord; pub fn pop_first(&mut self) -> Option<T> where T: Ord; pub fn pop_last(&mut self) -> Option<T> where T: Ord; } impl<K, V> BTreeMap<K, V> { pub fn first_key_value(&self) -> Option<(&K, &V)> where K: Ord; pub fn last_key_value(&self) -> Option<(&K, &V)> where K: Ord; pub fn first_entry(&mut self) -> Option<OccupiedEntry<'_, K, V>> where K: Ord; pub fn last_entry(&mut self) -> Option<OccupiedEntry<'_, K, V>> where K: Ord; pub fn pop_first(&mut self) -> Option<(K, V)> where K: Ord; pub fn pop_last(&mut self) -> Option<(K, V)> where K: Ord; } ``` Closes #62924 ~~Blocked on the [FCP](https://github.com/rust-lang/rust/issues/62924#issuecomment-1179489929) finishing.~~ Edit: It finished!
2022-10-01Make `feature(const_btree_len)` implied by `feature(const_btree_new)`Maybe Waffle-2/+10
2022-09-30Stabilize map_first_lastest31-12/+6
2022-09-23Stabilize const `BTree{Map,Set}::new`Nilstrieb-3/+3
Since `len` and `is_empty` are not const stable yet, this also creates a new feature for them since they previously used the same `const_btree_new` feature.
2022-07-18Add `PhantomData` marker for dropck to `BTreeMap`Frank Steffahn-4/+26
closes #99408
2022-06-23Fix BTreeSet's range API panic message, documenttnballo-2/+3
2022-06-18make btree not use &A: Allocator instanceRalf Jung-5/+5
2022-06-17comments explaining why we have and don't have ManuallyDropRalf Jung-0/+3
2022-06-16btree: avoid forcing the allocator to be a referenceRalf Jung-92/+107
2022-06-16Rollup merge of #98125 - KarlWithK:entry_add_modify_doc, r=Dylan-DPCMatthias Krüger-1/+6
Entry and_modify doc This PR modifies the documentation for [HashMap](https://doc.rust-lang.org/std/collections/struct.HashMap.html#) and [BTreeMap](https://doc.rust-lang.org/std/collections/struct.BTreeMap.html#) by introducing examples for `and_modify`. `and_modify` is a function that tends to give more idiomatic rust code when dealing with these data structures -- yet it lacked examples and was hidden away. This PR adds that and addresses #98122. I've made some choices which I tried to explain in my commits. This is my first time contributing to rust, so hopefully, I made the right choices.
2022-06-15change "1" to "c" to pass testKarlWithK-1/+1
Incorrectly wrote "1" twice when writing test.
2022-06-15Add examples using `add_modify` to btreeKarlWithK-1/+6
Updated the btree's documentation to include two references to add_modify. The first is when the `Entry` API is mentioned at the beginning. With the same reasoning as HashMap's documentation, I thought it would best to keep `attack`, but show the `mana` example. The second is with the `entry` function that is used for the `Entry` API. The code example was a perfect use for `add_modify`, which is why it was changed to reflect that.
2022-06-14btreemap-alloc: fix clear implJacob Hughes-15/+6
2022-06-14BTreeMap: Add alloc paramJacob Hughes-130/+256
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-07-14 18:59:50 +0000