最近,我注意到有人提到它std::list::size()
具有线性复杂性。
根据一些 消息来源,这实际上取决于实现,因为标准没有说明复杂性必须是什么。此博客条目中
的评论说:
实际上,这取决于您使用的是哪个 STL。Microsoft Visual Studio V6 将 size() 实现为 {return (_Size); } 而 gcc(至少在 3.3.2 和 4.1.0 版本中)将其作为 { return std::distance(begin(), end()); 第一个具有恒定速度,第二个具有 o(N) 速度
- 所以我的猜测是,对于 VC++ 人群来说
size()
,复杂性是恒定的,因为 Dinkumware 自 VC6 以来可能不会改变这一事实。我在吗? - 它现在看起来像什么
gcc
?如果真的是O(n),为什么开发者会选择这样做呢?