<STL>Deque

Deque

• Deque란
  • Deque는 C++ STL컨테이너중 하나이다.
  • Deque는 시퀀스 컨테이너이자, 배열 기반 컨테이너이다.
  • Deque는 Vector와 특징이 매우 유사하고 하나의 블록에 저장되는 Vector와 달리 Deque는 여러 개의 메모리 블록에 나뉘어 저장된다는 특징을 갖고있다.
  • 단순히 push_back을 통해서 추가하는 경우에도 deque가 Vector보다 효율적이다. Vector는 메모리가 가득 찼을 때 이 전 메모리를 삭제하고 원소를 복사한후 메모리를 재할당하는 방식을 채택하는데, Deque는 단순히 메모리 블록을 하나 새로 할당하기 때문이다.

그림과 같은 메모리 구조를 갖기에, 벡터와 달리 push_front(), pop_front()를 이용해 앞쪽에서도 원소를 추가/제거할 수 있다. 그리고 원소를 추가/삭제를 하는 경우 Vector에 비해서 효율이 약간 우수하다. 이유는 vector는 앞에서 원소를 추가하는 것이 불가능한 스택 구조이기에, 모든 원소를 뒤쪽으로 밀어야만 하는데, Deque는 앞 뒤 모두 원소의 추가/삭제가 가능하기에 뒤쪽이나 앞쪽 모두 밀어낼 수 있기 때문이다.

• Deque 멤버함수

• Deque 기본형태
  • Deque<자료형>변수명

• Deque 사용방법
  • 헤더포함
    • Deque를 사용하려면 #include<deque>를 해줘야한다.
  • 기본적인 선언 및 초기화방식

• Deque 사용방법
  • 값 추가/삭제
    • push_back& pop_back
      • 뒤에서 원소를 추가/ 삭제 합니다.값 추가/삭제

• • 값 추가/삭제
    • push_front & pop_front
      • 앞에서 원소를 추가/ 삭제 합니다.

• • 값 추가/삭제
    • Insert(위치, 값)
      • 중간에 값을 추가한다. Begin()과 함께 사용 가능하다.

• • 값 추가/삭제
    • erase(위치, 값)
      • 중간에 값을 삭제합니다. Begin()반복자와 함께 사용 가능하다.

• 첫 번째 원소 접근
  • front()
    • 첫번째 값에 접근이 가능하다.

• 마지막 원소 접근 
  • back()
    • 마지막 요소에 접근이 가능하다.

• 원소 접근
  • Deque는 []연산자와 at()멤버함수를 통해 원소에 접근한다. 둘의 차이는 []연산자는 범위 점검을 하지 않아서 속도가 빠르지만 out_of_range 에러가 날 수 있어서 위험하다. 반대로 at()멤버함수는 범위 점검을 수행하여 속도는 느리지만 안전하다.