STL 소스 코드 - list 전체 소스 코드

38212 단어 STL
//   list           
struct _List_node_base {  
  _List_node_base* _M_next;//          
  _List_node_base* _M_prev;//          
};  
  
template   
struct _List_node : public _List_node_base {  
  _Tp _M_data;//         
};  
  
//     List_iterator_base      
struct _List_iterator_base {  
    //      
  typedef size_t                     size_type;  
  typedef ptrdiff_t                  difference_type;  
  //list            bidirectional_iterator  
  typedef bidirectional_iterator_tag iterator_category;  
  
  //             
  _List_node_base* _M_node;  
  
  //      
  _List_iterator_base(_List_node_base* __x) : _M_node(__x) {}  
  _List_iterator_base() {}  
  
  //      ,               
  void _M_incr() { _M_node = _M_node->_M_next; }  
  void _M_decr() { _M_node = _M_node->_M_prev; }  
  
  //       
  bool operator==(const _List_iterator_base& __x) const {  
    return _M_node == __x._M_node;  
  }  
  bool operator!=(const _List_iterator_base& __x) const {  
    return _M_node != __x._M_node;  
  }  
};    
  
//     List_iterator      
template  
struct _List_iterator : public _List_iterator_base {  
  typedef _List_iterator<_tp>             iterator;  
  typedef _List_iterator<_tp _tp=""> const_iterator;  
  typedef _List_iterator<_tp>             _Self;  
  
  typedef _Tp value_type;  
  typedef _Ptr pointer;  
  typedef _Ref reference;  
  typedef _List_node<_tp> _Node;  
  
  //      
  _List_iterator(_Node* __x) : _List_iterator_base(__x) {}  
  _List_iterator() {}  
  _List_iterator(const iterator& __x) : _List_iterator_base(__x._M_node) {}  
  
  //            ,        
  reference operator*() const { return ((_Node*) _M_node)->_M_data; }  
  
#ifndef __SGI_STL_NO_ARROW_OPERATOR  
  pointer operator->() const { return &(operator*()); }  
#endif /* __SGI_STL_NO_ARROW_OPERATOR */  
  
  _Self& operator++() {   
    this->_M_incr();  
    return *this;  
  }  
  _Self operator++(int) {   
    _Self __tmp = *this;  
    this->_M_incr();  
    return __tmp;  
  }  
  _Self& operator--() {   
    this->_M_decr();  
    return *this;  
  }  
  _Self operator--(int) {   
    _Self __tmp = *this;  
    this->_M_decr();  
    return __tmp;  
  }  
};  
  
#ifndef __STL_CLASS_PARTIAL_SPECIALIZATION  
  
//          
inline bidirectional_iterator_tag  
iterator_category(const _List_iterator_base&)  
{  
  return bidirectional_iterator_tag();  
}  
  
template   
inline _Tp*  
value_type(const _List_iterator<_tp _ref="" _ptr="">&)  
{  
  return 0;  
}  
  
inline ptrdiff_t*  
distance_type(const _List_iterator_base&)  
{  
  return 0;  
}  
  
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */  
  
  
// Base class that encapsulates details of allocators.  Three cases:  
// an ordinary standard-conforming allocator, a standard-conforming  
// allocator with no non-static data, and an SGI-style allocator.  
// This complexity is necessary only because we're worrying about backward  
// compatibility and because we want to avoid wasting storage on an   
// allocator instance if it isn't necessary.  
  
#ifdef __STL_USE_STD_ALLOCATORS  
  
// Base for general standard-conforming allocators.  
template   
class _List_alloc_base {  
public:  
  typedef typename _Alloc_traits<_tp _allocator="">::allocator_type  
          allocator_type;//         
  allocator_type get_allocator() const { return _Node_allocator; }  
  
  _List_alloc_base(const allocator_type& __a) : _Node_allocator(__a) {}  
  
protected:  
  _List_node<_tp>* _M_get_node()  
   { return _Node_allocator.allocate(1); }  
  void _M_put_node(_List_node<_tp>* __p)  
    { _Node_allocator.deallocate(__p, 1); }  
  
protected:  
  typename _Alloc_traits<_list_node>, _Allocator>::allocator_type  
           _Node_allocator;  
  _List_node<_tp>* _M_node;  
};  
  
