std::projected cannot handle proxy iterator
Hewill Kang

Created on 2023-01-24.00:00:00 last changed 1 week ago


Date: 2023-03-22.00:00:00

[ 2023-03-22 Resolved by the adoption of P2609R3 in Issaquah. Status changed: New → Resolved. ]

Date: 2023-02-15.00:00:00

[ 2023-02-06; Reflector poll ]

Set priority to 3 after reflector poll.

This wording is relative to N4928.

[Drafting note: The proposed resolution is to alias projected as I when the projection function is exactly identity. This form of type aliasing has similarities to the proposed wording of P2538R1, except for the nested struct type. — end drafting note]

  1. Modify [iterator.synopsis], header <iterator> synopsis, as indicated:

    namespace std {
      // [projected], projected
      template<indirectly_readable I, indirectly_regular_unary_invocable<I> Proj>
        usingstruct projected = see below;                         // freestanding
      template<weakly_incrementable I, class Proj>
        struct incrementable_traits<projected<I, Proj>>;           // freestanding
  2. Modify [projected] as indicated:

    -1- Class template projected is used to constrain algorithms that accept callable objects and projections ([defns.projection]). It combines a indirectly_readable type I and a callable object type Proj into a new indirectly_readable type whose reference type is the result of applying Proj to the iter_reference_t of I.

    namespace std {
      template<classindirectly_readable I, classindirectly_regular_unary_invocable<I> Proj>
      struct projected-implprojected { // exposition only
        using value_type = remove_cvref_t<indirect_result_t<Proj&, I>>;
        using difference_type = iter_difference_t<I>;               // present only if I models weakly_incrementable
        indirect_result_t<Proj&, I> operator*() const;              // not defined
      template<weakly_incrementable I, class Proj>
      struct incrementable_traits<projected<I, Proj>> {
        using difference_type = iter_difference_t<I>;
      template<indirectly_readable I, indirectly_regular_unary_invocable<I> Proj>
        using projected = conditional_t<same_as<Proj, identity>, I, projected-impl<I, Proj>>;
Date: 2023-01-24.00:00:00

Currently, std::projected is heavily used in <algorithm> to transform the original iterator into a new readable type for concept checking, which has the following definition:

template<indirectly_readable I, indirectly_regular_unary_invocable<I> Proj>
struct projected {
  using value_type = remove_cvref_t<indirect_result_t<Proj&, I>>;
  indirect_result_t<Proj&, I> operator*() const;              // not defined

It provides the member type value_type, which is defined as the cvref-unqualified of a projection function applied to the reference of the iterator, this seems reasonable since this is how iterators are usually defined for the value type.

However, this does not apply to C++20 proxy iterators such as zip_view::iterator, we cannot obtain the tuple of value by simply removing the cvref-qualifier of the tuple of reference.
This incorrect definition allows us to unethically bypass the constraint checking of the constraint algorithm, for example:

#include <algorithm>
#include <ranges>
#include <vector>

struct Cmp {
  bool operator()(std::tuple<int&>, std::tuple<int&>) const;
  bool operator()(auto, auto) const = delete;

int main() {
  std::vector<int> v;
  std::ranges::sort(std::views::zip(v), Cmp{}); // hard error

In the above example, the value type and reference of the original iterator I are tuple<int> and tuple<int&> respectively, however, the value type and reference of projected<I, identity> will be tuple<int&> and tuple<int&>&&, which makes the constraint only require that the comparator can compare two tuple<int&>s, resulting in a hard error in the implementation.

Date User Action Args
2023-03-23 11:42:08adminsetstatus: new -> resolved
2023-02-06 15:13:50adminsetmessages: + msg13269
2023-01-28 12:44:11adminsetmessages: + msg13219
2023-01-24 00:00:00admincreate