search

chromium / subspace

A concept-centered standard library for C++20, enabling safer and more reliable products and a more modern feel for C++ code.; Also home of Subdoc the code-documentation generator.
https://suslib.cc
Apache License 2.0
89 stars 15 forks source link

Iterator nth (and nth_back) must be optimized for contiguous iterators #357

Open danakj opened 1 year ago

danakj commented 1 year ago

Slice iterators need to be able to perform nth() in O(1) time, which means Iterator needs to be able to delegate from the default impl to a specific one.

There's a few other important methods like that as well. Then aggressively use those methods from the default methods if there's any opportunities to do so that aren't done yet (mostly they should already be).

fold is also optimized for some iterators in std.rs I believe.

danakj commented 1 year ago

Can we compare the address of Iter::nth() to IteratorBase::nth to determine if we should branch and call the Iter overload from IteratorBase::nth?

It would loop forever if it was overloaded and called up to the IteratorBase but just don't do that.