// Specialization for instanceless allocators.  
//instanceless         
template   
class _List_alloc_base<_tp _allocator="" true=""> {  
public:  
    //         
  typedef typename _Alloc_traits<_tp _allocator="">::allocator_type  
          allocator_type;  
  //         
  allocator_type get_allocator() const { return allocator_type(); }  
  
  //      
  _List_alloc_base(const allocator_type&) {}  
  
protected:  
  typedef typename _Alloc_traits<_list_node>, _Allocator>::_Alloc_type  
          _Alloc_type;  
  //          
  _List_node<_tp>* _M_get_node() { return _Alloc_type::allocate(1); }  
  //          
  void _M_put_node(_List_node<_tp>* __p) { _Alloc_type::deallocate(__p, 1); }  
  
protected:  
    //        
  _List_node<_tp>* _M_node;  
};  
  
template   
class _List_base   
  : public _List_alloc_base<_tp _alloc="" _alloc_traits="">::_S_instanceless>  
{  
public:  
  typedef _List_alloc_base<_tp _alloc="" _alloc_traits="">::_S_instanceless>  
          _Base;   
  //allocator_type       
  typedef typename _Base::allocator_type allocator_type;  
  
 //      
  _List_base(const allocator_type& __a) : _Base(__a) {  
    _M_node = _M_get_node();//          
    _M_node->_M_next = _M_node;//  
    _M_node->_M_prev = _M_node;  
  }  
  //      
  ~_List_base() {  
    clear();//      
    _M_put_node(_M_node);//            
  }  
  
  void clear();//      
};  
  
#else /* __STL_USE_STD_ALLOCATORS */  
  
template   
class _List_base   
{  
public:  
  typedef _Alloc allocator_type;//         
  allocator_type get_allocator() const { return allocator_type(); }  
  
  //      
  _List_base(const allocator_type&) {  
    _M_node = _M_get_node();//          
    //             ,          
    _M_node->_M_next = _M_node;  
    _M_node->_M_prev = _M_node;  
  }  
  //      
  ~_List_base() {  
    clear();//      
    _M_put_node(_M_node);//            
  }  
  
  void clear();//      
  
protected:  
    //       
  typedef simple_alloc<_list_node>, _Alloc> _Alloc_type;  
  //            
  _List_node<_tp>* _M_get_node() { return _Alloc_type::allocate(1); }  
  //            
  void _M_put_node(_List_node<_tp>* __p) { _Alloc_type::deallocate(__p, 1); }   
  
protected:  
  _List_node<_tp>* _M_node;//         
};  
  
#endif /* __STL_USE_STD_ALLOCATORS */  
  
//clear()     ,       
template   
void   
_List_base<_tp>::clear()   
{  
 //  _M_node->_M_next        
 _List_node<_tp>* __cur = (_List_node<_tp>*) _M_node->_M_next;  
  while (__cur != _M_node) {//         
    _List_node<_tp>* __tmp = __cur;//            
    __cur = (_List_node<_tp>*) __cur->_M_next;//         
    _Destroy(&__tmp->_M_data);//        
    _M_put_node(__tmp);//    tmp         
  }  
  //   ,               
  _M_node->_M_next = _M_node;  
  _M_node->_M_prev = _M_node;  
}  
  
//       list    ,   _Alloc           
template   
class list : protected _List_base<_tp _alloc=""> {  
  // requirements:  
  
  __STL_CLASS_REQUIRES(_Tp, _Assignable);  
  
  typedef _List_base<_tp _alloc=""> _Base;  
protected:  
  typedef void* _Void_pointer;//        
  
public: //         
  typedef _Tp value_type;  
  typedef value_type* pointer;  
  typedef const value_type* const_pointer;  
  typedef value_type& reference;  
  typedef const value_type& const_reference;  
  typedef _List_node<_tp> _Node;  
  typedef size_t size_type;  
  typedef ptrdiff_t difference_type;  
  
