This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of NAD status.

### 2852. Specifications of `operator==` for `std::basic_string`s and `std::basic_string_view`s are difficult to conform to

Section: 21.3.4.2 [string.cmp], 21.3.3.8.4 [string.compare] Status: NAD Submitter: Ahti Leppänen Opened: 2017-01-09 Last modified: 2021-06-06

Priority: 2

View all issues with NAD status.

Discussion:

Currently (N4618, 2016-11-28) the specification of `operator==` for `std::basic_string` and `std::basic_string_view` objects is clearly defined, but when interpreted as written, it may lead to comparison of strings of different sizes being a 𝒪(n) operation instead of a simple size check. Actual implementations in standard libraries vary so that in practice the programmers can't rely neither on having the literal version of the standard specification nor reasonable performance characteristics.

The definition for `basic_string operator==` in N4618 is as follows:

> [string.operator==]

>     bool operator==(const basic_string<charT, traits, Allocator>& lhs,
>                     const basic_string<charT, traits, Allocator>& rhs) noexcept;

> > -1- Returns: `lhs.compare(rhs) == 0`.

> 21.3.3.8.4 [string.compare]

>     int compare(const basic_string& str) const noexcept;

> > -6- Effects: Equivalent to: `return compare(basic_string_view<charT, traits>(str));`

> 21.3.3.8.4 [string.compare]

>     int compare(basic_string_view<charT, traits> sv) const noexcept;

> > -1- Effects: Determines the effective length `rlen` of the strings to compare as the smaller of `size()` and `sv.size()`. The function then compares the two strings by calling `traits::compare(data(), sv.data(), rlen)`.

> > -2- Returns: The nonzero result if the result of the comparison is nonzero. Otherwise, returns a value as indicated in Table 63.

> > Table 63 — `compare()` results
> > Condition | Return Value
> > --- | ---
> > `size() < sv.size()` | `< 0`
> > `size() == sv.size()` | `0`
> > `size() > sv.size()` | `> 0`

From these it seems that `compare()` of strings of different sizes can't return zero and `operator==` will return `false`. However some implementations do not seem to call `traits::compare()` for `basic_string`s of different sizes even when the traits and it's `compare()` are user-defined. And those that call, make the `operator==` a worst case 𝒪(n) operation even for strings of different sizes.

This defect report does not propose a wording, but on a general level the wording should allow standard library implementers to write a standard conforming `operator==` for `basic_string` and `basic_string_view` (others?) in such a way that it's performance characteristics are reasonable and the programmers can rely on having a consistent behaviour across implementations. Perhaps the key issue here is that `operator==` is defined through `compare() == 0`: while it returns the intended result, for some inputs it does computations that are not needed by `operator==`. There are also related specifications that may need to be revised, for example `operator!=` for `basic_string_view`s is defined in 21.4.5 [string.view.comparison] as

> Returns: `lhs.compare(rhs) != 0`

[2017-01-26, Jonathan Wakely comments and provides proposed resolution]

As mentioned above, some implementations do not make a call to `Traits::compare` if the string lengths are not equal, even though in general this is an observable side effect. Some implementations only perform that optimisation for `std::string` and `std::wstring`, where we know that calls to `std::char_traits<char>::compare` and `std::char_traits<wchar_t>::compare` are not observable.

My reading is that the Returns: element describes the value that must be returned, not the precise steps that must be taken to calculate that value. If we intended to specify the precise steps that must be taken then we could say that using "Effects: Equivalent to […]", but we don't do that.

I would prefer this issue to be closed NAD with the rationale that my reading is correct and comparing the lengths to avoid calling `Traits::compare` is already permitted. But if my reading is wrong we need to permit this obvious optimisation.

[2017-01-27 Telecon]

Priority 2

[2017-02-04, Ahti Leppänen comments and recommends NAD]

While there seems to be varying interpretations of the standards wording, given the comments in this defect report and definitions in [structure.specification] (N4618):

> Effects: the actions performed by the function

> Returns: a description of the value(s) returned by the function

I fail to see that the specification of `operator==` "Returns: `lhs.compare(rhs) == 0`" would require call to `compare()` and no longer consider the report valid.

[2016-07, Toronto Saturday afternoon issues processing]

Status to NAD; we accept Jonathan's reasoning. Note that several implementations do this today.

Proposed resolution:

This wording is relative to N4618.

1. Preferred: NAD

2. Alternative:

   1. Modify [string.operator==] p1 as shown:

      >     template<class charT, class traits, class Allocator>
      >       bool operator==(const basic_string<charT, traits, Allocator>& lhs,
      >                       const basic_string<charT, traits, Allocator>& rhs) noexcept;

      > > -1- Returns: `lhs.size() == rhs.size() && lhs.compare(rhs) == 0`.

   2. Modify 21.4.5 [string.view.comparison] as shown:

      > [Example: A sample conforming implementation for `operator==` would be:

      >     template<class T> using __identity = decay_t<T>;
      >     template<class charT, class traits>
      >       constexpr bool operator==(basic_string_view<charT, traits> lhs,
      >                                 basic_string_view<charT, traits> rhs) noexcept {
      >         return lhs.size() == rhs.size() && lhs.compare(rhs) == 0;
      >       }
      >     template<class charT, class traits>
      >       constexpr bool operator==(basic_string_view<charT, traits> lhs,
      >                                 __identity<basic_string_view<charT, traits>> rhs) noexcept {
      >         return lhs.size() == rhs.size() && lhs.compare(rhs) == 0;
      >       }
      >     template<class charT, class traits>
      >       constexpr bool operator==(__identity<basic_string_view<charT, traits>> lhs,
      >                                 basic_string_view<charT, traits> rhs) noexcept {
      >         return lhs.size() == rhs.size() && lhs.compare(rhs) == 0;
      >       }

      > — end example]

      >     template<class charT, class traits>
      >       constexpr bool operator==(basic_string_view<charT, traits> lhs,
      >                                 basic_string_view<charT, traits> rhs) noexcept;

      > > -2- Returns: `lhs.size() == rhs.size() && lhs.compare(rhs) == 0`.

      >     template<class charT, class traits>
      >       constexpr bool operator!=(basic_string_view<charT, traits> lhs,
      >                                 basic_string_view<charT, traits> rhs) noexcept;

      > > -3- Returns: `lhs.size() != rhs.size() || lhs.compare(rhs) != 0`.