在“i <”中矢量.size()”循环条件，每次迭代都会调用 size() 吗？

Question

在以下代码中：

std::vector<int> var;
for (int i = 0; i < var.size(); i++);

size() 成员函数是为每次循环迭代调用，还是只调用一次？

Answer 1

理论上，它每次都会被调用，因为 for 循环：

for(initialization; condition; increment)
    body;

被扩展为类似的东西

{
    initialization;
    while(condition)
    {
        body;
        increment;
    }
}

（注意大括号，因为初始化已经在内部作用域中）

实际上 ，如果编译器知道您的条件的一部分在整个循环期间保持不变并且它没有副作用，它可以足够聪明地将其移出。这通常是在未写入其参数的循环中使用 strlen 和类似的东西（编译器熟知的）来完成的。

然而必须注意的是，最后一个条件的证明并不总是微不足道的。一般来说，如果容器是函数的本地容器并且从不传递给外部函数，那就很容易；如果容器不是本地的（例如，它是通过引用传递的 - 即使它是 const）并且循环体包含对其他函数的调用，则编译器通常必须假设此类函数可能会更改它，从而阻塞吊装长度的计算。

如果您知道条件的一部分评估起来“昂贵”，那么手动进行优化是值得的（而这样的条件通常不是，因为它通常归结为指针减法，这几乎肯定是内联的）。

---

编辑：正如其他人所说，一般来说，对于容器来说，最好使用迭代器，但对于 vector 来说，它并不那么重要，因为通过 operator[ 随机访问元素] 保证为 O(1)；实际上，对于向量，它通常是指针总和（向量基址+索引）和解引用与指针增量（前一个元素+1）和迭代器的解引用。由于目标地址仍然相同，我认为您无法从缓存局部性方面从迭代器中获得一些东西（即使是这样，如果您没有在紧密循环中遍历大数组，您甚至不应该注意到这样的情况）种改进）。

相反，对于列表和其他容器，使用迭代器而不是随机访问可能非常重要，因为使用随机访问可能意味着每次访问列表时都会遍历，而递增迭代器只是指针取消引用。

Answer 2

每次都会调用 size() 成员函数，但这将是一个非常糟糕的实现，不会内联它，并且一个奇怪的实现，它不是对固定数据的简单访问或两个指针相减。
不管怎样，在你分析你的应用程序并发现这是一个瓶颈之前，你不应该担心这些琐事。

但是，您应该注意的是：

1. 向量索引的正确类型是std::vector::size_type。
2. 在某些类型（例如某些迭代器）中，i++可能比++i慢。

因此，循环应该是：

for(vector<int>::size_type i=0; i<var.size(); ++i)
  ...

Answer 3

它每次都会被“调用”，但我将调用放入引号中，因为它实际上可能只是一个内联方法调用，因此您不必担心它的性能。

为什么不使用 vector::iterator 来代替呢？

Answer 4

你的问题的问题在于它没有任何意义。 C++ 编译器将一些源代码翻译成二进制程序。要求是生成的程序必须根据 C++ 标准的规则保留代码的可观察效果。这段代码：

for (int i = 0; i < var.size(); i++); 

根本没有任何可观察到的效果。此外，它不会以任何方式与周围的代码交互，并且编译器可能会完全优化它；即没有生成对应的程序集。

为了使您的问题有意义，您需要指定循环内发生的情况。问题在于

for (int i = 0; i < var.size(); i++) { ... }

答案很大程度上取决于 ... 实际是什么。我相信@MatteoItalia 提供了一个非常好的答案，只需添加我所做的一些实验的描述。考虑以下代码：

int g(std::vector<int>&, size_t);

int f(std::vector<int>& v) {
   int res = 0;
   for (size_t i = 0; i < v.size(); i++)
      res += g(v, i);
   return res;
}

首先，即使调用 var.size() 几乎 100% 肯定会内联启用的优化，并且此内联通常会转换为两个指针的减法，但这仍然会带来循环一些开销。如果编译器无法证明向量大小被保留（这通常是非常困难的，甚至是不可行的，例如在我们的例子中），那么您最终将得到不必要的加载和< em>sub（可能还有shift）指令。使用 GCC 9.2、-O3 和 x64 生成的循环汇编为：

.L3:
    mov     rsi, rbx
    mov     rdi, rbp
    add     rbx, 1
    call    g(std::vector<int, std::allocator<int> >&, unsigned long)
    add     r12d, eax
    mov     rax, QWORD PTR [rbp+8] // loads a pointer
    sub     rax, QWORD PTR [rbp+0] // subtracts another poniter
    sar     rax, 2                 // result * sizeof(int) => size()
    cmp     rbx, rax
    jb      .L3

如果我们按如下方式重写代码：

int g(std::vector<int>&, size_t);