  typedef typename _Base::allocator_type allocator_type;//       
  allocator_type get_allocator() const { return _Base::get_allocator(); }  
  
public:  
    //        
  typedef _List_iterator<_tp>             iterator;  
  typedef _List_iterator<_tp _tp=""> const_iterator;  
  
#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION  
  typedef reverse_iterator const_reverse_iterator;  
  typedef reverse_iterator       reverse_iterator;  
#else /* __STL_CLASS_PARTIAL_SPECIALIZATION */  
  typedef reverse_bidirectional_iterator  
          const_reverse_iterator;  
  typedef reverse_bidirectional_iterator  
          reverse_iterator;   
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */  
  
protected:  
#ifdef __STL_HAS_NAMESPACES  
  using _Base::_M_node;  
  using _Base::_M_put_node;  
  using _Base::_M_get_node;  
#endif /* __STL_HAS_NAMESPACES */  
  
protected:  
    //    x   ,           
  _Node* _M_create_node(const _Tp& __x)  
  {  
    _Node* __p = _M_get_node();//          
    __STL_TRY {// x        ,  data   
      _Construct(&__p->_M_data, __x);  
    }  
    __STL_UNWIND(_M_put_node(__p));  
    return __p;//        
  }  
  
  //          
  _Node* _M_create_node()  
  {  
    _Node* __p = _M_get_node();  
    __STL_TRY {  
      _Construct(&__p->_M_data);  
    }  
    __STL_UNWIND(_M_put_node(__p));  
    return __p;  
  }  
  
public:  
      
  
  //           
  iterator begin()             { return (_Node*)(_M_node->_M_next); }  
  const_iterator begin() const { return (_Node*)(_M_node->_M_next); }  
  
  iterator end()             { return _M_node; }  
  const_iterator end() const { return _M_node; }  
  
  reverse_iterator rbegin()   
    { return reverse_iterator(end()); }  
  const_reverse_iterator rbegin() const   
    { return const_reverse_iterator(end()); }  
  
  reverse_iterator rend()  
    { return reverse_iterator(begin()); }  
  const_reverse_iterator rend() const  
    { return const_reverse_iterator(begin()); }  
  
  //            
  bool empty() const { return _M_node->_M_next == _M_node; }  
   
  //         
  size_type size() const {  
    size_type __result = 0;  
    //              
    distance(begin(), end(), __result);  
    //           
    return __result;  
  }  
  size_type max_size() const { return size_type(-1); }  
  
  //            ,reference   value_type&  
  reference front() { return *begin(); }  
  const_reference front() const { return *begin(); }  
  //               
  reference back() { return *(--end()); }  
  const_reference back() const { return *(--end()); }  
  
  //           
  void swap(list<_tp _alloc="">& __x) { __STD::swap(_M_node, __x._M_node); }  
  
 //**********************************************************************  
 //*********************    *****************************************  
  /******************            ,      **************  
    //      pos      value       
    iterator insert( iterator pos, const T& value );  
    iterator insert( const_iterator pos, const T& value );  
  
    //      pos    n   value       
    void insert( iterator pos, size_type count, const T& value );  
    iterator insert( const_iterator pos, size_type count, const T& value );  
  
    //      pos    [first,last)         
    template< class InputIt >  
    void insert( iterator pos, InputIt first, InputIt last);  
    template< class InputIt >  
    iterator insert( const_iterator pos, InputIt first, InputIt last );  
  ***********************************************************************/  
  /**         ,          ,            **/  
//***********************************************************************  
  //            x     
  iterator insert(iterator __position, const _Tp& __x) {  
      //          x   ,           
    _Node* __tmp = _M_create_node(__x);  
    //      ,             
    __tmp->_M_next = __position._M_node;  
    __tmp->_M_prev = __position._M_node->_M_prev;  
    __position._M_node->_M_prev->_M_next = __tmp;  
    __position._M_node->_M_prev = __tmp;  
    //         
    return __tmp;  
  }  
  //                 
  iterator insert(iterator __position) { return insert(__position, _Tp()); }  
  
  //       n     x     
  void insert(iterator __pos, size_type __n, const _Tp& __x)  
    { _M_fill_insert(__pos, __n, __x); }  
  void _M_fill_insert(iterator __pos, size_type __n, const _Tp& __x);   
  
#ifdef __STL_MEMBER_TEMPLATES  
  // Check whether it's an integral type.  If so, it's not an iterator.  
  //    __type_traits    
   
