Home 实现一个zip (for C++20)
Post
Cancel

实现一个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::vectorstd::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适配

我们需要定制标准库缺失的zipzip_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

This post is licensed under CC BY 4.0 by the author.
Contents