empty()和size()都可以判断容器是否为空,谁更好?

到目前为止,我们已经了解了 C++ STL 标准库中 vector、deque 和 list 这 3 个容器的功能和具体用法。学习过程中,读者是否想过一个问题,即这些容器的模板类中都提供了 empty() 成员方法和 size() 成员方法,它们都可以用来判断容器是否为空。

换句话说,假设有一个容器 cont,则此代码:

if(cont.size() == 0)

本质上和如下代码是等价的:

if(cont.empty())

那么,在实际场景中,到底应该使用哪一种呢?

建议使用 empty() 成员方法。理由很简单,无论是哪种容器,只要其模板类中提供了 empty() 成员方法,使用此方法都可以保证在 O(1) 时间复杂度内完成对“容器是否为空”的判断;但对于 list 容器来说,使用 size() 成员方法判断“容器是否为空”,可能要消耗 O(n) 的时间复杂度。

注意,这个结论不仅适用于 vector、deque 和 list 容器,后续还会讲解更多容器的用法,该结论也依然适用。

那么,为什么 list 容器这么特殊呢?这和 list 模板类提供了独有的 splice() 成员方法有关。

深度剖析选用empty()的原因

做一个大胆的设想,假设我们自己就是 list 容器的设计者。从始至终,我们的目标都是让 list 成为标准容器,并被广泛使用,因此打造“高效率的 list”成为我们奋斗的目标。

在实现 list 容器的过程中我们发现,用户经常需要知道当前 list 容器中存有多少个元素,于是我们想让 size() 成员方法的执行效率达到 O(1)。为了实现这个目的,我们必须重新设计 list,使它总能以最快的效率知道自己含有多少个元素。

要想令 size() 的执行效率达到 O(1),最直接的实现方式是:在 list 模板类中设置一个专门用于统计存储元素数量的 size 变量,其位于所有成员方法的外部。与此同时,在每一个可用来为容器添加或删除元素的成员方法中,添加对 size 变量值的更新操作。由此,size() 成员方法只需返回 size 这个变量即可(时间复杂度为 O(1))。

不仅如此,由于 list 容器底层采用的是链式存储结构(也就是链表),该结构最大的特点就是,某一链表中存有元素的节点,无需经过拷贝就可以直接链接到其它链表中,且整个过程只需要消耗 O(1) 的时间复杂度。考虑到很多用户之所以选用 list 容器,就是看中了其底层存储结构的这一特性。因此,作为 list 容器设计者的我们,自然也想将 splice() 方法的时间复杂度设计为 O(1)。

这里就产生了一个矛盾,即如果将 size() 设计为 O(1) 时间复杂度,则由于 splice() 成员方法会修改 list 容器存储元素的个数,因此该方法中就需要添加更新 size 变量的代码(更新方式无疑是通过遍历链表来实现),这也就意味着 splice() 成员方法的执行效率将无法达到 O(1);反之,如果将 splice() 成员方法的执行效率提高到 O(1),则 size() 成员方法将无法实现 O(1) 的时间复杂度。

也就是说,list 容器中的 size() 和 splice() 总有一个要做出让步,即只能实现其中一个方法的执行效率达到 O(1)。

值得一提的是,不同版本的 STL 标准库,其底层解决此冲突的抉择是不同的。以本教程所用的 C++ STL 标准模板库为例,其选择将 splice() 成员方法的执行效率达到 O(1),而 size() 成员方法的执行效率为 O(n)。当然,有些版本的 STL 标准库中,选择将 size() 方法的执行效率设计为 O(1)。

但不论怎样,选用 empty() 判断容器是否为空,效率总是最高的。所以,如果程序中需要判断当前容器是否为空,应优先考虑使用 empty()。

原创文章,作者:奋斗,如若转载,请注明出处:https://blog.ytso.com/23725.html

(0)
上一篇 2021年7月20日
下一篇 2021年7月20日

相关推荐

发表回复

登录后才能评论