   //                 
  //           _InputIterator         
  template   
  void insert(iterator __pos, _InputIterator __first, _InputIterator __last) {  
    typedef typename _Is_integer<_inputiterator>::_Integral _Integral;  
    _M_insert_dispatch(__pos, __first, __last, _Integral());  
  }  
  
    
  //        _InputIterator      ,       
  template  
  void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,  
                          __true_type) {  
    _M_fill_insert(__pos, (size_type) __n, (_Tp) __x);  
  }  
  
  //        _InputIterator       ,       
  template   
  void _M_insert_dispatch(iterator __pos,  
                          _InputIterator __first, _InputIterator __last,  
                          __false_type);  
  
 #else /* __STL_MEMBER_TEMPLATES */  
  void insert(iterator __position, const _Tp* __first, const _Tp* __last);  
  void insert(iterator __position,  
              const_iterator __first, const_iterator __last);  
#endif /* __STL_MEMBER_TEMPLATES */  
    
  //          
  void push_front(const _Tp& __x) { insert(begin(), __x); }  
  void push_front() {insert(begin());}  
  //          
  void push_back(const _Tp& __x) { insert(end(), __x); }  
  void push_back() {insert(end());}  
  
  //***********************************************************  
  //********************         *********************  
  //********************            ***************  
  /************************************************************  
    //      pos     
    iterator erase( iterator pos );  
    iterator erase( const_iterator pos );  
  
    //      [first,last)       
    iterator erase( iterator first, iterator last );  
    iterator erase( const_iterator first, const_iterator last );  
  ************************************************************/  
  //***********************************************************  
  //     position    ,              
  iterator erase(iterator __position) {  
      //              
    _List_node_base* __next_node = __position._M_node->_M_next;  
    _List_node_base* __prev_node = __position._M_node->_M_prev;  
    _Node* __n = (_Node*) __position._M_node;  
    __prev_node->_M_next = __next_node;  
    __next_node->_M_prev = __prev_node;  
    _Destroy(&__n->_M_data);  
    _M_put_node(__n);  
    return iterator((_Node*) __next_node);  
  }  
  //              
  iterator erase(iterator __first, iterator __last);  
  //    ,        clear()    
  void clear() { _Base::clear(); }  
  
  //         
  void resize(size_type __new_size, const _Tp& __x);  
  void resize(size_type __new_size) { this->resize(__new_size, _Tp()); }  
  
  //           
  void pop_front() { erase(begin()); }  
  //            
  void pop_back() {   
    iterator __tmp = end();  
    erase(--__tmp);  
  }  
  
  //**********************************************************************  
  /***********************       **********************************  
  //*******************      ***************************************  
    explicit list( const Allocator& alloc = Allocator() );  
  //**********************            ************************  
    explicit list( size_type count,  
               const T& value = T(),  
               const Allocator& alloc = Allocator());  
         list( size_type count,  
               const T& value,  
               const Allocator& alloc = Allocator());  
  //**************         **************************************  
    explicit list( size_type count );  
  //************               ****************************  
    template< class InputIt >  
    list( InputIt first, InputIt last,  
      const Allocator& alloc = Allocator() );  
 //************      ***********************************************  
    list( const list& other );  
  */  
  //**********************************************************************  
  //      
  //           
  explicit list(const allocator_type& __a = allocator_type()) : _Base(__a) {}  
  list(size_type __n, const _Tp& __value,  
       const allocator_type& __a = allocator_type())  
    : _Base(__a)  
    { insert(begin(), __n, __value); }  
  explicit list(size_type __n)  
    : _Base(allocator_type())  
    { insert(begin(), __n, _Tp()); }  
  
#ifdef __STL_MEMBER_TEMPLATES  
  
  // We don't need any dispatching tricks here, because insert does all of  
  // that anyway.    
  template   
  list(_InputIterator __first, _InputIterator __last,  
       const allocator_type& __a = allocator_type())  
    : _Base(__a)  
    { insert(begin(), __first, __last); }  
  
