STL

《Effective STL》

4《用empty来代替检查size()是否为0》

Posted by Liangjf on April 9, 2019

条目四《用empty来代替检查size()是否为0》

首先先说结论:

  • empty()实现为内联函数。(众所周知, 优秀的内联函数的效率比一般函数是高的)
  • 在stl标准库中,empty()对所有容易的时间复杂度是常数时间, 而对于一些list实现,size()是线性时间的。

基于以上两点, 在实际使用中, 需要判断容易的元素是否为0时,最好的选择是使用empty()函数。

造成size()在list容器的特殊性是由于list中splice()的存在。

在实现list时,有两点是需要注意的:

  • 1.为了高效,让list知道自己的size是多大,即把size()做成时间复杂度是常数级别(每向list插入元素就往size()返回的变量自增1)
  • 2.选用list, 就是因为list的特殊性,两个list拼接的时间复杂度只是常数级别的。所以把splice()做成时间复杂度是常数级别。

以上两点可以并存吗?

很抱歉,不能并存。

为了让** size()常数级别 ,就是在调用splice()后调用size()的时间复杂度是常数级别,必须在splice后马上 遍历 **被splice的list的元素更新新list的size,这样后面再使用size()就是常数时间,因为list已经知道自己的size了。

但是这样做,区间splice()就不是常数时间了,而是线性时间。

为了让** splice()常数级别 ,那么在splice时就应该忽略size的更新,抛弃更新被拼接list的size()成员函数。等到在调用size()的时候再 遍历 **list来获得list的size。

但是这样做, size()就不是常数时间了,而是线性时间。

究其原因是区间splice()在底层实现不是一个一个插入元素的,而是根据迭代器的始末,来一次拷贝元素达到目的,所以才有条目五

所以在list中,size()和区间splice()不能同时是常数时间,在实际实现时要看我们比较倾向哪一个,如果基本不适用区间splice,那么可以把size实现为是常数时间的。

这一切,关键看需求……