imbl::ordmap::RangedIter does not implement ExactSizeIterator

[optevo]

Impact:
While RangedIter implements DoubleEndedIterator, .rev() is not fully supported beyond the first call when combined with adaptors like take(). This is because take() requires the iterator to implement ExactSizeIterator, as subsequent calls to .rev() depend on knowing the iterator’s exact length via len() provided by ExactSizeIterator.

This is a breaking change introduced from version 3.0.0 to 4.0.0 as ExactSizeIterator was implemented on imbl::ordmap::Iter

[jneem]

That's right: this was called out in the changelog here, and was the reason for bumping the major version number. More context at #85: your reliance on ExactSizeIterator was probably producing incorrect results.

[optevo]

Thanks sorry missed it. Do you have a recommended efficient workaround to iterate in reverse - get_prev? What are the challenges around implementing a correct ExactSizeIterator? Iterator impl needs size_hint() to return correct size so initialise with len() then decrement as consumed which it could track in the struct no? I'm missing something?

[jneem]

Iterating in reverse on its own is fine, because RangedIter implements DoubleEndedIterator. But if you want to do something like map.range(a..b).take(10).next_back(), I think the most efficient way is to collect map.range(a..b).take(10) into a Vec and then you can iterate over that vec as much as you like.

Implementing a correct ExactSizeIterator would require a lot of length-tracking internally and it would impose a cost on all other usages of OrdMap. The standard library BTreeMap doesn't support it either, probably for that reason.