#else /* __STL_MEMBER_TEMPLATES */  
  
  list(const _Tp* __first, const _Tp* __last,  
       const allocator_type& __a = allocator_type())  
    : _Base(__a)  
    { this->insert(begin(), __first, __last); }  
  list(const_iterator __first, const_iterator __last,  
       const allocator_type& __a = allocator_type())  
    : _Base(__a)  
    { this->insert(begin(), __first, __last); }  
  
#endif /* __STL_MEMBER_TEMPLATES */  
  list(const list<_tp _alloc="">& __x) : _Base(__x.get_allocator())  
    { insert(begin(), __x.begin(), __x.end()); }//        
  
  ~list() { }//      
  
  //      
  list<_tp _alloc="">& operator=(const list<_tp _alloc="">& __x);  
  //    ,    ,             
  //*******************************************************************  
  
public:  
  // assign(), a generalized assignment member function.  Two  
  // versions: one that takes a count, and one that takes a range.  
  // The range version is a member template, so we dispatch on whether  
  // or not the type is an integer.  
  /*********************************************************************  
  //assign()         ,        list       
    void assign( size_type count, const T& value );  
  
    template< class InputIt >  
    void assign( InputIt first, InputIt last );  
  //*******************************************************************  
      :  
    #include   
    #include   
   
    int main()  
    {  
        std::list characters;  
        //   characters        b,             
        //std::listcharacters(5,'b')  
   
        characters.assign(5, 'a');  
   
        for (char c : characters) {  
            std::cout << c << ' ';  
        }  
   
        return 0;  
    }  
        :a a a a a  
  *********************************************************************/  
    //        void assign( size_type count, const T& value );  
  void assign(size_type __n, const _Tp& __val) { _M_fill_assign(__n, __val); }  
  
  //       _M_fill_assign      public ??         ??  
  void _M_fill_assign(size_type __n, const _Tp& __val);  
  
#ifdef __STL_MEMBER_TEMPLATES  
  
  //     assign()          
  /* 
    template< class InputIt > 
    void assign( InputIt first, InputIt last ); 
             ,                
  */  
  template   
  void assign(_InputIterator __first, _InputIterator __last) {  
    typedef typename _Is_integer<_inputiterator>::_Integral _Integral;  
    _M_assign_dispatch(__first, __last, _Integral());  
  }  
  
  //            ,         
  template   
  void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)  
    { _M_fill_assign((size_type) __n, (_Tp) __val); }  
  
  //             ,         
  template   
  void _M_assign_dispatch(_InputIterator __first, _InputIterator __last,  
                          __false_type);  
  
#endif /* __STL_MEMBER_TEMPLATES */  
  //assign()        
  //*****************************************************************  
  
protected:  
    //   [first,last)            position  ,position         
    //     list  protected  ,      ,  list       
    //       void splice()    
  void transfer(iterator __position, iterator __first, iterator __last) {  
    if (__position != __last) {  
      // Remove [first, last) from its old position.  
      __last._M_node->_M_prev->_M_next     = __position._M_node;  
      __first._M_node->_M_prev->_M_next    = __last._M_node;  
      __position._M_node->_M_prev->_M_next = __first._M_node;   
  
      // Splice [first, last) into its new position.  
      _List_node_base* __tmp      = __position._M_node->_M_prev;  
      __position._M_node->_M_prev = __last._M_node->_M_prev;  
      __last._M_node->_M_prev     = __first._M_node->_M_prev;   
      __first._M_node->_M_prev    = __tmp;  
    }  
  }  
  
public:  
    //**********************************************************  
    //*******************        ***********************  
    //              position    
    /*void splice(const_iterator pos, list& other);  
      
    // it   other            pos  ,it pos         
    void splice(const_iterator pos, list& other, const_iterator it);  
  
    //   other     [first,last)             pos    
    //[first,last) pos         
    void splice(const_iterator pos, list& other,  
            const_iterator first, const_iterator last);  
    *************************************************************/  
    //**********************************************************  
    //   x            position    
    //  x *this    ,           
  void splice(iterator __position, list& __x) {  
    if (!__x.empty())   
      this->transfer(__position, __x.begin(), __x.end());  
  }  
  // i         position        
  //  :i position           
  void splice(iterator __position, list&, iterator __i) {  
    iterator __j = __i;  
    ++__j;  
    // i position       ,         
    //  i position       ,   position         
    //         ,        
    if (__position == __i || __position == __j) return;  
    //  ,        
    this->transfer(__position, __i, __j);  
  }  
  //   [first,last)        position        
  //  :[first,last) position        ,  
  //  position   [first,last)      
  void splice(iterator __position, list&, iterator __first, iterator __last) {  
    if (__first != __last)   
      this->transfer(__position, __first, __last);  
  }  
  //         ,   list      
  //************************************************************  
  //        value       
  void remove(const _Tp& __value);  
  //           ,      
  //  :          
  void unique();  
  //            
  void merge(list& __x);  
  //           
  void reverse();  
  //           
  void sort();  
  
