#57. deque

 

---

 

*deque ( double-ended quee )

=> 벡터처럼 데이터를 저장하지만 메모리 초과 시, 메모리를 재할당하는 것이 아니라,

리스트처럼 해당 크기만큼을 할당받고 연결한다.

=> vector, list 의 짬뽕

=> vector 와 마찬가지로 배열 기반으로 동작 다만, 메모리 할당 정책이 다름.

 

deque<int> dq; 
dq.push_back(1); 
dq.push_back(2); 
dq.push_front(3);

cout << dq[0] << endl;

 

*임의접근 가능.

 

 

 

*중간 삽입 / 삭제

=> 벡터와 마찬가지로 느림.

=> 중간에 삭제하면 나머지 부분들을 당겨서 맞춰야함.

=> 데이터가 연속적이어야함을 보장해야함.

 

 

 

*처음 / 끝 삽입 / 삭제

=> 둘 다 빠름.

 

 

 

*메모리 부족 시, 일정 크기의 메모리를 할당.

=> 벡터처럼 더 큰 메모리를 재할당하고 기존 값을 복사하지 않음.

 

 

 

*GetBlock ( )  /  Block_size

size_type _Getblock(size_type _Off) const noexcept { 
// NB: _Mapsize and _Block_size are guaranteed to be powers of 2 
    return (_Off / _Block_size) & (_Mapsize - 1); 
}

 

_NODISCARD reference operator*() const noexcept { 
	_Size_type _Block = _Mycont->_Getblock(_Myoff); 
	_Size_type _Off   = _Myoff % _Block_size; 
	return _Mycont->_Map[_Block][_Off]; 
}

 

=> Block * BlockSize 만큼의 2차원 공간에서 데이터를 관리하는 것을 볼 수 있음.

 

---

본 내용은 인프런의 루키스님 강의를 듣고 정리한 내용입니다.

강의 듣기 !!