实现一个 zip (for C++20)

众所周知，C++20 引进了 Ranges 标准库。然而搞笑的是没有完全引进，比如 std::views::zip 是直到 C++23 才进入标准。

因此本文的目的是为 C++20 Ranges 提供一个简单的 zip（为 实现一个 xyz 系列添砖加瓦！），顺便了解 Ranges 标准库的定制流程。

基本概念

（本章假定读者至少用过一次 Ranges。）

std::ranges 标准库有两个基本概念：range 和 view。

  /// [range.range] The range concept.
  template<typename _Tp>
    concept range = requires(_Tp& __t)
      {
        ranges::begin(__t);
        ranges::end(__t);
      };

什么是 range？看上面标准库 libstdc++ 的实现代码，它通过一个 concept 来描述自身的定义。一般情况下，存在 begin() 和 end() 的类型就是一个 range。对于传统容器来说，std::vector 和 std::string 等容器都是 range。

  /// [range.view] The ranges::enable_view boolean.
  template<typename _Tp>
    inline constexpr bool enable_view = derived_from<_Tp, view_base>
      || __detail::__is_derived_from_view_interface<_Tp>;

  /// [range.view] The ranges::view concept.
  template<typename _Tp>
    concept view
      = range<_Tp> && movable<_Tp> && enable_view<_Tp>;

什么是 view？很显然，派生自 std::ranges::view_base 或者 std::ranges::view_interface<...> 的可移动 range 类型就是 view。那么落地到具体代码，哪些类型是 view？简单的理解是 std::views 命名空间提供的 range 适配器 均会生成 view。假设存在 std::vector vec，执行 vec | transform(...) 得到的返回即 view；管道操作（operator |）也是可以接收 view 的，因此 view 之间的组合会生成新的 view。

NOTE: std::ranges::view_base 是一个空实现。

也就是说执行转换的对象是 view 而非容器（原有 range）本身，这样做就可以在容器外提供惰性计算和值语义。剩下的事情就靠 view 提供的迭代器 iterator 来完成，但是对于完成结果的收集来说，通常会使用到 C++11 的 range-based for 循环和 C++17 的结构化绑定，迭代器的存在感可以说是微乎其微。

NOTE: 关于值语义，通常来说 view 不具有数据的所有权，大部分场景下使用拷贝操作很廉价。

NOTE: 关于惰性求值，简单来说就是把组合的 view 类型信息放到模板中，并且嵌套存放 view 使得可以延迟到最后一刻再执行操作，这种做法要求用户使用 auto 推导 view 具体类型（因为很难正确得知复杂的组合后的 view 类型）。

如果不需要定制，那么对 view 的理解到这里其实也足够了。简单来说就是：

• 使用管道操作来组合算法。
• 鼓励使用拷贝而非引用或移动来提高代码安全和可读性。

range 适配

我们需要定制标准库缺失的 zip 和 zip_view（前者视为一个定制点以及 zip_view 工厂），最直接的问题是构造函数和工厂函数该如何同时处理 range 和 view。因为就算是接口也会有麻烦的情况，比如：zip(view, range, view...)。

NOTE: 标准中的 zip 允许接收可适配为 view 的 range：

// cppreference 示例：
template< ranges::viewable_range... Rs >
    requires /* see below */
constexpr auto zip( Rs&&... rs );

/*
1) zip_view is a range adaptor that takes one or more views, and produces a view whose ith element
 is a tuple-like value consisting of the ith elements of all views. The size of produced view is
 the minimum of sizes of all adapted views.
2) views::zip is a customization point object.
When calling with no argument, views::zip() is expression-equivalent to
 auto(views::empty<std::tuple<>>).
Otherwise, views::zip(rs...) is expression-equivalent to
 ranges::zip_view<views::all_t<decltype((rs))>...>(rs...).
*/

最简单的做法是使用已有的 range 适配器 std::views::all。对于一个 range，通过 range | all 即可得到一个原封不动的 view：

