这可能是“最差的实现".代理容器上的迭代器? [英] What could be a "least bad implementation" for an iterator over a proxied container?

问题描述

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

I was trying to implement a nD array like container. Something that would wrap an underlying sequence container and allow to process it as a container of containers (of...): arr[i][j][k] should be a (eventually const) reference for _arr[(((i * dim2) + j) * dim3) + k].

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

Ok until there, arr[i] has just to be a wrapper class over the subarray...

当我尝试实施中介者时，突然意识到龙四处可见:

And when I tried to implement interators, I suddenly realized that dragons were everywhere around:

• 我的容器不是符合标准的容器，因为operator []返回的是代理或包装，而不是真正的引用(参考无效在自定义迭代器上应用了reverse_iterator 及其接受的 answer )
• ...或不一定更好的代理迭代器(

• my container is not a standard compliant container because operator [] returns a proxy or wrapper instead of a true reference (When Is a Container Not a Container?)
• this causes the iterator to be either a stashing iterator (which is known to be bad (Reference invalidation after applying reverse_iterator on a custom made iterator and its accepted answer)
• ... or a proxy iterator which is not necessarily better (To Be or Not to Be (an Iterator))

真正的问题是，一旦有了代理容器，就没有迭代器可以满足以下对转发迭代器的要求:

The real problem is that as soon as you have a proxied container, no iterator can respect the following requirement for a forward iterator:

转发迭代器[forward.iterators]
...
⁶ 如果a和b都是可取消引用的，则a == b当且仅当*a和*b绑定到同一对象时，a == b./p>

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>不遵守容器的所有要求，因为它返回代理而不是引用:

• vector<bool> is known not to respect all the requirements for containers because it returns proxies instead of references:

类向量[vector.bool]
...
³ 不需要将数据存储为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.

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

filesystem path iterator is known to be a stashing iterator:

路径迭代器[fs.path.itr]
...
² path :: iterator是一个常量迭代器，它满足双向迭代器的所有要求(27.2.6) 除此之外，对于带有a == b的path :: iterator类型的可取消引用的迭代器a和b，没有要求 *a和*b绑定到同一对象.

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 :

注意:std :: reverse_iterator不适用于返回对成员对象的引用的迭代器(所谓的隐藏式迭代器").存放迭代器的一个示例是std :: filesystem :: path :: iterator.

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.

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

I have currently found plenty of references about why proxied containers are not true containers and why it would be nice if proxied containers and iterators were allowed by the standard. But I have still not understood what was the best that could be done and what were the real limitations.

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

So my question is why proxy iterators are really better that stashing ones, and what algorithms are allowed for either of them. If possible, I would really love to find a reference implementation for such an iterator

作为参考，我的代码的当前实现已通过代码审查提交.它包含一个隐藏式迭代器(当我尝试使用std::reverse_iterator时立即中断)

For references, a current implementation of my code has been submitted on Code Review. It contains a stashing iterator (that broke immediately when I try to use std::reverse_iterator)

推荐答案

好的，我们有两个相似但截然不同的概念.因此，让我们布置它们.

OK, we have two similar but distinct concepts. So lets lay them out.

但是首先，我需要区分C ++-pre-20的命名要求和为Ranges TS创建并包含在C ++ 20中的实际语言内概念.它们都被称为概念"，但是它们被分别定义为 .因此，当我谈论带有小写字母c的概念时，我指的是C ++ 20之前的要求.当我谈论带有电容C的概念"时，我的意思是C ++ 20的东西.

But first, I need to make a distinction between the named requirements of C++-pre-20, and the actual in-language concepts created for the Ranges TS and included in C++20. They're both called "concepts", but they're defined differently. As such, when I talk about concept-with-a-lowercase-c, I mean the pre-C++20 requirements. When I talk about Concept-with-a-captial-C, I mean the C++20 stuff.

代理迭代器是其reference不是value_type&的迭代器，而是某种其他类型，其行为类似于对value_type的引用.在这种情况下，*it返回此reference的prvalue.

Proxy iterators are iterators where their reference is not a value_type&, but is instead some other type that behaves like a reference to value_type. In this case, *it returns a prvalue to this reference.

InputIterator概念除了可以转换为value_type之外，没有对reference施加任何要求.但是，ForwardIterator概念明确声明"reference是对T的引用".

The InputIterator concept imposes no requirement on reference, other than that it is convertible to value_type. However, the ForwardIterator concept makes the explicit statement that "reference is a reference to T".

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

Therefore, a proxy iterator cannot fit the ForwardIterator concept. But it can still be an InputIterator. So you can safely pass a proxy iterator to any function that only requires InputIterators.

因此，vector<bool>的迭代器的问题不在于它们是代理迭代器.当他们实际上只是InputIterators和OutputIterators时，他们保证满足了RandomAccessIterator概念(尽管使用了适当的标记).

So, the problem with vector<bool>s iterators is not that they're proxy iterators. It's that they promise they fulfill the RandomAccessIterator concept (though the use of the appropriate tag), when they're really only InputIterators and OutputIterators.

(大多数)C ++ 20中采用的Ranges提案对迭代器概念进行了更改，使代理迭代器适用于 all 迭代器.因此，在Ranges下，vector<bool>::iterator确实满足了RandomAccessIterator概念.因此，如果您针对Ranges概念编写了代码，则可以使用各种代理迭代器.

The Ranges proposal (mostly) adopted into C++20 makes changes to the iterator Concepts which allow proxy iterators to be for all iterators. So under Ranges, vector<bool>::iterator really fulfills the RandomAccessIterator Concept. Therefore, if you have code written against the Ranges concepts, then you can use proxy iterators of all kinds.

这对于处理诸如计数范围之类的事情非常有用.您可以将reference和value_type设为相同的类型，因此您只能以任何一种方式处理整数.

This is very useful for dealing with things like counting ranges. You can have reference and value_type be the same type, so you're just dealing with integers either way.

当然，如果您可以控制使用迭代器的代码，只要不违反编写迭代器所依据的概念，就可以使其执行所需的任何操作.

And of course, if you have control over the code consuming the iterator, you can make it do whatever you want, so long as you don't violate the concept your iterator is written against.

隐藏式迭代器是迭代器，其中reference_type是(直接或间接)对存储在迭代器中的对象的引用.因此，如果您复制迭代器，则该副本将返回对与原始对象不同的对象的引用，即使它们引用的是同一元素.并且当您增加迭代器时，以前的引用将不再有效.

Stashing iterators are iterators where reference_type is (directly or indirectly) a reference to an object stored in the iterator. Therefore, if you make a copy of an iterator, the copy will return a reference to a different object than the original, even though they refer to the same element. And when you increment the iterator, previous references are no longer valid.

通常实现隐藏式迭代器，因为计算要返回的值非常昂贵.可能涉及内存分配(例如path::iterator)，也可能涉及可能仅执行一次的复杂操作(例如regex_iterator).因此，您只想在必要时这样做.

Stashing iterators are usually implemented because computing the value you want to return is expensive. Maybe it would involve a memory allocation (such as path::iterator) or maybe it would involve a possibly-complex operation that should only be done once (such as regex_iterator). So you only want to do it when necessary.

ForwardIterator作为概念(或概念)的基础之一是，这些迭代器的范围代表其迭代器独立地存在的值的范围.这样可以进行多遍操作，但也可以使其他事情变得有用.您可以存储对范围内项目的引用，然后在其他地方进行迭代.

One of the foundations of ForwardIterator as a concept (or Concept) is that a range of these iterators represents a range over values which exist independently of their iterators. This permits multipass operation, but it also makes doing other things useful. You can store references to items in the range, and then iterate elsewhere.

如果您需要迭代器成为ForwardIterator或更高版本，则应从不将其设为隐藏式迭代器.当然，C ++标准库并不总是与其自身保持一致.但是它通常会指出其不一致之处.

If you need an iterator to be a ForwardIterator or higher, you should never make it a stashing iterator. Of course, the C++ standard library is not always consistent with itself. But it usually calls out its inconsistencies.

path::iterator是隐藏式迭代器.该标准说它是一个BidirectionalIterator.但是，它也为该类型提供了引用/指针保留规则的例外.这意味着您不能将path::iterator传递给任何可能依赖该保留规则的代码.

path::iterator is a stashing iterator. The standard says that it is a BidirectionalIterator; however, it also gives this type an exception to the reference/pointer preservation rule. This means that you cannot pass path::iterator to any code that might rely on that preservation rule.

现在，这并不意味着您不能将其传递给任何东西.任何仅需要InputIterator的算法都将能够采用这样的迭代器，因为此类代码无法依赖该规则.当然，可以使用您编写的任何代码或在其文档中明确声明不依赖该规则的任何代码.但是，即使它说它是BidirectionalIterator，也不能保证可以在它上使用reverse_iterator.

Now, this doesn't mean you can't pass it to anything. Any algorithm which requires only InputIterator will be able to take such an iterator, since such code cannot rely on that rule. And of course, any code which you write or which specifically states in its documentation that it doesn't rely on that rule can be used. But there's no guarantee that you can use reverse_iterator on it, even though it says that it is a BidirectionalIterator.

regex_iterator甚至更糟.据说它们是基于其标签的ForwardIterators，但是该标准从未声明它们实际上是 ForwardIterators(与path::iterator不同).并且将它们指定为具有对成员对象的实际引用reference使得它们不可能成为真正的ForwardIterators.

regex_iterators are even worse in this regard. They are said to be a ForwardIterators based on their tag, but the standard never says that they actually are ForwardIterators (unlike path::iterator). And the specification of them as having reference be an actual reference to a member object makes it impossible for them to be true ForwardIterators.

请注意，我在C ++ 20之前的概念和Ranges概念之间没有任何区别.那是因为ForwardIterator概念仍然禁止存储迭代器. 这是设计使然.

Note that I made no distinction between the pre-C++20 concept and the Ranges Concept. That's because the ForwardIterator Concept still forbids stashing iterators. This is by design.

现在，显然，您可以在代码中做任何您想做的事情.但是，您无法控制的代码将归其所有者所有.他们将针对旧概念，新概念或它们指定的其他某些c/Concept或要求进行写作.因此，您的迭代器需要能够与他们的需求兼容.

Now obviously, you can do whatever you want in your code. But code you don't control will be under the domain of its owners. They will be writing against the old concepts, the new Concepts, or some other c/Concept or requirement that they specify. So your iterators need to be able to be compatible with their needs.

Ranges附加功能带来的算法使用了新的Concepts，因此您始终可以依靠它们与代理迭代器一起使用.但是，据我了解，范围概念不是 后移植到较旧的算法中.

The algorithms that the Ranges addition brings use the new Concepts, so you can always rely on them to work with proxy iterators. However, as I understand it, the Range Concepts are not back-ported into older algorithms.

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

Personally, I would suggest avoiding stashing iterator implementations entirely. By providing complete support for proxy iterators, most stashing iterators can be rewritten to return values rather than references to objects.

例如，如果存在path_view类型，则path::iterator可能会返回该类型，而不是完整的path.这样，如果您要执行昂贵的复制操作，则可以.同样，regex_iterator可能已返回匹配对象的副本.通过支持代理迭代器，新概念使以这种方式工作成为可能.

For example, if there were a path_view type, path::iterator could have returned that instead of a full-fledged path. That way, if you want to do the expensive copy operation, you can. Similarly, the regex_iterators could have returned copies of the match object. The new Concepts make it possible to work that way by supporting proxy iterators.

现在，隐藏式迭代器以一种有用的方式处理缓存.迭代器可以缓存其结果，以便重复使用*it仅执行一次昂贵的操作.但是请记住隐藏迭代器的问题:返回对其内容的引用.您不需要 只是为了进行缓存.您可以将结果缓存在optional<T>中(当迭代器增加/减少时，该值将无效).因此，您仍然可以返回一个值.它可能涉及其他副本，但reference不应为复杂类型.

Now, stashing iterators handle caching in a useful way; iterators can cache their results so that repeated *it usage only does the expensive operation once. But remember the problem with stashing iterators: returning a reference to their contents. You don't need to do that just to get caching. You can cache the results in an optional<T> (which you invalidate when the iterator is in/decremented). So you can still return a value. It may involve an additional copy, but reference shouldn't be a complex type.

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

Of course, all of this means that auto &val = *it; isn't legal code anymore. However, auto &&val = *it; will always work. This is actually a big part of the Range TS version of iterators.

这篇关于这可能是“最差的实现".代理容器上的迭代器?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！