Tracking issue for map_first_last: first/last methods on BTreeSet and BTreeMap #62924

nexplor · 2019-07-24T02:57:31Z

Feature gate: #![feature(map_first_last)]

Public API

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;
}

Steps / History

Implementation: proposal for BTreeMap/Set min/max, #62924 #65637
Changes: BTreeMap first last proposal tweaks #70850
Final commenting period (FCP)
Stabilization PR

Unresolved Questions

Naming (min/max, first/last, front/back, .. ?)
For BTreeMap: Separate entry and pair (and just-value) functions?

Original issue title: Finding minimum/maximum element in BTreeMap does twice the required amount of computation

Original issue text:

The standard way of finding the minimum element in BTreeMap is tree_map.iter().next()

The iter() function creates a btree_map::Iter, which finds both the minimum and maximum element to create its internal instance of btree_map::Range.

This is unnecessary, and a BTreeMap::get_min or similar function could be provided, which would just internally call the first_leaf_edge private function, without needing to call last_leaf_edge.

Ditto for finding the maximum element.

The text was updated successfully, but these errors were encountered:

cuviper · 2019-07-24T18:26:15Z

Here are what the other collections call similar methods:

[T] slices (and Vec via deref) have first/first_mut and last/last_mut.
VecDeque and LinkedList have front/front_mut and back/back_mut.
BinaryHeap has peek and peek_mut, i.e. only from the front.
HashMap and HashSet are unordered, and have no such methods.
str and String have no such methods.

cuviper · 2019-07-24T18:28:39Z

#59947 is related -- Iterator::min/max are even worse since they naively walk everything.

ssomers · 2019-10-19T13:48:40Z

#64820 is also related - BTreeSet is_subset, intersection and difference now always do this double work (they actually want both min and max at the same time, but requesting both next and next_back from the same iterator that may only see one element is not the most straightforward code).

I naively thought the redundant data (the other end and iterator length) and code would all get optimized away from an expression like tree_map.iter().next(), but after writing out code to avoid the double work in BTreeSet::is_subset, benchmarks report a 20 to 40% speed boost, for the cases where it can quickly bail out after getting min and max either side and comparing them. I'm going to measure the effect by adding the desired functions to map, and if successful I can put them in a pull request, but I have no idea what the procedure is for adding APIs. I vote for first and last as names.

ssomers · 2019-10-20T15:45:26Z

According to a raw benchmark, the specialized functions are about 3 times faster than .iter().next(). By the way, .range(..).next() is a little slower for small sets, despite not bothering with iterator length, presumably because iter() has access to internals to construct its unbounded range.

Details: benchmark code in liballoc/benches/btree/map.rs:

fn bench_first_and_last(b: &mut Bencher, size: i32) {
    let map: BTreeMap<_, _> = (0..size).map(|i| (i, i)).collect();
    b.iter(|| {
        for _ in 0..10 {
            black_box(map.first_key_value());
            black_box(map.last_key_value());
        }
    });
}

#[bench]
pub fn first_and_last_0(b: &mut Bencher) {
    bench_first_and_last(b, 0);
}

#[bench]
pub fn first_and_last_100(b: &mut Bencher) {
    bench_first_and_last(b, 100);
}

#[bench]
pub fn first_and_last_10k(b: &mut Bencher) {
    bench_first_and_last(b, 10_000);
}

Results using the new functions:

test btree::map::first_and_last_0                        ... bench:          14 ns/iter (+/- 0)
test btree::map::first_and_last_100                      ... bench:          37 ns/iter (+/- 2)
test btree::map::first_and_last_10k                      ... bench:          54 ns/iter (+/- 3)

test btree::map::first_and_last_0                        ... bench:          14 ns/iter (+/- 0)
test btree::map::first_and_last_100                      ... bench:          42 ns/iter (+/- 1)
test btree::map::first_and_last_10k                      ... bench:          56 ns/iter (+/- 2)

