c++ - 容器类型的 View

Question

根据 http://eel.is/c++draft/range.view#concept:view , range 的 view 仅当该范围允许恒定时间移动构建、移动赋值和销毁时才满足。

但是，我想知道如何将 container 项(例如 std::map)转换为 viewable_range。底层红黑树的时间复杂度对于典型操作是 O(log n) 而不是 O(1)。

理论位于:http://eel.is/c++draft/range.refinements#concept:viewable_range声明 viewable_range 概念指定了可以安全转换为 View 的范围类型的要求。 [“安全地”这个词有点难以理解]

换句话说，我想知道为什么这样的代码编译没有错误，其中 table_entries 被认为是 viewable_range 但理论上它不应该是因为时间复杂度不是 O(1)。

#include <map>
#include <algorithm>
#include <ranges>

auto main() -> int {

    std::map<int, int> table_entries;
    auto vals = std::ranges::min(table_entries | std::views::values);

    return 0;
}

Answer 1

混淆似乎是由这个 line 引起的:

The view concept specifies the requirements of a range type that has constant time move construction, move assignment, and destruction; ...

这并不意味着构建 View 的基础范围需要支持常量时间操作。只有 View 本身需要支持常量时间操作。

---

请注意，容器 table_entries 本身不是 view(出于您提到的原因)。但是，table_entries | std::views::values 是一个 View ，因为它懒惰地按需生成 map 中的每个值。

这是另一个例子:

table_entries;                  // not a view
std::views::all(table_entries); // is a view