int f(std::vector<int>& v) {
   int res = 0;
   for (size_t i = 0, e = v.size(); i < e; i++)
      res += g(v, i);
   return res;
}

那么，生成的汇编更简单（因此更快）：

.L3:
    mov     rsi, rbx
    mov     rdi, r13
    add     rbx, 1
    call    g(std::vector<int, std::allocator<int> >&, unsigned long)
    add     r12d, eax
    cmp     rbx, rbp
    jne     .L3

的值向量的大小简单地保存在寄存器（rbp）中。

我什至尝试了一个不同的版本，其中向量被标记为 const：

int g(const std::vector<int>&, size_t);

int f(const std::vector<int>& v) {
   int res = 0;
   for (size_t i = 0; i < v.size(); i++)
      res += g(v, i);
   return res;
}

令人惊讶的是，即使当 v.size() 无法在此处更改时，生成的程序集与第一种情况（带有附加的 mov、sub 和 sar 指令）。

现场演示位于此处。

此外，当我将循环更改为：

for (size_t i = 0; i < v.size(); i++)
   res += v[i];

then 时，在汇编级别的循环内没有对 v.size() 进行评估（指针相减）。 GCC 能够在这里“看到”循环体不会以任何方式改变大小。

Answer 5

每次都必须调用它，因为 size() 可能每次都会返回不同的值。

因此，没有什么大的选择，它只是必须的。

Answer 6

正如其他人所说，

• 语义必须就像每次
• 可能内联时都调用它一样，并且可能是一个简单的函数，

在其之上，

• 足够聪明的优化器可能能够推断出它是一个没有副作用的循环不变式，并且完全删除它（如果代码是内联的，这会更容易，但即使不是内联，如果编译器进行全局优化，这也是可能的）

Answer 7

但它可以通过这种方式完成（前提是该循环仅打算读/写而不实际更改向量的大小）：

for(vector<int>::size_type i=0, size = var.size(); i < size; ++i) 
{
//do something
}

在上面的循环中，您只需一次对 size 的调用，与内联或不内联的大小无关。

Answer 8

正如其他人所说，编译器应决定如何处理编写的实际代码。关键是每次都会被调用。但如果您想提高性能，最好在编写代码时考虑一些因素。你的情况就是其中之一，还有其他的情况，就像这两段代码之间的区别：

for (int i = 0 ; i < n ; ++i)
{
   for ( int j = 0 ; j < n ; ++j)
       printf("%d ", arr[i][j]);
   printf("\n");
}
for (int j = 0 ; j < n ; ++j)
{
   for ( int i = 0 ; i < n ; ++i)
       printf("%d ", arr[i][j]);
   printf("\n");
}

区别在于，第一个不会对每个引用改变太多的ram页面，但另一个会耗尽你的缓存和TLB和其他东西。

而且内联也没有多大帮助！因为调用函数的顺序将保持为 n(向量的大小) 次。虽然它在某些地方有帮助，但最好的办法是重写你的代码。

但！如果你想让编译器对你的代码进行优化，则永远不要放置 volatile，如下所示：

for(volatile int i = 0 ; i < 100; ++i)

它会阻止编译器优化。
如果您需要另一个性能提示，请使用寄存器而不是易失性。

for(register int i = 0 ; i < 100; ++i)

编译器将尝试不将 i 从 CPU 寄存器移动到 RAM。不能保证它能做到，但它会做到最好；）

Answer 9

我认为如果编译器可以最终推断出变量var在“循环体”内没有被修改

for(int i=0; i< var.size();i++) { 
    // loop body
}

，那么上面的内容可能会被转置为等价的

const size_t var_size = var.size();
for( int i = 0; i < var_size; i++ ) { 
    // loop body
}

但是，我是不太确定，所以欢迎评论:)

另外，

• 在大多数情况下，size() 成员函数是内联的，因此这个问题不必担心

• 这个问题可能同样适用于始终用于迭代器的 end()基于循环，即 it != container.end()

• 请考虑使用 size_t 或 vector::size_type 作为<的类型code>i [请参阅下面 Steve Jessop 的评论。]

Answer 10

测试了 900k 次迭代
预先计算大小需要 43 秒，使用 size() 调用需要 42 秒。

如果保证向量大小在循环中不会改变，最好使用预先计算的大小，否则别无选择，必须使用 size()。

#include <iostream>
#include <vector>

using namespace std;

int main() {
vector<int> v;

for (int i = 0; i < 30000; i++)
        v.push_back(i);

const size_t v_size = v.size();
for(int i = 0; i < v_size; i++)
        for(int j = 0; j < v_size; j++)
                cout << "";

//for(int i = 0; i < v.size(); i++)
//      for(int j = 0; j < v.size(); j++)
//              cout << "";
}