test btree::map::first_and_last_0                        ... bench:          14 ns/iter (+/- 0)
test btree::map::first_and_last_100                      ... bench:          37 ns/iter (+/- 1)
test btree::map::first_and_last_10k                      ... bench:          54 ns/iter (+/- 2)

test btree::map::first_and_last_0                        ... bench:          14 ns/iter (+/- 0)
test btree::map::first_and_last_100                      ... bench:          37 ns/iter (+/- 0)
test btree::map::first_and_last_10k                      ... bench:          55 ns/iter (+/- 1)

Results using .iter().next() / .iter().next_back():

test btree::map::first_and_last_0                        ... bench:          65 ns/iter (+/- 1)
test btree::map::first_and_last_100                      ... bench:          97 ns/iter (+/- 3)
test btree::map::first_and_last_10k                      ... bench:         141 ns/iter (+/- 0)

test btree::map::first_and_last_0                        ... bench:          64 ns/iter (+/- 1)
test btree::map::first_and_last_100                      ... bench:          97 ns/iter (+/- 3)
test btree::map::first_and_last_10k                      ... bench:         131 ns/iter (+/- 4)

test btree::map::first_and_last_0                        ... bench:          65 ns/iter (+/- 2)
test btree::map::first_and_last_100                      ... bench:          96 ns/iter (+/- 3)
test btree::map::first_and_last_10k                      ... bench:         131 ns/iter (+/- 7)

test btree::map::first_and_last_0                        ... bench:          65 ns/iter (+/- 2)
test btree::map::first_and_last_100                      ... bench:          99 ns/iter (+/- 2)
test btree::map::first_and_last_10k                      ... bench:         131 ns/iter (+/- 15)

Results using .range(..).next() / .range(..).next_back():

test btree::map::first_and_last_0                        ... bench:          66 ns/iter (+/- 3)
test btree::map::first_and_last_100                      ... bench:         100 ns/iter (+/- 1)
test btree::map::first_and_last_10k                      ... bench:         123 ns/iter (+/- 2)

test btree::map::first_and_last_0                        ... bench:          67 ns/iter (+/- 5)
test btree::map::first_and_last_100                      ... bench:         100 ns/iter (+/- 4)
test btree::map::first_and_last_10k                      ... bench:         127 ns/iter (+/- 4)

test btree::map::first_and_last_0                        ... bench:          66 ns/iter (+/- 1)
test btree::map::first_and_last_100                      ... bench:         101 ns/iter (+/- 6)
test btree::map::first_and_last_10k                      ... bench:         123 ns/iter (+/- 5)

proposal for BTreeMap/Set min/max, #62924 - Which pair of names: #62924 lists the existing possibilities min/max, first/last, (EDIT) front/back, peek(/peek_back?). Iterators have next/next_back or next/last. I'm slightly in favour of first/last because min/max might suggest they search over the entire map, and front/back pretends they are only about position. - Return key only instead of pair like iterator does? - If not, then keep the _key_value suffix? ~~Also provide variant with mutable value? But there is no such variant for get_key_value.~~ - Look for and upgrade more usages of `.iter().next()` and such in the libraries? I only upgraded the ones I contributed myself, all very recently.

matklad · 2019-12-26T19:41:55Z

I vote for min/max rather than first/last terminology. Rationale: I’ve recently had a bad bug when I used Rust’s BinaryHeap and assumed that pop yields a minimal item. If the API had used max in the method name, I wouldn’t have made the bug.

This case is similar: first is ambiguous, min is precise (and shorter ^^).

ssomers · 2019-12-26T21:24:03Z

I'm slightly in favour of min/max at the moment, having faced reverse iteration in (other) code with first/last names. It's a close call; min/max is ambiguous about performance, because many min/max functions out there are in fact linear searches. PS then again, that argument makes last double ambiguous, because last on an iterator can be sluggish (meticulously consume an iterator) or instant (on a well-behaved implementation of DoubleEndedIterator).

