Issue 4320 - WG21 LWG Issues
Title
`hive` operations involving insertion/erasure should have 𝒪(log n) time complexity
Status
new
Section
[hive]
Submitter
Matt Bentley

Created on 2025-08-19.00:00:00 last changed 3 weeks ago

Messages

msg15076 (view)
Date: 2025-09-27.10:24:58

Proposed resolution:

This wording is relative to N5014.

  1. Modify [hive.overview] as indicated:

    -1- A `hive` is a type of sequence container that provides constant-time insertion and erasure operations. Storage is automatically managed in multiple memory blocks, referred to as element blocks. Insertion position is determined by the container, and may re-use the memory locations of erased elements.

    -2- […]

    -3- Erasures use unspecified techniques of constant time complexity to identify the memory locations of erased elements, which are subsequently skipped during iteration in constant time, as opposed to relocating subsequent elements during erasure. The same or different techniques may be utilized to find and re-use these locations during subsequent insertions.

    [Note: The techniques are permitted to be at worst logarithmic in the capacity of the element blocks being inserted into or erased from, while maintaining constant-time iteration, to allow latitude for implementation-specific optimizations. — end note]

msg14947 (view)
Date: 2025-09-15.00:00:00

[ 2025-09-26; Matt comments and provides improved wording ]

Past LWG/LEWG telecon discussion around this topic concluded that because elements are not involved, and the logarithmic action is within the capacity of a block (a fixed number), not the size of the sequence, and the actual performance cost is negligible, that the complexity of these actions are in fact constant. But there is some disagreement on this.

One possibility is to add additional complexity data to each of the effected functions. This would impact on `emplace`, range `insert`, fill `insert`, `shrink_to_fit`, `reshape`, copy/move assignment operator, `erase` and `unique`. However I feel this is overkill and may confuse implementors as the log(n) complexity is not permitted to involve elements.

Having looked into it and sought feedback I think a blanket note on [hive.overview] p3 would be sufficient, such that the time complexity is limited to "techniques to identify the memory locations of erased elements". Otherwise we need to stay with the previous resolution that this is in fact constant time behaviour.

msg14946 (view)
Date: 2025-09-27.10:24:58

Under [hive.modifiers] p4 complexity is stated as "Constant. Exactly one object of type `T` is constructed."

However the approach to implementation necessary to support 8/16-bit types without artificially widening the type storage, as described under "Additional info for supporting small types" in P0447 basically specifies time complexity which is `Log(n)` (on most platforms, log64 or log32) in the capacity of the element block selected to insert into. This time complexity only occurs during the operation to find an erased element memory location within a block which is known to have one, and does not involve the elements themselves.

This is both the simplest and fastest solution to supporting small types in hive without artificial widening that I have come across.

Further, I have discovered that this approach can be extended to larger block capacities via "bitset stacking" while retaining 𝒪(log n) intra-block lookup time complexity, regardless of block capacity. Overall this approach would be useful for embedded and other memory-scarse platforms as it reduces the 16-bit-per-element cost of the reference implementation down to a 1-bit-per-element cost. For 64-bit and larger types, there are other ways to obtain this reduction without losing 𝒪(1) lookup but it is unclear whether those methods would in fact be faster. For approaches involving bitset-stacking, the logarithmic complexity also occurs during erasure, specifically adding a couple of extra instructions for every 64x (i.e. bit-depth) increase in block capacity. But again this does not involve the elements and is logarithmic in the capacity of the block erased from.

Regardless, the increased complexity during insertion is necessary for small-type support.

There was ambiguity as to whether this should result in a change to hive time complexity when discussed on the reflector, as it is unrelated to element numbers (unless all elements fit within one block), but it is related to block capacities, which are defined as part of the `hive` technical specification.

This wording is relative to N5014.

