[C++ Data Structure] Deque
Deque
#include <deque>로 사용할 수 있습니다.
데크(Deque)는 벡터의 단점을 보완하기 위해서 만들어진 컨테이너입니다.
메모리를 연속적으로 할당하지 않고, 필요한 만큼 메모리 블록을 동적으로 할당하여 관리합니다.
양 끝에서 삽입과 삭제가 가능한 큐로 동적 배열처럼 동작하는 컨테이너입니다.
임의 접근이 가능하며, 양쪽 끝에서의 삽입 및 삭제가 빠릅니다.
중간 삽입 및 삭제는 상대적으로 느립니다.
스택이나 큐와 같은 동작이 필요한 경우 유용합니다.
데크 초기화
선언은 다음과 같습니다.
std::deque<[DataType]> [변수이름]
// 기본 생성 및 초기화 없이 정의
std::deque<int> dq1;
// 오른쪽 변수 값으로 초기화
std::deque<int> dq2 = {1, 2, 3, 4, 5};
// 다른 데크를 기반으로 복사 초기화
std::deque<int> dq3(dq1);
// 다른 컨테이너 기반으로 초기화
std::vector<int> vec = {1, 2, 3, 4, 5};
std::deque<int> dq4(vec.begin(), vec.end());
// 특정 크기로 생성 및 초기화 없이 정의
std::deque<int> dq5(5);
// 특정 크기와 초기값으로 정의
std::deque<int> dq6(10, 3);
주요 연산자
[]
인덱스를 사용해 요소에 접근합니다.
범위를 확인하지 않습니다.
dq[index];
dq[1];
dq[5];
dq[14];
주요 함수
push_back
마지막 요소 끝에 새 요소를 추가합니다.
push_back(value);
dq.push_back(10);
dq.push_back(30);
push_front
첫 번째 요소 앞에 새 요소를 추가합니다.
push_front(value);
dq.push_front(20);
dq.push_front(40);
pop_back
마지막 요소를 제거합니다.
dq.pop_back();
pop_front
첫 번째 요소를 제거합니다.
dq.pop_front();
insert
특정 위치에 새 요소를 추가합니다.
중간 삽입 시, 앞쪽과 뒤쪽 요소 개수를 비교하여 이동 비용이 적은 방향으로 요소를 이동한 후 삽입됩니다.
insert(pos, value);
// 0번째 위치에 15의 값을 삽입
dq.insert(dq.begin(), 15);
// 1번째 위치에 15의 값을 삽입
dq.insert(dq.begin() + 1, 15);
// 2번째 위치에 2개의 15 값을 삽입
dq.insert(dq.begin() + 2, 2, 15);
erase
특정 위치나 범위의 요소를 제거합니다.
erase(value);
erase(pos);
erase(first, last);
// 0번 위치에 값 제거
dq.erase(dq.begin());
// 1번 위치에 값 제거
dq.erase(dq.begin() + 1);
// 0번 위치부터 2번 위치 값 제거
dq.erase(dq.begin(), dq.begin() + 2);
clear
모든 요소를 제거합니다.
요소만 제거하며, 메모리는 남아있습니다.
즉, size만 줄어들고 capacity는 변하지 않습니다.
dq.clear();
at
인덱스 범위를 확인하고, 접근합니다.
at(index);
dq.at(2);
dq.at(5);
dq.at(15);
front
첫번째 요소의 참조를 반환합니다.
dq.front();
back
마지막 요소의 참조를 반환합니다.
dq.back();
size
현재 저장된 요소의 개수를 반환합니다.
반환 자료형은 size_t입니다.
dq.size();
empty
데크가 비었으면 true값을 반환하고, 그렇지 않으면 false를 반환합니다.
dq.empty();
resize
데크의 크기인 size를 변경합니다.
새로 추가된 요소는 기본값이나 지정된 값으로 초기화 됩니다.
필요한 경우 메모리가 재할당됩니다.
resize(n);
resize(n, value);
// 크기를 2로 변경합니다.
// 크기가 더 커졌을 경우 기본값으로 초기화합니다.
// 크기가 더 작아졌을 경우 뒤의 요소가 삭제됩니다.
dq.resize(2);
// 크기를 5로 변경하고 더 커졌을 경우 100으로 초기화합니다.
dq.resize(5, 100);
begin & end
begin은 첫 번째 요소를 가리키는 반복자를 반환합니다.
end는 마지막 요소의 바로 다음 위치를 가리키는 반복자를 반환합니다.
데크의 요소를 순회하거나 반복자(Iterator)를 사용할 때 사용됩니다.
std::deque<int> dq = {10, 20, 30};
for (auto it = dq.begin(); it != dq.end(); ++it)
{
std::cout << *it << " "; // 10 20 30
}
rbegin & rend
rbegin은 마지막 요소를 가리키는 역방향 반복자를 반환합니다.
rend는 첫 번째 요소의 이전 위치를 가리키는 역방향 반복자를 반환합니다.
데크의 요소를 순회하거나 반복자(Iterator)를 사용할 때 사용됩니다.
std::deque<int> dq = {10, 20, 30};
for (auto it = dq.rbegin(); it != dq.rend(); ++it)
{
std::cout << *it << " "; // 30 20 10
}
댓글남기기