#include <ranges>
#include <vector>

int main() {
    std::vector vec {998, 244, 353};
    using namespace std::ranges;
    static_assert(!view<decltype(vec)>);
    static_assert(view<decltype(vec | views::all)>);
}

也就是说使用 all 后，我们的定制 zip 就可以一致的只处理 view。

NOTE: 事实上 libstdc++ 标准库的 C++23 zip 也是这种实现方式。

inline constexpr struct Zip_fn {
    template <std::ranges::input_range ...Rs>
    [[nodiscard]]
    constexpr auto operator()(Rs &&...rs) const {
        if constexpr (sizeof...(rs) == 0) {
            return std::views::empty<std::tuple<>>;
        } else {
            return Zip_view<std::views::all_t<Rs>...>(std::forward<Rs>(rs)...);
        }
    }
} zip;

如上，接口搞定后，Zip_view 就是后续实现的关键。有点小细节是空的 range 就返回 empty。

NOTE: 考虑到这是一个丐版 zip，后续对 requires/concept 部分比较随意（放过我吧），可假定为最终只处理符合 random_access_range 要求的 range 或者 view。

view 概念

前面基本概念中提到 view 需要继承 view_base 或者 view_interface<...>。如无特殊情况，我推荐使用后者。因为前者是一个空实现，后者只要继承并使用 CRTP，就能得到一系列的便利函数而无需再次实现，包括 empty()、operator bool() 和 front() / back() 等函数。

cppreference提供的例子如下：

// view_interface is typically used with CRTP:
class my_view : public std::ranges::view_interface<my_view>
{
public:
    auto begin() const { /*...*/ }
    auto end() const { /*...*/ }
    // empty() is provided if begin() returns a forward iterator
    // and end() returns a sentinel for it.
};

所以 Zip_view 也可以照着模板做一遍：

template <std::ranges::input_range ...Views>
class Zip_view : public std::ranges::view_interface<Zip_view<Views...>> {
  // ...
};

从现在起 Zip_view 就是 view 了！

view 细分

前面说到 std::views::all 适配器，它可以做到一切皆 view 的效果。但有必要往 all 里面看一眼，这里关乎实现上的正确认知。

    // 标准库参考
    struct _All  // : ...
    {
      // ...
      template<viewable_range _Range>
        requires view<decay_t<_Range>>
          || __detail::__can_ref_view<_Range>
          || __detail::__can_owning_view<_Range>
        constexpr auto
        operator() [[nodiscard]] (_Range&& __r) const
        noexcept(_S_noexcept<_Range>())
        {
          if constexpr (view<decay_t<_Range>>)
            return std::forward<_Range>(__r);
          else if constexpr (__detail::__can_ref_view<_Range>)
            return ref_view{std::forward<_Range>(__r)};
          else
            return owning_view{std::forward<_Range>(__r)};
        }
    };

转译为文字含义就是：

• 如果已经是 view，那原封完美转发。
• 如果还不是 view，但是可以引用，将适配为 std::ranges::ref_view。
• 既不是 view 也不能引用，将适配为 std::ranges::owning_view。

我们通常用到的 view 是不持有数据所有权的 ref_view，正如前面所说的，可拷贝且低成本。但是需要注意 owning_view，这种是持有唯一所有权的视图。一个例子是被移动的容器：

#include <ranges>
#include <vector>

int main() {
    std::vector eXpiring {998, 244, 353};
    // true
    static_assert(std::same_as<
            decltype(std::move(eXpiring) | std::views::all), 
            decltype(std::ranges::owning_view{std::move(eXpiring)})>);
}

那么这和实现有什么关系，考虑到构造函数的要求：

// std::ranges::zip_view<Views...>::zip_view
// C++ Ranges library std::ranges::zip_view 
zip_view() = default;                 // (1)	(since C++23)
constexpr zip_view( Views... views ); // (2)	(since C++23)

