第 6 章 范围和视图

背景: 如何更优雅地使用<algorithm>处理containers.

6.1 简单使用 ranges和views

接口和原有的库相似.

6.1.1 将容器作为ranges传递给algorithm

#include <fmt/core.h>
#include <fmt/ranges.h>

#include <algorithm>
#include <vector>

int main() {
    std::vector<int> vec{5, 2, 3, 4, 1};
    fmt::print("vec: [{}]\n", fmt::join(vec, ", "));
    std::ranges::sort(vec);
    fmt::print("vec: [{}]\n", fmt::join(vec, ", "));
    return 0;
}

6.1.1.1 源码实现

其实就是cpo的实现逻辑, 利用ADL进行代码派发

  struct __sort_fn
  {
    template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
         typename _Comp = ranges::less, typename _Proj = identity>
      requires sortable<_Iter, _Comp, _Proj>
      constexpr _Iter
      operator()(_Iter __first, _Sent __last,
         _Comp __comp = {}, _Proj __proj = {}) const
      {
    auto __lasti = ranges::next(__first, __last);
    _GLIBCXX_STD_A::sort(std::move(__first), __lasti,
                 __detail::__make_comp_proj(__comp, __proj));
    return __lasti;
      }

    template<random_access_range _Range,
         typename _Comp = ranges::less, typename _Proj = identity>
      requires sortable<iterator_t<_Range>, _Comp, _Proj>
      constexpr borrowed_iterator_t<_Range>
      operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
      {
    return (*this)(ranges::begin(__r), ranges::end(__r),
               std::move(__comp), std::move(__proj));
      }
  };

  // 定制点对象cpo
  inline namespace __cust
  {
    inline constexpr __cust_access::_Begin begin{};
    inline constexpr __cust_access::_End end{};
    inline constexpr __cust_access::_RBegin rbegin{};
    inline constexpr __cust_access::_REnd rend{};
    inline constexpr __cust_access::_Size size{};
    inline constexpr __cust_access::_SSize ssize{};
    inline constexpr __cust_access::_Empty empty{};
    inline constexpr __cust_access::_Data data{};
  }
  //
  namespace __cust_access
  {
    using std::ranges::__detail::__maybe_borrowed_range;
    using std::__detail::__range_iter_t;

    struct _Begin
    {
    private:
      template<typename _Tp>
    static constexpr bool
    _S_noexcept()
    {
      if constexpr (is_array_v<remove_reference_t<_Tp>>)
        return true;
      else if constexpr (__member_begin<_Tp>)
        return noexcept(__decay_copy(std::declval<_Tp&>().begin()));
      else
        return noexcept(__decay_copy(begin(std::declval<_Tp&>())));
    }

    public:
      template<__maybe_borrowed_range _Tp>
    requires is_array_v<remove_reference_t<_Tp>> || __member_begin<_Tp>
      || __adl_begin<_Tp>
    constexpr auto
    operator()[[nodiscard]](_Tp&& __t) const noexcept(_S_noexcept<_Tp&>())
    {
      if constexpr (is_array_v<remove_reference_t<_Tp>>)
        {
          static_assert(is_lvalue_reference_v<_Tp>);
          return __t + 0;
        }
      else if constexpr (__member_begin<_Tp>)
        return __t.begin();
      else
        return begin(__t);
    }
    };

    template<typename _Tp>
      concept __member_end = requires(_Tp& __t)
    {
      { __decay_copy(__t.end()) } -> sentinel_for<__range_iter_t<_Tp>>;
    };

    // Poison pills so that unqualified lookup doesn't find std::end.
    void end(auto&) = delete;
    void end(const auto&) = delete;

    template<typename _Tp>
      concept __adl_end = __class_or_enum<remove_reference_t<_Tp>>
    && requires(_Tp& __t)
    {
      { __decay_copy(end(__t)) } -> sentinel_for<__range_iter_t<_Tp>>;
    };

    struct _End
    {
    private:
      template<typename _Tp>
    static constexpr bool
    _S_noexcept()
    {
      if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>)
        return true;
      else if constexpr (__member_end<_Tp>)
        return noexcept(__decay_copy(std::declval<_Tp&>().end()));
      else
        return noexcept(__decay_copy(end(std::declval<_Tp&>())));
    }

    public:
      template<__maybe_borrowed_range _Tp>
    requires is_bounded_array_v<remove_reference_t<_Tp>>
      || __member_end<_Tp> || __adl_end<_Tp>
    constexpr auto
    operator()[[nodiscard]](_Tp&& __t) const noexcept(_S_noexcept<_Tp&>())
    {
      if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>)
        {
          static_assert(is_lvalue_reference_v<_Tp>);
          return __t + extent_v<remove_reference_t<_Tp>>;
        }
      else if constexpr (__member_end<_Tp>)
        return __t.end();
      else
        return end(__t);
    }
    };

    template<typename _Tp>
      concept __member_rbegin = requires(_Tp& __t)
    {
      { __decay_copy(__t.rbegin()) } -> input_or_output_iterator;
    };

    void rbegin(auto&) = delete;
    void rbegin(const auto&) = delete;

    template<typename _Tp>
      concept __adl_rbegin = __class_or_enum<remove_reference_t<_Tp>>
    && requires(_Tp& __t)
    {
      { __decay_copy(rbegin(__t)) } -> input_or_output_iterator;
    };

    template<typename _Tp>
      concept __reversable = requires(_Tp& __t)
    {
      { _Begin{}(__t) } -> bidirectional_iterator;
      { _End{}(__t) } -> same_as<decltype(_Begin{}(__t))>;
    };

    struct _RBegin
    {
    private:
      template<typename _Tp>
    static constexpr bool
    _S_noexcept()
    {
      if constexpr (__member_rbegin<_Tp>)
        return noexcept(__decay_copy(std::declval<_Tp&>().rbegin()));
      else if constexpr (__adl_rbegin<_Tp>)
        return noexcept(__decay_copy(rbegin(std::declval<_Tp&>())));
      else
        {
          if constexpr (noexcept(_End{}(std::declval<_Tp&>())))
        {
          using _It = decltype(_End{}(std::declval<_Tp&>()));
          // std::reverse_iterator copy-initializes its member.
          return is_nothrow_copy_constructible_v<_It>;
        }
          else
        return false;
        }
    }

    public:
      template<__maybe_borrowed_range _Tp>
    requires __member_rbegin<_Tp> || __adl_rbegin<_Tp> || __reversable<_Tp>
    constexpr auto
    operator()[[nodiscard]](_Tp&& __t) const
    noexcept(_S_noexcept<_Tp&>())
    {
      if constexpr (__member_rbegin<_Tp>)
        return __t.rbegin();
      else if constexpr (__adl_rbegin<_Tp>)
        return rbegin(__t);
      else
        return std::make_reverse_iterator(_End{}(__t));
    }
    };

    template<typename _Tp>
      concept __member_rend = requires(_Tp& __t)
    {
      { __decay_copy(__t.rend()) }
        -> sentinel_for<decltype(_RBegin{}(std::forward<_Tp>(__t)))>;
    };

    void rend(auto&) = delete;
    void rend(const auto&) = delete;

    template<typename _Tp>
      concept __adl_rend = __class_or_enum<remove_reference_t<_Tp>>
    && requires(_Tp& __t)
    {
      { __decay_copy(rend(__t)) }
        -> sentinel_for<decltype(_RBegin{}(std::forward<_Tp>(__t)))>;
    };

    struct _REnd
    {
    private:
      template<typename _Tp>
    static constexpr bool
    _S_noexcept()
    {
      if constexpr (__member_rend<_Tp>)
        return noexcept(__decay_copy(std::declval<_Tp&>().rend()));
      else if constexpr (__adl_rend<_Tp>)
        return noexcept(__decay_copy(rend(std::declval<_Tp&>())));
      else
        {
          if constexpr (noexcept(_Begin{}(std::declval<_Tp&>())))
        {
          using _It = decltype(_Begin{}(std::declval<_Tp&>()));
          // std::reverse_iterator copy-initializes its member.
          return is_nothrow_copy_constructible_v<_It>;
        }
          else
        return false;
        }
    }

    public:
      template<__maybe_borrowed_range _Tp>
    requires __member_rend<_Tp> || __adl_rend<_Tp> || __reversable<_Tp>
    constexpr auto
    operator()[[nodiscard]](_Tp&& __t) const
    noexcept(_S_noexcept<_Tp&>())
    {
      if constexpr (__member_rend<_Tp>)
        return __t.rend();
      else if constexpr (__adl_rend<_Tp>)
        return rend(__t);
      else
        return std::make_reverse_iterator(_Begin{}(__t));
    }
    };

    template<typename _Tp>
      concept __member_size = !disable_sized_range<remove_cvref_t<_Tp>>
    && requires(_Tp& __t)
    {
      { __decay_copy(__t.size()) } -> __detail::__is_integer_like;
    };

    void size(auto&) = delete;
    void size(const auto&) = delete;

    template<typename _Tp>
      concept __adl_size = __class_or_enum<remove_reference_t<_Tp>>
    && !disable_sized_range<remove_cvref_t<_Tp>>
    && requires(_Tp& __t)
    {
      { __decay_copy(size(__t)) } -> __detail::__is_integer_like;
    };

    template<typename _Tp>
      concept __sentinel_size = requires(_Tp& __t)
    {
      requires (!is_unbounded_array_v<remove_reference_t<_Tp>>);

      { _Begin{}(__t) } -> forward_iterator;

      { _End{}(__t) } -> sized_sentinel_for<decltype(_Begin{}(__t))>;

      __detail::__to_unsigned_like(_End{}(__t) - _Begin{}(__t));
    };

    struct _Size
    {
    private:
      template<typename _Tp>
    static constexpr bool
    _S_noexcept()
    {
      if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>)
        return true;
      else if constexpr (__member_size<_Tp>)
        return noexcept(__decay_copy(std::declval<_Tp&>().size()));
      else if constexpr (__adl_size<_Tp>)
        return noexcept(__decay_copy(size(std::declval<_Tp&>())));
      else if constexpr (__sentinel_size<_Tp>)
        return noexcept(_End{}(std::declval<_Tp&>())
                - _Begin{}(std::declval<_Tp&>()));
    }

    public:
      template<typename _Tp>
    requires is_bounded_array_v<remove_reference_t<_Tp>>
      || __member_size<_Tp> || __adl_size<_Tp> || __sentinel_size<_Tp>
    constexpr auto
    operator()[[nodiscard]](_Tp&& __t) const noexcept(_S_noexcept<_Tp&>())
    {
      if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>)
        return extent_v<remove_reference_t<_Tp>>;
      else if constexpr (__member_size<_Tp>)
        return __t.size();
      else if constexpr (__adl_size<_Tp>)
        return size(__t);
      else if constexpr (__sentinel_size<_Tp>)
        return __detail::__to_unsigned_like(_End{}(__t) - _Begin{}(__t));
    }
    };

    struct _SSize
    {
      // _GLIBCXX_RESOLVE_LIB_DEFECTS
      // 3403. Domain of ranges::ssize(E) doesn't match ranges::size(E)
      template<typename _Tp>
    requires requires (_Tp& __t) { _Size{}(__t); }
    constexpr auto
    operator()[[nodiscard]](_Tp&& __t) const noexcept(noexcept(_Size{}(__t)))
    {
      auto __size = _Size{}(__t);
      using __size_type = decltype(__size);
      // Return the wider of ptrdiff_t and make-signed-like-t<__size_type>.
      if constexpr (integral<__size_type>)
        {
          using __gnu_cxx::__int_traits;
          if constexpr (__int_traits<__size_type>::__digits
                < __int_traits<ptrdiff_t>::__digits)
        return static_cast<ptrdiff_t>(__size);
          else
        return static_cast<make_signed_t<__size_type>>(__size);
        }
#if defined __STRICT_ANSI__ && defined __SIZEOF_INT128__
      // For strict-ansi modes integral<__int128> is false
      else if constexpr (__detail::__is_int128<__size_type>)
        return static_cast<__int128>(__size);
#endif
      else // Must be one of __max_diff_type or __max_size_type.
        return __detail::__max_diff_type(__size);
    }
    };

    template<typename _Tp>
      concept __member_empty = requires(_Tp& __t) { bool(__t.empty()); };

    template<typename _Tp>
      concept __size0_empty = requires(_Tp& __t) { _Size{}(__t) == 0; };

    template<typename _Tp>
      concept __eq_iter_empty = requires(_Tp& __t)
    {
      requires (!is_unbounded_array_v<remove_reference_t<_Tp>>);

      { _Begin{}(__t) } -> forward_iterator;

      bool(_Begin{}(__t) == _End{}(__t));
    };

    struct _Empty
    {
    private:
      template<typename _Tp>
    static constexpr bool
    _S_noexcept()
    {
      if constexpr (__member_empty<_Tp>)
        return noexcept(bool(std::declval<_Tp&>().empty()));
      else if constexpr (__size0_empty<_Tp>)
        return noexcept(_Size{}(std::declval<_Tp&>()) == 0);
      else
        return noexcept(bool(_Begin{}(std::declval<_Tp&>())
        == _End{}(std::declval<_Tp&>())));
    }

    public:
      template<typename _Tp>
    requires __member_empty<_Tp> || __size0_empty<_Tp>
      || __eq_iter_empty<_Tp>
    constexpr bool
    operator()[[nodiscard]](_Tp&& __t) const noexcept(_S_noexcept<_Tp&>())
    {
      if constexpr (__member_empty<_Tp>)
        return bool(__t.empty());
      else if constexpr (__size0_empty<_Tp>)
        return _Size{}(__t) == 0;
      else
        return bool(_Begin{}(__t) == _End{}(__t));
    }
    };

    template<typename _Tp>
      concept __pointer_to_object = is_pointer_v<_Tp>
                    && is_object_v<remove_pointer_t<_Tp>>;

    template<typename _Tp>
      concept __member_data = requires(_Tp& __t)
    {
      { __decay_copy(__t.data()) } -> __pointer_to_object;
    };

    template<typename _Tp>
      concept __begin_data = contiguous_iterator<__range_iter_t<_Tp>>;

    struct _Data
    {
    private:
      template<typename _Tp>
    static constexpr bool
    _S_noexcept()
    {
      if constexpr (__member_data<_Tp>)
        return noexcept(__decay_copy(std::declval<_Tp&>().data()));
      else
        return noexcept(_Begin{}(std::declval<_Tp&>()));
    }

    public:
      template<__maybe_borrowed_range _Tp>
    requires __member_data<_Tp> || __begin_data<_Tp>
    constexpr auto
    operator()[[nodiscard]](_Tp&& __t) const noexcept(_S_noexcept<_Tp>())
    {
      if constexpr (__member_data<_Tp>)
        return __t.data();
      else
        return std::to_address(_Begin{}(__t));
    }
    };

  } // namespace __cust_access

