c++ - 容器的迭代器能产生左值以外的东西吗？

Question

我或多或少地得出结论，不可能编写一个不直接存储在容器中的 value_type 的一致性容器。我认为这很不幸，因为我经常希望我的容器中的值类型要么是部分计算的，要么是由不连续的部分组装而成的(下面的示例，但与问题没有直接关系)。我知道如何编写使用代理对象的迭代器，尽管这很烦人。但我现在想知道 C++ 标准中是否真的有空间用于此类野兽。这里可能有太多的措辞； tl;dr 版本很简单:§24.2.5 的第 1 段和第 6 段的真正含义是什么，违反明显含义会在多大程度上破坏标准算法？或者，换句话说，如何将它们解释为允许代理迭代器？

正如 Pete Becker 指出的那样，实际上没有什么可以强制我的容器符合标准库容器的要求。但是为了使用具有许多标准算法的容器，它必须具有至少具有 forward_iterator_tag 的符合迭代器。 ，或者它必须对此撒谎，但仍然设法满足特定算法对其迭代器强加的操作(如果不是正式的)要求。

这是我的推理:

表 96(第 23.2.1 节)，容器要求，包括:

Expression     Return type         Assertion/note
------------   -------------       ---------------------
X::iterator    iterator type       any iterator category
               whose value         that meets the
               type is T           forward iterator
                                   requirements.
                                   Convertible to
                                   const_iterator.

 a.begin()     iterator;
               const_iterator for
               constant a.

现在，向前迭代器:

§ 24.2.5, para. 1:

A class or pointer type X satisfies the requirements of a forward iterator if …

— if X is a mutable iterator, reference is a reference to T; if X is a const iterator, reference is a reference to const T

确实对 *a没有直接要求返回 reference (其中 a 的类型是 X )。要求是:

from Table 107 (input iterators) *a must be "convertible to T" if a is dereferencable.

from Table 106 (iterators) *r must have type reference where r is of type X& and is dereferencable.

但是，表 106 还指定了 ++r返回 X& , 所以 *++r必须是 reference .此外，(根据表 107)， *a++必须是 reference ，虽然(表 109) a[n]只需要“可转换为引用”。我不得不说我不明白 *a哪里 a类型为 X和 *r哪里 r类型为 X&可能会有所不同，但也许我错过了一些微妙之处。

也许这里有一点回旋余地，但不多；在某些时候，您需要准备好创建 T ，如果您实际上在容器中没有一个，那么您可以提供对它的引用。

但关键是

§ 24.2.5, para. 6 (a and b are values of type X): If a and b are both dereferenceable, then a == b if and only if *a and *b are bound to the same object.

我找不到 bound to 的正式定义，但在我看来，制作不可寻址对象的迭代器的通常策略是创建一个代理对象，通常存储在迭代器本身内部。在这种情况下，除了禁止在两个不同的迭代器对象之间成功进行相等比较之外，还需要对“绑定(bind)到”的含义有非常大的理解，即使它们在逻辑上指示相同的位置在容器中。

另一方面，我注意到应该知道的 Dietmar Kühl 在他对 this question 的回复中说:

C++ 2011 got relaxed requirements and iterators aren't necessarily required to yield an lvalue

那么，迭代器可以返回代理，还是不能？如果可以，这种代理的性质是什么？我认为这种迭代器不符合标准的推理在哪里失败？

正如 promise 的那样，一些有效 value_types 不会连续存储在容器中的容器:

1) 一个紧凑的关联容器，其键和值类型可以更有效地存储在两个单独的 vector 中。 (将键保存在 vector 中还可以提高缓存友好性，并减少分配开销。)

2) 一个 vector<T>伪装成 map<integer_type, T> ，简化与其他的互操作性 map<X, T>类型。

3) 通过压缩其他几个容器形成的逻辑容器，产生一个逻辑 value_type，即 tuple对压缩容器的值类型的引用。 (在某些应用程序中，一个或多个压缩容器可能会被完全计算，或者作为其他值的函数，或者作为序列号。)

4) 聚合类型容器的 View ，它只有一些值。 (很可能，底层容器和 View 都是元组，其中 View 元组的类型列表是底层容器类型的子集，可能以不同的顺序)。

我相信其他人可以很容易地添加到这个列表中；这些只是我在过去几个月中以某种方式破解的那些。

Answer 1

不要通过考虑“符合标准的容器”来限制自己:标准中没有任何内容依赖于拥有一个。将容器要求视为描述标准中定义的容器要求的速记方式。而已。只要您的容器生成的迭代器是有效的，您就可以使用所有相应的算法，并且大概可以使用您自己编写的算法。