这个 views 在后续初始化列表中只能移动而非拷贝，否则无法处理 owning 形式的 view。因为 owning_view 根本不支持拷贝，但是 view 肯定符合可移动的 concept。

template <std::ranges::input_range ...Views>
class Zip_view : public std::ranges::view_interface<Zip_view<Views...>> {
public:
    // ...
    Zip_view() = default;
    // Views are cheap to copy, but owning views cannot be done. (= delete)
    constexpr Zip_view(Views ...vs) noexcept: _views(std::move(vs)...) {}
    // ...
};

这里 _views 是按 tuple 形式去存放，并且都是经过 all 组合后的 view。

iterator 改进

Ranges 对于迭代器也有改进，begin() 和 end() 不再要求是同一类型：可以使用 sentinel 去描述哨兵。这方面的好处可以看N4128 的附录，这里提出来只是因为要写这个类型。

NOTE: 保持原有的同类型设计也不影响定制 zip，只是当前实现是尝试将 sentinel 用于 end()。

NOTE: 另外还有 borrowed iterator 这种描述迭代器引用的生命周期可超越原有 range 的类型提示，也许对某些实现可以提供新的思路。这些有需要再去了解吧。

template <std::ranges::input_range ...Views>
class Zip_view : public std::ranges::view_interface<Zip_view<Views...>> {
public:
    struct iterator;
    struct sentinel;
  // ...
};

哨兵的实现其实只需要满足 operator==，代码比较短可以直接展示全貌：

template <std::ranges::input_range ...Views>
struct Zip_view<Views...>::sentinel {
    sentinel() = default;
    constexpr sentinel(Zip_view *this_zip) noexcept: _this_zip(this_zip) {}

    friend bool operator==(const iterator &x, const sentinel &y) {
        return [&]<auto ...Is>(std::index_sequence<Is...>) {
            return ((std::get<Is>(x._currents) ==
                        std::ranges::end(std::get<Is>(y._this_zip->_views))) || ...);
        }(std::make_index_sequence<sizeof...(Views)>{});
    }

private:
    Zip_view *_this_zip;
};

这里 operator== 的意思是跟复合迭代器 iterator 中所有的子迭代器 _currents 比较，任意一个到达 end() 即为 true。

剩余要求

对于一个 zip_view 的完整函数要求可以看 cppreference。我做了点裁剪（偷懒）。

Zip_view 需要实现：

• begin()
• end()
• size()

Zip_view::iterator 需要实现：

• typenames
• operator* / operator[]
• operator+ / operator++ / operator+=
• operator== / operator<=>

Zip_view 部分

template <std::ranges::input_range ...Views>
class Zip_view : public std::ranges::view_interface<Zip_view<Views...>> {
public:
    struct iterator;
    struct sentinel;

public:
    Zip_view() = default;
    // Views are cheap to copy, but owning views cannot be done. (= delete)
    constexpr Zip_view(Views ...vs) noexcept: _views(std::move(vs)...) {}
    constexpr auto begin() {
        return std::apply([&](Views &...views) { return iterator(views...); }, _views);
    }
    constexpr auto end() requires (std::ranges::random_access_range<Views> && ...) {
        return sentinel{this};
    }
    constexpr auto size() const requires (std::ranges::sized_range<Views> && ...) {
        return std::apply([&](auto &&...views)
            { return std::min({std::ranges::size(views)...}); }, _views);
    }

private:
    std::tuple<Views...> _views;
};

由于实现了 sentinel，对于 end()，只需构造一个 sentinel 即可，传入 this 是为了能用到 _views。

对于 size() 则是一个萃取算出 std::min 的过程，因为 range 之间的长度是允许不等长的，这块需要用到 std::tuple 常用的萃取函数。

剩下的工作就是 begin() 与 iterator，先传入每一个 view 再做打算吧（肯定用得到）。

iterator 部分

iterator 的整体思路就是做一个复合的迭代器。