matklad · 2019-12-26T21:44:41Z

Correctness is more important than performance, and the performance ambiguity is an a safe direction (operation is faster than it might seem)

jmlMetaswitch · 2020-03-16T09:18:02Z

Can we also get pop forms that remove the entry at the same time? (I think that's probably better than take or other synonyms, especially as BTreeSet has pop_last.) They are particularly useful in algorithms that repeatedly process the max/min and may add entries during that processing (e.g A*). I think that suggests (from the above) max_key_value, max_entry, pop_max_key_value and the equivalent for min.

ssomers · 2020-03-16T10:35:58Z

I didn't add those back then because I thought they were intended to be used through the entry API. But using that in practice seems more complicated than I would want. There's no entry concept in BTreeSet, so pop_X seemed the only option there.

I wouldn't start mixing the naming scheme though. First/last or min/max (or something else) all the way.

I don't remember any discussion on whether it should be pop or take (or poll, anyone?) but there are lots of similar pops in Rust's standard library, the existing takes on sets work with a particular key, and the other takes seem to grab the entire contents.

ssomers · 2020-03-16T12:58:49Z

In the rust code base, there's only one use of this new API: last_entry. But anyone could have a feature(map_first_last), so not something I'd want to change without blessing.

By the way, that use would be slightly simpler if we had a last_key too. Should we? Is last_key trivial while pop_last would be worth while?

ssomers · 2020-03-16T13:49:13Z

And then there's the "_key_value" suffix. In a different line of development, get_key_value was added next to get (which returns only the value), and it obviously needed some different name. Plain last or max returning key and value, next to the mutable last_entry or max_entry, seemed overly terse and somewhat inconsistent, so it got the same "_key_value" suffix.

But pop_last or pop_max doesn't have that terseness nor inconsistency in my mind. On the contrary, pop_max_key_value makes me wonder if I could pop only a key or only a value. pop_max_key does sound better than pop_max, because it makes it clear what maximum we're talking about.

That means max_key_value sounds ambiguous to me now. What is the maximum of key,value pairs? Or maybe does it return the value of the max key? last_key_value doesn't raise that first question so you don't stray into the second question. max_key_with_value?

pipehappy1 · 2020-04-03T19:35:34Z

randomly come across this. pop_first and pop_last are more appropriate than min/max since this is an iteration and an iteration comes with the first and ends with the last.

ssomers · 2020-04-04T19:55:12Z

@pipehappy1, I don't understand what you mean. Which "this" is an iteration?

Of course first and last correspond to the various forms of forward iteration on maps, but that doesn't imply first/last is any clearer than min/max.

I think both naming schemes are reasonable. Min/max when the caller can have a good notion of how keys are ordered, and really wants the minimum or maximum. As it stands, almost all members have an Ord bound, meaning the caller must indeed know that there is an intrinsic order on the key type, and since it's the only order around, min/max is rather clear. But many methods don't need this bound, like BTreeMap::new and the methods discussed here. And funnily enough, the iterators that expose the order don't have this Ord bound, it's just documented in the methods ("sorted by key" or "in ascending order"). I don't think it was a conscious design decision.

Therefore, the first/last case is also reasonable, when the caller has no notion of key order and just wants to follow whatever order the container chooses, regardless of whether the container is a map or a vector (of pairs). But then it should not have the Ord bound.

pipehappy1 · 2020-04-06T15:06:40Z

@ssomers That's quite clear and an insight. Both naming schemes get their reason. Thx

ssomers · 2020-04-07T14:14:23Z

Point made in internals: the fact that first/last_entry are not constant time is the real problem. The "twice" in the title of this issue is just peanuts, the "required amount of computation" matters more.

PS But if it's not feasible to reduce the required amount of computation, the "twice" are still tasty peanuts.

@scottmcm

BTreeMap first last proposal tweaks Clean-up and following up on a request in rust-lang#62924. Trying the reviewer of the original code rust-lang#65637... r? @scottmcm

@scottmcm

BTreeMap first last proposal tweaks Clean-up and following up on a request in rust-lang#62924. Trying the reviewer of the original code rust-lang#65637... r? @scottmcm

frostyplanet · 2020-12-02T08:51:31Z

Is there any plan to stablize thie feature ? Since pop_first/pop_last is really useful.

BruceBrown · 2021-02-05T22:33:08Z

minor example error for BTreeSet::last(). Shouldn't assert_eq!(map.first(), None); be assert_eq!(map.last(), None); ?

pierzchalski · 2022-09-09T05:29:42Z

@BurntSushi @dtolnay @joshtriplett is there any potential next step here? This seems like an unusually long wait for FCP.

est31 · 2022-09-12T16:24:30Z

As the FCP is close to starting (only one more approval needed), I've opened a PR to stabilize the map_first_last feature: #101727 .

avl · 2022-09-13T06:17:31Z

Random bystander here.

Wouldn't it make sense for one of @Amanieu , @yaahc or @m-ou-se to either approve this, or provide some guidance on what further work is needed before this can be approved?

rfcbot · 2022-09-13T06:24:55Z

🔔 This is now entering its final comment period, as per the review above. 🔔

Amanieu · 2022-09-13T06:25:20Z

I've been away for the past few weeks and haven't had much time to check up on Rust-related things. I've checked my box, this API looks fine to me.

rfcbot · 2022-09-23T06:31:55Z

The final comment period, with a disposition to merge, as per the review above, is now complete.

As the automated representative of the governance process, I would like to thank the author for their work and everyone else who contributed.

This will be merged soon.

…m-ou-se 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 rust-lang#62924 ~~Blocked on the [FCP](rust-lang#62924 (comment)) finishing.~~ Edit: It finished!

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](rust-lang/rust#62924 (comment)) finishing.~~ Edit: It finished!

nexplor changed the title ~~Finding inimum/maximum element in BTreeMap does twice the required computation~~ Finding minimum/maximum element in BTreeMap does twice the required amount of computation Jul 24, 2019

ssomers mentioned this issue Oct 20, 2019

proposal for BTreeMap/Set min/max, #62924 #65637

Merged

ssomers added a commit to ssomers/rust that referenced this issue Oct 23, 2019

proposal for access to BTreeMap/BTreeSet first/last, rust-lang#62924

ffeac1f

ssomers mentioned this issue Apr 6, 2020

BTreeMap first last proposal tweaks #70850

Merged

est31 mentioned this issue Sep 12, 2022

Stabilize map_first_last #101727

Merged

joshtriplett added the I-libs-api-nominated Nominated for discussion during a libs-api team meeting. label Sep 12, 2022

rfcbot added final-comment-period In the final comment period and will be merged soon unless new substantive objections are raised. and removed proposed-final-comment-period Proposed to merge/close by relevant subteam, see T-<team> label. Will enter FCP once signed off. labels Sep 13, 2022

m-ou-se removed the I-libs-api-nominated Nominated for discussion during a libs-api team meeting. label Sep 13, 2022

rfcbot added finished-final-comment-period The final comment period is finished for this PR / Issue. and removed final-comment-period In the final comment period and will be merged soon unless new substantive objections are raised. labels Sep 23, 2022

rfcbot added the to-announce Announce this issue on triage meeting label Sep 23, 2022

apiraino removed the to-announce Announce this issue on triage meeting label Sep 29, 2022

bors closed this as completed in cadb37a Oct 11, 2022

evenyag mentioned this issue Oct 13, 2022

feat: manifest improvements GreptimeTeam/greptimedb#303

Merged

mattsse mentioned this issue Nov 16, 2022

Rust Stabilization Tracking issue paradigmxyz/reth#212

Closed

2 tasks

st3b1t mentioned this issue Jun 8, 2023

Update Readme.md RCasatta/fbbe#28

Merged

BigWingBeat mentioned this issue Mar 17, 2024

Make quinn_proto::Connection and quinn_proto::Endpoint impl Sync quinn-rs/quinn#1769

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Tracking issue for map_first_last: first/last methods on BTreeSet and BTreeMap #62924

Tracking issue for map_first_last: first/last methods on BTreeSet and BTreeMap #62924

nexplor commented Jul 24, 2019 •

edited by m-ou-se

Loading

cuviper commented Jul 24, 2019

cuviper commented Jul 24, 2019

ssomers commented Oct 19, 2019

ssomers commented Oct 20, 2019 •

edited

Loading

matklad commented Dec 26, 2019

ssomers commented Dec 26, 2019 •

edited

Loading

matklad commented Dec 26, 2019

jmlMetaswitch commented Mar 16, 2020 •

edited

Loading

ssomers commented Mar 16, 2020 •

edited

Loading

ssomers commented Mar 16, 2020

ssomers commented Mar 16, 2020 •

edited

Loading

pipehappy1 commented Apr 3, 2020

ssomers commented Apr 4, 2020 •

edited

Loading

pipehappy1 commented Apr 6, 2020

ssomers commented Apr 7, 2020 •

edited

Loading

frostyplanet commented Dec 2, 2020 •

edited

Loading

BruceBrown commented Feb 5, 2021

pierzchalski commented Sep 9, 2022

est31 commented Sep 12, 2022

avl commented Sep 13, 2022 •

edited

Loading

rfcbot commented Sep 13, 2022

Amanieu commented Sep 13, 2022

rfcbot commented Sep 23, 2022

Tracking issue for map_first_last: first/last methods on BTreeSet and BTreeMap #62924

Tracking issue for map_first_last: first/last methods on BTreeSet and BTreeMap #62924

Comments

nexplor commented Jul 24, 2019 • edited by m-ou-se Loading

Public API

Steps / History

Unresolved Questions

cuviper commented Jul 24, 2019

cuviper commented Jul 24, 2019

ssomers commented Oct 19, 2019

ssomers commented Oct 20, 2019 • edited Loading

matklad commented Dec 26, 2019

ssomers commented Dec 26, 2019 • edited Loading

matklad commented Dec 26, 2019

jmlMetaswitch commented Mar 16, 2020 • edited Loading

ssomers commented Mar 16, 2020 • edited Loading

ssomers commented Mar 16, 2020

ssomers commented Mar 16, 2020 • edited Loading

pipehappy1 commented Apr 3, 2020

ssomers commented Apr 4, 2020 • edited Loading

pipehappy1 commented Apr 6, 2020

ssomers commented Apr 7, 2020 • edited Loading

frostyplanet commented Dec 2, 2020 • edited Loading

BruceBrown commented Feb 5, 2021

pierzchalski commented Sep 9, 2022

est31 commented Sep 12, 2022

avl commented Sep 13, 2022 • edited Loading

rfcbot commented Sep 13, 2022

Amanieu commented Sep 13, 2022

rfcbot commented Sep 23, 2022

nexplor commented Jul 24, 2019 •

edited by m-ou-se

Loading

ssomers commented Oct 20, 2019 •

edited

Loading

ssomers commented Dec 26, 2019 •

edited

Loading

jmlMetaswitch commented Mar 16, 2020 •

edited

Loading

ssomers commented Mar 16, 2020 •

edited

Loading

ssomers commented Mar 16, 2020 •

edited

Loading

ssomers commented Apr 4, 2020 •

edited

Loading

ssomers commented Apr 7, 2020 •

edited

Loading

frostyplanet commented Dec 2, 2020 •

edited

Loading

avl commented Sep 13, 2022 •

edited

Loading