Question

c++ stl中size方法时间复杂度

Answer 1

c++中利用stl的size方法的时间复杂度分析程序如下：
#include<iostream>
#include<list>
#include<ctime>
using namespace std;

int main(){
time_t start, finish;
int num = 0;
list<int> coll;

start = clock();
for(int i=0;i<10000;++i){
coll.push_back(i);
num += coll.size();
}
finish = clock();
cout<<finish - start<<" num:"<<num<<endl;

coll.clear();
start = clock();
for(int i=0;i<10000;++i){
coll.push_back(i);
}
finish = clock();
cout<<finish - start<<endl;
return 0;
}
对以上分析结果：

对两个循环分别计时比较。前一个循环只比后一个多了一句 num += coll.size(); 为了使编译器确实生成 list::size() 的代码。
在 MinGW 5.1.4 中 (GCC 3.4.5) 编译结果运行如下：
450 num:50005000
10
可以看到，前一个循环居然比后一个多花了几乎 45 倍的时间...当我把循环次数从 10000 加到 100000 时程序半天没出结果...
由此有理由猜测 std::list 的 size() 方法难道是 O(N) 的？果然，在头文件中发现了这一段：
size_type
size() const
{ return std::distance(begin(), end()); }

Answer 2

size_type size() const
{ // return length of sequence
return (this->_Mylast - this->_Myfirst);
}
时间复杂度是O(n)