我一直认为std::vector是“作为数组实现的”，等等等等。今天我去测试了一下，结果似乎不是这样:
以下是一些测试结果:
UseArray completed in 2.619 seconds
UseVector completed in 9.284 seconds
UseVectorPushBack completed in 14.669 seconds
The whole thing completed in 26.591 seconds
这大约要慢3 - 4倍!这并不能证明“向量可能会慢几纳秒”的评论是正确的。
我使用的代码是:
#include <cstdlib>
#include <vector>
#include <iostream>
#include <string>
#include <boost/date_time/posix_time/ptime.hpp>
#include <boost/date_time/microsec_time_clock.hpp>
class TestTimer
{
public:
TestTimer(const std::string & name) : name(name),
start(boost::date_time::microsec_clock<boost::posix_time::ptime>::local_time())
{
}
~TestTimer()
{
using namespace std;
using namespace boost;
posix_time::ptime now(date_time::microsec_clock<posix_time::ptime>::local_time());
posix_time::time_duration d = now - start;
cout << name << " completed in " << d.total_milliseconds() / 1000.0 <<
" seconds" << endl;
}
private:
std::string name;
boost::posix_time::ptime start;
};
struct Pixel
{
Pixel()
{
}
Pixel(unsigned char r, unsigned char g, unsigned char b) : r(r), g(g), b(b)
{
}
unsigned char r, g, b;
};
void UseVector()
{
TestTimer t("UseVector");
for(int i = 0; i < 1000; ++i)
{
int dimension = 999;
std::vector<Pixel> pixels;
pixels.resize(dimension * dimension);
for(int i = 0; i < dimension * dimension; ++i)
{
pixels[i].r = 255;
pixels[i].g = 0;
pixels[i].b = 0;
}
}
}
void UseVectorPushBack()
{
TestTimer t("UseVectorPushBack");
for(int i = 0; i < 1000; ++i)
{
int dimension = 999;
std::vector<Pixel> pixels;
pixels.reserve(dimension * dimension);
for(int i = 0; i < dimension * dimension; ++i)
pixels.push_back(Pixel(255, 0, 0));
}
}
void UseArray()
{
TestTimer t("UseArray");
for(int i = 0; i < 1000; ++i)
{
int dimension = 999;
Pixel * pixels = (Pixel *)malloc(sizeof(Pixel) * dimension * dimension);
for(int i = 0 ; i < dimension * dimension; ++i)
{
pixels[i].r = 255;
pixels[i].g = 0;
pixels[i].b = 0;
}
free(pixels);
}
}
int main()
{
TestTimer t1("The whole thing");
UseArray();
UseVector();
UseVectorPushBack();
return 0;
}
我做错了吗?还是我刚刚打破了这个性能神话?
我使用Visual Studio 2005中的发布模式。
在Visual c++中，#define _SECURE_SCL 0将UseVector减少了一半(减少到4秒)。在我看来，这真的是件大事。
Martin York的回答让我很困扰，因为他似乎试图掩盖初始化问题。但他将冗余的默认构造确定为性能问题的根源是正确的。
[编辑:Martin的回答不再建议更改默认构造函数。]
对于眼前的问题，你当然可以调用2参数版本的向量<Pixel> ctor:
std::vector<Pixel> pixels(dimension * dimension, Pixel(255, 0, 0));
如果你想用一个常数值初始化，这是一种常见的情况。但更普遍的问题是:如何有效地初始化比常数值更复杂的东西?
为此，您可以使用back_insert_iterator，这是一个迭代器适配器。这里有一个int类型的向量的例子，尽管一般的思想也适用于像素:
#include <iterator>
// Simple functor return a list of squares: 1, 4, 9, 16...
struct squares {
squares() { i = 0; }
int operator()() const { ++i; return i * i; }
private:
int i;
};
...
std::vector<int> v;
v.reserve(someSize); // To make insertions efficient
std::generate_n(std::back_inserter(v), someSize, squares());
或者，您可以使用copy()或transform()来代替generate_n()。
缺点是，构造初始值的逻辑需要移动到一个单独的类中，这比将其放在原位更不方便(尽管c++ 1x中的lambdas使这更好)。此外，我希望这仍然不会像基于malloc()的非stl版本那样快，但我希望它会接近，因为它只对每个元素进行一次构造。
GNU's STL (and others), given vector<T>(n), default constructs a prototypal object T() - the compiler will optimise away the empty constructor - but then a copy of whatever garbage happened to be in the memory addresses now reserved for the object is taken by the STL's __uninitialized_fill_n_aux, which loops populating copies of that object as the default values in the vector. So, "my" STL is not looping constructing, but constructing then loop/copying. It's counter intuitive, but I should have remembered as I commented on a recent stackoverflow question about this very point: the construct/copy can be more efficient for reference counted objects etc..
So:
vector<T> x(n);
or
vector<T> x;
x.resize(n);
是-在许多STL实现中-类似于:
T temp;
for (int i = 0; i < n; ++i)
x[i] = temp;
The issue being that the current generation of compiler optimisers don't seem to work from the insight that temp is uninitialised garbage, and fail to optimise out the loop and default copy constructor invocations. You could credibly argue that compilers absolutely shouldn't optimise this away, as a programmer writing the above has a reasonable expectation that all the objects will be identical after the loop, even if garbage (usual caveats about 'identical'/operator== vs memcmp/operator= etc apply). The compiler can't be expected to have any extra insight into the larger context of std::vector<> or the later usage of the data that would suggest this optimisation safe.
这可以与更明显的直接实现形成对比:
for (int i = 0; i < n; ++i)
x[i] = T();
我们可以期待一个编译器优化。
为了更明确地解释vector行为的这一方面，可以考虑:
std::vector<big_reference_counted_object> x(10000);
显然，如果我们创建10000个独立对象，而不是创建10000个引用相同数据的对象，这是一个很大的区别。有一种合理的观点认为，保护普通c++用户不意外地做一些如此昂贵的事情的好处超过了现实世界中难以优化的拷贝构造的非常小的成本。
原始答案(供参考/理解评论):
没有机会。Vector和数组一样快，至少如果你合理地保留空间. ...
我不得不说我不是c++方面的专家。但要补充一些实验结果:
编译:
gcc-6.2.0/bin/g++ -O3 -std=c++14 vector.cpp
机:
Intel(R) Xeon(R) CPU E5-2690 v2 @ 3.00GHz
OS:
2.6.32-642.13.1.el6.x86_64
输出:
UseArray completed in 0.167821 seconds
UseVector completed in 0.134402 seconds
UseConstructor completed in 0.134806 seconds
UseFillConstructor completed in 1.00279 seconds
UseVectorPushBack completed in 6.6887 seconds
The whole thing completed in 8.12888 seconds
这里我唯一感到奇怪的是“UseFillConstructor”的性能与“UseConstructor”相比。
代码:
void UseConstructor()
{
TestTimer t("UseConstructor");
for(int i = 0; i < 1000; ++i)
{
int dimension = 999;
std::vector<Pixel> pixels(dimension*dimension);
for(int i = 0; i < dimension * dimension; ++i)
{
pixels[i].r = 255;
pixels[i].g = 0;
pixels[i].b = 0;
}
}
}
void UseFillConstructor()
{
TestTimer t("UseFillConstructor");
for(int i = 0; i < 1000; ++i)
{
int dimension = 999;
std::vector<Pixel> pixels(dimension*dimension, Pixel(255,0,0));
}
}
因此提供的额外“值”大大降低了性能，我认为这是由于多次调用复制构造函数造成的。但是…
编译:
gcc-6.2.0/bin/g++ -std=c++14 -O vector.cpp
输出:
UseArray completed in 1.02464 seconds
UseVector completed in 1.31056 seconds
UseConstructor completed in 1.47413 seconds
UseFillConstructor completed in 1.01555 seconds
UseVectorPushBack completed in 6.9597 seconds
The whole thing completed in 11.7851 seconds
因此，在这种情况下，gcc优化非常重要，但当一个值作为默认值提供时，它帮不了你太多。这，其实是对我的学费。希望它能帮助新程序员选择哪种矢量初始化格式。
顺便说一下，你在使用vector的类中看到的减速也发生在标准类型中，比如int。这是一个多线程代码:
#include <iostream>
#include <cstdio>
#include <map>
#include <string>
#include <typeinfo>
#include <vector>
#include <pthread.h>
#include <sstream>
#include <fstream>
using namespace std;
//pthread_mutex_t map_mutex=PTHREAD_MUTEX_INITIALIZER;
long long num=500000000;
int procs=1;
struct iterate
{
int id;
int num;
void * member;
iterate(int a, int b, void *c) : id(a), num(b), member(c) {}
};
//fill out viterate and piterate
void * viterate(void * input)
{
printf("am in viterate\n");
iterate * info=static_cast<iterate *> (input);
// reproduce member type
vector<int> test= *static_cast<vector<int>*> (info->member);
for (int i=info->id; i<test.size(); i+=info->num)
{
//printf("am in viterate loop\n");
test[i];
}
pthread_exit(NULL);
}
void * piterate(void * input)
{
printf("am in piterate\n");
iterate * info=static_cast<iterate *> (input);;
int * test=static_cast<int *> (info->member);
for (int i=info->id; i<num; i+=info->num) {
//printf("am in piterate loop\n");
test[i];
}
pthread_exit(NULL);
}
int main()
{
cout<<"producing vector of size "<<num<<endl;
vector<int> vtest(num);
cout<<"produced a vector of size "<<vtest.size()<<endl;
pthread_t thread[procs];
iterate** it=new iterate*[procs];
int ans;
void *status;
cout<<"begining to thread through the vector\n";
for (int i=0; i<procs; i++) {
it[i]=new iterate(i, procs, (void *) &vtest);
// ans=pthread_create(&thread[i],NULL,viterate, (void *) it[i]);
}
for (int i=0; i<procs; i++) {
pthread_join(thread[i], &status);
}
cout<<"end of threading through the vector";
//reuse the iterate structures
cout<<"producing a pointer with size "<<num<<endl;
int * pint=new int[num];
cout<<"produced a pointer with size "<<num<<endl;
cout<<"begining to thread through the pointer\n";
for (int i=0; i<procs; i++) {
it[i]->member=&pint;
ans=pthread_create(&thread[i], NULL, piterate, (void*) it[i]);
}
for (int i=0; i<procs; i++) {
pthread_join(thread[i], &status);
}
cout<<"end of threading through the pointer\n";
//delete structure array for iterate
for (int i=0; i<procs; i++) {
delete it[i];
}
delete [] it;
//delete pointer
delete [] pint;
cout<<"end of the program"<<endl;
return 0;
}
代码中的行为表明vector的实例化是代码中最长的部分。一旦你通过瓶颈。其余的代码运行得非常快。无论在多少个线程上运行，这都是正确的。
顺便说一下，忽略那些疯狂的包含数。我一直在使用这段代码来测试一个项目的东西，所以包含的数量不断增长。
这是一个古老而流行的问题。
在这一点上，许多程序员将使用c++ 11。在c++ 11中，OP的代码对于UseArray或UseVector运行得同样快。
UseVector completed in 3.74482 seconds
UseArray completed in 3.70414 seconds
基本的问题是，当你的像素结构未初始化时，std::vector<T>::resize(size_t, T const&=T())接受一个默认构造的像素并复制它。编译器没有注意到它被要求复制未初始化的数据，所以它实际执行了复制。
在c++ 11中，std::vector<T>::resize有两个重载。第一个是std::vector<T>::resize(size_t)，另一个是std::vector<T>::resize(size_t, T const&)。这意味着当调用resize而不带第二个参数时，它只是默认构造，而编译器足够聪明，可以意识到默认构造什么也不做，因此它跳过了缓冲区的传递。
(添加这两个重载是为了处理可移动、可构造和不可复制类型——处理未初始化数据时的性能提升是一个额外的好处)。
push_back解决方案还执行fencepost检查，这降低了它的速度，因此它仍然比malloc版本慢。
现场示例(我还用chrono::high_resolution_clock替换了计时器)。
注意，如果你有一个通常需要初始化的结构，但你想在增加缓冲区后处理它，你可以使用自定义std::vector分配器来做到这一点。如果你想把它移动到一个更正常的std::vector，我相信仔细使用allocator_traits和重写==可能会成功，但我不确定。
