원글: https://mystes.tistory.com/121
주요 특징
std::deque는 std::queue와 유사한 특징을 가집니다. (이하, "데크" 또는 "디큐", "덱")
queue는 FIFO (first in, first out) 구조를 가집니다. 따라서 일반적인 큐는 한쪽에서 자료를 입력하면, 다른 한쪽에서 데이터가 빠져 나오는 구조입니다.
반면 deque는 양쪽에서 데이터의 삽입, 삭제가 가능하기 때문에 FIFO와 더불어 LIFO (last in, first out) 의 특징 역시 가집니다.
일련의 컨테이너와 같이 deque 역시 sequencial(연속적인) 데이터 형태를 가지며 vector의 특징과 동일하게 인덱스를 통한 접근 (랜덤 엑세스), 순회 등과 같은 기능을 제공합니다.
기본 사용 예제
기본 예제는 모두 vector와 매우 유사하기 때문에 주요 함수만 알아보겠습니다.
추가 및 삭제
기존 vector에서 컨테이너의 맨 앞에 요소를 추가/삭제할 때 insert 또는 erase 함수를 사용했습니다. 하지만 deque는 위에서 설명한 것처럼 LIFO 특징을 갖기 때문에 push_front, pop_front 함수를 제공합니다.
std::deque<int> q = { 2, 3, 4 };
// 큐의 "맨 앞"에 요소를 추가합니다.
q.push_front(1); // v : { 1, 2, 3, 4 }
// 큐의 "맨 앞"에 요소를 삭제합니다.
q.pop_front(); // v : { 2, 3, 4 }
심화 학습
본문에서 제가 테스트 하는 환경은 ARMv8 Debian입니다. x86 계열이라고 값이 크게 차이나는 것은 아니지만 일부 퍼포먼스나 용량 수치가 변경될 수 있습니다.
stackoverflow에서 이런 말을 본 적이 있습니다.
vector와 deque의 사용처를 고민할 시기가 온다면 당신은 중급 개발자이다.
사실, 데크가 할 수 있는 일은 모두 벡터로 대체할 수 있습니다. 심지어 단일 퍼포먼스 측면에서 볼 때 드라마틱한 차이를 보이는 것도 아닙니다.
필자는 주로 15~30 fps 카메라의 이미치 처리를 다룹니다.
그럼에도 사소한 차이 하나가 모여 큰 변화를 만들 듯, 의도하는 기능에 적합한 가장 효율적인 방법과 설계를 찾는 것이 중급, 나아가 고급 개발자로서 가져야할 자세이기 때문에 항상 자료구조와 알고리즘이 강조되는 것이 아닐까 생각합니다.
vector vs deque
둘의 차이를 일차원적으로 설명하면 다음과 같습니다.
- 맨 앞에 원소를 추가/제거할 일이 많은 경우, 데크를 사용하자.
- 그 외 벡터를 사용하자.
맨 앞에 원소를 추가할 때 데크가 효율적인 것은 이전 설명에서 어느정도 유추할 수 있었습니다. 전용 함수(push_front)를 제공하는 만큼, 당연히 어느 정도 이점은 있을 것이라 생각했을 것입니다.
실제로 둘의 시간 차이를 비교하면 다음과 같습니다. (테스트는 Google benchmark를 사용하였습니다)
/* compiler = GCC 13.1 std = c++20 optim = O3 */
static void BM_VECTOR(benchmark::State& state) {
std::vector<int> v;
while (state.KeepRunning()) {
state.PauseTiming();
v.clear();
state.ResumeTiming();
for (size_t i = 0; i < 1000; i++)
v.insert(v.begin(), i);
}
}
BENCHMARK(BM_VECTOR);
static void BM_DEQUE(benchmark::State& state) {
std::deque<int> v;
while (state.KeepRunning()) {
state.PauseTiming();
v.clear();
state.ResumeTiming();
for (size_t i = 0; i < 1000; i++)
v.push_front(i);
}
}
BENCHMARK(BM_DEQUE);실행 결과는 다음과 같습니다.
테스트 횟수가 적긴 하지만, 일반적으로 데이터를 컨테이너 앞에 삽입하는 작업은 deque가 압도적으로 빠릅니다.
물론 컨테이너 뒤에 삽입하는 경우 vector가 더 빠릅니다. (약 1.2배)
벡터의 장점?
vector가 deque에 비해 가지는 이점 중 하나는 메모리의 연속성입니다. deque는 각 요소가 메모리에 연속적으로 존재한다고 보장할 수 없습니다.
이 말은 다시 말해 순회와 같은 메모리 엑세스 시 vector보다 deque가 약간 더 불리하다는 점과, 메모리 효율성 측면에서 떨어진다는 뜻입니다.
실제로 순회의 경우 유의미한 차이를 보이지 않습니다. Benchmark를 진행해도 랜덤 엑세스 시 vector가 미세하게 더 빠르다고 계산되지만 push_front 와 같이 다이나믹한 차이를 보이진 않았습니다.
그러나 다음 코드에서 테스트한 메모리는 꽤 차이가 있습니다.
struct HugeData { char data[8192]; };
int main()
{
// Vector
auto vstart = rs::utils::resource::processMemory();
std::vector<HugeData> vec;
vec.reserve(1000000);
for (int i = 0; i < 1000000; ++i)
vec.push_back(HugeData());
auto vend = rs::utils::resource::processMemory();
printf("vector usage : %lu\n", vend.physical_ - vstart.physical_); // 8193601536
// Deque
auto dstart = rs::utils::resource::processMemory();
std::deque<HugeData> que;
for (int i = 0; i < 1000000; ++i)
que.push_back(HugeData());
auto dend = rs::utils::resource::processMemory();
printf("deque usage : %lu\n", dend.physical_ - dstart.physical_); // 8216322048
}실제로 반복 테스트 시 실 사용 메모리는 각 OS에서 취급하는 Memory Management에 따라 값이 어느 정도 변합니다. 하지만 deque가 vector보다 메모리 사용량이 많다는 것을 확인할 수 있으며,
백 만개의 8kb 데이터 기준, 약 22mb의 용량을 더 차지한다는 것을 볼 수 있습니다.
