STL - Deque

#include <iostream>

#include <vector>

#include <list>

#include <deque>

using namespace std;

// Deque

// Vector : 동적 배열

// [        ]

// List : 이중 연결 리스트

// [] <-> [] <-> [] <->

// Deque : double-ended queue 데크 (양방향으로 큐를 사용)

// [        ]

// 리스트와 같이 연속되어 저장되지 않음

// vector와는 달리 데이터 영역을 증설하지 않고

// 기존 데이터영역 + 새로운 데이터 영역을 만듦

int main()

{

 // 시퀀스 컨테이너 (Sequence Container)

 // 데이터가 삽입 순서대로 나열되는 형태

 // vector list deque

 deque<int> dq1;

 dq1.push_back(1);

 dq1.push_front(2); //push_front 지원

 // dq.capacity(); 제공하지 않음

 cout << dq1[0] << endl; //임의 접근 허용

 // vector와 마찬가지로 배열 기반으로 동작

 // 다만 메모리 할당 정책이 다르다

 // vector

 // [     ] 기존의 영역

 // [              ] 새로운 영역( 이전 시 기존의 영역은 삭제됨)

 // deque

 // [     ]

 // [     ]

 // vector

 // [ 1 1 1 ] 기존의 영역

 // -> [ 1 1 1 2 2 ] 새로운 영역( 기존의 영역은 삭제됨 )

 

 // deque

 // [     3 3 ] 새롭게 추가된 영역 ( 기존의 영역 유지 )

 // [ 1 1 1 2(추가됨) ] 기존의 영역

 // [ 2       ] 새롭게 추가된 영역 ( 기존의 영역 유지 )

 vector<int> v(3, 1);

 deque<int> dq(3, 1);

 v.push_back(2);

 v.push_back(2);

 dq.push_back(2);

 dq.push_back(2);

 dq.push_front(3);

 dq.push_front(3);

 // - deque의 동작 원리

 // - 중간 삽입/삭제 (Bad / Bad) (벡터와 마찬가지로 중간이 삭제되면 한칸씩 당겨줘야함)

 // - 처음/끝 삽입/삭제 (Good/Good) (새로운 영역을 확장해 넣는 방식이므로 효율이 좋다)

 // - 임의 접근 (Good)

 deque<int>::iterator it;

 // Iterator의 임의 접근 코드

 //_Size_type _Block = _Mycont->_Getblock(_Myoff); 데이터의 값을 통해 블록을 찾을 수 있다.

 //_Size_type _Off = _Myoff % _DEQUESIZ; //데이터값을 데크 사이즈로 나누어 오프셋을 구함

 //return _Mycont->_Map[_Block][_Off]; 몇번째 블록의 몇번째 오프셋이다~

 //즉 데크의 size를 알면 데이터의 위치를 알 수 있다! -> 데크에 빈 공간이 있어선 안된다. 

 //-> 중간 삽입/삭제가 효율적일 수 없다. -> 대신 임의 접근은 빠르다!

 return 0;

}