15

我想知道为什么在 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 版本中，迭代器是按值传递的原因是什么？

谢谢！

4

4 回答 4

14

我想到的一件事是与const参考中的矛盾：迭代器在使用时需要修改。

另一个实现细节可能是迭代器实际上只是实现为指针。在大多数情况下，参考也是如此。如果按值传递指针，则复制一次，但仅在需要时取消引用。但是，如果迭代器指针本身是由引用指针传递的，那么必须首先取消引用，只是为了到达迭代器，并且每次访问迭代器时都必须这样做。那是多余的。

于 2013-08-01T09:57:12.987 回答
10

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

如何按值传递对象？您制作它的副本，这意味着您获取该值并将其推送到堆栈以进行函数调用。你如何通过引用传递？您将内存地址推入堆栈，然后被调用的函数必须获取该地址处的任何内容。现在，优化和缓存可能会发挥作用，使内存获取更便宜，但你仍然没有比从堆栈中获取确切值更便宜。在迭代器的情况下，这通常就像一个指针一样简单。这是一个字长，复制起来非常便宜。

另外，请注意您建议传递 const 引用。这意味着无论如何都必须在被调用的函数中复制它才能对其进行修改（例如在循环中递增）。

于 2013-08-01T08:22:15.693 回答
6

std迭代器的概念是指针的泛化。容器的迭代器std通常被实现为组成单个指针的类型。对于与指针复制一样便宜的参数类型，通过引用传递参数比通过值传递更昂贵。在可以使用对象的值之前，必须取消对对象的引用。有关更多详细信息，请参阅此答案。

因为几乎所有std算法都需要复制迭代器，为了获得最佳性能，迭代器复制成本低已经很重要。出于这个原因，很难找到一个通过值传递比通过引用传递更昂贵的迭代器。

在std::distance- 和许多其他算法的情况下 - 整个算法非常简单，以至于编译器很可能会内联调用。如果调用是内联的，则参数是通过引用传递还是通过值传递都没有关系。[请注意，内联函数调用与内联函数声明不同！]

在迭代器通过值传递比通过引用更昂贵的情况下，并且函数调用没有被内联，您可以为通过右值引用传递迭代器创建一个参数。在这种罕见情况下的性能提升可能不值得额外的复杂性。

于 2013-08-01T10:09:34.027 回答
2

大多数算法都会修改它们的参数。例如，distance可以按如下方式实现1：

template<class InputIterator>
typename iterator_traits<InputIterator>::difference_type
distance (InputIterator first, InputIterator last) {
    typename iterator_traits<InputIterator>::difference_type result{};
    while (first++ != last)
        ++result;
    return result;
}

first如果您作为const参考传递，显然这不起作用。

如果你将它作为非引用传递它也不起作用，const因为在大多数调用上下文中，调用者的对象不能被修改（例如，如果你将结果传递container.begin()给函数。

当然，您仍然可以通过引用传递，在函数内部const制作副本，然后对其进行修改。在这一点上，我们将一无所获。

再加上 C++ 标准建议迭代器应该是复制成本低的轻量级类型，通过值传递它们更简单，在大多数情况下更有效：

但即便如此：便宜的复制会比不复制更昂贵。

不对。您还需要复制引用（在非内联函数调用的情况下，它将被实现为指针）。然后您需要取消引用该指针，这也会增加开销。与在许多情况下可能与复制指针一样便宜的直接副本相比，并且不会产生任何取消引用开销。

1当然，真正的实现会针对随机访问迭代器进行优化，使其具有恒定的而不是线性的运行时间。上述实现仅用于说明。

于 2013-08-02T10:01:19.840 回答