4029. basic_string accidentally fails to meet the reversible container requirements

Section: 27.4.3.1 [basic.string.general] Status: New Submitter: Jan Schultke Opened: 2023-12-18 Last modified: 2024-03-15

Priority: 3

View all other issues in [basic.string.general].

View all issues with New status.

Discussion:

The complexity requirements for a reversible container (23.2.2.3 [container.rev.reqmts]) are that each function must have constant complexity. The corresponding member functions in 27.4.3.4 [string.iterators] have no complexity requirements, and basic_string unintentionally is not a reversible container (unless the implementation coincidentally provides constant complexity member functions).

[2024-03-15; Reflector poll]

Set priority to 3 after reflector poll.

Could harmonize with vector by saying: "A basic_string meets all of the requirements of a contiguous container (23.2.2.2 [container.reqmts]) and of a reversible container (23.2.2.3 [container.rev.reqmts])." It's not a sequence container (see LWG 718) but as per 23.2.2.5 [container.alloc.reqmts] p1 it is allocator-aware (although it doesn't use construct and destroy).

Not comfortable removing the detailed descriptions for those members. We don't have the "Descriptions are only provided here for operations on [...] that are not described in one of these tables" wording that the containers have.

Proposed resolution:

This wording is relative to N4971.

[Drafting Note: The proposed wording is similar to the specification in 23.3.11.1 [vector.overview] p2 and suggests to simply strike 27.4.3.4 [string.iterators] because it doesn't say anything new compared to 23.2.2.2 [container.reqmts] and 23.2.2.3 [container.rev.reqmts].

Alternatively, one could add a

Complexity: Constant.

paragraph to each function in 27.4.3.4 [string.iterators], but that would be less clearer and would not explicitly say basic_string meets the reversible container requirements. ]

1. Modify 27.4.3.1 [basic.string.general] as indicated:

   -2- A specialization of basic_string is a contiguous container (23.2.2.2 [container.reqmts]) and a reversible container (23.2.2.3 [container.rev.reqmts]).

   -3- In all cases, [data(), data() + size()] is a valid range, data() + size() points at an object with value charT() (a "null terminator"), and size() <= capacity() is true.

   namespace std {
     template<class charT, class traits = char_traits<charT>,
              class Allocator = allocator<charT>>
     class basic_string {
       […]
       // 27.4.3.4 [string.iterators], iterators
       constexpr iterator begin() noexcept;
       constexpr const_iterator begin() const noexcept;
       constexpr iterator end() noexcept;
       constexpr const_iterator end() const noexcept;
     
       constexpr reverse_iterator rbegin() noexcept;
       constexpr const_reverse_iterator rbegin() const noexcept;
       constexpr reverse_iterator rend() noexcept;
       constexpr const_reverse_iterator rend() const noexcept;
     
       constexpr const_iterator cbegin() const noexcept;
       constexpr const_iterator cend() const noexcept;
       constexpr const_reverse_iterator crbegin() const noexcept;
       constexpr const_reverse_iterator crend() const noexcept;
     
       // 27.4.3.5 [string.capacity], capacity
       […]
     };
     […]
   }
   

   […]

2. Remove subclause 27.4.3.4 [string.iterators] in its entirety:

   23.4.3.4 Iterator support [string.iterators]

   constexpr iterator begin() noexcept;
   constexpr const_iterator begin() const noexcept;
   constexpr const_iterator cbegin() const noexcept;
   

   -1- Returns: An iterator referring to the first character in the string.

   […]

   constexpr reverse_iterator rend() noexcept;
   constexpr const_reverse_iterator rend() const noexcept;
   constexpr const_reverse_iterator crend() const noexcept;
   

   -4- Returns: An iterator which is semantically equivalent to reverse_iterator(begin()).