stl::list的size實(shí)現(xiàn)太有問(wèn)題啦

這幾天做一個(gè)程序，在遍歷一個(gè)100萬(wàn)個(gè)數(shù)據(jù)的LIST的時(shí)候非常非常慢，我把可能出現(xiàn)消耗時(shí)間都打印出來(lái)了，死活都找不到消耗時(shí)間的地方在什么地方。

最后盯上了判斷size（）等于一個(gè)值的地方，因?yàn)榫褪Ｏ逻@個(gè)地方了，就打上了時(shí)間，結(jié)果發(fā)現(xiàn)竟然就是此處。一個(gè)size方法竟然消耗了0.02秒。注釋掉后就一切正常了。最后的解決辦法只好我?guī)椭鼇?lái)計(jì)數(shù)。

寫了個(gè)小程序，發(fā)現(xiàn)list的size果然消耗時(shí)間，不過(guò)幸運(yùn)的是empty不消耗時(shí)間。

而最幸運(yùn)的是最常用的map的size并不消耗時(shí)間。

有空看看源碼吧，難道每次size都要從頭計(jì)算一次嗎？

#include<list>
#include<sys/time.h>
#include<stdio.h>
using namespace std;

void p1()
{
struct timeval start;
gettimeofday(&start, 0);
printf("%u,%u\n",start.tv_sec,start.tv_usec);

}

int main()
{
list<int> lista;
p1();
for(int i=0;i<10000;i++)
lista.push_back(1);

p1();

for(int i=0;i<1000;i++)
{
lista.size();
lista.pop_front();
}
p1();

for(int i=0;i<1000;i++)
lista.pop_front();
p1();
return 0;
}

結(jié)果：
1238513193,693237
1238513193,695993
1238513193,795487
1238513193,795597

只是1W個(gè)數(shù)據(jù)就這樣慢的，100W的數(shù)據(jù)更是慢的驚人。

--------------------------------------------------------------------

查了一下源碼，果然是每次重新計(jì)算的，難道就為了節(jié)省4字節(jié)的空間？

size_type size() const {
    size_type __result = 0;
    distance(begin(), end(), __result);
    return __result;
}