template <std::ranges::input_range ...Views>
struct Zip_view<Views...>::iterator {
    friend struct sentinel;
    // TODO: flexible iterator_concepts.
    using iterator_concept = std::random_access_iterator_tag;
    using iterator_category = std::input_iterator_tag;
    using value_type = std::tuple<std::ranges::range_value_t<Views>...>;
    using difference_type = std::common_type_t<std::ranges::range_difference_t<Views>...>;

    // ...
};

typenames 指的是一些迭代器中需要定义的成员类型，这里的链接给出了详细的说明，如前面所说，我这里实际固定了随机访问的标签，简化了实现（后面距离 +1 都可以用距离+n 的函数复用）但是限制了泛型用途。

    iterator() = default;
    constexpr iterator(Views &...views): _currents{std::ranges::begin(views)...} {}

    // ...

    std::tuple<std::ranges::iterator_t<Views>...> _currents;

构造函数使得可以让 Zip_view 返回一个 begin() 迭代器，其实 zip 确实没啥好说的，就是 tuple 封包解包的过程。实现它是为了能与整个 Ranges 库组合起来。

    constexpr auto operator[](difference_type n) const {
        auto tmp = *this;
        tmp.operator+=(n);
        return tmp;
    }

    constexpr iterator& operator++() {
        return this->operator+=(1);
    }

    constexpr iterator operator++(int) {
        auto tmp = *this;
        this->operator+=(1);
        return tmp;
    }
    constexpr iterator& operator+=(difference_type n) {
        std::apply([&](auto &...iters) { ((iters += n),...); }, _currents);
        return *this;
    }

距离相关的操作如上，只需实现+=n，其它的就可以简单实现，这是因为我在前面已经限制了只作为随机访问迭代器来使用，显然对于单向 forward 的应该做更好的支持。另外提个小插曲，我想过直接用 return iterator(_this_zip, (views | std::ranges::drop(n))...) 来完成 operator[](n)，太疯狂了明显是错的。

friend constexpr auto operator<=>(const iterator &x, const iterator &y) = default;

判等或偏序的操作，就交给默认实现吧，只要子迭代器支持完善，默认实现即可满足要求。

    constexpr auto operator*() const {
        return std::apply([&](auto &&...iters) {
            // No <auto> decay!
            // Example: zip(views::iota(1, 5), named_vector_of_int).
            // Return: std::tuple<int, int&>.
            return std::tuple<decltype(*iters)...>((*iters)...);
        }, _currents);
    }

operator* 值得一提，需要返回的 std::tuple 内的元素类型 E 应该同时支持值 E 与引用 E& 的类型（取决于子迭代器的 operator* 操作）。如果只支持 E&，那么类似 std::views::iota('A', 'Z') 这种迭代只产出右值的 view 就无法被 zip 接收。所以迭代器解引用的过程是提供拷贝还是传递引用要区分开来。

完整示例

#include <array>
#include <ranges>
#include <tuple>
#include <iostream>
#include <algorithm>
#include <vector>
#include <format>
#include <cassert>

namespace punipuni {

template <std::ranges::input_range ...Views>
class Zip_view : public std::ranges::view_interface<Zip_view<Views...>> {
public:
    struct iterator;
    struct sentinel;

public:
    Zip_view() = default;
    // Views are cheap to copy, but owning views cannot be done. (= delete)
    constexpr Zip_view(Views ...vs) noexcept: _views(std::move(vs)...) {}
    constexpr auto begin() {
        return std::apply([&](Views &...views) { return iterator(views...); }, _views);
    }
    constexpr auto end() requires (std::ranges::random_access_range<Views> && ...) {
        return sentinel{this};
    }
    constexpr auto size() const requires (std::ranges::sized_range<Views> && ...) {
        return std::apply([&](auto &&...views)
            { return std::min({std::ranges::size(views)...}); }, _views);
    }

private:
    std::tuple<Views...> _views;
};

template <std::ranges::input_range ...Views>
struct Zip_view<Views...>::iterator {
    friend struct sentinel;
    // TODO: flexible iterator_concepts.
    using iterator_concept = std::random_access_iterator_tag;
    using iterator_category = std::input_iterator_tag;
    using value_type = std::tuple<std::ranges::range_value_t<Views>...>;
    using difference_type = std::common_type_t<std::ranges::range_difference_t<Views>...>;

