c++ - 代理容器上的迭代器可能是 “least bad implementation”？

Question

语境

我正在尝试实现类似容器的nD数组。可以包装基础序列容器并允许将其作为(of ...)容器的容器进行处理的东西:arr[i][j][k]应该是_arr[(((i * dim2) + j) * dim3) + k]的(最终是const)引用。

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

当我尝试实现干预者时，我突然意识到周围到处都是龙:

我的容器不是标准兼容的容器，因为operator []返回代理或包装而不是真实引用(When Is a Container Not a Container?)

这将导致迭代器成为隐藏式迭代器(已知是不好的(Reference invalidation after applying reverse_iterator on a custom made iterator及其接受的answer))

...或不一定更好的代理迭代器(To Be or Not to Be (an Iterator))

真正的问题是，一旦有了代理容器，任何迭代器都无法满足以下对转发迭代器的要求:

Forward iterators [forward.iterators]
...
⁶ If a and b are both dereferenceable, then a == b if and only if *a and *b are bound to the same object.

示例来自标准库本身:

vector<bool>不遵守容器的所有要求，因为它返回代理而不是引用:

Class vector [vector.bool]
...
³ There is no requirement that the data be stored as a contiguous allocation of bool values. A space-optimized representation of bits is recommended instead.
⁴ reference is a class that simulates the behavior of references of a single bit in vector.

文件系统路径迭代器是隐藏式迭代器:

path iterators [fs.path.itr]
...
² A path::iterator is a constant iterator satisfying all the requirements of a bidirectional iterator (27.2.6) except that, for dereferenceable iterators a and b of type path::iterator with a == b, there is no requirement that*a and *b are bound to the same object.

并从cppreference:

Notes: std::reverse_iterator does not work with iterators that return a reference to a member object (so-called "stashing iterators"). An example of stashing iterator is std::filesystem::path::iterator.

题

我目前发现了大量有关为什么代理容器不是真正的容器以及为什么如果标准允许代理容器和迭代器会更好的引用。但是我仍然不知道什么可以做的最好，什么是真正的限制。

所以我的问题是，为什么代理迭代器真的比隐藏迭代器好，以及它们允许使用哪种算法。如果可能的话，我真的很想找到这种迭代器的引用实现

作为引用，我的代码的当前实现已在Code Review上提交。它包含一个隐藏式迭代器(当我尝试使用std::reverse_iterator时，它立即中断了)

Answer 1

