比较两个C++迭代器的性能代价

Question

一般来说，两个STL容器迭代器之间的相等比较有什么性能成本呢？我只是在谈论已定义的操作；也就是说，比较指向同一对象的两个迭代器。

我的具体用例是我有一个std::map，它可能有非常大的元素，很多元素，或者两者都有。如果我不知道两个迭代器之间的相等比较有隐藏的惩罚，它可能会影响我的代码性能。

- George Hilliard

Answer 1

通常情况下，比较两个迭代器的性能取决于STL的实现。

然而，就时间复杂度而言，C++标准对输入迭代器（因此也包括正向迭代器、双向迭代器和随机访问迭代器）的比较施加了限制，即需要摊销常数时间。特别地，这意味着对于一个std::map，它的迭代器不能通过比较键的相等性来进行比较，因为这样做将与键的长度成线性关系。

- Oswald

---

这并没有说什么。比较两个迭代器的唯一方法是测试它们是否指向相同的元素。这并没有说明执行此比较的成本（或廉价程度）。 - jalf

@ChristianRau 不，这个答案没有涉及到任何那方面的内容。它只是说比较两个C++迭代器的成本就是测试它们是否相等的成本（这是显而易见且无益的），并且它可能就像比较两个指针一样简单。 - jalf

@jalf 如果它“可以”，为什么不呢？无论如何，你都不能期望得到更精确的答案，正如第一句话所说（但我在另一个答案中看到您至少可以从标准中期望O(1)）。 - Christian Rau

@ChristianRau：是的，我可以期望得到更精确的答案。例如，我可以期望得到像你说的那样，它必须是一个常数时间操作。或者我可以期望得到一个指定对象值不被考虑的答案，因此元素类型（或每个元素的大小）是无关紧要的。我可以期望得到一些实际的信息，而不是啰嗦的“谁知道呢”。 - jalf

@ChristianRau 迭代器不需要迭代具有有限元素数量的容器。这意味着，常数时间复杂度要求不能仅限于该容器中的元素数量。相反，常数时间复杂度要求是针对所有相同类型的迭代器而言的。 - Oswald

Answer 2

大多数STL容器的operator==()只是原始指针比较，除非用于边界检查，否则毫无意义。而且，如果你比较来自不同容器的迭代器，这是未定义的行为。

如果你重载了这个操作符或使用外部比较函数，性能取决于你要比较的对象有多大。

也许我误解了你的问题，不太清楚你所说的“迭代器比较”和你的用例是什么。

- Wintermute

Answer 3

草案标准指出迭代器操作是平摊常数时间的。

24.2.1 一般情况 [iterator.requirements.general]

8 所有迭代器类别仅需要对于给定类别可实现的函数以恒定时间（平摊）进行操作。因此，迭代器的要求表不具有复杂度列。

如果您查看迭代器操作的签名，没有与底层元素T本身相对应的参数或返回类型，只需要T*和T&。甚至operator==也不必直接比较两个任意大的元素T本身。

然而，这并不为迭代器操作提供了硬实时的上限。特别地，迭代器可以进行非常昂贵的边界检查（very costly bounds checking），但这些调试模式下的安全保护通常可以在发布版本中省略。

- TemplateRex

---

啊，好答案，附上引用。我想这就是我想要的答案。 - George Hilliard