push_back用于向量,双端队列和列表

我正在尝试优化C++例程.这个例程的主要瓶颈是对象向量的push_back().我尝试使用deque而不是尝试了一个列表.但奇怪的是(与理论相反)deque和list实现比vector对应运行得慢得多.

事实上,甚至clear()对于deque和list实现来说比向量对应运行慢得多.在这种情况下,Vector实现似乎是最快的,而列表实现是最慢的.

有什么指针吗？

注意:vector reserve()可以加快实现速度但不能完成,因为它的大小未知.

谢谢.

可以预期矢量比deque或list更快建立或清除; 这是一个更简单的数据结构.

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

检查向量是否足以容纳新项目.

插入新项目.

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

更新: 原始海报要求举例.下面的代码乘以128兆插入和输出

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

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

#include 
#include 
#include 

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

  const clock_t t0=clock();
  {
    std::vector a;
    for (size_t i=0;i a;
    a.reserve(n);
    for (size_t i=0;i a;
    a.resize(n);
    for (size_t i=0;i(CLOCKS_PER_SEC) << "s" << std::endl;
  std::cout << "reserve & push_back : " << (t2-t1)/static_cast(CLOCKS_PER_SEC) << "s" << std::endl;
  std::cout << "resize & place      : " << (t3-t2)/static_cast(CLOCKS_PER_SEC) << "s" << std::endl;

  return 0;  
}