deque(double ended queue)

vector의 단점을 보완하기 위해 만든 컨테이너이다.

 

배열기반의 구조.

 

vector는 새로운 원소가 추가 될 때 메모리 재할당 후 이전 원소를 복사하기 때문에, 삽입 때 성능이 저하 되는 단점이 있다.

 

deque 는 vector 의 단점을 보완하기 위해서 여러개의 메모리 블록을 할당하고 하나의 블록처럼 여기는 기능이 있다.

 

deque 는 메모리가 부족할 때 마다 일정한 크기의 새로운 메모리 블록을 할당한다.

따라서 이전 원소를 복사하지 않는다.

 

데이터의 삽입 삭제가 front 와 back 에서 이루어 질 수 있다.

 

deque 는 중간 원소도 삽입 삭제가 가능하다.

 

deque 의 생성자 및 연산자

• deque dq;
  - 비어있는 deque dq 를 생성합니다.
  
  
• deque dq(10);
  - default(0) 값 으로 초기화 된 10개의 원소를 가진 dq를 생성합니다
  
  
• deque dq(10, 4);
  - 4의 값으로 초기화 된 10 개의 원소를 가진 dq를 생성합니다.
  
  
• deque dq1;
  deque dq2(dq1);
  - dq1을 복사한 dq2를 생성합니다.
  
  
• 연산자
  "==", "!=", "<", ">", "<=", ">=" 사용 가능합니다. (return 은 bool 타입입니다.)
  ex) dq1 == dq2

멤버 함수

 

-> deque에는 capacity 멤버 함수가 없습니다.

-> deque<int> dq; 라고 가정.
-> 참조 한다는 것은 해당 데이터를 리턴 한다는 뜻입니다.

• dq.assign(4, 3);
  - 3의 값으로 4개의 원소 할당.
  
  
• dq.at(idx);
  - idx번째 원소를 참조합니다. 
  - 유효범위를 점검하므로 dq[idx]보다 "상대적"으로 속도가 느립니다.
  - dq[idx] 로도 참조가 가능합니다 (dq[idx]가 at보다 속도가 빠릅니다)
  
  
• dq[idx];
  - idx 번째 원소를 참조합니다.
  - 유효 범위를 점검하지 않으므로 상대적으로 속도가 dq.at(idx)보다 빠릅니다.
  
  
• dq.front();
  - 첫 번째 원소를 참조 합니다.
  
  
• dq.back();
  - 맨 마지막 원소를 참조 합니다.
  
  
• dq.clear();
  - 모든 원소를 제거합니다.
  
  
  
• dq.push_front(3);
  - dq의 첫 번째 원소 앞에 원소 3을 삽입합니다.
  
  

  

• dq.pop_front();
  - dq의 첫 번째 원소를 제거합니다.
  
  
  
• dq.push_back(5);
  - dq의 마지막 원소 뒤에 원소 5를 삽입합니다.
  

  

• dq.pop_back();
  - 마지막 원소를 제거합니다.
  
  
  
• dq.begin();
  - 첫번째 원소를 가리킵니다. (iterator와 사용)
  - ex) deque<int>::iterator iter = dq.begin();
  
  
• dq.end();
  - 마지막의 "다음"을 가리킵니다. (iterator와 사용)
  - ex) deque<int>::iterator iter = dq.end();
  
  

• dq.rbegin();
  - reverse begin을 가리킵니다.
  - 맨 마지막원소를 마치 첫 번째 원소처럼 가리킵니다. (역으로)
  - iterator와 사용.
  - ex) deque<int>::iterator iter = dq.rbegin();
  

• dq.rend();
  - reverse end 을 가리킵니다.
  - 맨 첫번째 원소의 "앞"을 마지막 원소의 "다음" 처럼 가리칩니다.
  - iterator와 사용.
  - ex) deque<int>::iterator iter = dq.rend();
  
  
  
• dq.resize(n);
  - 크기를 n 으로 변경합니다.
  - 만약 크기가 더 커졌을 경우 비어있는 원소를 default값인 0으로 초기화 합니다.

• dq.resize(n,2);
  - 크기를 n 으로 변경합니다.
  - 만약 크기가 더 커졌을 경우 빈 원소를 2로 초기화합니다.
  
  
• dq.size();
  - 원소의 개수를 리턴합니다.
  
  

• dq2.swap(dq1);
  - dq1과 dq2를 바꾸어 줍니다. (swap)
  
  
• dq.insert(1, 2, 3);
  - 1번째 위치에 2개의 3값을 삽입합니다.
  - 삽입 시에 앞뒤 원소의 개수를 판단하여 적은 쪽으로 미루어서 삽입합니다.
  - 만약 앞의 원소의 개수가 적을 경우, 앞쪽으로 블록을 만들어서 원소를 옮기고 삽입합니다.
  - 만약 뒤의 원소의 개수가 적을 경우, 뒤쪽으로 블록을 만들어서 원소를 옮기고 삽입합니다.
  
  
• dq.insert(3, 4);
  - 3번째 위치에 4의 값을 삽입합니다.
  - 삽입한 곳의 iterator를 반환합니다.
  
  
• dq.erase(iter);
  - iter가 가리키는 원소를 제거합니다.
  - 제거 한 후 앞 뒤의 원소의 개수를 판단하여 적은쪽의 원소를 당겨서 채웁니다.
  - 제거한 곳의 iterator 를 반환합니다.
  

• dq.empty()
  - dq가 비었으면 true를 반환합니다.

 

deck의 장점

• deck는 vector와 다르게 양쪽 끝에서 삽입 삭제가 가능하다!
• deck는 vector와 다르게 capacity와 reserve 가 없다!
• deck는 vector와 다르게 연속된 메모리에 존재하지 않는다. (포인터 연산으로 접근불가)
• deck는 vector와 다르게 capacity가 꽉 차면 덩어리채로 메모리가 이동하지 않고 메모리 상에서 잘게 쪼개어서 보관하게 된다.
• deck 객체 자체에서 메모리에 쪼개져서 보관되는 덩어리들의 위치를 기억하고, 각각의 원소에 대해 접근할 수 있는 인터페이스를 제공해준다.
• deck는 어떤 경우라도 각각의 원소는 임의 접근 반복자를 통해 접근할 수 있다.
• deck는 vector에 비해 조금 더 복잡하게 구현되어 있지만 vector보다 메모리 공간을 효율적으로 쓸 수 있다.(재할당을 하지 않기때문에 vector보다 빠름!)
• deck는 크기 할당이 자동으로 수행된다.

• 자원 접근이 쉽다
• 원소를 어떤 방향으로든 참조해 나갈 수 있다(iterate)
• 데크 끝과 시작 부분에 효율적으로 원소를 추가할 수 있다

 

 

 

 

 

 

 

 

 

출처 : 

https://blockdmask.tistory.com/73

[C++] deque container 정리 및 사용법

https://velog.io/@kbk5675/C-STL-deque%EB%9E%80

C++ STL) deque란?

https://www.hanbit.co.kr/channel/category/category_view.html?cms_code=CMS3942847236 

About STL : C++ STL 프로그래밍(5)-덱(deque) : (1)