[Drafting note: I am unclear on whether `assign()` and `assign_range()` operations would require specification since they also have the capability to reuse existing erased element memory spaces, but we do not currently supply time complexity wording for these in the standard in general and I'm unsure why that is.]

  1. Modify [hive.overview] as indicated:

    -1- A `hive` is a type of sequence container that provides constant-time insertion and erasure operations. Swhere storage is automatically managed in multiple memory blocks, referred to as element blocks. Insertion position is determined by the container, and insertion may re-use the memory locations of erased elements. Insertions are either constant time or logarithmic in the capacity of the element block inserted into.

    -2- […]

    -3- Erasures use unspecified techniques of constant time complexity to identify the memory locations of erased elements, which are subsequently skipped during iteration in constant time, as opposed to relocating subsequent elements during erasure. These techniques are either constant time or logarithmic in the capacity of the element block erased from.

  2. Modify [hive.cons] as indicated:

    hive& operator=(const hive& x);

    -25- Preconditions: […]

    -26- Effects: […]

    -27- Complexity: Linear in `size() + x.size()`. Additionally at worst 𝒪(log n) in the capacity of each element block which an element is constructed within. 

    hive& operator=(hive&& x)
  noexcept(allocator_traits<Allocator>::propagate_on_container_move_assignment::value ||
           allocator_traits<Allocator>::is_always_equal::value);

    -28- Preconditions: […]

    -29- Effects: […]

    -30- Postconditions: […]

    -31- Complexity: Linear in `size()`. If 

    (allocator_traits<Allocator>::propagate_on_container_move_assignment::value ||
get_allocator() == x.get_allocator())

    is `false`, also linear in `x.size()` and additionally at worst 𝒪(log n) in the capacity of each element block which an element is constructed within.

  3. Modify [hive.capacity] as indicated:

    void shrink_to_fit();

    -8- Preconditions: […]

    -9- Effects: […]

    -10- Complexity: If reallocation happens, linear in the size of the sequence and at worst 𝒪(log n) in the capacity of each element block which elements are reallocated into.

    -11- Remarks: […]

    […] 

    void reshape(hive_limits block_limits);

    -21- Preconditions: […]

    -22- Effects: […]

    -23- Postconditions: […]

    -24- Complexity: Linear in the number of element blocks in `*this`. If reallocation happens, also linear in the number of elements reallocated and at worst 𝒪(log n) in the capacity of each element block which elements are reallocated into.

    -25- Remarks: […]

  4. Modify [hive.modifiers] as indicated:

    template<class... Args> iterator emplace(Args&&... args);
template<class... Args> iterator emplace_hint(const_iterator hint, Args&&... args);

    -1- Preconditions: […]

    -2- Effects: […]

    -3- Returns: […]

    -4- Complexity: ConstantAt worst 𝒪(log n) in the capacity of the element block which the element is constructed within. Exactly one object of type `T` is constructed.

    […] 

    void insert(initializer_list<T> rg);
template<container-compatible-range<T> R>
  void insert_range(R&& rg);

    -7- Preconditions: […]

    -8- Effects: […]

    -9- Complexity: Linear in the number of elements inserted. Additionally at worst 𝒪(log n) in the capacity of each element block which an element is constructed within. Exactly one object of type `T` is constructed for each element inserted.

    -10- Remarks: […] 

    void insert(size_type n, const T& x);

    -11- Preconditions: […]

    -12- Effects: […]

    -13- Complexity: Linear in `n`. Additionally at worst 𝒪(log n) in the capacity of each element block which an element is constructed within.. Exactly one object of type `T` is constructed for each element inserted.

    -14- Remarks: […]

    […] 

    iterator erase(const_iterator position);
iterator erase(const_iterator first, const_iterator last);

    -16- Complexity: Linear in the number of elements erased and for each erased element at worst 𝒪(log n) in the capacity of the block containing the element. Additionally, if any active blocks become empty of elements as a result of the function call, at worst linear in the number of element blocks.

  5. Modify [hive.operations] as indicated:

    [Drafting note: If issue LWG 4323 is decided to be acted upon and the proposed solution accepted, the proposed complexity wording becomes:

    -11- Complexity: If `empty()` is `false`, exactly `size() - 1` applications of the corresponding predicate, otherwise no applications of the predicate. For each element erased as a result of this function call, at worst 𝒪(log n) in the capacity of the block containing the element. Additionally, if any active blocks become empty of elements as a result of the function call, at worst linear in the number of element blocks.

    ] 

    template<class BinaryPredicate = equal_to<T>>
  size_type unique(BinaryPredicate binary_pred = BinaryPredicate());

    -7- Preconditions: […]

    -8- Effects: […]

    -9- Returns: […]

    -10- Throws: […]

    -11- Complexity: If `empty()` is `false`, exactly `size() - 1` applications of the corresponding predicate, otherwise no applications of the predicate. Additionally, for each element erased as a result of this function call, at worst 𝒪(log n) in the capacity of each block containing the element.

    -12- Remarks: […]

History
Date User Action Args
2025-09-21 09:45:05adminsetmessages: + msg15076
2025-08-23 12:01:44adminsetmessages: + msg14947
2025-08-19 00:00:00admincreate