很奇怪的，或者说是一个不应成为问题的问题...
std::list 的 size() 方法时间复杂度是多少？第一感觉应该是 O(1) 没错吧，多一个变量用于储存链表长度应该是很轻易的事情。于是有了下面这段代码：
#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) 编译结果运行如下：
可以看到，前一个循环居然比后一个多花了几乎 45 倍的时间...当我把循环次数从 10000 加到 100000 时程序半天没出结果...
由此有理由猜测 std::list 的 size() 方法难道是 O(N) 的？果然，在头文件中发现了这一段：
size_type
size
(
)
const
{
return std::
distance
(begin
(
), end
(
)
);
}
直接调用 <algorithm> 算法库函数 distance() 计算元素个数……怪不得这么慢。然后又用 VS2008 (VC9.0)编译，结果如下：
奇怪的是前一个循环居然比后一个还快...不过至少知道 VS2008 (VC9.0)里的 size() 应该是 O(1) 的。同样查看了一下代码，如下：
size_type size
(
)
const
{
// return length of sequence
return
(_Mysize
);
}
_Mysize 是一个 size_type 类型的变量。疑问解决。不过又有了新问题：
--------------- 咱 -- 是 -- 分 -- 隔 -- 线 ------------------
为什么 GCC 里要把 list::size() 的复杂度搞成 O(N)？
一通搜索后终于看到有这样的讨论：关于 list::splice() 函数。
list 是链表结构，它的优势就在于可以 O(1) 的时间复杂度任意插入删除甚至拼接 list 片段(删除时可能不是，因为要释放内存)，list::splice() 是一个很强大的功能，它可在任意位置拼接两个 list，这正是 list 的优势。如果我们在类内部以一个变量储存 list 的长度，那么 splice() 之后新 list 的长度该如何确定？这是一个很严峻的问题，如果要在拼接操作时计算拼接部分的长度，那么将把 O(1) 的时间变成 O(N)，这么一来 list 相对 vector 的优势就消失殆尽。
面对这个问题，GCC 和 VC 的 STL 库作者们做了不同的选择。GCC 选择舍弃在 list 内部保存元素数量，而在 size() 时直接从头数到尾，这便出现了开头看到的 O(N) 时间才算出 size()；相反，VC 中有了变量 _Mysize ，无论在 insert() erase() splice() 或是 push() pop() 时都需要对其做相应修改。在上面的两个试验中已经看出同样是 10000 个 push_back() 操作，VC 花的时间比较长，不过也仅仅是一个 inc 指令，差别很小就是了。上面几种会改变 list 内容的操作中，大部分对元素数量的影响只是 +1 或 -1，只有 splice() 需要计算拼接部分元素个数，这个差别就大了，咱还是继续用实验证明吧：
#include<iostream>
#include<list>
#include<ctime>
using
namespace std;
int main
(
)
{
time_t start,finish;
list<int> col;
col.
push_back
(
1
);
col.
push_back
(
10000
);
list<int> col2;
start =
clock
(
);
for
(
int i=
2;i<
10000;++i
)
col2.
push_back
(i
);
finish =
clock
(
);
cout<<finish - start<<endl;
int num =
0;
start =
clock
(
);
for
(
int i=
0;i<
10000;++i
)
{
col.
splice
(++col.
begin
(
),col2,++col2.
begin
(
),--col2.
end
(
)
);
num += *
(++col.
begin
(
)
);
col2.
splice
(++col2.
begin
(
),col,++col.
begin
(
),--col.
end
(
)
);
num += *
(++col2.
begin
(
)
);
}
finish =
clock
(
);
cout<<finish - start<<
" num:"<<num<<endl;
return
0;
}
首先是 MinGW (GCC 3.4.5) 的结果：
可以看到 10000 次 push 是 10，相对的 20000 次 splice() 几乎没花时间 = =
然后是 VS2008 (VC9.0)：
差别非常明显，花了2秒多才完成。当我把循环次数改成 100000 后 GCC 仍是眨眼间的事，VC 却长时间运行无结果……
怎么说呢，GCC 显然是追求效率至上，尽量体现出 list 的优势所在，不过我觉得这么一来倒不如干脆不提供 list 的 size() 方法，有需求的程序员可以自己维护一个变量记录长度，以免误认为 size() 是 O(1) 的而犯下严重错误。相对的 VC 强调功能性和整体效率，可能在实际中需要对链表一段内容做 splice() 操作的机会远远小于求 size() 的操作，所以舍弃前者而保留后者，不过要维护 _Mysize 其他相关函数中也增加了开销。一个见仁见智的问题，我觉得还是 GCC 的选择比较好，list 的优势应该保留，但能在 size() 函数处给个 warning 什么的就好了。
我想还有一个选择是这样：在 list 内部用一个 bool 变量指示当前内部 size 值是有效还是无效。在通常操作时 bool 保持 true，这样在 size() 时直接返回原值即可；在 splice() 后将此 bool 值置为 false 并不计算长度，直到最后又有需要 size() 时发现 bool 是 false 则从头再来一遍 distance() 并再将 bool 置为 true。暂时只想出这么一个算是折中的方法，基本上都能保持两边 O(1) 的效率，但相应其他各关于元素数量的函数内部都要多一个判断当前 size 值是有效还是无效并选择是否改变其值。反正总是不能非常完美
嘛...本来只是发现 size() 的效率问题，没想到却扯出这么一桩事出来...也算长知识了吧
http://blog.sina.com.cn/s/blog_476a25110100magc.html
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
