我正在尝试优化C ++例程。这个例程的主要瓶颈是对象向量的push_back（）。我尝试使用deque而不是尝试了一个列表。但奇怪的是（与理论相反）deque和list实现比vector对应运行得慢得多。
事实上，甚至clear（）对于deque和list实现来说比向量对应运行要慢得多。在这种情况下，Vector实现似乎是最快的，而列表实现是最慢的。
有什么指针吗？
注意：vector reserve（）可以加速实现但不能完成，因为它的大小未知。
谢谢。
我正在尝试优化C ++例程。这个例程的主要瓶颈是对象向量的push_back（）。我尝试使用deque而不是尝试了一个列表。但奇怪的是（与理论相反）deque和list实现比vector对应运行得慢得多。
事实上，甚至clear（）对于deque和list实现来说比向量对应运行要慢得多。在这种情况下，Vector实现似乎是最快的，而列表实现是最慢的。
有什么指针吗？
注意：vector reserve（）可以加速实现但不能完成，因为它的大小未知。
谢谢。
可以预期矢量比deque或list更快建立或清除;这是一个更简单的数据结构。
关于至于对于有关 vector::push_back，它必须做两件事：
通常只需调整矢量大小并使用即可消除步骤1，从而加快速度 operator[] 设置项目。
更新： 原始海报问了一个例子。 下面的代码乘以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;
}
如果您不知道要添加多少个对象，则很难找到最佳解决方案。您所能做的就是尽量减少您所知道的成本 - 在这种情况下，您的矢量会不断调整大小。
你可以用两种方式做到这一点;
1）将您的操作分解为构建和完成。在这里，您可以将列表构建为一个保证足够大的向量，并在完成后将其复制到另一个向量。
例如。
std::vector<Foo> hugeVec;
hugeVec.reserve(1000); // enough for 1000 foo's
// add stuff
std::vector<Foo> finalVec;
finalVec = hugeVec;
2）或者，当你的向量是完整的呼叫保留时，足够用于另一组对象;
if (vec.capacity() == vec.size())
vec.reserve(vec.size() + 16); // alloc space for 16 more objects
您可以选择一个不同的容器，该容器不会导致在调整大小时复制所有元素，但您的瓶颈可能会成为新元素的单独内存分配。
你是在推回物体本身还是指向它们的指针？与无论对象的大小相比，指针通常要快得多，因为复制只需要4-8个字节。
如果对象的副本很慢，“push_back（）”可能会很慢。如果默认构造函数很快并且您有一种方法可以使用swap来避免复制，那么您可以使用更快的程序。
void test_vector1()
{
vector<vector<int> > vvi;
for(size_t i=0; i<100; i++)
{
vector<int> vi(100000, 5);
vvi.push_back(vi); // copy of a large object
}
}
void test_vector2()
{
vector<int> vi0;
vector<vector<int> > vvi;
for(size_t i=0; i<100; i++)
{
vector<int> vi(100000, 5);
vvi.push_back(vi0); // copy of a small object
vvi.back().swap(vi); // swap is fast
}
}
结果：
VS2005-debug
* test_vector1 -> 297
* test_vector2 -> 172
VS2005-release
* test_vector1 -> 203
* test_vector2 -> 94
gcc
* test_vector1 -> 343
* test_vector2 -> 188
gcc -O2
* test_vector1 -> 250
* test_vector2 -> 156
如果你想要矢量快，你必须保留（）足够的空间。它产生了巨大的差异，因为每次成长都是非常昂贵的。如果你不知道，做个好猜。
您需要提供有关例程行为的更多信息。
在一个地方，你关心的速度 push_back() 在另一个你关心的问题 clear()。你在建造集装箱，做什么然后倾倒它？
你看到的结果 clear() 是因为 vector<>只需释放单块内存， deque<> 必须发布几个，和 list<> 必须为每个元素释放一个。
Deque的结构比矢量更复杂，两者之间的速度差异将在很大程度上取决于特定的实现和推回的元素的实际数量，但对于大量数据，它应该更快。 clear（）可能会更慢，因为它可能会选择摆脱更复杂的底层结构。列表大致相同。
关于push_back（）很慢并且保留没有帮助，MSVC中使用的STL的实现类似于：当你第一次创建一个向量时，它为我认为10个元素保留了空间。从那时起，每当它变满时，它就会保留1.5倍于向量中元素数量的空间。所以，像10,15,22,33,49,73,105,157 ......重新分配是昂贵的。
即使您不知道确切的大小，reserve（）也很有用。如果需要，reserve（）不会阻止向量增长。如果你保留（）并且向量增长超过那个大小，你仍然会因为保留而改进了东西。如果向量变得更小，那么，也许这没关系，因为一般情况下，性能越好，尺寸越小。
您需要在RELEASE模式下进行分析，以确定哪种策略最有效。
你必须根据你将要做的事情选择你的容器。
相关行动是：延长（与 push），插入（可能根本不需要），提取，删除。
在 cplusplus.com，每个容器类型的操作有一个非常好的概述。
如果操作是 push-bound，向量击败所有其他向量是有意义的。 deque的好处在于它分配了固定的块，因此可以更有效地使用碎片内存。