3452. Are views really supposed to have strict 𝒪(1) destruction?

Section: 25.4.4 [range.view] Status: Resolved Submitter: Mathias Stearn Opened: 2020-06-16 Last modified: 2021-10-23

Priority: 2

View all other issues in [range.view].

View all issues with Resolved status.

Discussion:

The second bullet of 25.4.4 [range.view] paragraph 3 says "Examples of views are:[…] A range type that holds its elements by shared_ptr and shares ownership with all its copies". That clearly does not have 𝒪(1) destruction in all cases. However, that does seem like a useful type of view, and is related to the discussions around the proposed std::generator.

What is the purpose of requiring 𝒪(1) destruction? Would it still be achieved by weakening it slightly to something like "If N copies and/or moves are made from a view that yields M values, destroying all of them takes time proportional to at worst 𝒪(N+M)"? This in particular prevents the 𝒪(N*M) case that I think the rules are trying to prevent, while still allowing some more interesting types of views.

If instead we actually really do want strict 𝒪(1) destruction, then the example needs to be fixed.

[2020-06-26; Reflector prioritization]

Set priority to 2 after reflector discussions.

[2021-01-15; Telecon discussion]

Set status to LEWG for guidance on the issue of what it means to model view.

[2021-02-16; Library Evolution Telecon Minutes]

Poll: The shared_ptr part of the example mentioned in LWG3452 should be removed. 

SF F N A SA
4  6 3 1 0

Attendance: 25

Outcome: Remove the shared_ptr part.

Previous resolution [SUPERSEDED]:

This wording is relative to N4878.

  1. Modify 25.4.4 [range.view] as indicated:

    template<class T>
  concept view =
    range<T> && movable<T> && default_initializable<T> && enable_view<T>;
    […]

    -3- [Example 1: Examples of views are:

    1. (3.1) — A range type that wraps a pair of iterators.

    2. (3.2) — A range type that holds its elements by shared_ptr and shares ownership with all its copies.

    3. (3.3) — A range type that generates its elements on demand.

    Most containers (Clause 22) are not views since destruction of the container destroys the elements, which cannot be done in constant time. — end example]

[2021-10-23 Resolved by the adoption of P2415R2 at the October 2021 plenary. Status changed: LEWG → Resolved.]

Proposed resolution: