Repository: rust-itertools/itertools
Pull request #787 (2023-10-20 19:14:14)

docs: fixup docs of `tree_fold1`
I was just reading through the docs when I noticed something odd. It's probably just a typo:

There is a recommendation to use `reduce` instead of `tree_fold1` when `f` is associative. Since `tree_fold1` won't really work as expected (unless you know what you're doing) in non-associative cases, this would imply that we don't recommend the use of `tree_fold1` at all?

I just took a guess and adjusted that part of the docs to what it most likely was supposed to be. Feel free to close this PR if I'm completely wrong here 🙈 

Philippe-Cholet: @scottmcm I believe you wrote `Itertools::tree_fold1`, can you shed some light here?
RobWalt: Ok yeah, I see what you mean. Thanks for the explanation. I think I missed some things before. Let's take a closer look at all the possible cases:

- associative:
  - `f` is simple: e.g. cases like `u32::wrapping_add`. I guess you wanted to say that this case is so simple that it's better to use the more simplistic `reduce` since it's probably better for optimizations, code gen etc, right? Some evidence that this is true would be cool
    - I can try to benchmark this a little to shine some light on it
  - `f` is complex, e.g. the format case. Here we recommend the use of `tree_fold1` since it reduces the amount of required operations from `n` to `ln2(n)`. I thought this is the main use case of `tree_fold1` and this is where my confusions and "improvements" of the docs come from
    -  As mentioned, this is imo the main use case and should be highlighted. Writing
        > If `f` is associative, prefer the normal [`Iterator::reduce`] instead.
      
        seems misleading.
- non-associative:
  - in general: e.g. the `i32::sub` case from the docs. `tree_fold1` will most likely produce different results than `reduce` in an "unintuitive" way and this is why it shouldn't be recommended in this case
  - in special cases: e.g. your example with `f32::add`. If you really know what you're doing and if you can estimate the data you're dealing with then it might make sense that you use it in this case. I think your example is a bit constructed in a way since the result of the `f32::add` operations also depends on the order of the elements in the array and not only on the folding function used. So yeah, in a way `tree_fold1` can produce a more exact result, but you need to ensure that the data is ordered so that it works out. Take this example where we shuffle the array first https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=31ea48fe708bf3778358c48a930963b5

Both of the non-associative cases should be neglacted in my opinion.
RobWalt: Just did a very basic test on compiler explorer and both `reduce` and `tree_fold1` generate the exact same machine code for the simple case of `u32::add` as can be seen here.

https://rust.godbolt.org/z/b7K5EenEE
RobWalt: I guess my understanding of all of this is just lacking then. I'll just close the issue. Thanks a lot for the extra explanation, that was helpful! And sorry for the needless discussion
RobWalt: Thanks for the positive feedback :) Ok, then let me know which parts I should put the highlights on! The different use cases of `tree_fold1` and `reduce` based on the complexity of `f`?

Patch:
diff --git a/Cargo.toml b/Cargo.toml
index 2a023a1..69f653f 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -71,3 +71,7 @@ harness = false
 [[bench]]
 name = "powerset"
 harness = false
+
+[[bench]]
+name = "specializations"
+harness = false
diff --git a/benches/bench1.rs b/benches/bench1.rs
index fbcaa05..0946aff 100644
--- a/benches/bench1.rs
+++ b/benches/bench1.rs
@@ -1,8 +1,7 @@
 use criterion::{black_box, criterion_group, criterion_main, Criterion};
 use itertools::free::cloned;
+use itertools::iproduct;
 use itertools::Itertools;
-use itertools::Position;
-use itertools::{iproduct, EitherOrBoth};
 
 use std::cmp;
 use std::iter::repeat;
@@ -391,25 +390,6 @@ fn zip_unchecked_counted_loop3(c: &mut Criterion) {
     });
 }
 
-fn ziplongest(c: &mut Criterion) {
-    let v1 = black_box((0..768).collect_vec());
-    let v2 = black_box((0..1024).collect_vec());
-    c.bench_function("ziplongest", move |b| {
-        b.iter(|| {
-            let zip = v1.iter().zip_longest(v2.iter());
-            let sum = zip.fold(0u32, |mut acc, val| {
-                match val {
-                    EitherOrBoth::Both(x, y) => acc += x * y,
-                    EitherOrBoth::Left(x) => acc += x,
-                    EitherOrBoth::Right(y) => acc += y,
-                }
-                acc
-            });
-            sum
-        })
-    });
-}
-
 fn group_by_lazy_1(c: &mut Criterion) {
     let mut data = vec![0; 1024];
     for (index, elt) in data.iter_mut().enumerate() {
@@ -684,22 +664,6 @@ fn cartesian_product_iterator(c: &mut Criterion) {
     });
 }
 
-fn cartesian_product_fold(c: &mut Criterion) {
-    let xs = vec![0; 16];
-
-    c.bench_function("cartesian product fold", move |b| {
-        b.iter(|| {
-            let mut sum = 0;
-            iproduct!(&xs, &xs, &xs).fold((), |(), (&x, &y, &z)| {
-                sum += x;
-                sum += y;
-                sum += z;
-            });
-            sum
-        })
-    });
-}
-
 fn multi_cartesian_product_iterator(c: &mut Criterion) {
     let xs = [vec![0; 16], vec![0; 16], vec![0; 16]];
 
@@ -716,22 +680,6 @@ fn multi_cartesian_product_iterator(c: &mut Criterion) {
     });
 }
 
-fn multi_cartesian_product_fold(c: &mut Criterion) {
-    let xs = [vec![0; 16], vec![0; 16], vec![0; 16]];
-
-    c.bench_function("multi cartesian product fold", move |b| {
-        b.iter(|| {
-            let mut sum = 0;
-            xs.iter().multi_cartesian_product().fold((), |(), x| {
-                sum += x[0];
-                sum += x[1];
-                sum += x[2];
-            });
-            sum
-        })
-    });
-}
-
 fn cartesian_product_nested_for(c: &mut Criterion) {
     let xs = vec![0; 16];
 
@@ -820,22 +768,6 @@ fn permutations_slice(c: &mut Criterion) {
     });
 }
 
