Re: [hub] on the specialized iteration over elements

El 17/04/2026 a las 3:27, Jean-Louis Leroy via Boost escribió:
> It seems to me that 'visit' is useful and legal only in combination
> with 'operator++',
> 'operator--' and the likes of 'std::next', 'std::prev',
> 'std::advance', etc. For example:
>
>      int main() {
>          boost::container::hub<int> h {1, 3, 5, 7, 9};
>          auto first = h.begin();
>          auto middle = std::next(first, h.size() / 2);
>          auto last = h.end();
>          h.visit(first, middle, [](int i){
>              std::print("{} ", i);
>          });
>          std::print(" | ");
>          h.visit(middle, last, [](int i){
>              std::print("{} ", i);
>          });
>      }
>
> (https://godbolt.org/z/1e5E413r8)
>
> Important use cases are divide-and-conquer algorithms and parallelization.
>
> >From here, two things.
>
> If 'visit' is faster than just "ranging over", it probably (?) means
> that we need
> 'hub::advance' etc as well.


This paralellization/divide_and_conquer scenario opens up an interesting 
exploration opportunity. There's a performance problem with std::next, 
though: a hub is basically a linked list of 64-element blocks, each 
equipped with an occupancy bitmask; advancing an iterator n positions 
reduces necessarily to incrementing the iterator n times, checking for 
occupied slots etc at each step, that is, there's no shortcut that could 
make the operation faster. An alternative would be having something like

   mid(first, last)

that returns an iterator _roughly_ midway between first and last. The 
"roughly" part allows us to do the operation much more quickly (like 64x 
faster or more) by happily jumping over entire blocks, assuming the load 
factor of each block is more or less the same (which is not true 
generally, but it may be ok if your goal is to split the entire range 
into reasonably sized subranges for parallelization).


> But then an integer displacement is always involved, be it 1 or -1.
> Doesn't it suggest
> that 'visit' should take offsets, not iterators? That would take care
> of Andrzej's
> concern. And there is no need for public 'advance' etc members.


Sorry, I don't get your argument here, care elaborate? Thank you!


Joaquín M López Muñoz

_______________________________________________
Boost mailing list -- [email protected]
To unsubscribe send an email to [email protected]
https://lists.boost.org/mailman3/lists/boost.lists.boost.org/
Archived at: https://lists.boost.org/archives/list/[email protected]/message/JXQQT4VYGBKJCXP6GZYOG4XVUF23EGWT/