首页 > 代码库 > 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()所想到的事情