6.1.2 范围的约束和工具

ranges concept如下:

concept(std::ranges中的)	要求
range	可以从头到尾迭代码
output_range	写入值的元素的范围
input_range	读取元素值的范围
forward_range	范围可多次迭代这些元素
bidirectional_range	可以向前和向后遍历元素
random_access_range	随机访问范围(在元素之间来回跳转)
contiguous_range	**连续内存**中包含所有元素的范围
sized_range	具有恒定时间 size() 的范围

其他concepts | concept(std::ranges中的) | 要求 | | ------------------------ | --------------------------------------------- | | view | 复制或移动和分配成本较低的范围 | | viewable_range | 可以转换为视图的范围(使用 std::ranges::all()) | | borrowed_range | 使用与范围的生命周期无关的迭代器进行范围操作 | | common_range | 开始和结束(sentinel)的范围具有相同的类型 |

namespace test_concept_view {
void test_concept_view() {
    std::list<int> lst{5, 2, 3, 4, 1};
    // std::ranges::sort(lst); // compile error

}
} // namespace test_concept_view

6.1.3 视图

轻量级范围, 创建/复制/移动成本很低

• 参考范围和子范围
• 自有临时范围
• 过滤元素
• 生成转换后的元素值
• 生成一系列的值

视图通常用于在特定的基础上, 处理基础范围的元素子集和/或经过一些可选转换后的值, 简单的视图操作如下:

