empty()和size()的优劣

通常下面代码:

if(c.size() == 0)
if(c.empty())

我们会觉得它们是是等价的。


为何empty()比较好?

主要是他们之间的效率有一定差距:

  • empty对任意的容器都是常数时间
  • 对于有点list实现,size需要线性时间
bool empty() const       //list的empty操作
{
   return node->next == node;
}

而size()则是通过区间遍历来数一数。


为何size()不能是常数的?

如果size()想在常数时间内实现,那么每个操作都要维护size的值。
splice()的特点就是能常数实现链接。如果想实现size的常数,那么就需要放弃splice()的常数特点(需要遍历维护).
所以就要看你使用的list是把 size() or splice()放在第一位。
但是使用empty肯定总是花费常数的时间。


参考:

effective STL

原文地址:https://www.cnblogs.com/Przz/p/6590975.html