<xutility>: Evil member element_type can break non-ranges algorithms since C++20 #4436
Description
Describe the bug
Currently, MSVC STL defines _Iter_value_t in term of iter_value_t since C++20 and uses it in non-ranges algorithms.
Lines 1167 to 1168 in 8b081e2
Lines 1177 to 1178 in 8b081e2
Per [readable.traits], if a type I has mismatched member types value_type and element_type, then iter_value_t<I> is ill-formed by default (when there's no program-defined indirectly_readable_traits or iterator_traits specializations), and thus I doesn't satisfy any C++20 meow_iterator concept. However, I can still meet Cpp17MeowIterator requirements because the legacy requirements don't consider element_type, so such strategy sometimes rejects valid programs.
For example, this example should be valid since C++17. But MSVC STL starts to reject it since C++20 while other implementations don't (Godbolt link).
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <iterator>
#include <type_traits>
template <class T>
struct evil_contiguous_iterator {
T* ptr;
template <class CT = const T, std::enable_if_t<!std::is_const_v<T>, int> = 0>
constexpr operator evil_contiguous_iterator<CT>() const noexcept {
return {ptr};
}
using value_type = std::remove_cv_t<T>;
using reference = T&;
using pointer = T*;
using difference_type = std::ptrdiff_t;
using iterator_category = std::random_access_iterator_tag;
using element_type = void; // This is EVIL but shouldn't affect non-ranges algorithms.
friend constexpr bool operator==(evil_contiguous_iterator i, evil_contiguous_iterator j) noexcept {
return i.ptr == j.ptr;
}
friend constexpr bool operator!=(evil_contiguous_iterator i, evil_contiguous_iterator j) noexcept {
return i.ptr != j.ptr;
}
friend constexpr bool operator<(evil_contiguous_iterator i, evil_contiguous_iterator j) noexcept {
return i.ptr < j.ptr;
}
friend constexpr bool operator>(evil_contiguous_iterator i, evil_contiguous_iterator j) noexcept {
return i.ptr > j.ptr;
}
friend constexpr bool operator<=(evil_contiguous_iterator i, evil_contiguous_iterator j) noexcept {
return i.ptr <= j.ptr;
}
friend constexpr bool operator>=(evil_contiguous_iterator i, evil_contiguous_iterator j) noexcept {
return i.ptr >= j.ptr;
}
constexpr evil_contiguous_iterator& operator++() noexcept {
++ptr;
return *this;
}
constexpr evil_contiguous_iterator operator++(int) noexcept {
auto that = *this;
++*this;
return that;
}
constexpr evil_contiguous_iterator& operator--() noexcept {
--ptr;
return *this;
}
constexpr evil_contiguous_iterator operator--(int) noexcept {
auto that = *this;
--*this;
return that;
}
constexpr evil_contiguous_iterator& operator+=(difference_type n) noexcept {
ptr += n;
return *this;
}
constexpr evil_contiguous_iterator& operator-=(difference_type n) noexcept {
ptr -= n;
return *this;
}
friend constexpr evil_contiguous_iterator operator+(evil_contiguous_iterator i, difference_type n) noexcept {
return {i.ptr + n};
}
friend constexpr evil_contiguous_iterator operator+(difference_type n, evil_contiguous_iterator i) noexcept {
return {i.ptr + n};
}
friend constexpr evil_contiguous_iterator operator-(evil_contiguous_iterator i, difference_type n) noexcept {
return {i.ptr - n};
}
friend constexpr difference_type operator-(evil_contiguous_iterator i, evil_contiguous_iterator j) noexcept {
return i.ptr - j.ptr;
}
constexpr T& operator*() const noexcept {
return *ptr;
}
constexpr T& operator[](difference_type n) const noexcept {
return ptr[n];
}
constexpr T* operator->() const noexcept {
return ptr;
}
};
int main() {
int a[]{4, 2, 1, 7, 2, 9};
std::sort(evil_contiguous_iterator<int>{std::begin(a)}, evil_contiguous_iterator<int>{std::end(a)});
}Expected behavior
This example compiles in C++20/23 modes as in C++17.
STL version
Probably every version from 1e8b8d4 to 8b081e2.
Additional context
WG21-P2408R5 complicated the situation.
- As of C++23, requirements on constant iterators for non-ranges algorithms were changed to
meowiteratorconcepts, which would newly require well-formedness ofiter_value_tin some cases. Butstd::sortwasn't affected. - However, as implied the 6.2. section of the paper, such breakage was unlikely found by the author, and thus was possibly unintended.
- MSVC STL implemented the changes in C++20 mode and permitted both
meowiteratorand Cpp17MeowIterator.