Override Iterator methods when possible in `std`

[aturon]

Now that Iterator has re-emerged as a single trait, it's possible to override default methods like count, last and nth for iterators on slices, vectors, and so on. We should audit the applicable iterators and take advantage of overrides when possible.

libcore:

• slice::Iter(Mut): count, last, nth
• slice::Windows: count, last, nth O(1) count,nth,last for slice::{Windows,Chunks,ChunksMut} #27652
• slice::Chunks(Mut): count, last, nth O(1) count,nth,last for slice::{Windows,Chunks,ChunksMut} #27652
• char::{EscapeDefault, EscapeUnicode}: count, last, nth (techically but probably not worth it)
• str::Bytes: count, last, nth
• iter::Chain: count, last, nth
• iter::Enumerate: count, nth
• iter::Peekable: count, last, nth
• iter::Skip: count, last, next (should call nth), nth
• iter::Take: nth
• iter::Fuse: count, last, nth

[aturon]

I'd be happy to mentor work on this bug.

[djmally]

I would be interested in working on this.

[GuillaumeGomez]

Me too.

[tamird]

Also interested in working on this. Anything left to do?

[djmally]

@aturon Any word on this?

[pnkfelix]

Also, I'm curious if methods like skip(n) are required to actually call next n tines, or if they are allowed to "jump ahead" on random-access iterators. (Maybe that sort of trick will have to wait for specialization in the language, to avoid composing that with e.g. a map or other potentially side-effectful iterator

[Stebalien]

@pnkfelix skip can call nth on the underlying iterator and the underlying iterator can optimize nth if possible.

[pnkfelix]

@Stebalien I think that is my point: You say "the underlying iterator can optimize nth if possible", but I claim to allow that would require changing the specification of nth, which currently is specified as "going through n iterations", which I interpret as "calls the next() method n times" -- a side-effectful iterator chain (e.g. one using inspect) can observe the difference between that or jumping ahead n steps when given a random-access iterator.

[aturon]

Oh dear, I seem to've lost track of this thread, sorry to everyone who was waiting on me to organize things!

I think probably the first place to start is just to get a list of the public iterators in std, which we can turn into a checklist and track assignees for. Part of the work will just be figuring out which cases are actually opportunities for doing better.

Anyone interested in putting such a list together? I'd be glad to help coordinate.

[aturon]

(And if no one is in a position to make a list, I can put one together tomorrow.)

[Stebalien]

@pnkfelix It doesn't because:

1. Skip can assume that the underlying iterator correctly implements nth.
2. Some iterators (e.g. slice::Iter) have side-effect-free next methods. These iterators can implement optimized nth functions.

So vec![1, 2, 3, 4, 5].iter().skip(2) can have a constant time skip given an optimized slice::Iter::nth method. Unfortunately, as implemented, ranges can't optimize nth this way because they are generic.