Rollup merge of #77449 - ssomers:btree_drain_filter_size_hint, r=Mark-Simulacrum

BTreeMap: comment why drain_filter's size_hint is somewhat pessimistic

The `size_hint` of the `DrainFilter` iterator doesn't adjust as you iterate. This hardly seems important to me, but there has been a comparable PR #64383 in the past. I guess a scenario is that you first iterate half the map manually and keep most of the key/value pairs in the map, and then tell the predicate to drain most of the key/value pairs and `.collect` the iterator over the remaining half of the map.

I am totally ambivalent whether this is better or not.

r? @Mark-Simulacrum

1 files changed, 4 insertions, 0 deletions

diff --git a/library/alloc/src/collections/btree/map.rs b/library/alloc/src/collections/btree/map.rs
index 04f317401f1..606bf94f998 100644
--- a/library/alloc/src/collections/btree/map.rs
+++ b/library/alloc/src/collections/btree/map.rs
@@ -1783,6 +1783,10 @@ impl<'a, K: 'a, V: 'a> DrainFilterInner<'a, K, V> {
 
     /// Implementation of a typical `DrainFilter::size_hint` method.
     pub(super) fn size_hint(&self) -> (usize, Option<usize>) {
+        // In most of the btree iterators, `self.length` is the number of elements
+        // yet to be visited. Here, it includes elements that were visited and that
+        // the predicate decided not to drain. Making this upper bound more accurate
+        // requires maintaining an extra field and is not worth while.
         (0, Some(*self.length))
     }
 }