#ifdef __STL_MEMBER_TEMPLATES  
  template  void remove_if(_Predicate);  
  template  void unique(_BinaryPredicate);  
  template  void merge(list&, _StrictWeakOrdering);  
  template  void sort(_StrictWeakOrdering);  
#endif /* __STL_MEMBER_TEMPLATES */  
};  
//list      
//**************************************************************  
  
//**************************************************************  
//*****************             *******************  
//**************************************************************  
template   
inline bool   
operator==(const list<_tp>& __x, const list<_tp>& __y)  
{  
  typedef typename list<_tp>::const_iterator const_iterator;  
  const_iterator __end1 = __x.end();  
  const_iterator __end2 = __y.end();  
  
  const_iterator __i1 = __x.begin();  
  const_iterator __i2 = __y.begin();  
  while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2) {  
    ++__i1;  
    ++__i2;  
  }  
  return __i1 == __end1 && __i2 == __end2;  
}  
  
template   
inline bool operator& __x,  
                      const list<_tp>& __y)  
{  
  return lexicographical_compare(__x.begin(), __x.end(),  
                                 __y.begin(), __y.end());  
}  
  
#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER  
  
template   
inline bool operator!=(const list<_tp>& __x,  
                       const list<_tp>& __y) {  
  return !(__x == __y);  
}  
  
template   
inline bool operator>(const list<_tp>& __x,  
                      const list<_tp>& __y) {  
  return __y < __x;  
}  
  
template   
inline bool operator<=(const list<_tp>& __x,  
                       const list<_tp>& __y) {  
  return !(__y < __x);  
}  
  
template   
inline bool operator>=(const list<_tp>& __x,  
                       const list<_tp>& __y) {  
  return !(__x < __y);  
}  
  
  
//          
template   
inline void   
swap(list<_tp _alloc="">& __x, list<_tp _alloc="">& __y)  
{  
  __x.swap(__y);  
}  
  
#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */  
//         
//**************************************************************  
  
//   list            
//**************************************************************  
#ifdef __STL_MEMBER_TEMPLATES  
  
template  template   
void   
list<_tp _alloc="">::_M_insert_dispatch(iterator __position,  
                                      _InputIter __first, _InputIter __last,  
                                      __false_type)  
{  
  for ( ; __first != __last; ++__first)//    [first,last)  
    insert(__position, *__first);//          
}  
  
#else /* __STL_MEMBER_TEMPLATES */  
  
template   
void   
list<_tp _alloc="">::insert(iterator __position,   
                          const _Tp* __first, const _Tp* __last)  
{  
  for ( ; __first != __last; ++__first)//    [first,last)  
    insert(__position, *__first);//          
}  
  
template   
void   
list<_tp _alloc="">::insert(iterator __position,  
                         const_iterator __first, const_iterator __last)  
{  
  for ( ; __first != __last; ++__first)//    [first,last)  
    insert(__position, *__first);//          
}  
  
#endif /* __STL_MEMBER_TEMPLATES */  
  
template   
void   
list<_tp _alloc="">::_M_fill_insert(iterator __position,  
                                  size_type __n, const _Tp& __x)  
{  
  for ( ; __n > 0; --__n)//  n     
    insert(__position, __x);// position    x    
}  
  
template   
typename list<_tp>::iterator list<_tp _alloc="">::erase(iterator __first,   
                                                             iterator __last)  
{  
  while (__first != __last)//    [first,last)  
    erase(__first++);//          
  return __last;  
}  
  