namespace test_view {
void test_view() {
    std::vector<int> vec{5, 2, 3, 4, 1, 2, 3, 4, 5};
    for (const auto &ele : std::views::take(vec, 20)) {
        fmt::print("{} ", ele);
    }
    fmt::print("\n");
}

void test_view_stream() {
    std::vector<int> vec{5, 2, 3, 4, 1, 2, 3, 4, 5};
    auto v = vec | std::views::take(20) |
             std::views::filter([](auto ele) { return ele % 2 != 0; }) |
             std::views::transform([](auto ele) { return ele * 2; }) |
             std::views::take(5);
    fmt::print("v: [{}]\n", fmt::join(v, ", "));
}

void test_generate_views() {
    auto v = std::views::iota(1, 10) | std::views::transform([](auto ele) { return ele * 2; });
    fmt::print("v: [{}]\n", fmt::join(v, ", "));
}
} // namespace test_view

视图不总是read only, 也是可以写入的. 例如:

void test_write() {
    std::vector<int> vec{5, 2, 3, 4, 1, 2, 3, 4, 5};
    // std::ranges::sort(std::views::take(vec, 5));
    std::ranges::sort(vec | std::views::take(5));
    fmt::print("v: [{}]\n", fmt::join(vec, ", "));
}

6.1.3.1 延迟计算

