為什麼 GNU ISO C++ Library 的vector實現是這樣的?

dtimes6

/// 見stl_vector.h template<typename _InputIterator>         vector(_InputIterator __first, _InputIterator __last,            const allocator_type& __a = allocator_type())     : _Base(__a)         {       // Check whether it's an integral type.  If so, it's not an iterator.       typedef typename std::__is_integer<_InputIterator>::__type _Integral;       _M_initialize_dispatch(__first, __last, _Integral()); ///此處為了避免vector(int, int) 調用     } template<typename _InputIterator>         void         _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,                    __false_type)         {       typedef typename iterator_traits<_InputIterator>::iterator_category         _IterCategory;       _M_range_initialize(__first, __last, _IterCategory()); ///不理解的是這裡,為什麼要區分InputIterator和ForwardIterator     } template<typename _InputIterator>         void         _M_range_initialize(_InputIterator __first,                 _InputIterator __last, input_iterator_tag)         {       for (; __first != __last; ++__first)         push_back(*__first);             ///很明顯這裡用push_back只會降低效率.因為push_back會導致reallocation             ///況且另一個版本用的是__uninitialized_copy_a可以參考起實現(見 stl_uninitialized.h)             ///有一個InputIterator的版本.而且效率明顯比用push_back高.             ///查過標准上面也是這麼講的:             ///Complexity: The constructor template <class InputIterator> vector(InputIterator             ///first, InputIterator last) makes only N calls to the copy constructor of T (where N is the             ///distance between first and last) and no reallocations if iterators first and last are of forward, bidirectional,             ///or random access categories. It makes order N calls to the copy constructor of T and order             ///logN reallocations if they are just input iterators             ///搞不懂了?為什麼這樣做?請牛人指點迷津     } template<typename _ForwardIterator>         void         _M_range_initialize(_ForwardIterator __first,                 _ForwardIterator __last, forward_iterator_tag)         {       ///2L同學所問分配內存的地方在此       const size_type __n = std::distance(__first, __last);       this->_M_impl._M_start = this->_M_allocate(__n);       this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;       this->_M_impl._M_finish =         std::__uninitialized_copy_a(__first, __last,                     this->_M_impl._M_start,                     this->get_allocator());     } /// 見 stl_uninitialized.h template<typename _InputIterator, typename _ForwardIterator,        typename _Allocator>     _ForwardIterator     __uninitialized_copy_a(_InputIterator __first, _InputIterator __last,                _ForwardIterator __result,                _Allocator __alloc)     {       _ForwardIterator __cur = __result;       try     {       for (; __first != __last; ++__first, ++__cur)         __alloc.construct(&*__cur, *__first);       return __cur;     }       catch(...)     {       std::_Destroy(__result, __cur, __alloc);       __throw_exception_again;     }     }   template<typename _InputIterator, typename _ForwardIterator, typename _Tp>     inline _ForwardIterator     __uninitialized_copy_a(_InputIterator __first, _InputIterator __last,                _ForwardIterator __result,                allocator<_Tp>)     {       return std::uninitialized_copy(__first, __last, __result);     } ///stl_iterator_base_funcs.h &nbsp;&nbsp;template<typename _InputIterator> &nbsp;&nbsp;&nbsp;&nbsp;inline typename iterator_traits<_InputIterator>::difference_type &nbsp;&nbsp;&nbsp;&nbsp;distance(_InputIterator __first, _InputIterator __last) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;// concept requirements -- taken care of in __distance &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return std::__distance(__first, __last, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;     std::__iterator_category(__first)); &nbsp;&nbsp;&nbsp;&nbsp;}

[ 本帖最后由 dtimes6 于 2009-8-1 09:09 编辑 ]

dtimes6

分配內存有多種方式

      const size_type __n = std::distance(__first, __last);
      this->_M_impl._M_start = this->_M_allocate(__n);
      this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;

就是在分配內存

    ///stl_iterator_base_funcs.h
    template<typename _InputIterator>
    inline typename iterator_traits<_InputIterator>::difference_type
    distance(_InputIterator __first, _InputIterator __last)
    {
      // concept requirements -- taken care of in __distance
      return std::__distance(__first, __last,
                             std::__iterator_category(__first));
    }

OwnWaterloo

比如这样使用：
vector<int> v( istream_iterator<int>(cin), (istream_iterator<int>()) );

显然 istream_iterator<int>(cin) 构造出的iterator只能迭代“一次”。
第2次就是另外的输入了。



for (; __first != __last; ++__first)
        push_back(*__first);

这样就保证只迭代一次。



// 这样就不行
      const size_type __n = std::distance(__first, __last);  // 这里已经迭代一次。
// ...
        std::__uninitialized_copy_a(__first, __last,
                    this->_M_impl._M_start,
                    this->get_allocator()); // 这里再迭代一次。