为什么将比较对象与“end()”迭代器进行比较是合法的？

Question

根据C++标准（3.7.3.2/4），使用（不仅是解引用，还包括复制、转换等）无效指针是未定义的行为（如果有疑问，也可以参见此问题）。现在，遍历STL容器的典型代码看起来像这样：

std::vector<int> toTraverse;
//populate the vector
for( std::vector<int>::iterator it = toTraverse.begin(); it != toTraverse.end(); ++it ) {
    //process( *it );
}

std::vector::end()是一个指向容器中理论上的最后一个元素之后位置的迭代器。在那里没有元素，因此通过该迭代器使用指针是未定义的行为。

那么!= end()是如何工作的呢？为了进行比较，需要构造一个包装无效地址的迭代器，然后将该无效地址用于比较，这又是未定义的行为。这种比较是否合法，为什么？

- sharptooth

---

3.7.3.2/4并未说明复制和转换无效指针是UB。我认为你的解释过于宽泛了。 - Kirill V. Lyadvinsky

@Kirill V. Lyadvinsky：也许是这样，但这是链接问题的核心，共识是强制转换和分配无效指针是未定义行为。 - sharptooth

Answer 1

end()唯一的要求是++(--end()) == end()。 end()可以只是迭代器所在的一个特殊状态，没有理由让end()迭代器对应任何指针。
此外，即使它是指针，比较两个指针也不需要任何解引用。考虑以下代码：

char[5] a = {'a', 'b', 'c', 'd', 'e'};
char* end = a+5;
for (char* it = a; it != a+5; ++it);

那段代码完全可以正常工作，并且与您的向量代码相似。

- Nick Lewis

---

那句话比我的回答更好。我给你点赞。 - sbi

@Nick Lewis：我不会反驳其他观点，但标准规定即使使用无效指针也是未定义行为，因此char* end = a+5;是未定义行为。 - sharptooth

超出数组结尾的位置不是无效指针。 - UncleBens

Nick，我认为你的意思是 ++(--end()) == end()，因为例如 end()-- == end() 也会被评估为真，因为后缀形式返回未修改的原始值。 - fredoverflow

@FredOverflow: 你说得完全正确，我已经修复了这段代码。实际上，这段代码存在另一个错误：end()--返回的是end()，于是它尝试对end()进行增量操作，这是不被允许的。 - Nick Lewis

Answer 2

你说得没错，一个无效的指针是不能使用的，但是你错了，指向数组中最后一个元素之后的元素的指针不是无效的指针 - 它是有效的。C标准第6.5.6.8节规定了这是明确定义的和有效的:

如果表达式P指向数组对象的最后一个元素，则表达式(P)+1指向数组对象的最后一个元素之后的一个元素...

但是，它不能被解引用:

如果结果指向数组对象的最后一个元素之后的一个元素，则不能将其用作评估的一元*运算符的操作数...

- JoeG

---

关于C++的最后一条引用不正确。如果您知道在数组之后还有一个元素类型的另一个对象（如多维数组），那么您可以对其进行解引用操作。 - Johannes Schaub - litb

你有相关的参考资料吗？这只适用于C++而不是C吗？ - JoeG

在C ++中，这是有效的（不是未定义行为），而在C中则是未定义行为。但前提是确实存在一个对象在那个位置。请参见“5.7 / 5”和“3.9.2 / 3”。 - Johannes Schaub - litb

因为C和C++并不相同，正如上面所提到的那样，所以被踩是有道理的。这有点误导人。 - FrankHB

这似乎并没有解决问题。迭代器通常是类类型，而不是原始指针。此外，C标准引用对C++来说无关紧要。C++标准并没有说这些事情。 - M.M

Answer 3

超出末尾的位置不是无效值（无论是常规数组还是迭代器）。您不能对其进行引用，但可以用于比较。

std::vector<X>::iterator it;

这是一个单一的迭代器。你只能给它分配一个有效的迭代器。

std::vector<X>::iterator it = vec.end();

这是一个完全有效的迭代器。您不能对其进行解引用，但可以将其用于比较并递减它（假设容器具有足够的大小）。

- UncleBens

---

为什么“超出结尾一个”是有效的呢？ - sharptooth

C标准的第6.5.6.8节明确允许它。 - JoeG

@sharptooth：标准谈到了在许多地方比较数组末尾之外的地址的有效性。想象一下，如果不是这种情况，当循环、复制等操作时，您将无法使用！=来检测数组的末尾，这将非常繁琐。但是，解引用超出末尾一个位置是无效的。 - markh44

我认为“超出末尾一位”被定义为有效的另一个好理由是，这极大地简化了数组指针算术运算。如果它无效，你必须使用last-first+1来获取数组的大小。只是猜测而已。 - Björn Pollex

@BjörnPollex，这在动态数组为空的情况下是行不通的，因为根本就没有“last”。 - curiousguy

Answer 4

什么？没有规定迭代器必须只使用指针实现。

它可以有一个布尔标志，当增量操作看到它通过有效数据的末尾时设置该标志。

- unwind

Answer 5

标准库容器的end()迭代器的实现是由具体实现定义的，因此实现可以使用它知道平台支持的技巧。
如果您实现了自己的迭代器，那么您可以做任何您想做的事情 - 只要符合标准。例如，如果您的迭代器存储指针，则可以存储NULL指针以表示结束迭代器。或者它可以包含布尔标志或其他内容。

