容器的迭代器可以产生除左值之外的东西吗？

Question

我或多或少得出的结论是,不可能编写一个符合条件的容器,其value_type没有直接存储在容器中.我认为这是不幸的,因为我经常最终希望我有容器,其中值类型是部分计算或由不连续的部分组装(下面的例子,但与问题没有直接关系).我知道如何编写使用代理对象的迭代器,虽然这很烦人.但我现在想知道这些野兽的C++标准是否确实存在空间.这里可能有太多的措辞; tl; dr版本很简单:§24.2.5的第1段和第6段真正意味着什么,以及违反明显意义的程度会破坏标准算法？或者,换句话说,它们如何被解释为允许代理迭代器？

正如Pete Becker所指出的那样,实际上没有任何东西迫使我的容器符合为标准库容器设定的要求.但是为了使用具有许多标准算法的容器,它必须要么具有至少为a的符合迭代器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,第14段.1:

X如果......,类或指针类型满足前向迭代器的要求

- 如果X是一个可变的迭代器,reference是一个引用T; if X是一个const迭代器,reference是一个引用const T

确实没有直接要求*a返回reference(a类型的地方X).要求是:

从表107(输入迭代器)*a必须是"可转换为T",如果a是不可引用的.

从表106(迭代器)*r必须有类型reference,其中r的类型的X&并且是dereferencable.

但是,表106还指定了++r返回X&,所以*++r必须如此reference.而且,(根据表107),*a++必须是reference,尽管(表109)a[n]仅需要"可转换为参考".我得说,我看不出*a哪里a是一个类型的X和*r地方r的类型是X&可能是不同的,但也许我错过了一些微妙.

也许这里有一个小小的摆动空间,但并不多; 在某些时候,你需要准备创建一个T,如果你实际上没有容器中的一个,那么你可以提供它的引用.

但踢球者是

§24.2.5,第14段.6(a并且b是类型的值X):如果a和b都是可解除引用的,那么a == b当且仅当*a和*b并且绑定到同一个对象时.

我找不到正式的定义bound to,但在我看来,制作非可寻址对象迭代器的通常策略是创建一个代理对象,通常存储在迭代器本身内.在这种情况下,除非禁止在两个不同的迭代器对象之间进行相等比较,否则需要非常慷慨地理解"约束"意味着以何种方式解释24.2.5/6,即使它们在逻辑上指示相同的位置在容器中.

另一方面,我注意到DietmarKühl在回答这个问题时应该知道:

C++ 2011得到了宽松的要求,并不一定要求迭代器产生左值

那么,迭代器可以返回一个代理,还是不能呢？如果可以的话,这种代理的本质是什么？我认为这样的迭代器不符合的原因在哪里失败？

---

正如所承诺的那样,一些容器的有效value_types不会在容器中连续存储:

1)紧凑的关联容器,其键和值类型可以更有效地存储在两个单独的向量中.(将密钥保存在向量中也可以提高缓存友好性,并减少分配开销.)

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

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

4)聚合类型的容器的视图,其仅具有一些值.(很可能,底层容器和视图都是元组,其中视图元组的类型列表是底层容器类型的子集,可能是不同的顺序).

我相信其他人可以轻松添加到此列表中; 这些只是我在过去几个月中以某种方式破解的.

Answer 1

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