当心那些有歧义的命名(2)
来源:未知 责任编辑:责任编辑 发表时间:2013-11-18 20:56 点击:次
void ShrinkList(list<Node>& list, int max_size) {
while (list.size() > max_size) {
FreeNode(list.back());
list.pop_back();
}
}
这样的bug的导致是作者没有意识到list.size()是一个O(n)复杂度的操作——它挨个计数链表的节点得出总数而不是返回已计算 好的总个数,这将导致ShrintList是一个O(n2) 的操作。
从技术角度讲,这段代码没有问题,也能通过所有的单元测试。但是当调用ShrintList()并传入一个包含上亿数量级的list时,它可能将 耗费数小时的时间。
或许你会认为,这个是调用者的错误使用,他/她没有认真仔细的阅读相关的文档!确实是这样的,但是,事实上,这里的list.size()不是一 个恒准时(constant-time)操作,这太意外了!其他所有的C++容器类都是恒准时的size()方法呀。
假如把size()更名成countSize()或者countElements(),类似的错误就会大大减少了。C++标准库的实现者可能想的 是使用一个size()方法去和其他的容器匹配,像vector和map,这样API的一致性看起来更好。正是由于这样的做了,导致程序员容易误 用并认为这是一个很快的操作,和其他的容器一样!幸运的是,最新的C++标准要求size()是O(1)复杂度。
摘自 葡萄城控件技术团队博客
相关新闻>>
最新推荐更多>>>
- 发表评论
-
- 最新评论 进入详细评论页>>