//           
template   
void list<_tp _alloc="">::resize(size_type __new_size, const _Tp& __x)  
{  
  iterator __i = begin();  
  size_type __len = 0;//           
  for ( ; __i != end() && __len < __new_size; ++__i, ++__len)  
    ;  
  if (__len == __new_size)//            ,          
    erase(__i, end());  
  else//            ,       x    // __i == end()  
    insert(end(), __new_size - __len, __x);  
}  
  
//      
template   
list<_tp _alloc="">& list<_tp _alloc="">::operator=(const list<_tp _alloc="">& __x)  
{  
  if (this != &__x) {  
    iterator __first1 = begin();  
    iterator __last1 = end();  
    const_iterator __first2 = __x.begin();  
    const_iterator __last2 = __x.end();  
    while (__first1 != __last1 && __first2 != __last2)   
      *__first1++ = *__first2++;  
    if (__first2 == __last2)//          x      
      erase(__first1, __last1);//         
    else//         x    ,  x                 
      insert(__last1, __first2, __last2);  
    //  if                
    /* 
        clear(); 
        this->assign(__x.begin(),__x.end()); 
    */  
  }  
  return *this;  
}  
  
//    list     n     val     
template   
void list<_tp _alloc="">::_M_fill_assign(size_type __n, const _Tp& __val) {  
  iterator __i = begin();  
  for ( ; __i != end() && __n > 0; ++__i, --__n)  
    *__i = __val;  
  if (__n > 0)//         n   ,         
    insert(end(), __n, __val);  
  else//           n ,          
    erase(__i, end());  
  // :              :  
  //             
  //       n   val       
  /* 
  _Tp tmp = __val; 
  clear(); 
  insert(begin(),__n,__val); 
  */  
}  
  
#ifdef __STL_MEMBER_TEMPLATES  
  
//              ,assign(_InputIter __first, _InputIter __last)       
// [first,last)          
template  template   
void  
list<_tp _alloc="">::_M_assign_dispatch(_InputIter __first2, _InputIter __last2,  
                                      __false_type)  
{  
  //           
  iterator __first1 = begin();  
  iterator __last1 = end();  
  //      [first2,last2)    0 1,         
  for ( ; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2)  
    *__first1 = *__first2;  
  if (__first2 == __last2)//         [first2,last2)   
    erase(__first1, __last1);  
  else  
      //         [first2,last2)   
    insert(__last1, __first2, __last2);  
}  
  
#endif /* __STL_MEMBER_TEMPLATES */  
  
//       value         
template   
void list<_tp _alloc="">::remove(const _Tp& __value)  
{  
  iterator __first = begin();  
  iterator __last = end();  
  while (__first != __last) {//        
    iterator __next = __first;  
    ++__next;  
    if (*__first == __value) erase(__first);//     ,     
    __first = __next;//    ,  first == last  
  }  
}  
  
//  
template   
void list<_tp _alloc="">::unique()  
{  
  iterator __first = begin();  
  iterator __last = end();  
  if (__first == __last) return;//     ,     
  iterator __next = __first;  
  while (++__next != __last) {//       1,  while    
    if (*__first == *__next)//         
      erase(__next);//     
    else//  ,        
      __first = __next;  
    __next = __first;  
  }  
}  
  
//          ,              
template   
void list<_tp _alloc="">::merge(list<_tp _alloc="">& __x)  
{  
  iterator __first1 = begin();  
  iterator __last1 = end();  
  iterator __first2 = __x.begin();  
  iterator __last2 = __x.end();  
  while (__first1 != __last1 && __first2 != __last2)  
    if (*__first2 < *__first1) {  
      iterator __next = __first2;  
      transfer(__first1, __first2, ++__next);// first2   first1    
      __first2 = __next;  
    }  
    else  
      ++__first1;  
  //   x      ,                     
  if (__first2 != __last2) transfer(__last1, __first2, __last2);  
}  
  
  
inline void __List_base_reverse(_List_node_base* __p)  
{  
  _List_node_base* __tmp = __p;  
  do {  
    __STD::swap(__tmp->_M_next, __tmp->_M_prev);//             
    __tmp = __tmp->_M_prev;     // Old next node is now prev.  
  } while (__tmp != __p);  
}  
  
