# \[Pre-RFC\] Change the ExactSizeIterator spec

**URL:** <https://internals.rust-lang.org/t/pre-rfc-change-the-exactsizeiterator-spec/1646>\
**Category:** ideas (deprecated)\
**Created:** [February 24, 2015, 4:26am UTC](https://internals.rust-lang.org/t/pre-rfc-change-the-exactsizeiterator-spec/1646 "2015-02-24T04:26:09Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![stebalien](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/stebalien/32/228_2.png) [@stebalien](https://internals.rust-lang.org/u/stebalien)\
**Post date:** [February 24, 2015, 4:26am UTC](https://internals.rust-lang.org/t/pre-rfc-change-the-exactsizeiterator-spec/1646/1 "2015-02-24T04:26:09Z")

</div>

Currently, the `ExactSizeIterator` spec specifies that `Iterator::size_hint` must return `(exact_size, Some(exact_size)`.

> `Iterator::size_hint` must return the exact size of the iterator. Note that the size must fit in usize.

However, it also specifies that its own `ExactSizeIterator::len` method must also return `exact_size`.

I propose that the requirement on `Iterator::size_hint` be removed because it:

1. Is redundant.
2. Imposes a requirement on a method provided by a different trait.
3. Makes it impossible to implement an iterator that can quickly give an approximate `size_hint` but can take longer to give an exact `len`.

---

<div class="post-metadata">

**Author:** ![mzabaluev](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/mzabaluev/32/3082_2.png) [@mzabaluev](https://internals.rust-lang.org/u/mzabaluev)\
**Post date:** [February 24, 2015, 9:06am UTC](https://internals.rust-lang.org/t/pre-rfc-change-the-exactsizeiterator-spec/1646/2 "2015-02-24T09:06:25Z")

</div>

Making one trait implementation impose additional requirements on another is not new, we have `Eq` and `PartialEq`.

`size_hint` is useful for generic code that should work if the exact size is not known, but needs a reasonable estimate for e.g. reserving capacity in a collecting container.

As for 3, if the cost of calculating the size is not (amortized) constant, perhaps the iterator should not implement `ExactSizeIterator` at all. To take the opposite to extremes, any cloneable or bidirectional iterator might implement `ExactSizeIterator`, but the performance of generic code using that as a bound would be anyone’s guess.

---

<div class="post-metadata">

**Author:** ![stebalien](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/stebalien/32/228_2.png) [@stebalien](https://internals.rust-lang.org/u/stebalien)\
**Post date:** [February 24, 2015, 2:21pm UTC](https://internals.rust-lang.org/t/pre-rfc-change-the-exactsizeiterator-spec/1646/3 "2015-02-24T14:21:40Z")

</div>

> [@mzabaluev](#):
>
> Making one trait implementation impose additional requirements on another is not new, we have Eq and PartialEq.

Good point.

> [@mzabaluev](#):
>
> size\_hint is useful for generic code that should work if the exact size is not known, but needs a reasonable estimate for e.g. reserving capacity in a collecting container.

I'm not suggesting getting rid of size\_hint.

> [@mzabaluev](#):
>
> As for 3, if the cost of calculating the size is not (amortized) constant, perhaps the iterator should not implement ExactSizeIterator at all. To take the opposite to extremes, any cloneable or bidirectional iterator might implement ExactSizeIterator, but the performance of generic code using that as a bound would be anyone's guess.

However, one could reasonably design an algorithm that can compute an exact size in `log(n)` time but give a estimate a bound in constant time (restrict `n <= c`). Generic code that just needs a reasonable estimate for allocation could use the constant time method but code that absolutely needs to know an exact size could call `len()` to get an exact size. I don't know of any algorithms like this but I feel that needlessly restricting the API is a bad idea.

Essentially, I argue that this constraint should be removed because it serves no purpose and _could_ restrict future APIs.

---

<div class="post-metadata">

**Author:** ![bluss](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/bluss/32/2264_2.png) [@bluss](https://internals.rust-lang.org/u/bluss)\
**Post date:** [February 24, 2015, 2:36pm UTC](https://internals.rust-lang.org/t/pre-rfc-change-the-exactsizeiterator-spec/1646/4 "2015-02-24T14:36:54Z")

</div>

The use case it was introduced for, which is .enumerate().rev() – does not make sense for the scenario of an expensive version of length calculation.

Does ExactSizeIterator have a real purpose? Counter-proposal: Remove ExactSizeIterator.

---

<div class="post-metadata">

**Author:** ![stebalien](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/stebalien/32/228_2.png) [@stebalien](https://internals.rust-lang.org/u/stebalien)\
**Post date:** [February 24, 2015, 8:23pm UTC](https://internals.rust-lang.org/t/pre-rfc-change-the-exactsizeiterator-spec/1646/5 "2015-02-24T20:23:28Z")

</div>

A logarithmic length calculation definitely makes sense for `iter.enumerate().rev().take(n)` where `n` \<\< `iter.len()`.

How is this not a real purpose for `ExactSizeIterator`?

---

<div class="post-metadata">

**Author:** ![bluss](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/bluss/32/2264_2.png) [@bluss](https://internals.rust-lang.org/u/bluss)\
**Post date:** [February 24, 2015, 8:56pm UTC](https://internals.rust-lang.org/t/pre-rfc-change-the-exactsizeiterator-spec/1646/6 "2015-02-24T20:56:50Z")

</div>

It’s kind of a gotcha to have non-constant time .len(), but logarithmic isn’t so bad.

---

<div class="post-metadata">

**Author:** ![system](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/system/32/14092_2.png) [@system](https://internals.rust-lang.org/u/system)\
**Post date:** [March 25, 2019, 8:23am UTC](https://internals.rust-lang.org/t/pre-rfc-change-the-exactsizeiterator-spec/1646/7 "2019-03-25T08:23:59Z")

</div>

Closed on March 25, 2019, 8:23am UTC

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.