求教：list.size()会导致遍历吗？

cokeboL

c++了解的少，今天看见公司有人在群里说list的size会导致遍历。

个人觉得标准库不会这么浪费效率吧？加个private变量神马的不就行了？求指点。

bruceteen

加个static变量神马的不就行了
------ static变量？

不会，我记得标准是要求size()的时间复杂度为O(1)

cokeboL

回复 2# bruceteen


    private....脑子一抖，想都没想。。

    比如 private:  int count;初始化为0，增减做++、--，size() return count就行了，干嘛非要遍历？如果容器元素多了，遍历岂不很浪费？

cokeboL

回复 2# bruceteen


    时间复杂度为O（1）？那就是不需要遍历撒。。谢谢

wenlq

1. 
   
2.   size_type size() const {
   
3.     size_type __result = distance(begin(), end());
   
4.     return __result;
   
5.   }
   
6. template <class _InputIterator>
   
7. inline _STLP_DIFFERENCE_TYPE(_InputIterator) _STLP_CALL
   
8. distance(const _InputIterator& __first, const _InputIterator& __last) {
   
9.   return __distance(__first, __last, _STLP_ITERATOR_CATEGORY(__first, _InputIterator));  
   
10. }
    
11. 
    
12. 
    
13. template <class _InputIterator>
    
14. inline _STLP_DIFFERENCE_TYPE(_InputIterator) _STLP_CALL
    
15. __distance(const _InputIterator& __first, const _InputIterator& __last, const input_iterator_tag &) {
    
16.   _STLP_DIFFERENCE_TYPE(_InputIterator) __n = 0;
    
17.   _InputIterator __it(__first);  
    
18.   while (__it != __last) {
    
19.     ++__it; ++__n;
    
20.   }
    
21.   return __n;
    
22. }
    

复制代码

littledick

VC下的STL是

1. size_type size() const
   
2. {
   
3.     return (_Mysize);
   
4. }

复制代码

linux_c_py_php

让你写一个list, 你会让它遍历的统计size吗?

littledick

linux_c_py_php 发表于 2012-09-24 11:10
让你写一个list, 你会让它遍历的统计size吗?

大部分情况下 ，必然用空间换时间

cokeboL

回复 5# wenlq


    这是啥意思？迭代器的模板？您别丢个代码啥都不解释啊

    我刚查了下C++ STL那书，list那章代码：

1.     size_type size() const
   
2.      {
   
3.         return (Size);
   
4.      }

复制代码

cokeboL

回复 7# linux_c_py_php


    我都是C，写list都是int个size，增减时操作，size()直接返回。