25 Ranges library [ranges]

25.7 Range adaptors [range.adaptors]

25.7.33 Cartesian product view [range.cartesian]

25.7.33.1 Overview [range.cartesian.overview]

cartesian_product_view takes any non-zero number of ranges n and produces a view of tuples calculated by the n-ary cartesian product of the provided ranges.

The name views::cartesian_product denotes a customization point object ([customization.point.object]).

Given a pack of subexpressions Es, the expression views::cartesian_product(Es...) is expression-equivalent to

(2.1)
views::single(tuple()) if Es is an empty pack,
(2.2)
otherwise, cartesian_product_view<views::all_t<decltype((Es))>...>(Es...).

[Example 1: vector<int> v { 0, 1, 2 }; for (auto&& [a, b, c] : views::cartesian_product(v, v, v)) { cout << a << ' ' << b << ' ' << c << '\n'; } // The above prints // 0 0 0 // 0 0 1 // 0 0 2 // 0 1 0 // 0 1 1 // ... — end example]

25.7.33.2 Class template cartesian_product_view [range.cartesian.view]

namespace std::ranges { template<bool Const, class First, class... Vs> concept cartesian-product-is-random-access = // exposition only (random_access_range<maybe-const<Const, First>> && ... && (random_access_range<maybe-const<Const, Vs>> && sized_range<maybe-const<Const, Vs>>)); template<class R> concept cartesian-product-common-arg = // exposition only common_range<R> || (sized_range<R> && random_access_range<R>); template<bool Const, class First, class... Vs> concept cartesian-product-is-bidirectional = // exposition only (bidirectional_range<maybe-const<Const, First>> && ... && (bidirectional_range<maybe-const<Const, Vs>> && cartesian-product-common-arg<maybe-const<Const, Vs>>)); template<class First, class...> concept cartesian-product-is-common = // exposition only cartesian-product-common-arg<First>; template<class... Vs> concept cartesian-product-is-sized = // exposition only (sized_range<Vs> && ...); template<bool Const, template<class> class FirstSent, class First, class... Vs> concept cartesian-is-sized-sentinel = // exposition only (sized_sentinel_for<FirstSent<maybe-const<Const, First>>, iterator_t<maybe-const<Const, First>>> && ... && (sized_range<maybe-const<Const, Vs>> && sized_sentinel_for<iterator_t<maybe-const<Const, Vs>>, iterator_t<maybe-const<Const, Vs>>>)); template<cartesian-product-common-arg R> constexpr auto cartesian-common-arg-end(R& r) { // exposition only if constexpr (common_range<R>) { return ranges::end(r); } else { return ranges::begin(r) + ranges::distance(r); } } template<input_range First, forward_range... Vs> requires (view<First> && ... && view<Vs>) class cartesian_product_view : public view_interface<cartesian_product_view<First, Vs...>> { private: tuple<First, Vs...> bases_; // exposition only // [range.cartesian.iterator], class template cartesian_product_view::iterator template<bool Const> class iterator; // exposition only public: constexpr cartesian_product_view() = default; constexpr explicit cartesian_product_view(First first_base, Vs... bases); constexpr iterator<false> begin() requires (!simple-view<First> || ... || !simple-view<Vs>); constexpr iterator<true> begin() const requires (range<const First> && ... && range<const Vs>); constexpr iterator<false> end() requires ((!simple-view<First> || ... || !simple-view<Vs>) && cartesian-product-is-common<First, Vs...>); constexpr iterator<true> end() const requires cartesian-product-is-common<const First, const Vs...>; constexpr default_sentinel_t end() const noexcept; constexpr see below size() requires cartesian-product-is-sized<First, Vs...>; constexpr see below size() const requires cartesian-product-is-sized<const First, const Vs...>; }; template<class... Vs> cartesian_product_view(Vs&&...) -> cartesian_product_view<views::all_t<Vs>...>; }

🔗

constexpr explicit cartesian_product_view(First first_base, Vs... bases);

Effects: Initializes bases_ with std::move(first_base), std::move(bases)....

🔗

constexpr iterator<false> begin()
  requires (!simple-view<First> || ... || !simple-view<Vs>);

Effects: Equivalent to: return iterator<false>(*this, tuple-transform(ranges::begin, bases_));

🔗

constexpr iterator<true> begin() const
  requires (range<const First> && ... && range<const Vs>);

Effects: Equivalent to: return iterator<true>(*this, tuple-transform(ranges::begin, bases_));

🔗

constexpr iterator<false> end()
  requires ((!simple-view<First> || ... || !simple-view<Vs>)
    && cartesian-product-is-common<First, Vs...>);
constexpr iterator<true> end() const
  requires cartesian-product-is-common<const First, const Vs...>;

Let:

(4.1)
is-const be true for the const-qualified overload, and false otherwise;
(4.2)
is-empty be true if the expression ranges::empty(rng) is true for any rng among the underlying ranges except the first one and false otherwise; and
(4.3)
begin-or-first-end(rng) be expression-equivalent to is-empty ? ranges::begin(rng) : cartesian-common-arg-end(rng) if rng is the first underlying range and ranges::begin(rng) otherwise.

Effects: Equivalent to: iterator<is-const> it(*this, tuple-transform( [](auto& rng){ return begin-or-first-end(rng); }, bases_)); return it;

🔗

constexpr default_sentinel_t end() const noexcept;

Returns: default_sentinel.

🔗

constexpr see below size()
  requires cartesian-product-is-sized<First, Vs...>;
constexpr see below size() const
  requires cartesian-product-is-sized<const First, const Vs...>;

The return type is an implementation-defined unsigned-integer-like type.

Recommended practice: The return type should be the smallest unsigned-integer-like type that is sufficiently wide to store the product of the maximum sizes of all the underlying ranges, if such a type exists.

Let p be the product of the sizes of all the ranges in bases_.

Preconditions: p can be represented by the return type.

Returns: p.

25.7.33.3 Class template cartesian_product_view::iterator [range.cartesian.iterator]

namespace std::ranges { template<input_range First, forward_range... Vs> requires (view<First> && ... && view<Vs>) template<bool Const> class cartesian_product_view<First, Vs...>::iterator { public: using iterator_category = input_iterator_tag; using iterator_concept = see below; using value_type = tuple<range_value_t<maybe-const<Const, First>>, range_value_t<maybe-const<Const, Vs>>...>; using reference = tuple<range_reference_t<maybe-const<Const, First>>, range_reference_t<maybe-const<Const, Vs>>...>; using difference_type = see below; iterator() = default; constexpr iterator(iterator<!Const> i) requires Const && (convertible_to<iterator_t<First>, iterator_t<const First>> && ... && convertible_to<iterator_t<Vs>, iterator_t<const Vs>>); constexpr auto operator*() const; constexpr iterator& operator++(); constexpr void operator++(int); constexpr iterator operator++(int) requires forward_range<maybe-const<Const, First>>; constexpr iterator& operator--() requires cartesian-product-is-bidirectional<Const, First, Vs...>; constexpr iterator operator--(int) requires cartesian-product-is-bidirectional<Const, First, Vs...>; constexpr iterator& operator+=(difference_type x) requires cartesian-product-is-random-access<Const, First, Vs...>; constexpr iterator& operator-=(difference_type x) requires cartesian-product-is-random-access<Const, First, Vs...>; constexpr reference operator[](difference_type n) const requires cartesian-product-is-random-access<Const, First, Vs...>; friend constexpr bool operator==(const iterator& x, const iterator& y) requires equality_comparable<iterator_t<maybe-const<Const, First>>>; friend constexpr bool operator==(const iterator& x, default_sentinel_t); friend constexpr auto operator<=>(const iterator& x, const iterator& y) requires all-random-access<Const, First, Vs...>; friend constexpr iterator operator+(const iterator& x, difference_type y) requires cartesian-product-is-random-access<Const, First, Vs...>; friend constexpr iterator operator+(difference_type x, const iterator& y) requires cartesian-product-is-random-access<Const, First, Vs...>; friend constexpr iterator operator-(const iterator& x, difference_type y) requires cartesian-product-is-random-access<Const, First, Vs...>; friend constexpr difference_type operator-(const iterator& x, const iterator& y) requires cartesian-is-sized-sentinel<Const, iterator_t, First, Vs...>; friend constexpr difference_type operator-(const iterator& i, default_sentinel_t) requires cartesian-is-sized-sentinel<Const, sentinel_t, First, Vs...>; friend constexpr difference_type operator-(default_sentinel_t, const iterator& i) requires cartesian-is-sized-sentinel<Const, sentinel_t, First, Vs...>; friend constexpr auto iter_move(const iterator& i) noexcept(see below); friend constexpr void iter_swap(const iterator& l, const iterator& r) noexcept(see below) requires (indirectly_swappable<iterator_t<maybe-const<Const, First>>> && ... && indirectly_swappable<iterator_t<maybe-const<Const, Vs>>>); private: using Parent = maybe-const<Const, cartesian_product_view>; // exposition only Parent* parent_ = nullptr; // exposition only tuple<iterator_t<maybe-const<Const, First>>, iterator_t<maybe-const<Const, Vs>>...> current_; // exposition only template<size_t N = sizeof...(Vs)> constexpr void next(); // exposition only template<size_t N = sizeof...(Vs)> constexpr void prev(); // exposition only template<class Tuple> constexpr difference_type distance-from(const Tuple& t) const; // exposition only constexpr iterator(Parent& parent, tuple<iterator_t<maybe-const<Const, First>>, iterator_t<maybe-const<Const, Vs>>...> current); // exposition only }; }

iterator::iterator_concept is defined as follows:

(1.1)
If cartesian-product-is-random-access<Const, First, Vs...> is modeled, then iterator_concept denotes random_access_iterator_tag.
(1.2)
Otherwise, if cartesian-product-is-bidirectional<Const, First, Vs...> is modeled, then iterator_concept denotes bidirectional_iterator_tag.
(1.3)
Otherwise, if maybe-const<Const, First> models forward_range, then iterator_concept denotes forward_iterator_tag.
(1.4)
Otherwise, iterator_concept denotes input_iterator_tag.

iterator::difference_type is an implementation-defined signed-integer-like type.

Recommended practice: iterator::difference_type should be the smallest signed-integer-like type that is sufficiently wide to store the product of the maximum sizes of all underlying ranges if such a type exists.

🔗

template<size_t N = sizeof...(Vs)>
  constexpr void next();

Effects: Equivalent to: auto& it = std::get<N>(current_); ++it; if constexpr (N > 0) { if (it == ranges::end(std::get<N>(parent_->bases_))) { it = ranges::begin(std::get<N>(parent_->bases_)); next<N - 1>(); } }

🔗

template<size_t N = sizeof...(Vs)>
  constexpr void prev();

Effects: Equivalent to: auto& it = std::get<N>(current_); if constexpr (N > 0) { if (it == ranges::begin(std::get<N>(parent_->bases_))) { it = cartesian-common-arg-end(std::get<N>(parent_->bases_)); prev<N - 1>(); } } --it;

🔗

template<class Tuple>
  constexpr difference_type distance-from(const Tuple& t) const;

Let:

(7.1)
scaled-size(N) be the product of static_cast<difference_type>(ranges::size(std::get<N>(parent_->bases_))) and $scaled-size (N + 1)$ if N ≤ sizeof...(Vs), otherwise static_cast<difference_type>(1);
(7.2)
scaled-distance(N) be the product of static_cast<difference_type>(std::get<N>(current_) - std::get<N>(t)) and $scaled-size (N + 1)$ ; and
(7.3)
scaled-sum be the sum of scaled-distance(N) for every integer 0 ≤ N ≤ sizeof...(Vs).

Preconditions: scaled-sum can be represented by difference_type.

Returns: scaled-sum.

🔗

constexpr iterator(Parent& parent, tuple<iterator_t<maybe-const<Const, First>>,
  iterator_t<maybe-const<Const, Vs>>...> current);

Effects: Initializes parent_ with addressof(parent) and current_ with std::move(current).

🔗

constexpr iterator(iterator<!Const> i) requires Const &&
  (convertible_to<iterator_t<First>, iterator_t<const First>> &&
    ... && convertible_to<iterator_t<Vs>, iterator_t<const Vs>>);

Effects: Initializes parent_ with i.parent_ and current_ with std::move(i.current_).

🔗

constexpr auto operator*() const;

Effects: Equivalent to: return tuple-transform([](auto& i) -> decltype(auto) { return *i; }, current_);

🔗

constexpr iterator& operator++();

Effects: Equivalent to: next(); return *this;

🔗

constexpr void operator++(int);

Effects: Equivalent to ++*this.

🔗

constexpr iterator operator++(int) requires forward_range<maybe-const<Const, First>>;

Effects: Equivalent to: auto tmp = *this; ++*this; return tmp;

🔗

constexpr iterator& operator--()
  requires cartesian-product-is-bidirectional<Const, First, Vs...>;

Effects: Equivalent to: prev(); return *this;

🔗

constexpr iterator operator--(int)
  requires cartesian-product-is-bidirectional<Const, First, Vs...>;

Effects: Equivalent to: auto tmp = *this; --*this; return tmp;

🔗

constexpr iterator& operator+=(difference_type x)
  requires cartesian-product-is-random-access<Const, First, Vs...>;

Let orig be the value of *this before the call.

Let ret be:

(18.1)
If x > 0, the value of *this had next been called x times.
(18.2)
Otherwise, if x < 0, the value of *this had prev been called -x times.
(18.3)
Otherwise, orig.

Preconditions: x is in the range [ranges::distance(*this, ranges::begin(*parent_)),
ranges::distance(*this, ranges::end(*parent_))].

Effects: Sets the value of *this to ret.

Returns: *this.

Complexity: Constant.

🔗

constexpr iterator& operator-=(difference_type x)
  requires cartesian-product-is-random-access<Const, First, Vs...>;

Effects: Equivalent to: *this += -x; return *this;

🔗

constexpr reference operator[](difference_type n) const
  requires cartesian-product-is-random-access<Const, First, Vs...>;

Effects: Equivalent to: return *((*this) + n);

🔗

friend constexpr bool operator==(const iterator& x, const iterator& y)
  requires equality_comparable<iterator_t<maybe-const<Const, First>>>;

Effects: Equivalent to: return x.current_ == y.current_;

🔗

friend constexpr bool operator==(const iterator& x, default_sentinel_t);

Returns: true if std::get(x.current_) == ranges::end(std::get(x.parent_->bases_)) is true for any integer 0 ≤ i ≤ sizeof...(Vs); otherwise, false.

🔗

friend constexpr auto operator<=>(const iterator& x, const iterator& y)
  requires all-random-access<Const, First, Vs...>;

Effects: Equivalent to: return x.current_ <=> y.current_;

🔗

friend constexpr iterator operator+(const iterator& x, difference_type y)
  requires cartesian-product-is-random-access<Const, First, Vs...>;

Effects: Equivalent to: return iterator(x) += y;

🔗

friend constexpr iterator operator+(difference_type x, const iterator& y)
  requires cartesian-product-is-random-access<Const, First, Vs...>;

Effects: Equivalent to: return y + x;

🔗

friend constexpr iterator operator-(const iterator& x, difference_type y)
  requires cartesian-product-is-random-access<Const, First, Vs...>;

Effects: Equivalent to: return iterator(x) -= y;

🔗

friend constexpr difference_type operator-(const iterator& x, const iterator& y)
  requires cartesian-is-sized-sentinel<Const, iterator_t, First, Vs...>;

Effects: Equivalent to: return x.distance-from(y.current_);

🔗

friend constexpr difference_type operator-(const iterator& i, default_sentinel_t)
  requires cartesian-is-sized-sentinel<Const, sentinel_t, First, Vs...>;

Let end-tuple be an object of a type that is a specialization of tuple, such that:

(32.1)
std::get<0>(end-tuple) has the same value as ranges::end(std::get<0>(i.parent_->bases_));
(32.2)
std::get<N>(end-tuple) has the same value as ranges::begin(std::get<N>(i.parent_->bases_)) for every integer 1 ≤ N ≤ sizeof...(Vs).

Effects: Equivalent to: return i.distance-from(end-tuple);

🔗

friend constexpr difference_type operator-(default_sentinel_t s, const iterator& i)
  requires cartesian-is-sized-sentinel<Const, sentinel_t, First, Vs...>;

Effects: Equivalent to: return -(i - s);

🔗

friend constexpr auto iter_move(const iterator& i) noexcept(see below);

Effects: Equivalent to: return tuple-transform(ranges::iter_move, i.current_);

Remarks: The exception specification is equivalent to the logical and of the following expressions:

(36.1)
noexcept(ranges::iter_move(std::get<N>(i.current_))) for every integer
0 ≤ N ≤ sizeof...(Vs),
(36.2)
is_nothrow_move_constructible_v<range_rvalue_reference_t<maybe-const<Const, T>>>
for every type T in First, Vs....

🔗

friend constexpr void iter_swap(const iterator& l, const iterator& r) noexcept(see below)
  requires (indirectly_swappable<iterator_t<maybe-const<Const, First>>> && ... &&
        indirectly_swappable<iterator_t<maybe-const<Const, Vs>>>);

Effects: For every integer 0 ≤ i ≤ sizeof...(Vs), performs: ranges::iter_swap(std::get(l.current_), std::get(r.current_))