视图具有延迟计算的能力, 但是最好是只读的, 否则会出现并发问题, 最好在使用前直接创建, 再进行使用.

6.1.3.2 视图类型和声明周期

需要注意 std::ranges::ref_view.

namespace test_lifetime_view {
void test_lifetime_view() {
    std::vector<int> vec{5, 2, 3, 4, 1, 2, 3, 4, 5};
    auto v = vec | std::views::take(5);
    static_assert(std::is_same_v<typename std::ranges::take_view<
                                     std::ranges::ref_view<std::vector<int>>>,
                                 decltype(v)>,
                  "");
    vec.clear();       // ok, v also is cleared
    assert(v.empty()); // v is empty
    fmt::print("v: [{}]\n", fmt::join(v, ", "));
}
} // namespace test_lifetime_view

6.1.4 哨兵(

在传统STL方法中, 哨兵是end迭代器, 通常要求与迭代集合具有相同的类型, 但是在ranges中不再需要类型一致.

如何定义自己的哨兵类型 定义一个结构体, 实现operator==(auto iter)或者operator!=(auto iter); 算法库很多仍然不兼容哨兵类型, 需要使用std::ranges来代替.

#include <iterator>

namespace test_sentinel_view {
struct NullTerm {
    template <std::input_iterator It>
    friend bool operator==(It pos, NullTerm) noexcept {
        return *pos == '\0';
    }

    template <std::input_iterator It>
    friend bool operator==(NullTerm, It pos) noexcept {
        return *pos == '\0';
    }
};
void test_sentinel_view() {
    // clang-format off
    // auto null_term = [](auto pos) {return *pos == '\0';}; // compile error,require impl operator==/operator!=
    // clang-format on
    auto null_term = NullTerm{};
    auto raw_string = "hello\0 world\0";
    auto rng = std::ranges::subrange(raw_string, null_term);
    fmt::print("rng: [{}]\n", fmt::join(rng, ", "));

    std::ranges::for_each(raw_string, null_term,
                          [](auto c) { fmt::print("{} ", c); });
    fmt::print("\n");

    // clang-format off
    // std::for_each(raw_string, null_term, [](auto c) { fmt::print("{} ", c); }); // compile error, require sentinel's type equal raw_string's element type
    // clang-format on
}
} // namespace test_sentinel_view

6.1.5 使用哨兵计数和定义范围

范围不仅仅是容器或者一对迭代器, 也可以这么定义: + 同一类型的开始和结束迭代器 + 开始迭代器和哨兵 + 开始迭代器和count, 类似std::copy_n这样的接口 + 数组

6.1.5.1 子范围

为了定义迭代器和哨兵的范围, ranges库提供了std::ranges::subrange接口.subrange其实就是输入两个迭代器, 其中结束迭代器允许是哨兵类型. 例子如下:

namespace test_subrange {
template<int N>
struct NullTerm {
    template <std::input_iterator It>
    friend bool operator==(It pos, NullTerm) noexcept {
        return *pos == N;
    }

    template <std::input_iterator It>
    friend bool operator==(NullTerm, It pos) noexcept {
        return *pos == N;
    }
};
void test_subrange() {
    auto null_term = NullTerm<5>{};
    std::vector<int> vec{1, 2, 3, 4, 5};
    auto rng = std::ranges::subrange(vec.begin(), null_term);
    fmt::print("rng: [{}]\n", fmt::join(rng, ", "));
}
} // namespace test_subrange

6.1.5.2 范围的开始和计数

可以简单地理解为ranges实现了很多iterator和algorithm中的算法

#include <source_location>

void test_sentinel_and_counter() {
    auto location = std::source_location::current();
    fmt::print("{}, {}: {}\n", location.function_name(), location.line(),
               location.column());

    auto null_term = NullTerm<5>{};
    std::vector<int> vec{1, 2, 3, 4, 5};
    auto pos = std::ranges::find(vec, 3);
    if (std::ranges::distance(pos, null_term) >= 2) {
        for (auto val : std::views::counted(pos, 2)) {
            fmt::print("{} ", val);
        }
        fmt::print("\n");
    }
}

6.1.6 投影

sort和很多其它适用于范围的算法一样, 通常有一个额外的可选模板参数, 一个投影:

template<std::ranges::random_access_range R,
    typename Comp = std::ranges::less,
    typename Proj = std::identity>
requires std::sortable<std::ranges::iterator_t<R>, Comp, Proj>
... sort(R &&r, Comp comp = {}, Proj proj = {});

可选的附加参数, 允许在算法进一步处理之前为每个元素指定一个转换(投影/projection).

默认投影是:std::identity, 是std::function中定义的一个函数对象

投影的签名为: 输入一个参数并为转换后的参数返回一个值, 输入类型和输出类型允许不一样,但需要注意输出类型的比较函数.

例如, sort允许指定要排序的元素的绝对值进行比较

#include <cxxabi.h>

namespace test_projection_view {
void test_projection_view() {
    auto location = std::source_location::current();
    fmt::print("{}, {}: {}\n", location.function_name(), location.line(),
               location.column());

    std::vector<int> vec{1, 2, -3, 4, 5};
    // std::ranges::sort(vec, std::ranges::less{},
    //                   [](auto ele) { return std::abs(ele); });
    // fmt::print("vec: [{}]\n", fmt::join(vec, ", "));

    // other solution
    // std::ranges::sort(vec, [](auto &&left, auto &&right) {
    //     return std::abs(left) < std::abs(right);
    // });
    // fmt::print("vec: [{}]\n", fmt::join(vec, ", "));

    // only test in ubuntu gcc
    static auto demangle = [](const char *name) -> std::string {
        int status = 0;
        std::unique_ptr<char, decltype(&std::free)> result(
            abi::__cxa_demangle(name, nullptr, nullptr, &status), &std::free);
        return (status == 0) ? result.get() : name;
    };

    std::ranges::sort(
        vec,
        [](auto &&left, auto &&right) {
            fmt::print("L: {}, R: {}\n", demangle(typeid(left).name()),
                       demangle(typeid(right).name()));
            return left < right;
        },
        [](auto ele) { return std::to_string(ele); });
    fmt::print("vec: [{}]\n", fmt::join(vec, ", "));
}
} // namespace test_projection_view

6.1.7 实现范围代码的工具

ranges提供的相关接口: + concept std::ranges::input_range要求传递的参数是一个可以读取的范围 + 函数std::ranges::range_value_t, 产生范围内相应类型的元素 + 函数std::ranges:empty,判断范围是否是空 + 函数std::ranges::begin生成指向第一个元素的迭代器(如果存在) + 函数std::ranges::end生成哨兵

6.1.8 ranges的局限性和缺点

3.2 租借迭代器和范围

主要解决: 当range作为单个参数传递给算法时, 会遇到生命周期问题. 例子如下:

namespace test_borrowed_range {
void test_borrowed_range() {
    auto fn = [] { return std::vector<int>{1, 2, 3, 4, 5}; };
    // auto vec = fn();
    auto pos = std::ranges::find(fn(), 3);
    // clang-format off
    // fmt::print("pos: {}\n", *pos); // compile error, pos's type is dangling
    // clang-format on

    // there is ok
    auto &&vec = fn();
    auto pos2 = std::ranges::find(vec, 3);
    fmt::print("pos: {}\n", *pos2);

    // also ok
    const auto& vec2 = fn();
    auto pos3 = std::ranges::find(vec2, 3);
    fmt::print("pos: {}\n", *pos3);
}
} // namespace test_borrowed_range

实现原理: 基本原理是: 如果传递过去的对象是纯右值或者亡值, 那么返回一个std::ranges::dangling类型, 这样就会编译报错.

template<bool>
struct __conditional
{
    template<typename _Tp, typename>
using type = _Tp;
};

template<>
struct __conditional<false>
{
    template<typename, typename _Up>
using type = _Up;
};

// More efficient version of std::conditional_t for internal use (and C++11)
template<bool _Cond, typename _If, typename _Else>
using __conditional_t
    = typename __conditional<_Cond>::template type<_If, _Else>;

template<typename>
    inline constexpr bool disable_sized_range = false;

  template<typename _Tp>
    inline constexpr bool enable_borrowed_range = false;


// Part of the constraints of ranges::borrowed_range
    template<typename _Tp>
      concept __maybe_borrowed_range
    = is_lvalue_reference_v<_Tp>
      || enable_borrowed_range<remove_cvref_t<_Tp>>;

  /// [range.range] The borrowed_range concept.
  template<typename _Tp>
    concept borrowed_range
      = range<_Tp> && __detail::__maybe_borrowed_range<_Tp>;


template<range _Range>
    using borrowed_iterator_t = __conditional_t<borrowed_range<_Range>,
                    iterator_t<_Range>,
                    dangling>;


struct __find_if_fn
{
template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
        typename _Proj = identity,
        indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
    constexpr _Iter
    operator()(_Iter __first, _Sent __last,
        _Pred __pred, _Proj __proj = {}) const
    {
while (__first != __last
    && !(bool)std::__invoke(__pred, std::__invoke(__proj, *__first)))
    ++__first;
return __first;
    }

template<input_range _Range, typename _Proj = identity,
        indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
        _Pred>
    constexpr borrowed_iterator_t<_Range>
    operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
    {
return (*this)(ranges::begin(__r), ranges::end(__r),
            std::move(__pred), std::move(__proj));
    }
};

6.3 使用视图

6.3.1 视图的范围性

视图可以接受左值容器和纯右值prvalue容器, 前者返回的是std::ref_view, 后者则是std::owing_view

namespace test_range_lvalue_prvalue {
void test_range_lvalue_prvalue() {
    std::vector<int> vec{1, 2, 3, 4, 5};
    auto v = std::views::all(vec);
    std::vector<int> vec2{1, 2, 3, 4, 5};
    auto v2 = std::views::all(std::move(vec2)); // ok, vec2 is prvalue
    static_assert(
        std::is_same_v<decltype(v), std::ranges::ref_view<std::vector<int>>>,
        "");
    static_assert(std::is_same_v<decltype(v2),
                                 std::ranges::owning_view<std::vector<int>>>,
                  "");
}
} // namespace test_range_lvalue_prvalue

6.3.2 惰性计算

其实就是访问时触发计算.

6.3.3 缓存视图

6.3.4 过滤器的性能问题

6.4 销毁或修改范围的视图

6.4.1 视图及其范围之间的生命周期依赖关系

将视图理解为引用, 注意生命周期. 禁止 + 函数内部返回views

6.4.2 具有写访问权限的视图

其实就是const的修饰问题.

6.4.3 更改范围的视图

本质上就是引用的值发生了改变.

6.4.4 复制视图可能会改变行为

因为惰性求值,复制迭代器的行为可能无法预料

6.5 视图和常量

静态是有bug的.

类似cbegin和cend之类的接口可能有问题

6.5.1 视图及其范围之间的生命周期依赖关系

部分视图api是有状态(比如缓存), const auto &这样的参数会导致视图无法更新自己的状态导致编译失败.

const auto&无法适用于所有的视图, 当视图为const时, 视图不总是支持遍历元素. 因为: 迭代这些视图的元素有时需要能够修改视图的状态 (例如，由于缓存), 但是universal referenceauto&&可以.

const声明了以下标准视图中的元素, 则不能迭代: + 永远不能迭代的const视图 + filter + drop + split + IStream + 偶尔能够迭代的视图 + drop: 如果引用的range没有随机访问和size() + reverse: 如果引用的range的开始迭代器和哨兵类型不同 + join: 如果引用的range生成值而不是引用 + 若引用的ramge本身不是const可迭代的, 则引用其他range的所有view

namespace test_lifetime_view_and_dependency {
template<typename T>
void print(const T &col) {
    for(const auto& ele : col) {
        fmt::print("{} ", ele);
    }
    fmt::print("\n");
}

// using universal reference then ok
// void print(auto &&col) {
//     for (const auto &ele : col) {
//         fmt::print("{} ", ele);
//     }
//     fmt::print("\n");
// }

void test_lifetime_view_and_dependency() {
    std::vector<int> vec{1, 2, 3, 4, 5};
    std::list<int> lst{1, 2, 3, 4, 5};
    print(vec | std::views::take(3));
    print(lst | std::views::take(3));

    print(vec | std::views::drop(3));
    // clang-format off
        // print(lst | std::views::drop(3)); // compile error
        for(const auto& ele : lst | std::views::drop(3)) {
            fmt::print("{} ", ele);
        }
    // clang-format on

    auto is_even = [](int ele) { return ele % 2 == 0; };
    // clang-format off
        // print(vec | std::views::filter(is_even)); // compile error
    // clang-format on
}
} // namespace test_lifetime_view_and_dependency

6.5.2 具有写访问权限的视图

6.5.3 更改范围的视图

6.6 视图分解容器的习惯用法

完整代码

#include <fmt/core.h>
#include <fmt/ranges.h>

#include <algorithm>
#include <cassert>
#include <complex>
#include <iterator>
#include <list>
#include <ranges>
#include <vector>

#include <cxxabi.h>

#include <source_location>

namespace test_sort {
void test_sort() {
    std::vector<int> vec{5, 2, 3, 4, 1};
    fmt::print("vec: [{}]\n", fmt::join(vec, ", "));
    std::ranges::sort(vec);
    fmt::print("vec: [{}]\n", fmt::join(vec, ", "));
}
} // namespace test_sort

namespace test_concept_view {
void test_concept_view() {
    std::list<int> lst{5, 2, 3, 4, 1};
    // std::ranges::sort(lst); // compile error
}
} // namespace test_concept_view

namespace test_view {
void test_view() {
    std::vector<int> vec{5, 2, 3, 4, 1, 2, 3, 4, 5};
    for (const auto &ele : std::views::take(vec, 20)) {
        fmt::print("{} ", ele);
    }
    fmt::print("\n");
}

void test_view_stream() {
    std::vector<int> vec{5, 2, 3, 4, 1, 2, 3, 4, 5};
    auto v = vec | std::views::take(20) |
             std::views::filter([](auto ele) { return ele % 2 != 0; }) |
             std::views::transform([](auto ele) { return ele * 2; }) |
             std::views::take(5);
    fmt::print("v: [{}]\n", fmt::join(v, ", "));
}

void test_generate_views() {
    auto v = std::views::iota(1, 10) |
             std::views::transform([](auto ele) { return ele * 2; });
    fmt::print("v: [{}]\n", fmt::join(v, ", "));
}

void test_write() {
    std::vector<int> vec{5, 2, 3, 4, 1, 2, 3, 4, 5};
    auto v = vec | std::views::take(5);
    static_assert(std::is_same_v<typename std::ranges::take_view<
                                     std::ranges::ref_view<std::vector<int>>>,
                                 decltype(v)>,
                  "");
    std::ranges::sort(v);
    fmt::print("v: [{}]\n", fmt::join(vec, ", "));
}
} // namespace test_view

namespace test_lifetime_view {
void test_lifetime_view() {
    std::vector<int> vec{5, 2, 3, 4, 1, 2, 3, 4, 5};
    auto v = vec | std::views::take(5);
    static_assert(std::is_same_v<typename std::ranges::take_view<
                                     std::ranges::ref_view<std::vector<int>>>,
                                 decltype(v)>,
                  "");
    vec.clear();       // ok, v also is cleared
    assert(v.empty()); // v is empty
    fmt::print("v: [{}]\n", fmt::join(v, ", "));
}
} // namespace test_lifetime_view

namespace test_sentinel_view {
struct NullTerm {
    template <std::input_iterator It>
    friend bool operator==(It pos, NullTerm) noexcept {
        return *pos == '\0';
    }

    template <std::input_iterator It>
    friend bool operator==(NullTerm, It pos) noexcept {
        return *pos == '\0';
    }
};
void test_sentinel_view() {
    // clang-format off
    // auto null_term = [](auto pos) {return *pos == '\0';}; // compile error,require impl operator==/operator!=
    // clang-format on
    auto null_term = NullTerm{};
    auto raw_string = "hello\0 world\0";
    auto rng = std::ranges::subrange(raw_string, null_term);
    fmt::print("rng: [{}]\n", fmt::join(rng, ", "));

    std::ranges::for_each(raw_string, null_term,
                          [](auto c) { fmt::print("{} ", c); });
    fmt::print("\n");

    // clang-format off
    // std::for_each(raw_string, null_term, [](auto c) { fmt::print("{} ", c); }); // compile error, require sentinel's type equal raw_string's element type
    // clang-format on
}
} // namespace test_sentinel_view

namespace test_subrange {
template <int N> struct NullTerm {
    template <std::input_iterator It>
    friend bool operator==(It pos, NullTerm) noexcept {
        return *pos == N;
    }

    template <std::input_iterator It>
    friend bool operator==(NullTerm, It pos) noexcept {
        return *pos == N;
    }
};
void test_subrange() {
    auto null_term = NullTerm<5>{};
    std::vector<int> vec{1, 2, 3, 4, 5};
    auto rng = std::ranges::subrange(vec.begin(), null_term);
    fmt::print("rng: [{}]\n", fmt::join(rng, ", "));
}

void test_sentinel_and_counter() {
    auto location = std::source_location::current();
    fmt::print("{}, {}: {}\n", location.function_name(), location.line(),
               location.column());

    auto null_term = NullTerm<5>{};
    std::vector<int> vec{1, 2, 3, 4, 5};
    auto pos = std::ranges::find(vec, 3);
    if (std::ranges::distance(pos, null_term) >= 2) {
        for (auto val : std::views::counted(pos, 2)) {
            fmt::print("{} ", val);
        }
        fmt::print("\n");
    }
}
} // namespace test_subrange

namespace test_projection_view {
void test_projection_view() {
    auto location = std::source_location::current();
    fmt::print("{}, {}: {}\n", location.function_name(), location.line(),
               location.column());

    std::vector<int> vec{1, 2, -3, 4, 5};
    // std::ranges::sort(vec, std::ranges::less{},
    //                   [](auto ele) { return std::abs(ele); });
    // fmt::print("vec: [{}]\n", fmt::join(vec, ", "));

    // other solution
    // std::ranges::sort(vec, [](auto &&left, auto &&right) {
    //     return std::abs(left) < std::abs(right);
    // });
    // fmt::print("vec: [{}]\n", fmt::join(vec, ", "));

    // only test in ubuntu gcc
    static auto demangle = [](const char *name) -> std::string {
        int status = 0;
        std::unique_ptr<char, decltype(&std::free)> result(
            abi::__cxa_demangle(name, nullptr, nullptr, &status), &std::free);
        return (status == 0) ? result.get() : name;
    };

    std::ranges::sort(
        vec,
        [](auto &&left, auto &&right) {
            fmt::print("L: {}, R: {}\n", demangle(typeid(left).name()),
                       demangle(typeid(right).name()));
            return left < right;
        },
        [](auto ele) { return std::to_string(ele); });
    fmt::print("vec: [{}]\n", fmt::join(vec, ", "));
}
} // namespace test_projection_view

namespace test_borrowed_range {
void test_borrowed_range() {
    auto fn = [] { return std::vector<int>{1, 2, 3, 4, 5}; };
    // auto vec = fn();
    auto pos = std::ranges::find(fn(), 3);
    // clang-format off
    // fmt::print("pos: {}\n", *pos); // compile error, pos's type is dangling
    // clang-format on

    // there is ok
    auto &&vec = fn();
    auto pos2 = std::ranges::find(vec, 3);
    fmt::print("pos: {}\n", *pos2);

    // also ok
    const auto &vec2 = fn();
    auto pos3 = std::ranges::find(vec2, 3);
    fmt::print("pos: {}\n", *pos3);
}
} // namespace test_borrowed_range

namespace test_range_lvalue_prvalue {
void test_range_lvalue_prvalue() {
    std::vector<int> vec{1, 2, 3, 4, 5};
    auto v = std::views::all(vec);
    std::vector<int> vec2{1, 2, 3, 4, 5};
    auto v2 = std::views::all(std::move(vec2)); // ok, vec2 is prvalue
    static_assert(
        std::is_same_v<decltype(v), std::ranges::ref_view<std::vector<int>>>,
        "");
    static_assert(std::is_same_v<decltype(v2),
                                 std::ranges::owning_view<std::vector<int>>>,
                  "");
}
} // namespace test_range_lvalue_prvalue

namespace test_range_cache {
void test_range_cache() {
    std::vector<int> vec{1, 2, 3, 4, 5};
    auto v = std::views::all(vec) | std::views::filter([](auto ele) {
                 fmt::print("filter ele: {}\n", ele);
                 return ele % 2 != 0;
             }) |
             std::views::transform([](auto ele) {
                 fmt::print("transform ele: {}\n", ele);
                 return ele * 2;
             }) |
             std::views::take(3);
    fmt::print("v: [{}]\n", fmt::join(v, ", "));
    fmt::print("\n\n\n");
    fmt::print("v: [{}]\n", fmt::join(v, ", "));
}
} // namespace test_range_cache

namespace test_lifetime_view_and_dependency {
template<typename T>
void print(const T &col) {
    for(const auto& ele : col) {
        fmt::print("{} ", ele);
    }
    fmt::print("\n");
}

// using universal reference then ok
// void print(auto &&col) {
//     for (const auto &ele : col) {
//         fmt::print("{} ", ele);
//     }
//     fmt::print("\n");
// }

void test_lifetime_view_and_dependency() {
    std::vector<int> vec{1, 2, 3, 4, 5};
    std::list<int> lst{1, 2, 3, 4, 5};
    print(vec | std::views::take(3));
    print(lst | std::views::take(3));

    print(vec | std::views::drop(3));
    // clang-format off
        // print(lst | std::views::drop(3)); // compile error
        for(const auto& ele : lst | std::views::drop(3)) {
            fmt::print("{} ", ele);
        }
    // clang-format on

    auto is_even = [](int ele) { return ele % 2 == 0; };
    // clang-format off
        // print(vec | std::views::filter(is_even)); // compile error
    // clang-format on
}
} // namespace test_lifetime_view_and_dependency

int main() {
    //
    // test_sort::test_sort();
    // test_view::test_view();
    // test_view::test_view_stream();
    // test_view::test_generate_views();
    // test_view::test_write();
    // test_lifetime_view::test_lifetime_view();
    // test_sentinel_view::test_sentinel_view();
    // test_subrange::test_subrange();
    // test_subrange::test_sentinel_and_counter();
    // test_projection_view::test_projection_view();
    // test_borrowed_range::test_borrowed_range();
    // test_range_cache::test_range_cache();
    test_lifetime_view_and_dependency::test_lifetime_view_and_dependency();
    return 0;
}