c++ - vector 、双端队列和列表的 push_back

Question

我正在尝试优化 C++ 例程。此例程中的主要瓶颈是对象 vector 的 push_back()。我尝试使用双端队列，甚至尝试使用列表。但奇怪的是(与理论相反)双端队列和列表实现比 vector 对应物运行得慢得多。

事实上，对于 deque 和 list 实现，甚至 clear() 的运行速度也比 vector 对应物慢得多。同样在这种情况下，Vector 实现似乎是最快的，而 list 实现是最慢的。

有什么建议吗？

注意:vector reserve() 可以加快执行速度，但无法完成，因为它的大小未知。

谢谢。

Answer 1

vector 比双端队列或列表更快地构建或清除是可以预料的；这是一个更简单的数据结构。

关于vector::push_back ，它必须做两件事:

1. 检查 vector 是否足够大持有新项目。
2. 插入新项目。

您通常可以通过简单地调整 vector 大小并使用 operator[] 来消除步骤 1 来加快速度。设置项目。

更新:原始发帖人要求举个例子。下面的代码乘以 128 兆插入，并输出

push_back           : 2.04s
reserve & push_back : 1.73s
resize & place      : 0.48s

在旧 P4 机器上的 Debian/Lenny 上使用 g++ -O3 编译和运行时。

#include <iostream>
#include <time.h>
#include <vector>

int main(int,char**)
{
  const size_t n=(128<<20);

  const clock_t t0=clock();
  {
    std::vector<unsigned char> a;
    for (size_t i=0;i<n;i++) a.push_back(i);
  }
  const clock_t t1=clock();
  {
    std::vector<unsigned char> a;
    a.reserve(n);
    for (size_t i=0;i<n;i++) a.push_back(i);
  }
  const clock_t t2=clock();
  {
    std::vector<unsigned char> a;
    a.resize(n);
    for (size_t i=0;i<n;i++) a[i]=i;
  }
  const clock_t t3=clock();

  std::cout << "push_back           : " << (t1-t0)/static_cast<float>(CLOCKS_PER_SEC) << "s" << std::endl;
  std::cout << "reserve & push_back : " << (t2-t1)/static_cast<float>(CLOCKS_PER_SEC) << "s" << std::endl;
  std::cout << "resize & place      : " << (t3-t2)/static_cast<float>(CLOCKS_PER_SEC) << "s" << std::endl;

  return 0;  
}