好的，我们有两个相似但截然不同的概念。因此，让他们进行布局。
但是首先，我需要区分C++-pre-20的命名要求和为Ranges TS创建并包含在C++ 20中的实际语言内概念。它们都被称为“概念”，但是它们的定义有所不同。因此，当我谈论小写字母c的概念时，我的意思是C++ 20之前的要求。当我谈论“带有空间C的概念”时，我指的是C++ 20的东西。
代理迭代器
代理迭代器是迭代器，其中reference不是value_type&，而是其他一些类型，其行为类似于对value_type的引用。在这种情况下，*it将prvalue返回到此reference。
InputIterator概念除了可以转换为reference之外，没有对value_type施加任何要求。但是，ForwardIterator概念明确声明“reference是对T的引用”。
因此，代理迭代器不能满足ForwardIterator概念。但是它仍然可以是InputIterator。因此，您可以安全地将代理迭代器传递给仅需要InputIterators的任何函数。
因此，vector<bool>迭代器的问题不在于它们是代理迭代器。当他们实际上只是InputIterators和OutputIterators时，他们 promise 将满足RandomAccessIterator概念(尽管使用了适当的标记)。
C++ 20中采用的Ranges提议(大多数情况下)对迭代器概念进行了更改，使代理迭代器适用于所有迭代器。因此，在Ranges下，vector<bool>::iterator确实实现了RandomAccessIterator概念。因此，如果您针对Ranges概念编写了代码，则可以使用各种代理迭代器。
这对于处理诸如计数范围之类的事情非常有用。您可以将reference和value_type设为相同的类型，因此您只能以任何一种方式处理整数。
当然，如果您可以控制使用迭代器的代码，则只要不违反编写迭代器所依据的概念，就可以使其执行所需的任何操作。
隐藏式迭代器
隐藏式迭代器是迭代器，其中reference_type是(直接或间接)对存储在迭代器中的对象的引用。因此，如果您复制迭代器，则该副本将返回对与原始对象不同的对象的引用，即使它们引用的是同一元素。并且当您增加迭代器时，先前的引用将不再有效。
通常实现隐藏式迭代器，因为计算要返回的值非常昂贵。可能涉及内存分配(例如path::iterator)，或者涉及可能仅执行一次的复杂操作(例如regex_iterator)。因此，您只想在必要时这样做。
ForwardIterator作为概念(或概念)的基础之一是，这些迭代器的范围代表独立于其迭代器而存在的值的范围。这样可以进行多遍操作，但也可以使其他事情变得有用。您可以存储对范围内项目的引用，然后在其他地方进行迭代。
如果需要迭代器成为ForwardIterator或更高版本，则永远不要使其成为隐藏式迭代器。当然，C++标准库并不总是与其自身保持一致。但是它通常会指出其不一致之处。path::iterator是一个隐藏的迭代器。该标准说它是一个BidirectionalIterator。但是，它也为该类型提供了引用/指针保留规则的异常(exception)。这意味着您不能将path::iterator传递给任何可能依赖该保留规则的代码。
现在，这并不意味着您不能将其传递给任何东西。任何仅需要InputIterator的算法都将能够采用这样的迭代器，因为此类代码无法依赖该规则。当然，可以使用您编写的任何代码或在其文档中明确声明不依赖该规则的任何代码。但是，即使它说它是BidirectionalIterator，也不能保证可以在上面使用reverse_iterator。
在这方面，regex_iterator甚至更糟。据说它们是基于其标签的ForwardIterators，但是标准从未说过它们实际上是ForwardIterators(与path::iterator不同)。而且，由于将reference作为对成员对象的实际引用而指定了它们，这使它们不可能成为真正的ForwardIterators。
请注意，在C++ 20之前的概念和Ranges概念之间没有区别。这是因为ForwardIterator概念仍然禁止存储迭代器。 This is by design.
用法
现在显然，您可以在代码中做任何您想做的事情。但是您无法控制的代码将归其所有者所有。他们将针对旧概念，新概念或它们指定的其他某些c / Concept或要求进行写作。因此，您的迭代器需要能够与他们的需求兼容。
Ranges附加功能带来的算法使用了新的Concepts，因此您始终可以依靠它们与代理迭代器一起使用。但是，据我所知，范围概念并未移植到较旧的算法中。
就个人而言，我建议避免完全隐藏迭代器实现。通过提供对代理迭代器的完全支持，可以将大多数隐藏式迭代器重写为返回值，而不是对对象的引用。
例如，如果存在path_view类型，则path::iterator可能会返回该类型，而不是完整的path。这样，如果您要执行昂贵的复制操作，则可以。同样，regex_iterator可以返回match对象的副本。新概念通过支持代理迭代器使以这种方式工作成为可能。
现在，隐藏式迭代器以一种有用的方式处理缓存。迭代器可以缓存其结果，以便重复使用*it仅执行一次昂贵的操作。但是请记住隐藏迭代器的问题:返回对其内容的引用。您不需要这样做只是为了获得缓存。您可以将结果缓存在optional<T>中(当迭代器增加/减少时，该代码将无效)。因此，您仍然可以返回一个值。它可能涉及其他副本，但reference不应为复杂类型。
当然，所有这些都意味着auto &val = *it;不再是合法代码。但是，auto &&val = *it;将始终有效。实际上，这是Range TS版本迭代器的很大一部分。