时间戳

首页 > 解决方案 > 容器类型的视图

c++ - 容器类型的视图

问题描述

根据http://eel.is/c++draft/range.view#concept:view，仅当范围允许恒定时间移动构造、移动分配和破坏时，才满足aview的 a 。range

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

该理论位于：http ://eel.is/c++draft/range.refinements#concept:viewable_range指出该viewable_­range概念指定了可以安全地转换为视图的范围类型的要求。[“安全”这个词理解起来有点模棱两可]

以另一种方式提出我的问题，我想知道为什么像这样的代码编译时没有错误，其中 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;
}

标签： c++c++20

解决方案

混乱似乎是由这一行引起的：

视图概念指定了具有恒定时间移动构造、移动分配和销毁的范围类型的要求；...

这并不意味着构建视图的基础范围需要支持恒定时间操作。只有视图本身需要支持恒定时间操作。

请注意，容器本身table_entries不是一个view（出于您提到的原因）。然而，它table_entries | std::views::values 是一个view因为它在地图中生成每个值，懒惰和按需。

这是另一个例子：

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

推荐阅读