//         
template   
inline void list<_tp _alloc="">::reverse()   
{  
  __List_base_reverse(this->_M_node);  
}      
  
//       ,list                
//  STL       sort()          ,         
template   
void list<_tp _alloc="">::sort()  
{  
  // Do nothing if the list has length 0 or 1.  
  if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node)   
  {  
    list<_tp _alloc=""> __carry;//carry           
    //counter           
    /* 
    *    counter[i]          2^(i+1)    
    *          counter[i+1] 
    */  
    list<_tp _alloc=""> __counter[64];  
    int __fill = 0;  
    while (!empty())   
    {//        
        //   :  
      __carry.splice(__carry.begin(), *this, begin());//             carry     
      int __i = 0;  
      while(__i < __fill && !__counter[__i].empty())   
      {  
        //   :  
          __counter[__i].merge(__carry);//   carry   counter[i]  
        //   :  
          __carry.swap(__counter[__i++]);//    carry counter[i]    
      }  
      //   :  
      __carry.swap(__counter[__i]);//    carry counter[i]             
      //   :  
      if (__i == __fill) ++__fill;  
    }   
  
    for (int __i = 1; __i < __fill; ++__i)  
      //   :  
        __counter[__i].merge(__counter[__i-1]);//                          
    //   :  
    swap(__counter[__fill-1]);//                     
  }  
}  
  
#ifdef __STL_MEMBER_TEMPLATES  
  
template  template   
void list<_tp _alloc="">::remove_if(_Predicate __pred)  
{  
  iterator __first = begin();  
  iterator __last = end();  
  while (__first != __last) {  
    iterator __next = __first;  
    ++__next;  
    if (__pred(*__first)) erase(__first);  
    __first = __next;  
  }  
}  
  
template  template   
void list<_tp _alloc="">::unique(_BinaryPredicate __binary_pred)  
{  
  iterator __first = begin();  
  iterator __last = end();  
  if (__first == __last) return;  
  iterator __next = __first;  
  while (++__next != __last) {  
    if (__binary_pred(*__first, *__next))  
      erase(__next);  
    else  
      __first = __next;  
    __next = __first;  
  }  
}  
  
template  template   
void list<_tp _alloc="">::merge(list<_tp _alloc="">& __x,  
                              _StrictWeakOrdering __comp)  
{  
  iterator __first1 = begin();  
  iterator __last1 = end();  
  iterator __first2 = __x.begin();  
  iterator __last2 = __x.end();  
  while (__first1 != __last1 && __first2 != __last2)  
    if (__comp(*__first2, *__first1)) {  
      iterator __next = __first2;  
      transfer(__first1, __first2, ++__next);  
      __first2 = __next;  
    }  
    else  
      ++__first1;  
  if (__first2 != __last2) transfer(__last1, __first2, __last2);  
}  
  
template  template   
void list<_tp _alloc="">::sort(_StrictWeakOrdering __comp)  
{  
  // Do nothing if the list has length 0 or 1.  
  if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) {  
    list<_tp _alloc=""> __carry;  
    list<_tp _alloc=""> __counter[64];  
    int __fill = 0;  
    while (!empty()) {  
      __carry.splice(__carry.begin(), *this, begin());  
      int __i = 0;  
      while(__i < __fill && !__counter[__i].empty()) {  
        __counter[__i].merge(__carry, __comp);  
        __carry.swap(__counter[__i++]);  
      }  
      __carry.swap(__counter[__i]);           
      if (__i == __fill) ++__fill;  
    }   
  
    for (int __i = 1; __i < __fill; ++__i)   
      __counter[__i].merge(__counter[__i-1], __comp);  
    swap(__counter[__fill-1]);  
  }  
}  
  
#endif /* __STL_MEMBER_TEMPLATES */  
  
#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)  
#pragma reset woff 1174  
#pragma reset woff 1375  
#endif  
  
__STL_END_NAMESPACE   
  
#endif /* __SGI_STL_INTERNAL_LIST_H */  
  
// Local Variables:  
// mode:C++  
// End:  

좋은 웹페이지 즐겨찾기