STL 소스 노트 (10) - 시퀀스 용기 list

STL 소스 노트 (10) - 시퀀스 용기 list
STL 의 list 용 기 는 본질 적 으로 양 방향 링크 로 삽입 삭제 등 을 효과적으로 완성 할 수 있 기 때문에 소스 코드 에서 데이터 구조 중의 양 방향 링크 와 차이 가 많 지 않 고 STL 소스 코드 에서 list 는 템 플 릿 류 로 일부 작업 을 패키지 합 니 다.
list 데이터 구조
우 리 는 링크 의 노드 가 데이터 필드 와 포인터 필드 로 나 뉘 는 것 을 알 고 있 습 니 다. 양 방향 링크 에 있어 서 그 포인터 필드 는 이전 노드 를 가리 키 는 지침 을 추가 로 포함 하고 STL 소스 코드 stl_list.h 에서 계승 하 는 방법 으로 표시 합 니 다.

struct _List_node_base {
  _List_node_base* _M_next;
  _List_node_base* _M_prev;
};
template <class _Tp>
struct _List_node : public _List_node_base {
  _Tp _M_data;
};
template <class _Tp, class _Alloc>
class _List_base 
{
//...
protected:
  _List_node<_Tp>* _M_node;//         
//...
};
// class list ， typedef       
template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class list : protected _List_base<_Tp, _Alloc> {
//...
    typedef _List_node<_Tp> _Node;
//...
};

책 에서 SGI list 는 양 방향 링크 일 뿐만 아니 라 링 모양 의 양 방향 링크 이기 도 한다. STL 용기 앞에서 닫 은 후에 열 리 는 일치 성 을 확보 하기 위해 여 기 는 꼬리 부분 에 공백 노드 를 삽입 할 수 있다. list (사실은 아버지 류 가 정의 한 _List_node<_Tp>* _M_node; 유지 하 는 양 방향 링크 의 '헤드 포인터' 는 이 공백 노드 를 가리킨다. 이 양 방향 링크 는 하나의 링 이기 때문이다.그래서 생 겼 다.

template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class list : protected _List_base<_Tp, _Alloc> {
public:
    iterator begin()             { return (_Node*)(_M_node->_M_next); }
    const_iterator begin() const { return (_Node*)(_M_node->_M_next); }

    //  end()           ，               ，
    //           
    iterator end()             { return _M_node; }
    const_iterator end() const { return _M_node; }
};

이 를 통 해 링크 의 일부 속성 을 쉽게 얻 을 수 있 습 니 다:

//      “   ”    list  
bool empty() const { return _M_node->_M_next == _M_node; }
//distance          
size_type size() const 
{
    size_type __result = 0;
    distance(begin(), end(), __result);
    return __result;
}

상기 distance 함수 에 대해 서 는 책 에서 하나의 전역 함수 만 간단 합 니 다. 제3 장 교체 기 에서 추출 할 때 advance 를 예 로 들 고 distance 함수 와 advance 는 같은 파일 에서 stl_iterator_base.h 서로 다른 iteratorcategory (교체 기 형식) 는 서로 다른 리 셋 버 전 을 선택 합 니 다. 여 기 는 링크 의 특성 (무 작위 요소 접근 지원 하지 않 음) 에 따라 선택 해 야 합 니 다.

template <class _InputIterator, class _Distance>
inline void __distance(_InputIterator __first, _InputIterator __last,
                       _Distance& __n, input_iterator_tag)
{
  while (__first != __last) { ++__first; ++__n; }
}

list 의 구조 와 메모리 관리
책 에서 보 여 주 는 4list-test.cpp 에서 list 의 일부 체 제 를 대충 볼 수 있다. 예 를 들 어 찾기, 삽입, 삭제 등 이다. 이런 체 제 는 모두 링크 를 바탕 으로 하 는 작업 이다. 링크 와 같은 데이터 구조 에 있어 메모리 관리 (삽입 을 예 로 들 어) 는 매번 에 만 든 노드 는 메모리 배분 과정 이다. 여 기 는 공간 설정 기와 관련 이 있다.

typedef simple_alloc<_List_node<_Tp>, _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); }//   

초기 화 할 때 하나의 노드 를 생 성 합 니 다. next 와 prev 지침 은 모두 자신 을 가리 키 고 책 에서 이 를 간소화 합 니 다 (링크 조작 일 뿐). 소스 코드 에서 실제 적 으로 계승 하 는 내용 을 사 용 했 습 니 다.

template <class _Tp, class _Alloc>
class _List_base //  
{
public:
  typedef _Alloc allocator_type;
  _List_base(const allocator_type&) {//    
    _M_node = _M_get_node();
    _M_node->_M_next = _M_node;
    _M_node->_M_prev = _M_node;
  }
};

template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class list : protected _List_base<_Tp, _Alloc> {//  
  typedef _List_base<_Tp, _Alloc> _Base;
  typedef typename _Base::allocator_type allocator_type;
  allocator_type get_allocator() const { return _Base::get_allocator(); }

public:
//allocator_type()        
//         
  explicit list(const allocator_type& __a = allocator_type()) : _Base(__a) {}
};

list 요소 조작
링크 작업, 삽입, 삭제 등 이다.

void push_front(const _Tp& __x) { insert(begin(), __x); }//    
void push_back(const _Tp& __x) { insert(end(), __x); }//    
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);
 }
//erase      
template <class _Tp, class _Alloc>
typename list<_Tp,_Alloc>::iterator list<_Tp, _Alloc>::erase(iterator __first, 
                                                             iterator __last)
{
  while (__first != __last)
    erase(__first++);
  return __last;
}

비슷 한 것 도 많 습 니 다. 예 를 들 어 pop_front()、pop_back() 등 은 모두 간단 한 링크 조작 입 니 다. 그러나 책 에서 중요 한 조작 을 transfer() 이 라 고 언급 했 습 니 다. 역할 은 특정한 범위 의 요 소 를 position 까지 이동 시 키 는 것 입 니 다. 말하자면 링크 조작 이기 도 하고 힘 들 어 보일 뿐 입 니 다.이 transfer 는 내부 함수 로 서 splice, sort, merge 등에 좋 은 기반 을 다 져 주 었 습 니 다.

//           __position  
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;
    }
  }

그림:
방금 언급 한 splice, sort, merge 등 조작 을 보면 간결 합 니 다.splice

//  1：       __position  
 void splice(iterator __position, list& __x) {
    if (!__x.empty()) 
      this->transfer(__position, __x.begin(), __x.end());
  }
 //  2： __i        __position  
  void splice(iterator __position, list&, iterator __i) {
    iterator __j = __i;
    ++__j;
    if (__position == __i || __position == __j) return;
    this->transfer(__position, __i, __j);
  }
 //  3： first last        position  
 //position    [fisrt，last) 
  void splice(iterator __position, list&, iterator __first, iterator __last) {
    if (__first != __last) 
      this->transfer(__position, __first, __last);
  }

merge

//          *this 
template <class _Tp, class _Alloc>
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 = __next;
    }
    else
      ++__first1;
  if (__first2 != __last2) transfer(__last1, __first2, __last2);
}

sort

//list          sort()，  list           ，
//  ，list       sort，       quick sort，           ，
// VS       ，        ，           list        ，
//  carry  ，  counter        lists（  list size         ），
//  counter           list         ，   list              。
// carry            list，           ，
//   counter  list          。
//    list             (  while  )，
//  counter        merge       ，
//        swap     list（   sort()   list     *this）
template <class _Tp, class _Alloc>
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;
    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);//  
        __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]);// __counter               
    swap(__counter[__fill-1]);//        
  }
}