Title
Are views really supposed to have strict 𝒪(1) destruction?
Status
resolved
Section
[range.view]
Submitter
Mathias Stearn

Created on 2020-06-16.00:00:00 last changed 29 months ago

Messages

Date: 2021-10-23.00:00:00

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

Date: 2021-02-15.00:00:00

[ 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 [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]

Date: 2021-01-15.00:00:00

[ 2021-01-15; Telecon discussion ]

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

Date: 2020-06-15.00:00:00

[ 2020-06-26; Reflector prioritization ]

Set priority to 2 after reflector discussions.

Date: 2020-06-20.22:01:58

The second bullet of [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.

History
Date User Action Args
2021-10-23 11:04:22adminsetstatus: lewg -> resolved
2021-02-25 18:10:21adminsetmessages: + msg11698
2021-02-25 18:10:21adminsetmessages: + msg11697
2021-01-15 21:46:14adminsetmessages: + msg11654
2021-01-15 21:46:14adminsetstatus: new -> lewg
2020-06-26 11:48:00adminsetmessages: + msg11344
2020-06-16 00:00:00admincreate