[C++ STL] Deque

1. Deque

- FIFO, LIFO가 모두 가능한 자료형이다.

- 임의 접근이 가능하다.

- Vector와 의 비교

	Deque	Vector	효율성
크기 변경 가능	O (여러 개의 메로리 블록을 하나의 블록처럼 사용 메모리 부족시 새로운 블록 추가 할당)	O (할당된 메모리가 부족할 시 이전 메모리 블록 삭제후 새로운 메모리 블록을 재할당)	Deque
앞에 삽입, 삭제 용이	O	X	Deque
뒤에 삽입, 삭제 용이	O	O	Deque
중간 삽입, 삭제 용이	X	X	Vector
순차 접근 가능	O	O	=
임의 접근 가능	O	O	Vector (거의 같음)

 

2. Include

#include <deque>

 

3. 생성자

std::deque<T> name;
std::deque<T> name(size_type size);
std::deque<T> name(size_type size, const T initializeValue);
std::deque<T> name(const deque& otherDeque);
std::deque<T> name(_Iter first, _Iter last); // [first,last)

namespace std를 사용.

초기 size를 지정 할 수 있음. (기본생성자로 초기화된 원소들이 들어감. push할 경우 size가 늘어남)

초기 size를 지정 하며 원하는 값으로 초기화 가능.

기존의 deque를 복사하여 생성 가능.

2개의 반복자 사이에 있는 원소들로 초기화 가능.

 

4. function

// 주어진 파라미터로 deque를 초기화 (기존원소 모두 제거됨)
void assign(initializer_list<T> _Ilist)
void assign(size_type size, const T& value)
void assign(_Iter first, _Iter last) // [first,last)

// deque의 끝 부분에 새로운 원소 삽입
void push_back(T)

// deque의 시작 부분에 새로운 원소 삽입
void push_front(T)

// deque의 끝 부분에 있는 원소를 제거(반환값 없음)
void pop_back()

// deque의 시작 부분에 있는 원소를 제거(반환값 없음)
void pop_front()

// deque의 시작 부분에 있는 원소의 값을 반환한다.
reference front()

// deque의 끝 부분에 있는 원소의 값을 반환한다.
reference back()

// deque의 n번째 원소를 반환.
reference at(size_type n)

// deque의 원소 수를 반환
size_type size()

// deque가 비어있으면 true를 반환
bool empty()

// deque의 모든 원소를 제거
void clear()

// deque의 크기를 size로 변경한다.
void resize(size_type size) // 확장되는 공간을 기본값으로 초기화.
void resize(size_type size, const T& value) // 확장되는 공간을 value로 초기화.

// 두 deque의 내용을 바꾼다.
void swap(deque<T>& _Right)

// deque의 첫 번째 원소를 가리키는 반복자 반환
iterator begin()
const_iterator cbegin() // 순회 불가능

// deque의 마지막 원소 다음의 공간을 가리키는 반복자 반환
iterator end()
const_iterator cend() // 순회 불가능

// deque의 마지막 원소를 가리키는 역순 반복자 반환
reverse_iterator rbegin()
const_reverse_iterator crbegin() // 순회 불가능

// deque의 첫 번째 원소 이전의 공간을 가리키는 반복자 반환
reverse_iterator rend()
const_reverse_iterator crend() // 순회 불가능

// iter가 가리키는 위치에 value를 삽입한다. 반환값은 삽입한 원소를 가리키는 반복자. 
// 여러개를 삽입 할 경우 삽입한 원소중 가장 앞에 있는 원소를 가리키는 반복자를 반환.
iterator insert(const_iterator iter, T value)
iterator insert(const_iterator iter, size_type size, const T& value) // size개 만큼 삽입
iterator insert(const_iterator iter, initializer_list<T> _list) // _list의 원소들을 삽입
iterator insert(const_iterator iter, _iter first, _iter last) // [first,last) 사이의 원소 삽입

// iter가 가리키는 위치에 있는 원소를 제거. 반환값은 제거한 원소의 다음 원소를 가리키는 반복자.
iterator erase(const_iterator iter)
iterator erase(const_iterator first, const_iterator last) // [first,last) 사이의 원소 모두 제거

// T의 생성자에 파라미터를 넘겨서 T객체 생성후 삽입, 반환값은 삽입된 원소를 가리키는 반복자
iterator emplace(const_iterator iter,_Valty&&... _Val) // iter가 가르키는 곳에 삽입
iterator emplace_front(_Valty&&... _Val) // 앞에 삽입
iterator emplace_back(_Valty&&... _Val) // 뒤에 삽입