Search code examples
c++language-lawyerstdstring

Is std::basic_string a ReversibleContainer?

I was documenting a piece of code, writing that we need the chosen container to be a ReversibleContainer.
Reading in details the description for std::vector and std::basic_string:

  • For std::vector and under its member types section (iterator), we read respectively:

std::vector (for T other than bool) meets the requirements of Container, AllocatorAwareContainer(since C++11), SequenceContainer, ContiguousContainer(since C++17) and ReversibleContainer.

LegacyRandomAccessIterator and LegacyContiguousIterator to value_type

std::basic_string satisfies the requirements of AllocatorAwareContainer (except that customized construct/destroy are not used for construction/destruction of elements), SequenceContainer and ContiguousContainer(since C++17).

LegacyRandomAccessIterator and LegacyContiguousIterator to value_type

It seems to me std::basic_string meets all the requirements to be a ReversibleContainerthe same way std::vector does, yet is not described as such.
Not my question but I also do not understand why it is not described as a Container the same way std::vector is.

Any idea why it was like this?

Solution

  • The only thing I see in the reversible container requirements that isn't reflected in the specification of std::basic_string is that the rbegin/rend/crbegin/crend member functions lack the constant-time complexity requirement ([string.iterators]). std::basic_string's member functions have no such complexity guarantee.

    I am not sure whether this is intentional, since a std::basic_string has a constant time-complexity requirement on its size member function ([string.capacity]). So a std::basic_string implementation should also always be able to obtain rbegin in constant time. @JanSchultke has opened a LWG issue to propose clarifying that std::basic_string's iterator functions have constant time complexity.

    Otherwise it seems to me that they are reversible containers and the proposed resolution for the LWG issue mentioned above would clarify that std::basic_string ought to be a reversible container.