El 27/05/2026 a las 2:29, Matt Bentley escribió:
Hey Joaquin,
thanks for our personal discussion on this stuff, I think we've both improved our respective containers.
Thank _you_, it's been a most instructive exchange.
Just to chime in in a more official capacity, good to see you've provided some post-iteration erasure results, I think that balances things out a bit, though it still lacks some longitudinal churn testing.
? Post-erase iteration benchmarks were there all along. Maybe the confusion arises because what used to be called "for_each" and "visit all" is now called "range for" and "for_each" respectively, after the syntax change proposed by Andrzej (namely, replacing visit[_while] member functions with global std::algorithm-like for_each[_while] functions).
If you want, you're welcome to link to my benchmarking in your docs. I realised visitation-like prefetching can be applied as a hive overload of std::for_each, hopefully will have time to do that at some point, and will be interesting to see the difference.
Also glad to see the plf:: stuff is separate from the std:: stuff.
/ Minor corrections to the docs:/
"|boost::container::hub| does not conform to the specification of |std::hive| in a few aspects:
* Minimum and maximum block size limits can't be specified and are fixed (to 64 in this implementation). |reshape| is not provided as it doesn't make sense when block capacity is fixed."
That wording (inadvertently) suggests that min/max can't be fixed and equal in a std::hive implementation, which isn't the case. Better phrasing:
|boost::container::hub| does not conform to the specification of |std::hive| in a few aspects:
* Minimum and maximum block capacity limits can't be specified and are fixed to (to 64 in this implementation). The std::hive spec allows for this, but due to this we've decided to not provide reshape() or constructors which take capacity-limit arguments, since these would not result in any effect on the instance's capacity limits. In addition block_capacity_limits(), block_capacity_default_limits() and block_capacity_hard_limits() are not provided as they would always return 64, 64.
Yes, I can rewrite that part. As you have pointed out here and elsewhere, the non-conformance is, strictly speaking, not a technical one, as boost::container::hub could always provide a dummy hive_limits interface.
Likewise the following is slightly ambiguous:
"The |end| iterator is stable and non-transferable, whereas for |std::hive| the |end| iterator is invalidated upon any insertion or the erasure of the last element (briefly put, |boost::container::hub::end| behaves like |std::list::end| whereas |std::hive::end| behaves like |std::vector::end|). Technically, this is not a non-conformance but rather an extension to the specification of |std::hive|."
I would word it like this:
"The |end| iterator is guaranteed to be stable and non-transferable, whereas for |std::hive| the |end| iterator is allowed to invalidate upon any insertion or the erasure of the last element (briefly put, |boost::container::hub::end| behaves like |std::list::end| whereas |std::hive::end| is allowed to behave like either |std::list::end| or std::vector::end)."
Will use this, thank you.
Though less important, I would change the bit about three-way-comparable from 'overhead' to 'overhead for small elements', since for a 6-word type, an additional 1 word per (6x64) 384-word block makes no measurable difference to cache locality , though it does when dealing with 8->64-bit types. re: Bookkeeping, in my hive benchmarking with/without the group number metadata it made no difference except for splicing, since otherwise the numbers are in pragmatic reality pretty much never updated.
Noted.
Also, if you intend to fix that behaviour we talked about regarding iteration/visitation performance degradation over time (due to blocks which become empty not being moved to the tail of the 'available' list, and non-empty blocks thereby not being preferentially-used during insertion, resulting in greater gaps during iteration) you can remove the line "trim_capacity is linear on the number of available blocks (std::hive::trim_capacity is linear on the number of reserved blocks, i.e. those without any used slot).". As, once that aspect is fixed that it becomes possible to implement trim_capacity() as linear in the number of reserved blocks, by iterating backwards from the tail and stopping once a block with active elements is found.
After our talk I went and did exactly as you suggested: https://github.com/joaquintides/hub/compare/feature/review-feedback...featur... I'm measuring performance right now but seems like this is not producing any real degradation, so it'll go in. This also removes one of the non-conformances of boost::container::hub wrt to std::hive spec.
Finally a note re: Andrezj's container category note, this is a hive-lite container, therefore a sequence container, according to the standard: "organizes a finite set of objects, all of the same type, into a strictly linear arrangement". "In addition, array and hive are provided as sequence containers which provide limited sequence operations, in array's case because it has a fixed number of elements, and in hive's case because insertion order is unspecified.". "Limited" in the case of hive means no insertion position in insert/emplace functions. Otherwise there are no pragmatic differences.
This stemmed from an objection by Andrzej. Originally hub was presented as a sequence container, much in line with the standard text for std::hive, but I then leaned towards Andrzej's stance that this is misleading because the core functionality that makes a container a sequence, namely control of positioning, is not provided. I guess the committee does not have the appetite (understandably so) for making great rearrangements of the text, but IMHO this would have called for a new kind of "unordered containers". Anyway, the current writing is a bit in between, it doesn't call the container a sequence container right away but then in the reference it states (https://github.com/joaquintides/hub/tree/feature/review-feedback#class-templ...): /boost::container::hub<T, Allocator> is also a model of SequenceContainer, with the following exception: * Positional insertion operations of the form insert(position, ...) or emplace(position, ...) are not provided or ignore the position argument. / I readily admit this is all quite non-committal to either side of the discussion :-)
Cheers once again-
Matt
Thanks for your feedback, Joaquín M López Muñoz