- sbi

---

没有任何技巧要求 - 最后一个元素的下一个是一个有效的指针，但不能被解引用。 - JoeG

@Joe：我并没有说需要使用技巧。我只是说实现可以玩一些小花招。（并尝试为列表使用一个超出末尾的迭代器。）所以我不确定这个踩的目的是什么。 - sbi

这个问题涉及为什么可以合法使用超出数组末尾的指针，您的回答暗示end()之所以有效是因为实现定义的技巧。 - JoeG

@Joe：我理解这个问题是如何为任何容器实现end()方法是合法的（而不仅仅是针对std::vector）。我甚至认为讨论std::vector没有意义，因为我（错误地）假设sharptooth知道指向数组末尾的指针是允许的。即使不是这样，实现始终可以为一个额外的对象分配空间并使用其地址作为end() - 这就是为什么我认为指向数组末尾的指针规则仅适用于数组，而不适用于STL容器的原因。因此，我的答案是关于任何STL容器，而不是std::vector。 - sbi

Answer 6

我在这里回答，因为其他的回答现在已经过时了；尽管如此，它们对于问题并不完全正确。

首先，C++14已经改变了问题中提到的规则。通过无效指针值进行间接引用或将无效指针值传递给解除分配函数仍然是未定义的，但是其他操作现在是实现定义的，请参见 C++实现中“无效指针值”转换的文档。

第二点，措辞很重要。在应用规则时，你不能绕过定义。关键点在于“无效”一词的定义。对于迭代器，这是在[iterator.requirements]中定义的。尽管指针也是迭代器，但它们的“无效”含义略有不同。指针的规则将“无效”解释为“不要通过无效值进行间接引用”，这是迭代器“不可解引用”的特例；然而，“不可解引用”并不意味着迭代器是“无效”的。 “无效”明确定义为“可能是奇异的”，而“奇异”值被定义为“与任何序列都不相关”（在“可解引用”的定义段落中）。该段甚至明确定义了“超出末尾值”。

从 [iterator.requirements] 标准的文本中可以清楚地看出以下内容：

• 超过末尾的值不被假定为可解引用（至少不被标准库），正如标准所述。
• 可解引用的值不是奇异的，因为它们与序列相关联。
• 超过末尾的值不是奇异的，因为它们与序列相关联。
• 如果迭代器肯定不是奇异的（通过“无效迭代器”的定义否定），则该迭代器不是无效的。换句话说，如果一个迭代器与一个序列相关联，则它不是无效的。

end() 的值是一个超过末尾的值，在它被使无效之前，它与一个序列相关联。因此，根据定义，它实际上是有效的。 即使对“无效”的误解字面意义上来说，指针的规则在这里也不适用。

这段文本讲述了关于使用==比较值的规则。这些规则在输入迭代器要求中定义，并被其他类型的迭代器（如正向迭代器、双向迭代器等）所继承。 更具体地说，有效的迭代器 在迭代器的域上是可以比较的，用==进行比较。此外，前向迭代器的要求指定了域在基础序列上。容器要求还指定了iterator和const_iterator成员类型 在任何迭代器类别满足前向迭代器的要求。因此，end()和同一容器中的迭代器之间的==比较是必须定义明确的。作为标准容器，vector<int>也遵循这些要求。这就是整个故事。

第三，即使`end()`是一个指针值（在`vector`实例的迭代器的优化实现中可能会发生这种情况），问题中的规则仍然不适用。原因如上所述（以及其他一些答案中提到的）：“无效”涉及间接引用，而不是比较。标准明确允许按照指定的方式比较超出末尾的值。 还要注意的是，ISO C++不是ISO C，它们也有细微的差异（例如，在不同数组中的指针值上使用`<`时，未指定与未定义），尽管它们在这里有类似的规则。

- FrankHB

Answer 7

简单来说，迭代器不一定是指针。

它们有一些相似之处（例如可以对其进行解引用），但仅限于此。

- Roddy

Answer 8

除了已经提到的（迭代器不需要是指针），我想指出你引用的规则。

根据C++标准（3.7.3.2/4），使用（不仅仅是解引用，还包括复制、转换等）无效指针是未定义行为。

无论如何，这个规则不适用于end()迭代器。基本上，当你有一个数组时，它的所有元素的指针，加上一个超过末尾的指针，再加上一个在数组开始之前的指针，都是有效的。这意味着：

int arr[5];
int *p=0;
p==arr+4; // OK
p==arr+5; // past-the-end, but OK
p==arr-1; // also OK
p==arr+123456; // not OK, according to your rule

- jpalecek

---

为什么“在第一个元素之前”和“超出最后一个元素”的指针是有效的？ - sharptooth

p==arr-1; 调用未定义的行为（“如果指针操作数和结果都指向同一数组对象的元素，或者指向数组对象的最后一个元素之一，则评估不应产生溢出；否则，行为是未定义的。”） - JoeG

“plus one pointer past-the-end”是有效的，尽管措辞不够准确。而“plus one pointer before the start of the array”则是无效的。标准对于1-past-end有特殊规定，但并未对1-before-start做出类似的特殊规定。 - underscore_d