This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of New status.

4380. hive::reserve() complexity does not reflect potential deallocation of blocks

Section: 23.3.9.3 [hive.capacity] Status: New Submitter: Matt Bentley Opened: 2025-09-23 Last modified: 2025-10-22

Priority: 3

View other active issues in [hive.capacity].

View all other issues in [hive.capacity].

View all issues with New status.

Discussion:

As noted by Arthur in issue 4379(i), reserve(n) could choose to deallocate some reserved (empty) blocks if in doing so it could then allocate blocks which brought capacity() closer to n.

For example if capacity() is 460, n is 480, the current-limits.min is 40 and there is a reserved block of capacity 70, the latter could be deallocated and a new reserved block allocated of capacity 90, bringing total capacity to 480. As opposed to allocating a new reserved block at the min capacity of 40, bringing the total capacity to 500.

The implicit assumption in this issue is that we want reserve() to be able to deallocate. No-one has objected to this before, but if you want to, please speak up.

Anyway, the Complexity of reserve() does not presently reflect this ability.

[2025-10-22; Reflector poll.]

Set priority to 3 after reflector poll.

An explicit objection was raised that the Effects: should state whether reserve() is allowed, or even required, to deallocate blocks.

Proposed resolution:

This wording is relative to N5014.

  1. Modify 23.3.9.3 [hive.capacity] as indicated:

    void reserve(size_type n);

    -3- Effects: If n <= capacity() is true, there are no effects. Otherwise increases capacity() by allocating reserved blocks.

    -4- Postconditions: capacity() >= n is true.

    -5- Throws: length_error if n > max_size(), as well as any exceptions thrown by the allocator.

    -6- Complexity: It does not change the size of the sequence and takes at most linear time in the number of reserved blocks allocated and deallocated.

    -7- Remarks: All references, pointers, and iterators referring to elements in *this, as well as the past-the-end iterator, remain valid.