[Pre-RFC] Change the ExactSizeIterator spec

[stebalien]

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.

[mzabaluev]

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.

[stebalien]

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

Good point.

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.

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.

[bluss]

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.

[stebalien]

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?

[bluss]

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

[system]

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