4029. basic_string accidentally fails to meet the reversible container requirements

Section: 23.4.3.1 [basic.string.general] Status: New Submitter: Jan Schultke Opened: 2023-12-18 Last modified: 2023-12-22 16:45:15 UTC

Priority: Not Prioritized

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

View all issues with New status.

Discussion:

The complexity requirements for a reversible container (24.2.2.3 [container.rev.reqmts]) are that each function must have constant complexity. The corresponding member functions in 23.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).

Proposed resolution:

This wording is relative to N4971.

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

Alternatively, one could add a

Complexity: Constant.

paragraph to each function in 23.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 23.4.3.1 [basic.string.general] as indicated:

   -2- A specialization of basic_string is a contiguous container (24.2.2.2 [container.reqmts]) and reversible container (24.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 {
       […]
       // 23.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;
     
       // 23.4.3.5 [string.capacity], capacity
       […]
     };
     […]
   }
   

   […]

2. Remove subclause 23.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()).