El 17/04/2026 a las 8:26, Ion Gaztañaga via Boost escribió:
El 17/04/2026 a las 1:16, Peter Dimov via Boost escribió:
Andrzej Krzemienski wrote:
First, should we draw from this a more general observation that iterators are an abstraction with overhead, and other containers (deque?) would also benefit from this inversion-of-control approach?
This is called "segmented iterators" (originally motivated by std::deque as the best known segmented data structure); Matt Austern coined the name in
https://lafstern.org/matt/segmented.pdf
and libc++ has been doing work on it (under the hood), e.g.
https://github.com/llvm/llvm-project/blob/main/libcxx/include/__iterator/seg...
https://github.com/llvm/llvm-project/issues/102817
When I last looked at this I had some ideas how it can be improved and possibly standardized, but I've forgotten everything already. :-)
This might be a good opportunity for Boost to add a segmented iterator API.
You can find the experiments that I'm doing with segmented iterators and several algorithms (some are more complicated to implement, if you want to support recursively segmented iterators or input and output iterator) that the Austern's std::fill example). Here the experimental implementation of several segmented algorithms using Austern's traits:
Prototype implementations:
https://github.com/boostorg/container/tree/develop/include/boost/container/e...
Some tests and a general bench agains std:
https://github.com/boostorg/container/tree/develop/experimental
If the vectorizer is activated (deque is the best example, as the local_iterator can be a raw pointer) you can get 5x-10x performance improvement in some scenarios. You can have worse performance in some cases. I haven't investigate those.
I tried to design efficient segmented iterators for a hub-like container but I didn't have success (the hub segmente is relatively small, 64 elements, and the local iterator is not a sufficiently simpler iterator than the general iterator that Joaquín has designed).
Exactly, hub doesn't have a local iterator per se, and intrablock visit resolves to (simplified pseoducode): auto mask = pb->mask; // pb is a pointer to the block while(mask) { int n = std::countr_zero(mask); f(pb->data[n]); mask &= mask - 1; // clear least significant one } which, I presume, any local iterator abstraction wouldn't optimize to unless the compiler is extremely smart, though I can work with you Ion to see if we can get close. Joaquín M López Muñoz