Issue 2852: Specifications of operator== for std::basic_strings and std::basic_string

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

Section: 27.4.4.2 [string.cmp], 27.4.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.

27.4.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));

27.4.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

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_strings 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_views is defined in 27.3.4 [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.

Preferred: NAD

Alternative:

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.

Modify 27.3.4 [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.

2852. Specifications of operator== for std::basic_strings and std::basic_string_views are difficult to conform to

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