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.