3

语境

我试图实现一个像容器一样的 nD 数组。可以包装底层序列容器并允许将其作为容器容器处理的东西 (of...):arr[i][j][k]应该是_arr[(((i * dim2) + j) * dim3) + k].

好的，直到那里，arr[i]只需成为子数组的包装类......

当我尝试实现交互器时，我突然意识到周围到处都是龙：

真正的问题是，一旦你有一个代理容器，没有迭代器可以遵守前向迭代器的以下要求：

前向迭代器 [forward.iterators]
...
6如果a和b都是可解引用的，那么a == b当且仅当*a和*b绑定到同一个对象。

示例来自标准库本身：

  • vector<bool>众所周知，它不尊重容器的所有要求，因为它返回代理而不是引用：

    类向量 [vector.bool]
    ...
    3不要求将数据存储为 bool 值的连续分配。建议使用空间优化的位表示。
    4引用是模拟向量中单个位的引用行为的类。

  • 文件系统路径迭代器被称为存储迭代器：

    path iterators [fs.path.itr]
    ...
    2 path::iterator 是一个常量迭代器，它满足双向迭代器 (27.2.6) 的所有要求，除了对于可解引用的迭代器a和b带有 的 path::iterator 类型a == b，不要求*a和*b绑定到同一个对象。

    并来自cppreference：

    注意： std::reverse_iterator 不适用于返回对成员对象的引用的迭代器（所谓的“存储迭代器”）。存储迭代器的一个例子是 std::filesystem::path::iterator。

问题

我目前找到了很多关于为什么代理容器不是真正的容器以及如果标准允许代理容器和迭代器会很好的参考资料。但我仍然不明白什么是最好的，什么是真正的限制。

所以我的问题是为什么代理迭代器真的比存储迭代器更好，以及它们中的任何一个都允许哪些算法。如果可能的话，我真的很想为这种迭代器找到一个参考实现

作为参考，我的代码的当前实现已在Code Review上提交。它包含一个存储迭代器（当我尝试使用时立即中断std::reverse_iterator）

4

1 回答 1

6

好的，我们有两个相似但不同的概念。所以让我们把它们摆出来。

但首先，我需要区分 C++-pre-20 的命名要求和为 Ranges TS 创建并包含在 C++20 中的实际语言概念。它们都被称为“概念”，但它们的定义不同。因此，当我谈论带有小写字母 c 的概念时，我指的是 C++20 之前的要求。当我谈论 Concept-with-a-captial-C 时，我指的是 C++20 的东西。

代理迭代器

代理迭代器是迭代器，它们reference不是 a value_type&，而是一些其他类型，其行为类似于对 的引用value_type。在这种情况下，*it返回一个纯右值到 this reference。

InputIterator 概念对 没有任何要求reference，只是它可以转换为value_type。但是，ForwardIterator 概念明确声明“reference是对”的引用T。

因此，代理迭代器不能符合 ForwardIterator 的概念。但它仍然可以是 InputIterator。因此，您可以安全地将代理迭代器传递给任何只需要 InputIterators 的函数。

所以，vector<bool>s 迭代器的问题不在于它们是代理迭代器。这是他们承诺他们实现了 RandomAccessIterator 概念（尽管使用了适当的标签），但实际上它们只是 InputIterators 和 OutputIterators。

C++20 中采用的 Ranges 提议（大部分）对迭代器概念进行了更改，允许代理迭代器适用于所有迭代器。所以在 Ranges 下，vector<bool>::iterator真正实现了 RandomAccessIterator 的概念。因此，如果您有针对 Ranges 概念编写的代码，那么您可以使用各种代理迭代器。

这对于处理诸如计数范围之类的事情非常有用。你可以拥有reference并且value_type是相同的类型，所以你只是在处理整数。

当然，如果你可以控制使用迭代器的代码，你可以让它做你想做的任何事情，只要你不违反你的迭代器所针对的概念。

存储迭代器

存储迭代器是迭代器，其中reference_type（直接或间接）对存储在迭代器中的对象的引用。因此，如果您制作一个迭代器的副本，则该副本将返回对与原始对象不同的对象的引用，即使它们引用相同的元素。当你增加迭代器时，以前的引用不再有效。

通常会实现存储迭代器，因为计算要返回的值很昂贵。也许它会涉及内存分配（例如path::iterator），或者它可能会涉及一个可能很复杂的操作，该操作应该只执行一次（例如regex_iterator）。所以你只想在必要时这样做。

ForwardIterator 作为一个概念（或概念）的基础之一是这些迭代器的范围表示独立于其迭代器存在的值的范围。这允许多通道操作，但它也使做其他事情变得有用。您可以存储对范围内项目的引用，然后在其他地方迭代。

如果您需要将迭代器设为 ForwardIterator 或更高版本，则绝不应将其设为存储迭代器。当然，C++ 标准库并不总是与自身一致。但它通常会指出其不一致之处。

path::iterator是一个存储迭代器。标准说它是一个双向迭代器；但是，它也为这种类型提供了引用/指针保留规则的例外。这意味着您不能传递path::iterator给任何可能依赖于该保留规则的代码。

现在，这并不意味着你不能将它传递给任何东西。任何只需要 InputIterator 的算法都可以采用这样的迭代器，因为这样的代码不能依赖于该规则。当然，您编写的任何代码或在其文档中明确指出它不依赖该规则的任何代码都可以使用。但是不能保证你可以使用reverse_iterator它，即使它说它是一个双向迭代器。

regex_iterators在这方面就更差了。根据它们的标签，它们被称为 ForwardIterators，但标准从未说它们实际上是ForwardIterators（与 不同path::iterator）。并且将它们指定为reference对成员对象的实际引用使得它们不可能成为真正的 ForwardIterators。

请注意，我没有区分 C++20 之前的概念和 Ranges 概念。这是因为 ForwardIterator 概念仍然禁止存储迭代器。这是设计使然。

用法

现在显然，您可以在代码中做任何您想做的事情。但是您无法控制的代码将在其所有者的域下。他们将针对旧概念、新概念或他们指定的某些其他 c/Concept 或要求进行编写。所以你的迭代器需要能够满足他们的需求。

Ranges 添加带来的算法使用新的概念，因此您始终可以依赖它们来使用代理迭代器。但是，据我了解，范围概念不会向后移植到旧算法中。

就个人而言，我建议完全避免隐藏迭代器实现。通过提供对代理迭代器的完整支持，大多数存储迭代器可以被重写为返回值而不是对对象的引用。

例如，如果有一个path_view类型，path::iterator可能会返回它而不是一个完整的path. 这样，如果你想做昂贵的复制操作，你可以。同样，regex_iterators 可能已经返回了匹配对象的副本。新概念通过支持代理迭代器使以这种方式工作成为可能。

现在，存储迭代器以一种有用的方式处理缓存；迭代器可以缓存它们的结果，这样重复*it使用只会执行一次昂贵的操作。但请记住存储迭代器的问题：返回对其内容的引用。您不需要仅仅为了获得缓存而这样做。您可以将结果缓存在一个optional<T>（当迭代器在/递减时，您会使其无效）。所以你仍然可以返回一个值。它可能涉及一个额外的副本，但reference不应该是一个复杂的类型。

当然，所有这些都意味着它auto &val = *it;不再是合法代码。但是，auto &&val = *it;将始终有效。这实际上是 Range TS 版本的迭代器的重要组成部分。

于 2018-06-26T19:15:50.853 回答