首页 > 代码库 > C++ list size()所想到的事情
C++ list size()所想到的事情
effective STL 某个Item里重点提出了 list.size()是一个O(n)的效率 当时只是记下来了 后面看了csdn有人在实际工程上遇到坑了 我近来闲来无事 把STL的list相关部分好好看下:
看看STL大牛们设置成O(n)的原因:
1) size() 调用algorithm里的distance() 得出长度 而empty()就是判断头和尾是否相等 O(1) 大部分情况下 咱们都是判断这个list是否为空
2) 设计原因: list引入了一个重要的splice操作,在常量级别也就是o(1)完成list的tranfer 这个操作对merge reverse sort有很大的帮助 如果:
size()不这样做 那么tranfer就不能是o(1)完成 不是o(1) 那么就在Merge 和sort就不能高效完成 而且事实上 merge 和sort操作显的更为重要些,所以size()在每次调用时调用distance 而不是更好的O(1) 这样就可以均摊tranfer的常量级操作 看到网上人吐槽这个地方 我想懂了上述设计原理 也不会吐槽这个结构了。
C++ list size()所想到的事情
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。