On 05/03/2025 23.06, Matt Bentley via SG14 wrote:

I'm just wondering what people's assumptions are around hive::assign()/fill-insert/range-insert and capacity. This is not a standardisation question.

The standard ([sequence.reqmts]) does not specify one way or another whether capacity changes as a result of a call to assign(), but obviously if the assigned range is larger than capacity(), capacity() will increase.

However, if the assigned range is smaller than capacity, would capacity be expected to decrease? Or rather, what would /you /expect to happen? Leave capacity as-is, avoid deallocations and put the burden on the developer to call trim()? This has implications for whether or not assign does the right thing by cache locality ie. maintaining the minimum number of larger contiguous blocks, or by allocation/deallocation.

I can't parse this last sentence.

I had to parse my explanation a little before replying.

A non-pathological implementation for a general (ie. not embedded or memory-sparse) platform would allocate small blocks first and have a growth factor, if a user is inserting elements on an adhoc basis (and the user has not defined set block sizes that are larger or called reserve()). For this reason you can end up with a large hive with some small blocks at the beginning which're not good for cache locality during iteration.

If you're assigning and the smaller blocks are not needed to fill the assign(num, element) quota, these could either be deallocated or retained as reserved blocks. Ideally from a cache-locality-during-iteration perspective, you would deallocate because at this point in the container's expansion, it's clear that we're using a large number of elements, so the smaller blocks aren't necessary. They were necessary when the container was not certain how many elements the user would need.

The performance tradeoff is an immediate deallocation cost vs a long-term cache locality cost, is what I'm getting at.

The alternative of retaining them as reserved blocks and just using the large ones where possible, then letting the user trim, is fine but also not ideal because the user could also potentially deallocate many larger reserved blocks when calling trim. Shrink_to_fit is possible but also not ideal particularly for non-trivial types.

For assign(), you first need to destroy all elements that are currently
stored in the std::hive (iteration over the contents).  That results in a
bunch of empty blocks, which are then (partially) filled from the arguments
to assign().

For trivial types this's the best way of doing the operation, as it allows the above optimization of retaining only appropriately-large blocks as active blocks.

However for non-trivial types you want to call operator = on the existing elements in the hive, then insert the remainder (or erase remainder if assign size < hive size). This is particularly important if the type allocates.

Which leads me to another question.

For fill/range-insert, we don't guarantee for hive that placement of the inserted elements within the hive is contiguous ie. to allow for re-use of erased element locations.

My assumption has been that for assign, the same thing applies, otherwise the above optimization for non-trivial types is complicated.

Would people expect that when you call hive::assign({1, 2, 3, 4, 5}) on a non-empty hive, that those numbers would be in the supplied order when iterating over the hive? Given that they do not expect that when calling hive::insert({1, 2, 3, 4, 5}) on a non-empty hive.

Otherwise you end up having to insert a bunch of elements at the end of the hive for non-trivial types, rather than filling up existing erased element slots, which could potentially create an unnecessary allocation.

Similarly, would you expect a call to hive::insert(num, element) when size() == 0 but capacity() > num to potentially decrease capacity()?

No, same rationale.

Okay, thanks.