deque(double ended queue)
양쪽에서 끝나는 큐 줄여서 '데크' 라고 불린다.
stack의 경우엔 최상단에서 삽입, 삭제가 일어나지만,
queue같은 경우는 한쪽에서 삽입, 반대쪽에서 삭제가 일어난다.
(한쪽입구에서 삽입,삭제중 하의 기능만 가능)
But, deck의 경우는 스택과 큐를 합친 멋진 친구다! 모든 입구에서 삽입 삭제가 가능하다!
구조
stack의 경우엔 LIFO(Last In First Out)
deck의 경우엔 FIFO(First In First Out)
deck의 장점
-
deck는 vector와 다르게 양쪽 끝에서 삽입 삭제가 가능하다!
-
deck는 vector와 다르게 capacity와 reserve 가 없다!
-
deck는 vector와 다르게 연속된 메모리에 존재하지 않는다. (포인터 연산으로 접근불가)
-
deck는 vector와 다르게 capacity가 꽉 차면 덩어리채로 메모리가 이동하지 않고 메모리 상에서 잘게 쪼개어서 보관하게 된다.
-
deck 객체 자체에서 메모리에 쪼개져서 보관되는 덩어리들의 위치를 기억하고, 각각의 원소에 대해 접근할 수 있는 인터페이스를 제공해준다.
-
deck는 어떤 경우라도 각각의 원소는 임의 접근 반복자를 통해 접근할 수 있다.
-
deck는 vector에 비해 조금 더 복잡하게 구현되어 있지만 vector보다 메모리 공간을 효율적으로 쓸 수 있다.(재할당을 하지 않기때문에 vector보다 빠름!)
-
deck는 크기 할당이 자동으로 수행된다.
-
자원 접근이 쉽다
-
원소를 어떤 방향으로든 참조해 나갈 수 있다(iterate)
-
데크 끝과 시작 부분에 효율적으로 원소를 추가할 수 있다
코드 작성법
template <class T, class Allocator = allocator<T> >
class deque;
deque<int> dq;T : 보관하려는 원소의 타입
Allocator : 어떠한 방법으로 메모리에 할당할지에 관련한 할당(allocator) 타입을 나타낸다. 기본적으로 T의 할당자 클래스 템플릿을 사용해 Heap에 할당!
생성자 : 데크를 생성
소멸자 : 데크를 소멸
operator= : 데크의 내용을 복사
멤버 함수들
반복자
begin()
end()
rbegin()
ex) deque::iterator iter = dp.rbegin();
rend()
ex) deque::iterator iter = dq.rend();
할당 관련
size()
max_size()
resize()
empty() : 비었으면 true 반환
임의 접근
operator[]
at() : operator[]보다 상대적으로 느리다. (유효범위를 점검하므로)
front()
back()
수정자(Modifier)
assign() : 데크에 원소를 집어넣는다.
ex) 3의 값으로 4개의 원소 할당
dq.assign(4, 3);push_back() : 데크 끝에 원소를 집어 넣는다.
push_front() : 데크 맨 앞에 원소를 집어 넣는다.
pop_back() : 마지막 원소 제거
pop_front() : 첫번째 원소를 제거
insert() : 데크 중간에 원소 추가
ex) 3번째 위치에 4의 값 삽입
dp.insert(3, 4);erase() : 원소 제거
swap() : 다른 데크와 바꿔치기
clear() : 원소를 모두 제거
할당자
get_allocator : 할당자(allocator)를 얻는다.
멤버변수들
refrence : Allocator::reference
const_reference : Allocator::const_reference
iterator : 임의 접근 반복자(random access iterator)
const_iterator : 상수 임의 접근 반복자
size_type : 데크 size를 나타내는 타입
difference_type : 데크 내의 두 원소 사이의 거리를 나타내는 타입
value_type : 원소 타입(T)
alloactor_type : 할당자
pointer : 포인터
const_pointer : 상수 포인터
reverse_iterator : 역 반복자(끝에서 부터 참조해나간다)
reverse_iterator
const_reverse_iterator : 상수 역 반복자(reverse_iterator<const_iterator>)
예제
#include <iostream>
#include <deque>
int main()
{
std::deque<int> dq;
for (int i = 0; i < 5; i++)
dq.push_back((i + 1) * 10);
// 반복자 선언
std::deque<int>::iterator iter;
std::cout << "기본 deque 값 : ";
for (iter = dq.begin(); iter != dq.end(); iter++)
{
std::cout << *iter << " ";
}
std::cout << std::endl << std::endl;
// test1. 앞뒤 삽입하기
std::cout << "[Test1] push_front & end" << std::endl;
dq.push_front(1);
dq.push_front(2);
dq.push_back(100);
dq.push_back(200);
std::cout << "[Test1] deque 값 : ";
for (iter = dq.begin(); iter != dq.end(); iter++)
std::cout << *iter << " ";
std::cout << std::endl << std::endl;
//[test2] : 역으로 출력
std::cout << "[Test2] reverse_iterator" << std::endl;
std::deque<int>::reverse_iterator rlter;
for (rlter = dq.rbegin(); rlter != dq.rend(); rlter++)
std::cout << *rlter << " ";
std::cout << std::endl << std::endl;
std::cout << "[Test3] insert(conlter ++ 두번, 2, INSERT)" << std::endl;
std::deque<int>::const_iterator conlter = dq.begin();
conlter += 2; // 두번째 자리에.
dq.insert(conlter, 1, 333); // conlter반복자 333 원소 1개 삽입
for (conlter =dq.begin(); conlter != dq.end(); conlter++)
{
std::cout << *conlter << " ";
}
std::cout << std::endl << std::endl;
return 0;
}