通过值与引用传递std算法迭代器参数

Question

我想知道为什么在STL中的许多模板算法中,参数不是通过引用传递的,而是通过值传递的.以下是<iterator>标题中的示例:

template<class InputIterator>
typename iterator_traits<InputIterator>::difference_type
distance (InputIterator first, InputIterator last);

当我将两个迭代器传递给此函数时,它们将被复制.我天真的想法是,最好通过const-reference传递这些迭代器,以避免复制迭代器对象:

template<class InputIterator>
typename iterator_traits<InputIterator>::difference_type
distance (const InputIterator &first, const InputIterator &last);

可以说迭代器通常是非常小的对象,复制它们并不昂贵.但即便如此:便宜的复制将比没有复制更昂贵.

那么在STL版本中,迭代器是按值传递的原因是什么？

谢谢!

Answer 1

我想到的一件事是反对const引用的内容:使用它们时需要修改迭代器.

另一个实现细节可能是迭代器实际上只是作为指针实现的.大多数情况下参考也是如此.如果按值传递指针,则将其复制一次,但仅在需要时取消引用.然而,如果迭代器指针本身是由参考指针传递,然后是必须首先解除引用,只是为了得到迭代器,并且必须在每次迭代器访问的时间内完成.这是多余的.

Answer 2

对于某些廉价复制类型,按值传递它们实际上比通过引用传递更快.来自教程等的传统智慧指出,通过引用更快,但这不一定适用于廉价复制类型.

你如何按价值传递一个对象？您复制它,这意味着您获取值并将其推送到堆栈以进行函数调用.你如何通过参考传递？您将内存地址推送到堆栈,然后被调用的函数必须获取该地址的任何内容.现在,优化和缓存可能会发挥作用,使内存提取更便宜,但你仍然没有比从堆栈中获取精确值更便宜.在迭代器的情况下,通常只需要一个简单的指针.这是一个字长,复制非常便宜.

另外,请注意您建议传递const引用.这意味着它必须在被调用的函数中被复制以允许它被修改(例如在循环中递增).

Answer 3

std迭代器的概念是指针的泛化.std容器的迭代器通常实现为组成单个指针的类型.如果参数类型与指针一样便宜,则通过引用传递参数比通过值传递更昂贵.必须先取消引用对象,然后才能使用对象的值.有关详细信息,请参阅此答案.

因为几乎所有std算法都需要复制迭代器,为了获得最佳性能,迭代器的复制成本非常低.出于这个原因,找到一个迭代器是非常不寻常的,它通过值传递比引用要贵得多.

在std::distance- 和许多其他算法 - 的情况下,整个算法非常简单,编译器很可能会内联调用.如果内联调用,则参数是通过引用还是通过值传递并不重要.[请注意,内联函数调用与内联函数声明不同!]

如果迭代器通过值传递比通过引用更昂贵,并且函数调用没有内联,则可以通过rvalue-reference创建用于传递迭代器的参数.在这种罕见情况下的性能提升可能不值得额外的复杂性.