C++向量的at/[]运算符速度

Question

为了让函数有修改向量的选项，我不能这样做。

curr = myvec.at( i );
doThis( curr );
doThat( curr );
doStuffWith( curr );

但我必须要做的是：

doThis( myvec.at( i ) );
doThat( myvec.at( i ) );
doStuffWith( myvec.at( i ) );

（正如我的另一个问题的答案所指出的）

• 我打算大量调用myvec.at()，那它有多快，与使用变量存储结果的第一个示例相比如何？

• 我有其他选择吗？我能以某种方式使用指针吗？

当情况严重时，每秒将有数千次调用myvec.at()。因此，任何一点性能消耗都很重要。

- sub

---

除了性能方面的考虑，你需要问自己使用 at() 而不是 [] 有什么好处。索引边界检查对于调试很有用，但是当你在调试模式下编译时，[] 也会执行此操作。如果代码已经正确，使用 at() 而不是 [] 是没有必要的，而且是多余的。写出正确的代码才是王道。 - Konrad Rudolph

红鼻独角兽：并非所有的编译器在调试模式下都会检查[]。 - Brian Neal

@红鼻独角兽：Brian的评论不仅正确，而且在调试模式下测试不能找出所有问题。根据很多因素，使用.at()代替[]可能在生产代码中非常值得。 - David Thornley

以定义的方式崩溃比随意践踏内存要好得多。是的，这可能会不方便，但它确实可以防止各种安全关键代码中的攻击。误引本·富兰克林的话，“那些可以放弃基本安全以获取一点临时速度的人，既不值得安全也不值得速度。” - Donal Fellows

引用我自己的话：“想找Java的人知道在哪里找到它。” - MSalters

Answer 1

你可以使用引用：

int &curr = myvec.at(i);
// do stuff with curr

at 成员函数会进行边界检查以确保参数在 vector 的大小范围内。使用性能分析工具是了解它与 operator[] 相比慢多少的唯一方法。在这里使用引用允许您进行一次查找，然后在其他地方使用结果。如果您想保护自己免受意外更改值的影响，可以将其设置为指向 const 的引用。

- Michael Kristofik

---

取决于“给函数修改向量的选项”的含义。一些向量修改会使引用无效 - 任何导致重新分配的操作。 - Steve Jessop

@Steve，这是一个很好的观点。我假设OP正在根据给定的示例代码修改向量中的值。如果函数可能会修改向量本身，我们需要采用不同的方法。 - Michael Kristofik

Answer 2

从我自己使用类似代码（在gcc和Linux下编译）的测试来看，operator[] 可以比 at 更快，不是因为边界检查，而是因为异常处理的开销。用自己的边界检查替换 at（当越界时抛出异常）并在越界时引发 assert 可以带来可衡量的改进。

正如 Kristo 所说，使用引用可以让你只承担一次边界检查的开销。

忽略边界检查和异常处理开销，operator[] 和 at 都应该被优化为等同于直接数组访问或通过指针直接访问。

但正如 Chris Becke 所说，没有什么能替代性能分析。

- Josh Kelley

---

实际上触发异常通常很慢，但检查异常并不一定太慢。 - Martin Beckett

@Martin：这在很大程度上取决于实现方式。在许多情况下，昂贵的是堆栈展开，而不是“触发”（抛出）。 - MSalters

@MSalters - 是的，但如果异常不被捕获，测试并不一定昂贵。 - Martin Beckett

Answer 3

Operator[]可能比at更快，因为它不需要进行边界检查。

您可以将curr设置为引用以实现您想要的功能。

MyClass & curr = myvec.at(i);

在感到担忧之前，您可能需要进行一些基准测试。现代处理器可以轻松处理数千个操作每秒。

- Mark Ransom

Answer 4

第一个方法不起作用的原因是您没有将指针或迭代器设置为第i个变量的地址。相反，您将curr设置为第i个变量的值，然后修改curr。我假设doThis和doThat是引用。

请这样做：

MyObject& curr = myvec.at( i );

- wheaties

Answer 5

当性能成为问题时，没有比分析更好的解决办法。编译器的优化能力会因版本而异，源代码微小的改动可能会极大地影响性能。

没有人能回答这个问题，只有你自己：创建一个测试工具，并将多个算法应用到其中以查看结果。

附注：如果性能真的是问题，我曾通过删除向量并将其替换为原始数组，使PNG解码器的速度提高了10倍。但需要注意的是，这是针对Visual Studio 6的情况。我并不是在声称使用原始数组替换就能实现10倍的性能提升，但这值得一试。

- Chris Becke

---

我不了解VS6（幸运的是当时我能使用gcc），但是十倍的速度增长似乎是非常大的差异。在两种情况下您是否使用相同的算法？向实现中暗示了向量大小吗？在g ++中向量的当前实现包含三个指针，分别指向begin()，end()和begin()+capacity，除非启用了检查的迭代器，否则对向量的操作与对原始数据的操作一样快。 - David Rodríguez - dribeas

算法是一样的，我们只是将字节向量改为原始字节数组。函数被修改为接受指针，并在必要时接受数组大小的整数。一些循环被转换为memcpy。 - Chris Becke

Answer 6

我看到的选项，按照偏好的相反顺序大致如下：

1. 在容器中存储指针而不是实际对象。如果对象足够复杂，复制它们可能会带来问题，这种做法可能是明智的。
2. 使用索引运算符[]而不是at()。
3. 只调用一次at()，并将其保存为引用（参见上面的Kristo的答案）。
4. 直到你真正遇到运行时间过长的问题之前都可以忘记它。如果发生这种情况，请先对代码进行性能分析，确保瓶颈确实出现在这里，然后再考虑采取上述方法之一来加速。

老实说，你应该尝试四种不同的方法，并选择产生最易于理解的代码的那个。在大多数情况下，我们愿意为了更易于维护的代码而牺牲一些机器周期。

- T.E.D.

Answer 7

at() 的复杂度是常数级别的，也就是说，在实践中，它必须被设计成没有任何相关的性能惩罚。

你可以使用 []，它也是常数级别的复杂度，但不检查边界。这相当于使用指针算术，因此可能比前者稍微快一点。

无论如何，向量是专门设计用于对其任何元素进行恒定性能访问的。所以这应该是你最不用担心的事情。

- Daniel Daranas

Answer 8

向量是最适合访问速度的数据结构。在向量中随机访问一个元素的复杂度为O(1)，而对于一般的链表和链树，其复杂度分别为O(n)和O(log n)。

然而，这个问题被错误地提出了，因为你其他问题的答案误导了你，没有解释如何通过使用引用来修复你的原始问题。

- Richard Harrison

Answer 9

如果您加载了一个向量，然后在不添加或删除任何更多元素的情况下对其进行处理，则考虑获取指向基础数组的指针，并在其上使用数组操作以“避免向量开销”。

如果您正在添加或删除元素作为处理的一部分，则不安全这样做，因为基础数组可能会被向量本身在任何时候移动。

- EvilTeach