STL 소스 노트 (12) - 시퀀스 용기 의 deque (2)
deque 데이터 구조 재 론
우 리 는 deque 가 map 를 통 해 서로 독립 된 연속 공간 을 관리 하 는 것 을 알 고 있 습 니 다. 왜냐하면 dequeiterator 의 특수 한 디자인 으로 사용 할 때 연속 적 인 것 같 습 니 다.deque 가 생 겼 습 니 다.iterator 의 기초 (예 를 들 어 다시 불 러 오 는 조작 부호 등) 는 우리 가 용 기 를 실현 하 는 몇 가지 방법 에 매우 편리 하 다.vector 와 마찬가지 로 deque 도 하나의 start 를 유지 하고 finish 두 개의 교체 기 를 유지 합 니 다. start 는 용기 의 한 요 소 를 가리 키 고 finish 는 마지막 요소 의 다음 위 치 를 가리 키 며 미시적 으로 start 는 map 관리의 첫 번 째 버퍼 의 첫 번 째 요 소 를 가리 키 며 finish 는 마지막 버퍼 의 한 요 소 를 관리 합 니 다.(이 요 소 는 전체 용기 의 마지막 요소 입 니 다) 다음 위치 입 니 다. STL 소스 코드 에 서 는 이 포인터 들 을 기본 클래스 로 정의 하고 하위 클래스 에서 직접 사용 합 니 다.
template <class _Tp, class _Alloc>
class _Deque_base {//
public:
typedef _Deque_iterator<_Tp,_Tp&,_Tp*> iterator;
typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
//...
//...
protected:
iterator _M_start;//start
iterator _M_finish;//finish
};
//----------------------- -----------------
template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class deque : protected _Deque_base<_Tp, _Alloc> {//
typedef _Deque_base<_Tp, _Alloc> _Base;
public: // Iterators
typedef typename _Base::iterator iterator;
typedef typename _Base::const_iterator const_iterator;
protected:
using _Base::_M_map;//map
using _Base::_M_map_size;
using _Base::_M_start;//start
using _Base::_M_finish;//finish 상기 기초 가 있 으 면 deque 에서 정 의 된 많은 함수 들 이 쉽게 완성 할 수 있 습 니 다. (많은 조작 은 deque iterator 에서 합 니 다)
iterator begin() { return _M_start; }//
iterator end() { return _M_finish; }//
const_iterator begin() const { return _M_start; }//const
const_iterator end() const { return _M_finish; }//const
//--------------------- -----------------------------------------------
reference front() { return *_M_start; }//
reference back() {// ，（ ）
iterator __tmp = _M_finish;
--__tmp;
return *__tmp;
}
// ： *(_M_finish-1) ， deque_iterator ， ， ：
_Self operator-(difference_type __n) const {
_Self __tmp = *this;
return __tmp -= __n;// -=
}
const_reference front() const { return *_M_start; }//const
const_reference back() const {//const
const_iterator __tmp = _M_finish;
--__tmp;
return *__tmp;
}
//=================== =====================
size_type size() const { return _M_finish - _M_start; }
size_type max_size() const { return size_type(-1); }
bool empty() const { return _M_finish == _M_start; }deque 의 구조 와 메모리 관리
deque 데이터 구조
책 에서
4deque-test.cpp 예 를 들 어 버퍼 의 크기 는 32bytes 라 고 언급 했 는데 여 기 는 후 선생님 의 코드 에서 실제 적 으로 보 여 주 었 습 니 다.deque<int,alloc,8>ideq(20,9);템 플 릿 실 삼 8 은 버퍼 크기 가 8 개의 요 소 를 나 타 냅 니 다. 여기 가 int 형 (4 바이트) 이기 때문에 크기 가
8*sizeof(int)=32bytes 입 니 다. 위의 다른 템 플 릿 실 삼 은 공간 설정 기 입 니 다.원본 코드 에서 공간 설정 기 를 정의 하 는 방식 은 vector 와 유사 합 니 다. 모두 simple alloc 를 통 해 퍼 가기 도 하고 deque 의 기본 클래스 에서 정의 하 며 하위 클래스 에서 도 사 용 됩 니 다.template <class _Tp, class _Alloc>
class _Deque_base {//
//...
typedef _Alloc allocator_type;//
typedef simple_alloc<_Tp, _Alloc> _Node_alloc_type;
typedef simple_alloc<_Tp*, _Alloc> _Map_alloc_type;
_Tp* _M_allocate_node()//
{ return _Node_alloc_type::allocate(__deque_buf_size(sizeof(_Tp))); }
void _M_deallocate_node(_Tp* __p)//
{ _Node_alloc_type::deallocate(__p, __deque_buf_size(sizeof(_Tp))); }
_Tp** _M_allocate_map(size_t __n) // map
{ return _Map_alloc_type::allocate(__n); }
void _M_deallocate_map(_Tp** __p, size_t __n) //
{ _Map_alloc_type::deallocate(__p, __n); }
protected:
void _M_initialize_map(size_t);
void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish);
void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish);
//...
};
//=================> <========================
template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class deque : protected _Deque_base<_Tp, _Alloc> {
//...
typedef _Deque_base<_Tp, _Alloc> _Base;
typedef typename _Base::allocator_type allocator_type;
allocator_type get_allocator() const { return _Base::get_allocator(); }
using _Base::_M_initialize_map;
using _Base::_M_create_nodes;
using _Base::_M_destroy_nodes;
using _Base::_M_allocate_node;
using _Base::_M_deallocate_node;
using _Base::_M_allocate_map;
using _Base::_M_deallocate_map;
//...
};deque 구조 기 상세 설명
모든 것 이 준비 되 어 있 습 니 다. 이 제 는 상기 정 의 된 지침, 공간 설정 기 등 을 사용 하여 deque 의 구 조 를 만 들 고 배정 해 야 합 니 다. deque 의 constructor 구조 기: 앞서 언급 한 많은 것 과 마찬가지 로 기본 클래스 에서 도 이 루어 집 니 다. 구조 함 수 는 지침 을 초기 화 하 는 것 외 에 deque 를 위해 공간 을 배정 해 야 합 니 다. 여 기 는 공간 설정 기 를 사용 해 야 합 니 다.(위의 코드 에는 이미 봉인 이 되 어 있 습 니 다) 책 에서 제공 하 는
create_map_and_nodes 방법 은 SGI STL 소스 코드 에 이러한 함수 가 있 습 니 다.// ，
template <class _Tp, class _Alloc>//
void
_Deque_base<_Tp,_Alloc>::_M_initialize_map(size_t __num_elements)
{
// =( / ) +1
//
size_t __num_nodes =
__num_elements / __deque_buf_size(sizeof(_Tp)) + 1;
// map （ “ ”）
// 8 ， “ 2”（ ）
//enum { _S_initial_map_size = 8 };
_M_map_size = max((size_t) _S_initial_map_size, __num_nodes + 2);
_M_map = _M_allocate_map(_M_map_size);// ， _M_map_size
// map 2 ， map
// ， ，
_Tp** __nstart = _M_map + (_M_map_size - __num_nodes) / 2;
_Tp** __nfinish = __nstart + __num_nodes;// 1（ ， ）
/* STL_TRY STL_UNWIND try catch */
__STL_TRY {
// （ ） 。
_M_create_nodes(__nstart, __nfinish);// [__nstart,__nfinish)
}
__STL_UNWIND((_M_deallocate_map(_M_map, _M_map_size),
_M_map = 0, _M_map_size = 0));//try catch block
// （deque_iterator）
_M_start._M_set_node(__nstart);// _M_start （ ， ， ）
_M_finish._M_set_node(__nfinish - 1);// _M_finish
_M_start._M_cur = _M_start._M_first;//
_M_finish._M_cur = _M_finish._M_first +
__num_elements % __deque_buf_size(sizeof(_Tp));//
}
//====================> <=====================
template <class _Tp, class _Alloc>
void _Deque_base<_Tp,_Alloc>::_M_create_nodes(_Tp** __nstart, _Tp** __nfinish)
{
_Tp** __cur;
__STL_TRY {
for (__cur = __nstart; __cur < __nfinish; ++__cur)// __cur<=__nfinish
*__cur = _M_allocate_node();// ， 512/sizeof(T);T
// map
}
__STL_UNWIND(_M_destroy_nodes(__nstart, __cur));// （ try catch block）
}deque 공간 관리
사실은 Deque 양 방향 개 구 부 특성 으로 인해 push back () 과 push front () 두 가지 조작 을 제공 합 니 다. 또한 이 deque 는 실제 적 으로 여러 개의 버퍼 와 중간 제어 map 로 연속 공간 을 모 의 하기 때문에 구조 요 소 를 추가 할 때 현재 버퍼 가 충분 한 지 고려 해 야 합 니 다. 부족 하면 중간 제어 map 의 노드 포인 터 를 뒤로 (push back) 하거나 앞으로 가 야 합 니 다.(push front) 작은 칸 을 옮 깁 니 다. 물론 중간 제어 맵 도 확장 할 노드 가 충분 하지 않 으 면 맵 을 다시 정리 해 야 합 니 다.
void push_back(const value_type& __t) {
if (_M_finish._M_cur != _M_finish._M_last - 1) {
construct(_M_finish._M_cur, __t);// ，
++_M_finish._M_cur;
}
else
_M_push_back_aux(__t);// ， map 。
}
// Called only if _M_finish._M_cur == _M_finish._M_last - 1.
//
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_push_back_aux(const value_type& __t)
{
value_type __t_copy = __t;
_M_reserve_map_at_back();// map
*(_M_finish._M_node + 1) = _M_allocate_node();//
__STL_TRY {
construct(_M_finish._M_cur, __t_copy);// ，
_M_finish._M_set_node(_M_finish._M_node + 1);// ，
_M_finish._M_cur = _M_finish._M_first;//
}
__STL_UNWIND(_M_deallocate_node(*(_M_finish._M_node + 1)));//
}
//-----------------> <---------------------------------
void push_front(const value_type& __t) {
if (_M_start._M_cur != _M_start._M_first) {//
construct(_M_start._M_cur - 1, __t);//
--_M_start._M_cur;//
}
else
_M_push_front_aux(__t);//
}
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_push_front_aux(const value_type& __t)
{
value_type __t_copy = __t;
_M_reserve_map_at_front();
*(_M_start._M_node - 1) = _M_allocate_node();// map
__STL_TRY {
_M_start._M_set_node(_M_start._M_node - 1);//
_M_start._M_cur = _M_start._M_last - 1;//
construct(_M_start._M_cur, __t_copy);//
}
__STL_UNWIND((++_M_start, _M_deallocate_node(*(_M_start._M_node - 1))));
} 상기 두 가지 관건 적 인 조작 (실제 적 으로 하나의 효과) 이 있 는데 그것 이 바로 map 노드 를 확대 하 는 것 이다.
_M_reserve_map_at_front()&_M_reserve_map_at_back() 안의 실제 조작 은 _M_reallocate_map() 에 의 해 이 루어 진다.void _M_reserve_map_at_back (size_type __nodes_to_add = 1) {
if (__nodes_to_add + 1 > _M_map_size - (_M_finish._M_node - _M_map))
//map
_M_reallocate_map(__nodes_to_add, false);// ， ，
}물론 대응 하 는 것
pop_back() 과 pop_front() 은 전단 과 백 엔 드 에 삽입 하 는 것 과 유사 하 므 로 전체 버퍼 를 방출 해 야 하 는 지 여 부 를 판단 해 야 합 니 다.맨 끝 에 삭제 요 소 를 삽입 하 는 것 외 에 deque 는 clear (), erase (), insert () 등 흔히 볼 수 있 는 방법 도 있다.
//clear()
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::clear()
{
for (_Map_pointer __node = _M_start._M_node + 1;
__node < _M_finish._M_node;
++__node) {
destroy(*__node, *__node + _S_buffer_size());
_M_deallocate_node(*__node);
}//
if (_M_start._M_node != _M_finish._M_node) {//
destroy(_M_start._M_cur, _M_start._M_last);//
destroy(_M_finish._M_first, _M_finish._M_cur);//
_M_deallocate_node(_M_finish._M_first);//
}
else// ，
destroy(_M_start._M_cur, _M_finish._M_cur);// ，
_M_finish = _M_start;//
}//erase()
iterator erase(iterator __pos) {
iterator __next = __pos;
++__next;
difference_type __index = __pos - _M_start;//
if (size_type(__index) < (this->size() >> 1)) {
copy_backward(_M_start, __pos, __next);// （ ）
pop_front();//
}
else {
copy(__next, _M_finish, __pos);//
pop_back();//
}
return _M_start + __index;//
}
//============>> <<========================
//earse()
template <class _Tp, class _Alloc>
typename deque<_Tp,_Alloc>::iterator
deque<_Tp,_Alloc>::erase(iterator __first, iterator __last)
{
if (__first == _M_start && __last == _M_finish) {
clear();//
return _M_finish;
}
else {
difference_type __n = __last - __first;//
difference_type __elems_before = __first - _M_start;//
if (__elems_before < difference_type((this->size() - __n) / 2)) {//
copy_backward(_M_start, __first, __last);// last
iterator __new_start = _M_start + __n;//
destroy(_M_start, __new_start);//
_M_destroy_nodes(__new_start._M_node, _M_start._M_node);//
_M_start = __new_start;//
}
else {//
copy(__last, _M_finish, __first);
iterator __new_finish = _M_finish - __n;
destroy(__new_finish, _M_finish);
_M_destroy_nodes(__new_finish._M_node + 1, _M_finish._M_node + 1);
_M_finish = __new_finish;
}
return _M_start + __elems_before;
}
}iterator insert(iterator position, const value_type& __x) {
if (position._M_cur == _M_start._M_cur) {//
push_front(__x);// push_front()
return _M_start;
}
else if (position._M_cur == _M_finish._M_cur) {//
push_back(__x);// push_back()
iterator __tmp = _M_finish;
--__tmp;
return __tmp;
}
else {
return _M_insert_aux(position, __x);
}
}
//===========>> <<=====================
template <class _Tp, class _Alloc>
typename deque<_Tp, _Alloc>::iterator
deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos, const value_type& __x)
{
difference_type __index = __pos - _M_start;//
value_type __x_copy = __x;
if (size_type(__index) < this->size() / 2) {//
push_front(front());//
iterator __front1 = _M_start;//
++__front1;
iterator __front2 = __front1;
++__front2;
__pos = _M_start + __index;
iterator __pos1 = __pos;
++__pos1;
copy(__front2, __pos1, __front1);// ，
}
else {//
push_back(back());
iterator __back1 = _M_finish;
--__back1;
iterator __back2 = __back1;
--__back2;
__pos = _M_start + __index;
copy_backward(__pos, __back2, __back1);
}
*__pos = __x_copy;//
return __pos;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
STL 원자로 작동먼저 전연 두 갈래 나무의 정의를 살펴보자. 만약에 두 갈래 나무의 깊이를 h로 설정하면 h층을 제외한 다른 각 층(1~h-1)의 결점은 모두 최대 개수에 달하고 h층의 모든 결점은 연속적으로 맨 왼쪽에 집중된다. ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
