一般来说，在两个 STL 容器迭代器之间进行相等比较的性能成本是多少？我只是在谈论定义的操作；也就是说，比较两个引用同一个对象的迭代器。
我的具体用例是我有一个std::map可能包含非常大的元素、很多元素或两者兼有的元素。如果这样一个映射上的两个迭代器之间的相等比较隐藏了我不知道的惩罚，它可能会影响我的代码的性能。
问问题
1326 次
3 回答
5
通常，比较两个迭代器的性能取决于 STL 的实现。
但是，关于时间复杂度，C++ 标准施加了限制，即输入迭代器（以及因此前向迭代器、双向迭代器和随机访问迭代器）的比较需要分摊的常数时间。特别是，这意味着对于 a std::map<std::string, int>，它的迭代器不能通过比较键的相等性来比较，因为这将与键的长度成线性关系。
于 2013-10-14T03:51:35.350 回答
4
大多数 STL 容器operator==()只是原始指针比较。除非用于边界检查，否则这是没有意义的。此外，如果您正在比较来自不同容器的迭代器 - 这是未定义的行为。
如果您覆盖此运算符或使用外部比较函数，则性能取决于您要比较的对象有多大。
可能我的问题错了，“迭代器比较”是什么意思以及你的用例是什么并不是 100% 清楚。
于 2013-10-14T03:43:37.243 回答
4
24.2.1 一般 [iterator.requirements.general]
8 迭代器的所有类别只需要在恒定时间内（摊销）对于给定类别可实现的那些函数。因此，迭代器的需求表没有复杂度列。
如果您查看迭代器操作的签名，则没有与底层元素T本身相对应的参数或返回类型，只有T*并且T&是必需的。甚至operator==不必直接比较两个任意大的元素T本身。
然而，这并没有给出迭代器操作的硬实时上限。特别是，迭代器可以进行非常昂贵的边界检查，但这些 Debug 模式的安全防护通常可以在 Release 构建中省略。
于 2013-10-14T07:12:28.053 回答