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

Question

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

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

有什么指针吗？

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

谢谢.

Answer 1

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

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

1. 检查向量是否足以容纳新项目.
2. 插入新项目.

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

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

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

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

#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;  
}

Answer 2

你是推回对象本身，还是指向它们的指针？与任何大小的对象相比，指针通常要快得多，因为它只需复制 4-8 个字节。