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

[nexplor]

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.

[cuviper]

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]

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

[ssomers]

#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]

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)

[matklad]

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]

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]

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

[jmlMetaswitch]

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.