|
看到篇文章，内容很基础，但是反应的问题是值得思考的。遍历vector的标准方法是什么？之前按照书中的理论，认为stl标准的迭代器或者stl的for_each算法应该是最快的。但是如果不经过实际程序的检验，那么理论永远是理论。实践表明operator[]的访问速度是最快的（至少不比迭代器更慢）。之前我洁癖性的把所有使用operator[]进行vector遍历的地方都改成迭代器，认为这样更高效，看来是没有必要的。 当然根据stl的版本不同以及编译器的优化级别不同，数据可能会有偏差（甚至会影响到结论），所以程序这个东西最大的真理就是实践。写个代码测试下就知道理论是否正确了。
============================================原文如下=============================================
今天闲来没事看了一下N久就在我电脑里面的《Effective STL 中文版》。
当我看到第43条的时候发现，按上面所讲用：算法替换手工循环。
不由得产生了疑问。
我记得我以前看vector源代码的时候循环效率最高的是operator[]操作(下标操作)。
怎么这里竟然说是算法速度快。
下面先做个测试，代码如下：
// 测试类及其调用函数
class AAA
{
public:
void MakeFull2()
{
}
};
// 创建1000000个指针
int nCount = 1000000;
std::vector< AAA* > vAAA;
vAAA.resize(nCount);
for (size_t i = 0; i < nCount; ++i)
vAAA[i] = new AAA;
// 时间
DWORD start, end;
// 测试成员函数调用(STL算法方式)
start = timeGetTime();
std::for_each(vAAA.begin(), vAAA.end(),
std::mem_fun< void, AAA >(&AAA::MakeFull2));
end = timeGetTime();
std::cout<<end-start<<std::endl;
// 测试成员函数调用(STL迭代器方式)
start = timeGetTime();
std::vector< AAA* >::iterator itr_end = vAAA.end();
for (std::vector< AAA* >::iterator itr = vAAA.begin(); itr != itr_end; ++itr)
(*itr)->MakeFull2();
end = timeGetTime();
std::cout<<end-start<<std::endl;
// 测试成员函数调用(std::vector下标访问方式)
start = timeGetTime();
size_t count = vAAA.size();
for (size_t i = 0; i < count; ++i)
vAAA[i]->MakeFull2();
end = timeGetTime();
std::cout<<end-start<<std::endl;
测试结果分别是：237/208/103
最高得分是下标方式。
最差的却是STL算法方式。
为什么呢？
如果我们将迭代器方式的代码改为如下(书上所讲的方法)：
// 测试成员函数调用(STL迭代器方式)
start = timeGetTime();
for (std::vector< AAA* >::iterator itr = vAAA.begin(); itr != vAAA.end();; ++itr)
(*itr)->MakeFull2();
end = timeGetTime();
std::cout<<end-start<<std::endl;
测试结果分别是：239/644/107
结果反映出迭代器方法最差劲，而且差得非常远。
回到书上再看看，原来他所讲迭代器操作慢是因为for循环中，判断部分造成的。
先看看std::vector::end()函数
iterator end()
{// return iterator for end of mutable sequence
return (iterator(_Mylast, this));
}
这里问题很严重，原来是在访问end的时候是重新构造一个新的迭代器，看到问题了吧．
原因就在这一句．
所以我们进行优化，只构造一次vector::end()，也就有了最上面的测试代码．
这样一来，书上说的STL算法方式就变为最慢的了．
其实std::for_each和std::vector::iterator两种循环方法效率理论上完全一样，
但是std::for_each相比之只有一个慢点：
经过测试我发现，std::mem_fun< void, AAA >(&AAA::MakeFull2)
这两者的时间差就在mem_fun类的构造函数上．
到此，我已经说明了std::for_each和std::vector::iterator两种循环的效率，那么为什么下标访问方式速度更快呢？
还是先看源代码：
const_reference operator[](difference_type _Off) const
{// subscript
return (*(*this + _Off));
}
这个函数只做了一个加法操作．相比其它两种，不依赖各种判断和构造，因此速度最快．
由此可见vector的速度了．
但是，不是所有的容都用operator[]操作速度最快的．
因为我这里只讨论了vector，其它容器我并没有说明．
不过，像vector这一类的顺序容器来说，operator[]操作肯定是最快的．
就像list非顺序的，那么list不行，并且list也没有operator[]操作．
the end;
| 
转播