    iterator() = default;
    constexpr iterator(Views &...views): _currents{std::ranges::begin(views)...} {}

    constexpr auto operator*() const {
        return std::apply([&](auto &&...iters) {
            // No <auto> decay!
            // Example: zip(views::iota(1, 5), named_vector_of_int).
            // Return: std::tuple<int, int&>.
            return std::tuple<decltype(*iters)...>((*iters)...);
        }, _currents);
    }

    constexpr auto operator[](difference_type n) const {
        auto tmp = *this;
        tmp.operator+=(n);
        return tmp;
    }

    constexpr iterator& operator++() {
        return this->operator+=(1);
    }

    constexpr iterator operator++(int) {
        auto tmp = *this;
        this->operator+=(1);
        return tmp;
    }
    constexpr iterator& operator+=(difference_type n) {
        std::apply([&](auto &...iters) { ((iters += n),...); }, _currents);
        return *this;
    }

    friend constexpr auto operator<=>(const iterator &x, const iterator &y) = default;

private:
    std::tuple<std::ranges::iterator_t<Views>...> _currents;
};

template <std::ranges::input_range ...Views>
struct Zip_view<Views...>::sentinel {
    sentinel() = default;
    constexpr sentinel(Zip_view *this_zip) noexcept: _this_zip(this_zip) {}

    friend bool operator==(const iterator &x, const sentinel &y) {
        return [&]<auto ...Is>(std::index_sequence<Is...>) {
            return ((std::get<Is>(x._currents)
                        == std::ranges::end(std::get<Is>(y._this_zip->_views))) || ...);
        }(std::make_index_sequence<sizeof...(Views)>{});
    }

private:
    Zip_view *_this_zip;
};

inline constexpr struct Zip_fn {
    template <std::ranges::input_range ...Rs>
    [[nodiscard]]
    constexpr auto operator()(Rs &&...rs) const {
        if constexpr (sizeof...(rs) == 0) {
            return std::views::empty<std::tuple<>>;
        } else {
            return Zip_view<std::views::all_t<Rs>...>(std::forward<Rs>(rs)...);
        }
    }
} zip;

} // namespace punipuni

int main() {
    std::vector vec1 {"Ave", "Mujica", "Haruhikage"};
    std::array arr2 {'a', 'b', 'c', 'd', 'e'};
    std::array arr3 {1, 2, 3, 4, 5, 6, 7};
    using namespace std::literals;
    std::vector eXpiring {"Chino"s, "Cocoa"s, "Rize"s, "Syaro"s, "Chiya"s};

    // std::tuple<const char*&, char&, int&, char, std::string&>
    for(auto [s, c, i, A, X] : punipuni::zip(vec1,
                                             arr2,
                                             arr3 | std::views::drop(1),
                                             std::views::iota('A', 'Z'),
                                             std::move(eXpiring))) {
        std::cout << std::format("[{}|{}|{}|{}|{}] ", s, c, i, A, X);
        // char& refers to arr2[...].
        if(c == 'a') c = 'b';
    }
    std::cout << std::endl;

    // Modified.
    std::ranges::for_each(arr2, [](auto c) { assert(c != 'a'); });
    // Moved.
    assert(eXpiring.empty());
}

写得一般，只保证能动，可以处理常见的容器、组合过的 view 以及被移动的 range 及其各种组合。（const_iterator 和各种 concept 处于完全无视/乱写的状态😊。）

代码存放于：github。
测试结果见：godbolt。

References

std::ranges::zip_view – cppreference
Ranges for the Standard Library, Revision 1 – Open Standards