-fn with_position_fold(c: &mut Criterion) {
-    let v = black_box((0..10240).collect_vec());
-    c.bench_function("with_position fold", move |b| {
-        b.iter(|| {
-            v.iter()
-                .with_position()
-                .fold(0, |acc, (pos, &item)| match pos {
-                    Position::Middle => acc + item,
-                    Position::First => acc - 2 * item,
-                    Position::Last => acc + 2 * item,
-                    Position::Only => acc + 5 * item,
-                })
-        })
-    });
-}
-
 criterion_group!(
     benches,
     slice_iter,
@@ -857,7 +789,6 @@ criterion_group!(
     zipdot_i32_unchecked_counted_loop,
     zipdot_f32_unchecked_counted_loop,
     zip_unchecked_counted_loop3,
-    ziplongest,
     group_by_lazy_1,
     group_by_lazy_2,
     slice_chunks,
@@ -873,9 +804,7 @@ criterion_group!(
     step_range_2,
     step_range_10,
     cartesian_product_iterator,
-    cartesian_product_fold,
     multi_cartesian_product_iterator,
-    multi_cartesian_product_fold,
     cartesian_product_nested_for,
     all_equal,
     all_equal_for,
@@ -883,6 +812,5 @@ criterion_group!(
     permutations_iter,
     permutations_range,
     permutations_slice,
-    with_position_fold,
 );
 criterion_main!(benches);
diff --git a/benches/specializations.rs b/benches/specializations.rs
new file mode 100644
index 0000000..1392708
--- /dev/null
+++ b/benches/specializations.rs
@@ -0,0 +1,176 @@
+use criterion::black_box;
+use itertools::iproduct;
+use itertools::Itertools;
+
+/// Create multiple functions each defining a benchmark group about iterator methods.
+///
+/// Each created group has functions with the following ids:
+///
+/// - `next`, `size_hint`, `count`, `last`, `nth`, `collect`, `fold`
+/// - and when marked as `DoubleEndedIterator`: `next_back`, `rfold`
+/// - and when marked as `ExactSizeIterator`: `len`
+///
+/// Note that this macro can be called only once.
+macro_rules! bench_specializations {
+    (
+        $(
+            $name:ident {
+                $($extra:ident)*
+                {$(
+                    $init:stmt;
+                )*}
+                $iterator:expr
+            }
+        )*
+    ) => {
+        $(
+            fn $name(c: &mut ::criterion::Criterion) {
+                let mut bench_group = c.benchmark_group(stringify!($name));
+                $(
+                    $init
+                )*
+                let bench_first_its = {
+                    let mut bench_idx = 0;
+                    [0; 1000].map(|_| {
+                        let mut it = $iterator;
+                        if bench_idx != 0 {
+                            it.nth(bench_idx - 1);
+                        }
+                        bench_idx += 1;
+                        it
+                    })
+                };
+                bench_specializations!(@Iterator bench_group bench_first_its: $iterator);
+                $(
+                    bench_specializations!(@$extra bench_group bench_first_its: $iterator);
+                )*
+                bench_group.finish();
+            }
+        )*
+
+        ::criterion::criterion_group!(benches, $($name, )*);
+        ::criterion::criterion_main!(benches);
+    };
+
+    (@Iterator $group:ident $first_its:ident: $iterator:expr) => {
+        $group.bench_function("next", |bencher| bencher.iter(|| {
+            let mut it = $iterator;
+            while let Some(x) = it.next() {
+                black_box(x);
+            }
+        }));
+        $group.bench_function("size_hint", |bencher| bencher.iter(|| {
+            $first_its.iter().for_each(|it| {
+                black_box(it.size_hint());
+            })
+        }));
+        $group.bench_function("count", |bencher| bencher.iter(|| {
+            $iterator.count()
+        }));
+        $group.bench_function("last", |bencher| bencher.iter(|| {
+            $iterator.last()
+        }));
+        $group.bench_function("nth", |bencher| bencher.iter(|| {
+            for start in 0_usize..10 {
+                for n in 0..10 {
+                    let mut it = $iterator;
+                    if let Some(s) = start.checked_sub(1) {
+                        black_box(it.nth(s));
+                    }
+                    while let Some(x) = it.nth(n) {
+                        black_box(x);
+                    }
+                }
+            }
+        }));
+        $group.bench_function("collect", |bencher| bencher.iter(|| {
+            $iterator.collect::<Vec<_>>()
+        }));
+        $group.bench_function("fold", |bencher| bencher.iter(|| {
+            $iterator.fold((), |(), x| {
+                black_box(x);
+            })
+        }));
+    };
+
+    (@DoubleEndedIterator $group:ident $_first_its:ident: $iterator:expr) => {
+        $group.bench_function("next_back", |bencher| bencher.iter(|| {
+            let mut it = $iterator;
+            while let Some(x) = it.next_back() {
+                black_box(x);
+            }
+        }));
+        $group.bench_function("nth_back", |bencher| bencher.iter(|| {
+            for start in 0_usize..10 {
+                for n in 0..10 {
+                    let mut it = $iterator;
+                    if let Some(s) = start.checked_sub(1) {
+                        black_box(it.nth_back(s));
+                    }
+                    while let Some(x) = it.nth_back(n) {
+                        black_box(x);
+                    }
+                }
+            }
+        }));
+        $group.bench_function("rfold", |bencher| bencher.iter(|| {
+            $iterator.rfold((), |(), x| {
+                black_box(x);
+            })
+        }));
+    };
+
+    (@ExactSizeIterator $group:ident $first_its:ident: $_iterator:expr) => {
+        $group.bench_function("len", |bencher| bencher.iter(|| {
+            $first_its.iter().for_each(|it| {
+                black_box(it.len());
+            })
+        }));
+    };
+}
+
+// Example: To bench only `ZipLongest::fold`, you can do
+//     cargo bench --bench specializations zip_longest/fold
+bench_specializations! {
+    cartesian_product {
+        {
+            let v = black_box(vec![0; 16]);
+        }
+        iproduct!(&v, &v, &v)
+    }
+    multi_cartesian_product {
+        {
+            let vs = black_box([0; 3].map(|_| vec![0; 16]));
+        }
+        vs.iter().multi_cartesian_product()
+    }
+    tuple_combinations {
+        {
+            let v = black_box((0..64).collect_vec());
+        }
+        v.iter().tuple_combinations::<(_, _, _, _)>()
+    }
+    while_some {
+        {}
+        (0..)
+            .map(black_box)
+            .map(|i| char::from_digit(i, 16))
+            .while_some()
+    }
+    with_position {
+        ExactSizeIterator
+        {
+            let v = black_box((0..10240).collect_vec());
+        }
+        v.iter().with_position()
+    }
+    zip_longest {
+        DoubleEndedIterator
+        ExactSizeIterator
+        {
+            let xs = black_box(vec![0; 1024]);
+            let ys = black_box(vec![0; 768]);
+        }
+        xs.iter().zip_longest(ys.iter())
+    }
+}
diff --git a/src/adaptors/mod.rs b/src/adaptors/mod.rs
index 90cf46e..4355937 100644
--- a/src/adaptors/mod.rs
+++ b/src/adaptors/mod.rs
@@ -185,6 +185,7 @@ where
 /// item to the front of the iterator.
 ///
 /// Iterator element type is `I::Item`.
+#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 pub struct PutBack<I>
 where
     I: Iterator,
@@ -581,6 +582,22 @@ where
     fn size_hint(&self) -> (usize, Option<usize>) {
         (0, self.iter.size_hint().1)
     }
+
+    fn fold<B, F>(mut self, acc: B, mut f: F) -> B
+    where
+        Self: Sized,
+        F: FnMut(B, Self::Item) -> B,
+    {
+        let res = self.iter.try_fold(acc, |acc, item| match item {
+            Some(item) => Ok(f(acc, item)),
+            None => Err(acc),
+        });
+        let res = match res {
+            Ok(val) => val,
+            Err(val) => val,
+        };
+        res
+    }
 }
 
 /// An iterator to iterate through all combinations in a `Clone`-able iterator that produces tuples
@@ -634,6 +651,13 @@ where
     fn count(self) -> usize {
         self.iter.count()
     }
+
+    fn fold<B, F>(self, init: B, f: F) -> B
+    where
+        F: FnMut(B, Self::Item) -> B,
+    {
+        self.iter.fold(init, f)
+    }
 }
 
 impl<I, T> FusedIterator for TupleCombinations<I, T>
@@ -668,6 +692,13 @@ impl<I: Iterator> Iterator for Tuple1Combination<I> {
     fn count(self) -> usize {
         self.iter.count()
     }
+
+    fn fold<B, F>(self, init: B, f: F) -> B
+    where
+        F: FnMut(B, Self::Item) -> B,
+    {
+        self.iter.map(|x| (x,)).fold(init, f)
+    }
 }
 
 impl<I: Iterator> HasCombination<I> for (I::Item,) {
@@ -701,25 +732,25 @@ macro_rules! impl_tuple_combination {
 
         impl<I, A> Iterator for $C<I>
             where I: Iterator<Item = A> + Clone,
-                  I::Item: Clone
+                  A: Clone,
         {
             type Item = (A, $(ignore_ident!($X, A)),*);
 
             fn next(&mut self) -> Option<Self::Item> {
-                if let Some(($($X),*,)) = self.c.next() {
+                if let Some(($($X,)*)) = self.c.next() {
                     let z = self.item.clone().unwrap();
                     Some((z, $($X),*))
                 } else {
                     self.item = self.iter.next();
                     self.item.clone().and_then(|z| {
                         self.c = self.iter.clone().into();
-                        self.c.next().map(|($($X),*,)| (z, $($X),*))
+                        self.c.next().map(|($($X,)*)| (z, $($X),*))
                     })
                 }
             }
 
             fn size_hint(&self) -> SizeHint {
-                const K: usize = 1 + count_ident!($($X,)*);
+                const K: usize = 1 + count_ident!($($X)*);
                 let (mut n_min, mut n_max) = self.iter.size_hint();
                 n_min = checked_binomial(n_min, K).unwrap_or(usize::MAX);
                 n_max = n_max.and_then(|n| checked_binomial(n, K));
@@ -727,10 +758,29 @@ macro_rules! impl_tuple_combination {
             }
 
             fn count(self) -> usize {
-                const K: usize = 1 + count_ident!($($X,)*);
+                const K: usize = 1 + count_ident!($($X)*);
                 let n = self.iter.count();
                 checked_binomial(n, K).unwrap() + self.c.count()
             }
+
+            fn fold<B, F>(self, mut init: B, mut f: F) -> B
+            where
+                F: FnMut(B, Self::Item) -> B,
+            {
+                let Self { c, item, mut iter } = self;
+                if let Some(z) = item.as_ref() {
+                    init = c
+                        .map(|($($X,)*)| (z.clone(), $($X),*))
+                        .fold(init, &mut f);
+                }
+                while let Some(z) = iter.next() {
+                    let c: $P<I> = iter.clone().into();
+                    init = c
+                        .map(|($($X,)*)| (z.clone(), $($X),*))
+                        .fold(init, &mut f);
+                }
+                init
+            }
         }
 
         impl<I, A> HasCombination<I> for (A, $(ignore_ident!($X, A)),*)
@@ -885,6 +935,7 @@ where
 ///
 /// See [`.filter_map_ok()`](crate::Itertools::filter_map_ok) for more information.
 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
+#[derive(Clone)]
 pub struct FilterMapOk<I, F> {
     iter: I,
     f: F,
diff --git a/src/combinations.rs b/src/combinations.rs
index 1c834a7..d8b5351 100644
--- a/src/combinations.rs
+++ b/src/combinations.rs
@@ -37,12 +37,9 @@ pub fn combinations<I>(iter: I, k: usize) -> Combinations<I>
 where
     I: Iterator,
 {
-    let mut pool = LazyBuffer::new(iter);
-    pool.prefill(k);
-
     Combinations {
         indices: (0..k).collect(),
-        pool,
+        pool: LazyBuffer::new(iter),
         first: true,
     }
 }
@@ -107,6 +104,7 @@ where
     type Item = Vec<I::Item>;
     fn next(&mut self) -> Option<Self::Item> {
         if self.first {
+            self.pool.prefill(self.k());
             if self.k() > self.n() {
                 return None;
             }
diff --git a/src/combinations_with_replacement.rs b/src/combinations_with_replacement.rs
index f1a0bc0..88d858b 100644
--- a/src/combinations_with_replacement.rs
+++ b/src/combinations_with_replacement.rs
@@ -10,6 +10,7 @@ use crate::adaptors::checked_binomial;
 /// See [`.combinations_with_replacement()`](crate::Itertools::combinations_with_replacement)
 /// for more information.
 #[derive(Clone)]
+#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 pub struct CombinationsWithReplacement<I>
 where
     I: Iterator,
diff --git a/src/duplicates_impl.rs b/src/duplicates_impl.rs
index a80316a..71ed218 100644
--- a/src/duplicates_impl.rs
+++ b/src/duplicates_impl.rs
@@ -122,7 +122,7 @@ mod private {
     }
 
     /// Apply the identity function to elements before checking them for equality.
-    #[derive(Debug)]
+    #[derive(Debug, Clone)]
     pub struct ById;
     impl<V> KeyMethod<V, V> for ById {
         type Container = JustValue<V>;
@@ -133,6 +133,7 @@ mod private {
     }
 
     /// Apply a user-supplied function to elements before checking them for equality.
+    #[derive(Clone)]
     pub struct ByFn<F>(pub(crate) F);
     impl<F> fmt::Debug for ByFn<F> {
         debug_fmt_fields!(ByFn,);
diff --git a/src/free.rs b/src/free.rs
index 6de0a0d..5ce1b49 100644
--- a/src/free.rs
+++ b/src/free.rs
@@ -295,3 +295,22 @@ where
 {
     iterable.into_iter().sorted()
 }
+
+/// Sort all iterator elements into a new iterator in ascending order.
+/// This sort is unstable (i.e., may reorder equal elements).
+/// [`IntoIterator`] enabled version of [`Itertools::sorted_unstable`].
+///
+/// ```
+/// use itertools::sorted_unstable;
+/// use itertools::assert_equal;
+///
+/// assert_equal(sorted_unstable("rust".chars()), "rstu".chars());
+/// ```
+#[cfg(feature = "use_alloc")]
+pub fn sorted_unstable<I>(iterable: I) -> VecIntoIter<I::Item>
+where
+    I: IntoIterator,
+    I::Item: Ord,
+{
+    iterable.into_iter().sorted_unstable()
+}
diff --git a/src/impl_macros.rs b/src/impl_macros.rs
index 7c0b0c2..3db5ba0 100644
--- a/src/impl_macros.rs
+++ b/src/impl_macros.rs
@@ -30,5 +30,5 @@ macro_rules! ignore_ident{
 
 macro_rules! count_ident {
     () => {0};
-    ($i0:ident, $($i:ident,)*) => {1 + count_ident!($($i,)*)};
+    ($i0:ident $($i:ident)*) => {1 + count_ident!($($i)*)};
 }
diff --git a/src/lib.rs b/src/lib.rs
index c8422f5..11b624d 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -2499,7 +2499,18 @@ pub trait Itertools: Iterator {
     /// └─f─f─f─f─f─f
     /// ```
     ///
-    /// If `f` is associative, prefer the normal [`Iterator::reduce`] instead.
+    /// If `f` is associative you should also decide carefully:
+    ///
+    /// - if `f` is a trivial operation like `u32::wrapping_add`, prefer the normal
+    /// [`Iterator::reduce`] instead since it will most likely result in the generation of simpler
+    /// code because the compiler is able to optimize it
+    /// - otherwise if `f` is non-trivial like `format!`, you should use `tree_fold1` since it
+    /// reduces the number of operations from `O(n)` to `O(ln(n))`
+    ///
+    /// Here "non-trivial" means:
+    ///
+    /// - any allocating operation
+    /// - any function that is a composition of many operations
     ///
     /// ```
     /// use itertools::Itertools;
diff --git a/src/multipeek_impl.rs b/src/multipeek_impl.rs
index 339cf97..00c5d4e 100644
--- a/src/multipeek_impl.rs
+++ b/src/multipeek_impl.rs
@@ -7,6 +7,7 @@ use std::iter::Fuse;
 
 /// See [`multipeek()`] for more information.
 #[derive(Clone, Debug)]
+#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 pub struct MultiPeek<I>
 where
     I: Iterator,
diff --git a/src/peek_nth.rs b/src/peek_nth.rs
index 5f7fb93..e854603 100644
--- a/src/peek_nth.rs
+++ b/src/peek_nth.rs
@@ -5,6 +5,7 @@ use std::iter::Fuse;
 
 /// See [`peek_nth()`] for more information.
 #[derive(Clone, Debug)]
+#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 pub struct PeekNth<I>
 where
     I: Iterator,
diff --git a/src/permutations.rs b/src/permutations.rs
index b6ff5c4..534ca59 100644
--- a/src/permutations.rs
+++ b/src/permutations.rs
@@ -1,6 +1,7 @@
 use alloc::vec::Vec;
 use std::fmt;
 use std::iter::once;
+use std::iter::FusedIterator;
 
 use super::lazy_buffer::LazyBuffer;
 use crate::size_hint::{self, SizeHint};
@@ -26,22 +27,17 @@ where
 
 #[derive(Clone, Debug)]
 enum PermutationState {
-    StartUnknownLen { k: usize },
-    OngoingUnknownLen { k: usize, min_n: usize },
-    Complete(CompleteState),
-    Empty,
-}
-
-#[derive(Clone, Debug)]
-enum CompleteState {
-    Start {
-        n: usize,
-        k: usize,
-    },
-    Ongoing {
+    /// No permutation generated yet.
+    Start { k: usize },
+    /// Values from the iterator are not fully loaded yet so `n` is still unknown.
+    Buffered { k: usize, min_n: usize },
+    /// All values from the iterator are known so `n` is known.
+    Loaded {
         indices: Vec<usize>,
         cycles: Vec<usize>,
     },
+    /// No permutation left to generate.
+    End,
 }
 
 impl<I> fmt::Debug for Permutations<I>
@@ -53,25 +49,10 @@ where
 }
 
 pub fn permutations<I: Iterator>(iter: I, k: usize) -> Permutations<I> {
-    let mut vals = LazyBuffer::new(iter);
-
-    if k == 0 {
-        // Special case, yields single empty vec; `n` is irrelevant
-        let state = PermutationState::Complete(CompleteState::Start { n: 0, k: 0 });
-
-        return Permutations { vals, state };
+    Permutations {
+        vals: LazyBuffer::new(iter),
+        state: PermutationState::Start { k },
     }
-
-    vals.prefill(k);
-    let enough_vals = vals.len() == k;
-
-    let state = if enough_vals {
-        PermutationState::StartUnknownLen { k }
-    } else {
-        PermutationState::Empty
-    };
-
-    Permutations { vals, state }
 }
 
 impl<I> Iterator for Permutations<I>
@@ -82,169 +63,123 @@ where
     type Item = Vec<I::Item>;
 
     fn next(&mut self) -> Option<Self::Item> {
-        {
-            let &mut Permutations {
-                ref mut vals,
-                ref mut state,
-            } = self;
-            match *state {
-                PermutationState::StartUnknownLen { k } => {
-                    *state = PermutationState::OngoingUnknownLen { k, min_n: k };
+        let Self { vals, state } = self;
+        match state {
+            PermutationState::Start { k: 0 } => {
+                *state = PermutationState::End;
+                Some(Vec::new())
+            }
+            &mut PermutationState::Start { k } => {
+                vals.prefill(k);
+                if vals.len() != k {
+                    *state = PermutationState::End;
+                    return None;
                 }
-                PermutationState::OngoingUnknownLen { k, min_n } => {
-                    if vals.get_next() {
-                        *state = PermutationState::OngoingUnknownLen {
-                            k,
-                            min_n: min_n + 1,
-                        };
-                    } else {
-                        let n = min_n;
-                        let prev_iteration_count = n - k + 1;
-                        let mut complete_state = CompleteState::Start { n, k };
-
-                        // Advance the complete-state iterator to the correct point
-                        for _ in 0..(prev_iteration_count + 1) {
-                            complete_state.advance();
+                *state = PermutationState::Buffered { k, min_n: k };
+                Some(vals[0..k].to_vec())
+            }
+            PermutationState::Buffered { ref k, min_n } => {
+                if vals.get_next() {
+                    let item = (0..*k - 1)
+                        .chain(once(*min_n))
+                        .map(|i| vals[i].clone())
+                        .collect();
+                    *min_n += 1;
+                    Some(item)
+                } else {
+                    let n = *min_n;
+                    let prev_iteration_count = n - *k + 1;
+                    let mut indices: Vec<_> = (0..n).collect();
+                    let mut cycles: Vec<_> = (n - k..n).rev().collect();
+                    // Advance the state to the correct point.
+                    for _ in 0..prev_iteration_count {
+                        if advance(&mut indices, &mut cycles) {
+                            *state = PermutationState::End;
+                            return None;
                         }
-
-                        *state = PermutationState::Complete(complete_state);
                     }
+                    let item = indices[0..*k].iter().map(|&i| vals[i].clone()).collect();
+                    *state = PermutationState::Loaded { indices, cycles };
+                    Some(item)
                 }
-                PermutationState::Complete(ref mut state) => {
-                    state.advance();
-                }
-                PermutationState::Empty => {}
-            };
-        }
-        let &mut Permutations {
-            ref vals,
-            ref state,
-        } = self;
-        match *state {
-            PermutationState::StartUnknownLen { .. } => panic!("unexpected iterator state"),
-            PermutationState::OngoingUnknownLen { k, min_n } => {
-                let latest_idx = min_n - 1;
-                let indices = (0..(k - 1)).chain(once(latest_idx));
-
-                Some(indices.map(|i| vals[i].clone()).collect())
             }
-            PermutationState::Complete(CompleteState::Ongoing {
-                ref indices,
-                ref cycles,
-            }) => {
+            PermutationState::Loaded { indices, cycles } => {
+                if advance(indices, cycles) {
+                    *state = PermutationState::End;
+                    return None;
+                }
                 let k = cycles.len();
                 Some(indices[0..k].iter().map(|&i| vals[i].clone()).collect())
             }
-            PermutationState::Complete(CompleteState::Start { .. }) | PermutationState::Empty => {
-                None
-            }
+            PermutationState::End => None,
         }
     }
 
     fn count(self) -> usize {
-        fn from_complete(complete_state: CompleteState) -> usize {
-            complete_state
-                .remaining()
-                .expect("Iterator count greater than usize::MAX")
-        }
-
-        let Permutations { vals, state } = self;
-        match state {
-            PermutationState::StartUnknownLen { k } => {
-                let n = vals.count();
-                let complete_state = CompleteState::Start { n, k };
-
-                from_complete(complete_state)
-            }
-            PermutationState::OngoingUnknownLen { k, min_n } => {
-                let prev_iteration_count = min_n - k + 1;
-                let n = vals.count();
-                let complete_state = CompleteState::Start { n, k };
-
-                from_complete(complete_state) - prev_iteration_count
-            }
-            PermutationState::Complete(state) => from_complete(state),
-            PermutationState::Empty => 0,
-        }
+        let Self { vals, state } = self;
+        let n = vals.count();
+        state.size_hint_for(n).1.unwrap()
     }
 
     fn size_hint(&self) -> SizeHint {
-        let at_start = |k| {
-            // At the beginning, there are `n!/(n-k)!` items to come (see `remaining`) but `n` might be unknown.
-            let (mut low, mut upp) = self.vals.size_hint();
-            low = CompleteState::Start { n: low, k }
-                .remaining()
-                .unwrap_or(usize::MAX);
-            upp = upp.and_then(|n| CompleteState::Start { n, k }.remaining());
-            (low, upp)
-        };
-        match self.state {
-            PermutationState::StartUnknownLen { k } => at_start(k),
-            PermutationState::OngoingUnknownLen { k, min_n } => {
-                // Same as `StartUnknownLen` minus the previously generated items.
-                size_hint::sub_scalar(at_start(k), min_n - k + 1)
-            }
-            PermutationState::Complete(ref state) => match state.remaining() {
-                Some(count) => (count, Some(count)),
-                None => (::std::usize::MAX, None),
-            },
-            PermutationState::Empty => (0, Some(0)),
-        }
+        let (mut low, mut upp) = self.vals.size_hint();
+        low = self.state.size_hint_for(low).0;
+        upp = upp.and_then(|n| self.state.size_hint_for(n).1);
+        (low, upp)
     }
 }
 
-impl CompleteState {
-    fn advance(&mut self) {
-        *self = match *self {
-            CompleteState::Start { n, k } => {
-                let indices = (0..n).collect();
-                let cycles = ((n - k)..n).rev().collect();
-
-                CompleteState::Ongoing { cycles, indices }
-            }
-            CompleteState::Ongoing {
-                ref mut indices,
-                ref mut cycles,
-            } => {
-                let n = indices.len();
-                let k = cycles.len();
-
-                for i in (0..k).rev() {
-                    if cycles[i] == 0 {
-                        cycles[i] = n - i - 1;
-
-                        let to_push = indices.remove(i);
-                        indices.push(to_push);
-                    } else {
-                        let swap_index = n - cycles[i];
-                        indices.swap(i, swap_index);
-
-                        cycles[i] -= 1;
-                        return;
-                    }
-                }
+impl<I> FusedIterator for Permutations<I>
+where
+    I: Iterator,
+    I::Item: Clone,
+{
+}
 
-                CompleteState::Start { n, k }
-            }
+fn advance(indices: &mut [usize], cycles: &mut [usize]) -> bool {
+    let n = indices.len();
+    let k = cycles.len();
+    // NOTE: if `cycles` are only zeros, then we reached the last permutation.
+    for i in (0..k).rev() {
+        if cycles[i] == 0 {
+            cycles[i] = n - i - 1;
+            indices[i..].rotate_left(1);
+        } else {
+            let swap_index = n - cycles[i];
+            indices.swap(i, swap_index);
+            cycles[i] -= 1;
+            return false;
         }
     }
+    true
+}
 
-    /// Returns the count of remaining permutations, or None if it would overflow.
-    fn remaining(&self) -> Option<usize> {
+impl PermutationState {
+    fn size_hint_for(&self, n: usize) -> SizeHint {
+        // At the beginning, there are `n!/(n-k)!` items to come.
+        let at_start = |n, k| {
+            debug_assert!(n >= k);
+            let total = (n - k + 1..=n).try_fold(1usize, |acc, i| acc.checked_mul(i));
+            (total.unwrap_or(usize::MAX), total)
+        };
         match *self {
-            CompleteState::Start { n, k } => {
-                if n < k {
-                    return Some(0);
-                }
-                (n - k + 1..=n).try_fold(1usize, |acc, i| acc.checked_mul(i))
+            Self::Start { k } if n < k => (0, Some(0)),
+            Self::Start { k } => at_start(n, k),
+            Self::Buffered { k, min_n } => {
+                // Same as `Start` minus the previously generated items.
+                size_hint::sub_scalar(at_start(n, k), min_n - k + 1)
             }
-            CompleteState::Ongoing {
+            Self::Loaded {
                 ref indices,
                 ref cycles,
-            } => cycles.iter().enumerate().try_fold(0usize, |acc, (i, &c)| {
-                acc.checked_mul(indices.len() - i)
-                    .and_then(|count| count.checked_add(c))
-            }),
+            } => {
+                let count = cycles.iter().enumerate().try_fold(0usize, |acc, (i, &c)| {
+                    acc.checked_mul(indices.len() - i)
+                        .and_then(|count| count.checked_add(c))
+                });
+                (count.unwrap_or(usize::MAX), count)
+            }
+            Self::End => (0, Some(0)),
         }
     }
 }
diff --git a/src/put_back_n_impl.rs b/src/put_back_n_impl.rs
index 5fdbd5a..9b23fa7 100644
--- a/src/put_back_n_impl.rs
+++ b/src/put_back_n_impl.rs
@@ -7,6 +7,7 @@ use crate::size_hint;
 ///
 /// Iterator element type is `I::Item`.
 #[derive(Debug, Clone)]
+#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 pub struct PutBackN<I: Iterator> {
     top: Vec<I::Item>,
     iter: I,
diff --git a/src/rciter_impl.rs b/src/rciter_impl.rs
index 1282ae8..e3b7532 100644
--- a/src/rciter_impl.rs
+++ b/src/rciter_impl.rs
@@ -4,6 +4,7 @@ use std::iter::{FusedIterator, IntoIterator};
 
 /// A wrapper for `Rc<RefCell<I>>`, that implements the `Iterator` trait.
 #[derive(Debug)]
+#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
 pub struct RcIter<I> {
     /// The boxed iterator.
     pub rciter: Rc<RefCell<I>>,
diff --git a/src/take_while_inclusive.rs b/src/take_while_inclusive.rs
index 46c7a9b..5207d8a 100644
--- a/src/take_while_inclusive.rs
+++ b/src/take_while_inclusive.rs
@@ -8,6 +8,7 @@ use std::fmt;
 /// See [`.take_while_inclusive()`](crate::Itertools::take_while_inclusive)
 /// for more information.
 #[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
+#[derive(Clone)]
 pub struct TakeWhileInclusive<I, F> {
     iter: I,
     predicate: F,
diff --git a/src/tuple_impl.rs b/src/tuple_impl.rs
index 688df44..2bd9a04 100644
--- a/src/tuple_impl.rs
+++ b/src/tuple_impl.rs
@@ -345,7 +345,7 @@ macro_rules! impl_tuple_collect {
         impl_tuple_collect!($($Y,)*);
         impl<A> TupleCollect for ($(ignore_ident!($Y, A),)*) {
             type Item = A;
-            type Buffer = [Option<A>; count_ident!($($Y,)*) - 1];
+            type Buffer = [Option<A>; count_ident!($($Y)*) - 1];
 
             #[allow(unused_assignments, unused_mut)]
             fn collect_from_iter<I>(iter: I, buf: &mut Self::Buffer) -> Option<Self>
@@ -388,7 +388,7 @@ macro_rules! impl_tuple_collect {
             }
 
             fn num_items() -> usize {
-                count_ident!($($Y,)*)
+                count_ident!($($Y)*)
             }
 
             fn left_shift_push(&mut self, mut item: A) {


Test patch:
diff --git a/tests/specializations.rs b/tests/specializations.rs
index 3f5e106..fe14234 100644
--- a/tests/specializations.rs
+++ b/tests/specializations.rs
@@ -1,7 +1,7 @@
 #![allow(unstable_name_collisions)]
 
 use itertools::Itertools;
-use quickcheck::quickcheck;
+use quickcheck::{quickcheck, TestResult};
 use std::fmt::Debug;
 
 struct Unspecialized<I>(I);
@@ -76,29 +76,188 @@ where
 }
 
 quickcheck! {
+    fn interleave(v: Vec<u8>, w: Vec<u8>) -> () {
+        test_specializations(&v.iter().interleave(w.iter()));
+    }
+
+    fn interleave_shortest(v: Vec<u8>, w: Vec<u8>) -> () {
+        test_specializations(&v.iter().interleave_shortest(w.iter()));
+    }
+
+    fn batching(v: Vec<u8>) -> () {
+        test_specializations(&v.iter().batching(Iterator::next));
+    }
+
+    fn tuple_windows(v: Vec<u8>) -> () {
+        test_specializations(&v.iter().tuple_windows::<(_,)>());
+        test_specializations(&v.iter().tuple_windows::<(_, _)>());
+        test_specializations(&v.iter().tuple_windows::<(_, _, _)>());
+    }
+
+    fn circular_tuple_windows(v: Vec<u8>) -> () {
+        test_specializations(&v.iter().circular_tuple_windows::<(_,)>());
+        test_specializations(&v.iter().circular_tuple_windows::<(_, _)>());
+        test_specializations(&v.iter().circular_tuple_windows::<(_, _, _)>());
+    }
+
+    fn tuples(v: Vec<u8>) -> () {
+        test_specializations(&v.iter().tuples::<(_,)>());
+        test_specializations(&v.iter().tuples::<(_, _)>());
+        test_specializations(&v.iter().tuples::<(_, _, _)>());
+    }
+
+    fn cartesian_product(a: Vec<u8>, b: Vec<u8>) -> TestResult {
+        if a.len() * b.len() > 100 {
+            return TestResult::discard();
+        }
+        test_specializations(&a.iter().cartesian_product(&b));
+        TestResult::passed()
+    }
+
+    #[ignore] // It currently fails because `MultiProduct` is not fused.
+    fn multi_cartesian_product(a: Vec<u8>, b: Vec<u8>, c: Vec<u8>) -> TestResult {
+        if a.len() * b.len() * c.len() > 100 {
+            return TestResult::discard();
+        }
+        test_specializations(&vec![a, b, c].into_iter().multi_cartesian_product());
+        TestResult::passed()
+    }
+
+    fn coalesce(v: Vec<u8>) -> () {
+        test_specializations(&v.iter().coalesce(|x, y| if x == y { Ok(x) } else { Err((x, y)) }))
+    }
+
+    fn dedup(v: Vec<u8>) -> () {
+        test_specializations(&v.iter().dedup())
+    }
+
+    fn dedup_by(v: Vec<u8>) -> () {
+        test_specializations(&v.iter().dedup_by(PartialOrd::ge))
+    }
+
+    fn dedup_with_count(v: Vec<u8>) -> () {
+        test_specializations(&v.iter().dedup_with_count())
+    }
+
+    fn dedup_by_with_count(v: Vec<u8>) -> () {
+        test_specializations(&v.iter().dedup_by_with_count(PartialOrd::ge))
+    }
+
+    fn duplicates(v: Vec<u8>) -> () {
+        test_specializations(&v.iter().duplicates());
+    }
+
+    fn duplicates_by(v: Vec<u8>) -> () {
+        test_specializations(&v.iter().duplicates_by(|x| *x % 10));
+    }
+
+    fn unique(v: Vec<u8>) -> () {
+        test_specializations(&v.iter().unique());
+    }
+
+    fn unique_by(v: Vec<u8>) -> () {
+        test_specializations(&v.iter().unique_by(|x| *x % 50));
+    }
+
+    fn take_while_inclusive(v: Vec<u8>) -> () {
+        test_specializations(&v.iter().copied().take_while_inclusive(|&x| x < 100));
+    }
+
+    fn while_some(v: Vec<u8>) -> () {
+        test_specializations(&v.iter().map(|&x| if x < 100 { Some(2 * x) } else { None }).while_some());
+    }
+
+    fn pad_using(v: Vec<u8>) -> () {
+        use std::convert::TryFrom;
+        test_specializations(&v.iter().copied().pad_using(10, |i| u8::try_from(5 * i).unwrap_or(u8::MAX)));
+    }
+
     fn with_position(v: Vec<u8>) -> () {
         test_specializations(&v.iter().with_position());
     }
 
-    fn tuple_combinations(v: Vec<u8>) -> () {
-        let mut v = v;
-        v.truncate(10);
+    fn positions(v: Vec<u8>) -> () {
+        test_specializations(&v.iter().positions(|x| x % 5 == 0));
+    }
+
+    fn update(v: Vec<u8>) -> () {
+        test_specializations(&v.iter().copied().update(|x| *x = x.wrapping_mul(7)));
+    }
+
+    fn tuple_combinations(v: Vec<u8>) -> TestResult {
+        if v.len() > 10 {
+            return TestResult::discard();
+        }
+        test_specializations(&v.iter().tuple_combinations::<(_,)>());
+        test_specializations(&v.iter().tuple_combinations::<(_, _)>());
         test_specializations(&v.iter().tuple_combinations::<(_, _, _)>());
+        TestResult::passed()
     }
 
     fn intersperse(v: Vec<u8>) -> () {
         test_specializations(&v.into_iter().intersperse(0));
     }
 
-    fn powerset(a: Vec<u8>) -> () {
-        let mut a = a;
-        a.truncate(6);
-        test_specializations(&a.iter().powerset())
+    fn intersperse_with(v: Vec<u8>) -> () {
+        test_specializations(&v.into_iter().intersperse_with(|| 0));
+    }
+
+    fn combinations(a: Vec<u8>, n: u8) -> TestResult {
+        if n > 3 || a.len() > 8 {
+            return TestResult::discard();
+        }
+        test_specializations(&a.iter().combinations(n as usize));
+        TestResult::passed()
+    }
+
+    fn combinations_with_replacement(a: Vec<u8>, n: u8) -> TestResult {
+        if n > 3 || a.len() > 7 {
+            return TestResult::discard();
+        }
+        test_specializations(&a.iter().combinations_with_replacement(n as usize));
+        TestResult::passed()
+    }
+
+    fn permutations(a: Vec<u8>, n: u8) -> TestResult {
+        if n > 3 || a.len() > 8 {
+            return TestResult::discard();
+        }
+        test_specializations(&a.iter().permutations(n as usize));
+        TestResult::passed()
+    }
+
+    fn powerset(a: Vec<u8>) -> TestResult {
+        if a.len() > 6 {
+            return TestResult::discard();
+        }
+        test_specializations(&a.iter().powerset());
+        TestResult::passed()
     }
 
     fn zip_longest(a: Vec<u8>, b: Vec<u8>) -> () {
         test_specializations(&a.into_iter().zip_longest(b))
     }
+
+    fn zip_eq(a: Vec<u8>) -> () {
+        test_specializations(&a.iter().zip_eq(a.iter().rev()))
+    }
+
+    fn multizip(a: Vec<u8>) -> () {
+        let its = (a.iter(), a.iter().rev(), a.iter().take(50));
+        test_specializations(&itertools::multizip(its));
+    }
+
+    fn izip(a: Vec<u8>, b: Vec<u8>) -> () {
+        test_specializations(&itertools::izip!(b.iter(), a, b.iter().rev()));
+    }
+
+    fn iproduct(a: Vec<u8>, b: Vec<u8>, c: Vec<u8>) -> TestResult {
+        if a.len() * b.len() * c.len() > 200 {
+            return TestResult::discard();
+        }
+        test_specializations(&itertools::iproduct!(a, b.iter(), c));
+        TestResult::passed()
+    }
 }
 
 quickcheck! {
@@ -108,11 +267,85 @@ quickcheck! {
         pb.put_back(1);
         test_specializations(&pb);
     }
+
+    fn put_back_n(v: Vec<u8>, n: u8) -> () {
+        let mut it = itertools::put_back_n(v);
+        for k in 0..n {
+            it.put_back(k);
+        }
+        test_specializations(&it);
+    }
+
+    fn multipeek(v: Vec<u8>, n: u8) -> () {
+        let mut it = v.into_iter().multipeek();
+        for _ in 0..n {
+            it.peek();
+        }
+        test_specializations(&it);
+    }
+
+    fn peek_nth_with_peek(v: Vec<u8>, n: u8) -> () {
+        let mut it = itertools::peek_nth(v);
+        for _ in 0..n {
+            it.peek();
+        }
+        test_specializations(&it);
+    }
+
+    fn peek_nth_with_peek_nth(v: Vec<u8>, n: u8) -> () {
+        let mut it = itertools::peek_nth(v);
+        it.peek_nth(n as usize);
+        test_specializations(&it);
+    }
+
+    fn peek_nth_with_peek_mut(v: Vec<u8>, n: u8) -> () {
+        let mut it = itertools::peek_nth(v);
+        for _ in 0..n {
+            if let Some(x) = it.peek_mut() {
+                *x = x.wrapping_add(50);
+            }
+        }
+        test_specializations(&it);
+    }
+
+    fn peek_nth_with_peek_nth_mut(v: Vec<u8>, n: u8) -> () {
+        let mut it = itertools::peek_nth(v);
+        if let Some(x) = it.peek_nth_mut(n as usize) {
+            *x = x.wrapping_add(50);
+        }
+        test_specializations(&it);
+    }
 }
 
 quickcheck! {
-    fn merge_join_by_qc(i1: Vec<usize>, i2: Vec<usize>) -> () {
-        test_specializations(&i1.into_iter().merge_join_by(i2.into_iter(), std::cmp::Ord::cmp));
+    fn merge(a: Vec<u8>, b: Vec<u8>) -> () {
+        test_specializations(&a.into_iter().merge(b))
+    }
+
+    fn merge_by(a: Vec<u8>, b: Vec<u8>) -> () {
+        test_specializations(&a.into_iter().merge_by(b, PartialOrd::ge))
+    }
+
+    fn merge_join_by_ordering(i1: Vec<u8>, i2: Vec<u8>) -> () {
+        test_specializations(&i1.into_iter().merge_join_by(i2, Ord::cmp));
+    }
+
+    fn merge_join_by_bool(i1: Vec<u8>, i2: Vec<u8>) -> () {
+        test_specializations(&i1.into_iter().merge_join_by(i2, PartialOrd::ge));
+    }
+
+    fn kmerge(a: Vec<i8>, b: Vec<i8>, c: Vec<i8>) -> () {
+        test_specializations(&vec![a, b, c]
+            .into_iter()
+            .map(|v| v.into_iter().sorted())
+            .kmerge());
+    }
+
+    fn kmerge_by(a: Vec<i8>, b: Vec<i8>, c: Vec<i8>) -> () {
+        test_specializations(&vec![a, b, c]
+            .into_iter()
+            .map(|v| v.into_iter().sorted_by_key(|a| a.abs()))
+            .kmerge_by(|a, b| a.abs() < b.abs()));
     }
 }
 
@@ -120,12 +353,23 @@ quickcheck! {
     fn map_into(v: Vec<u8>) -> () {
         test_specializations(&v.into_iter().map_into::<u32>());
     }
-}
 
-quickcheck! {
     fn map_ok(v: Vec<Result<u8, char>>) -> () {
         test_specializations(&v.into_iter().map_ok(|u| u.checked_add(1)));
     }
+
+    fn filter_ok(v: Vec<Result<u8, char>>) -> () {
+        test_specializations(&v.into_iter().filter_ok(|&i| i < 20));
+    }
+
+    fn filter_map_ok(v: Vec<Result<u8, char>>) -> () {
+        test_specializations(&v.into_iter().filter_map_ok(|i| if i < 20 { Some(i * 2) } else { None }));
+    }
+
+    // `Option<u8>` because `Vec<u8>` would be very slow!! And we can't give `[u8; 3]`.
+    fn flatten_ok(v: Vec<Result<Option<u8>, char>>) -> () {
+        test_specializations(&v.into_iter().flatten_ok());
+    }
 }
 
 quickcheck! {
diff --git a/tests/test_std.rs b/tests/test_std.rs
index 732790e..732be7b 100644
--- a/tests/test_std.rs
+++ b/tests/test_std.rs
@@ -1044,7 +1044,7 @@ fn combinations_inexact_size_hints() {
         let len = binomial(real_n, k);
         assert_eq!(len, it.clone().count());
 
-        let mut nb_loaded = numbers.by_ref().take(k).count(); // because of `LazyBuffer::prefill(k)`
+        let mut nb_loaded = 0;
         let sh = numbers.size_hint();
         assert_eq!(binomial(sh.0 + nb_loaded, k), it.size_hint().0);
         assert_eq!(sh.1.map(|n| binomial(n + nb_loaded, k)), it.size_hint().1);
@@ -1053,8 +1053,10 @@ fn combinations_inexact_size_hints() {
             let elem = it.next();
             assert!(elem.is_some());
             assert_eq!(len - next_count, it.clone().count());
-            // It does not load anything more the very first time (it's prefilled).
-            if next_count > 1 {
+            if next_count == 1 {
+                // The very first time, the lazy buffer is prefilled.
+                nb_loaded = numbers.by_ref().take(k).count();
+            } else {
                 // Then it loads one item each time until exhausted.
                 let nb = numbers.next();
                 if nb.is_some() {