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

3859. std::projected cannot handle proxy iterator

Section: 25.3.6.4 [projected] Status: Resolved Submitter: Hewill Kang Opened: 2023-01-24 Last modified: 2023-03-23

Priority: 3

View all other issues in [projected].

View all issues with Resolved status.

Discussion:

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.

[2023-02-06; Reflector poll]

Set priority to 3 after reflector poll.

Previous resolution [SUPERSEDED]:

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 25.2 [iterator.synopsis], header <iterator> synopsis, as indicated:

    namespace std {
      […]
      // 25.3.6.4 [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 25.3.6.4 [projected] as indicated:

    -1- Class template projected is used to constrain algorithms that accept callable objects and projections (3.42 [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>>;
    }
    

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

Proposed resolution: