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.

4323. hive::unique time complexity should incorporate potential block removal complexity

Section: 23.3.9.5 [hive.operations] Status: New Submitter: Matt Bentley Opened: 2025-08-24 Last modified: 2025-08-25

Priority: Not Prioritized

View all issues with New status.

Discussion:

Currently we specify for erase 23.3.9.4 [hive.modifiers] p16:

Complexity: Linear in the number of elements erased. 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.

This is to allow for potential hive implementations as vectors of pointers to blocks, as opposed to linked-lists of blocks (reference implementation approach). In that scenario removing a block would involve a vector erasure and subsequent pointer-to-block relocations. swap-and-pop of block pointers would not work as this would re-arrange the sequence during erasure. Anyway, we have neglected to apply this same complexity to hive::unique. It would be rare that this would occur for unique, as it would involve (1) a block A with only one non-erased element left in it and (2) a block B preceding/following block A in the sequence, whose last/first element is equal to the element in block A. But it is possible, so the same consideration in terms of time complexity applies.

This is a separate but related issue to LWG 4320(i), but it would affect the outcome wording of that issue for unique.

Proposed resolution:

This wording is relative to N5014.

  1. Modify 23.3.9.5 [hive.operations] as indicated:

    [Drafting note: If issue LWG 4320(i) 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, if any active blocks become empty of elements as a result of the function call, at worst linear in the number of element blocks.

    -12- Remarks: […]