std::deque

std::deque (양방향 큐 컨테이너)

양쪽 끝에서 빠른 삽입·삭제가 가능한 인덱스 시퀀스 컨테이너예요. double-ended queue의 줄임말이에요. 양 끝 삽입·삭제가 나머지 원소를 가리키는 포인터나 참조를 무효화하지 않아요.

출처: cppreference

본문

<deque> 헤더에 정의돼 있고, 양방향 큐(deque) 컨테이너예요.

template<
    class T,
    class Allocator = std::allocator<T>
> class deque;

C++17부터 pmr 별칭도 있어요: std::pmr::deque<T> = std::deque<T, std::pmr::polymorphic_allocator<T>>.

std::deque는 시작과 끝 모두에서 빠른 삽입·삭제를 허용하는 인덱스 시퀀스 컨테이너예요. 게다가 deque 양 끝에서의 삽입·삭제는 나머지 원소를 가리키는 포인터나 참조를 절대 무효화하지 않아요.

std::vector와 달리 deque의 원소는 연속적으로 저장되지 않아요. 일반적인 구현은 개별적으로 할당된 고정 크기 배열들의 시퀀스와 추가 부킵(bookkeeping)을 사용해요. 따라서 deque의 인덱스 접근은 두 번의 포인터 역참조를 수행해야 하는 반면, vector의 인덱스 접근은 한 번만 수행해요.

deque의 저장 공간은 필요에 따라 자동으로 확장·축소돼요. deque의 확장은 std::vector의 확장보다 저렴한데, 기존 원소를 새 메모리 위치로 복사하는 작업이 포함되지 않기 때문이에요. 반면 deque는 일반적으로 최소 메모리 비용이 커요. 원소 하나만 담는 deque도 내부 배열 전체를 할당해야 해요(예: 64비트 libstdc++에서 객체 크기의 8배, 64비트 libc++에서 객체 크기의 16배 또는 4096바이트 중 더 큰 쪽).

deque의 일반적인 연산 복잡도:

임의 접근: 상수 O(1).
끝 또는 시작에서 원소 삽입·제거: 상수 O(1).
그 외 원소 삽입·제거: 선형 O(n).

std::deque는 Container, AllocatorAwareContainer, SequenceContainer, ReversibleContainer 요구사항을 만족해요. C++26부터 모든 멤버 함수가 constexpr이어서 상수 표현식 평가에서도 std::deque 객체를 만들고 쓸 수 있어요. 다만 constexpr std::deque 변수를 정의하는 건 일반적으로 오류인데, 상수 평가는 동적 할당 저장소가 같은 평가에서 해제되어야 하는데 std::deque의 초기화자에서는 보통 그렇지 않기 때문이에요.

템플릿 매개변수

T: 원소 타입. (C++11 이후) 원소에 부과되는 요구사항은 실제 수행되는 연산에 따라 달라져요. 일반적으로 원소 타입이 완전 타입이고 Erasable 요구사항을 만족해야 하지만 많은 멤버 함수가 더 엄격한 요구사항을 부과해요.
Allocator: 메모리를 획득·해제하고 그 안의 원소를 생성·파괴하는 데 쓰는 할당자. Allocator 요구사항을 만족해야 해요. Allocator::value_type이 T와 다르면 (C++20부터) 프로그램은 ill-formed예요.

반복자 무효화

읽기 전용 연산: 절대 무효화 안 됨.
swap, std::swap: past-the-end 반복자가 무효화될 수 있음(구현 정의).
shrink_to_fit, clear, insert, emplace, push_front, push_back, emplace_front, emplace_back: 항상 무효화.
erase: 끝 부분 erase면 지워진 원소만, 아니면 모든 반복자 무효화 등 위치에 따라 다름.
resize: 크기 변경 방향·여부에 따라 다름.
pop_front, pop_back: 지워진 원소에 대한 것. past-the-end 반복자도 (C++11부터) 무효화.

무효화 참고:

deque 양 끝에 삽입할 때 insert·emplace는 참조를 무효화하지 않아요.
push_front, push_back, emplace_front, emplace_back은 deque 원소에 대한 어떤 참조도 무효화하지 않아요.
deque 양 끝에서 지울 때 erase, pop_front, pop_back은 지워지지 않은 원소의 참조를 무효화하지 않아요.
더 작은 크기로 resize해도 지워지지 않은 원소의 참조는 무효화되지 않아요.

멤버 타입

value_type = T, allocator_type = Allocator, size_type(보통 std::size_t), difference_type(보통 std::ptrdiff_t), reference = T&, const_reference = const T&, pointer = std::allocator_traits<Allocator>::pointer, const_pointer = ...::const_pointer, iterator = LegacyRandomAccessIterator(및 C++26부터 ConstexprIterator), const_iterator, reverse_iterator = std::reverse_iterator<iterator>, const_reverse_iterator.

멤버 함수

생성자, 소멸자, operator=, assign, assign_range(C++23), get_allocator.
원소 접근: at, operator[], front, back.
반복자: begin/cbegin, end/cend, rbegin/crbegin, rend/crend.
용량: empty, size, max_size, shrink_to_fit.
수정자: clear, insert, insert_range(C++23), emplace, erase, push_back, emplace_back, append_range(C++23), pop_back, push_front, emplace_front, prepend_range(C++23), pop_front, resize, swap.

비멤버 함수

operator==, !=, <, <=, >, >=, <=>: 두 deque 사전식 비교.
std::swap(std::deque): std::swap 특수화.
erase, erase_if(std::deque) (C++20): 특정 기준을 만족하는 원소를 모두 지움.

C++17부터 추론 가이드가 있어요. 피처 테스트 매크로 __cpp_lib_containers_ranges(C++23), __cpp_lib_constexpr_deque(C++26)가 있어요.

예제를 보면요.

#include <deque>
#include <iostream>

int main()
{
    // 정수를 담는 deque 생성
    std::deque<int> d = {7, 5, 16, 8};

    // deque의 앞과 뒤에 정수 추가
    d.push_front(13);
    d.push_back(25);

    // deque 값들을 순회하며 출력
    for (int n : d)
        std::cout << n << ' ';
    std::cout << '\n';
}

출력:

13 7 5 16 8 25

결함 보고로 LWG 230(C++98, T가 CopyConstructible일 것을 요구하지 않음 → 요구 추가)이 있어요.

더 알아보기 (Learn more)

cppreference