std:: deque

std::deque (double-ended queue)는 양쪽 끝에서 빠른 삽입과 삭제를 허용하는 인덱스 기반 시퀀스 컨테이너입니다. 또한, deque의 어느 쪽 끝에서든 삽입과 삭제를 수행해도 나머지 요소들에 대한 포인터나 참조가 무효화되지 않습니다.

std::vector 와 달리, deque의 요소들은 연속적으로 저장되지 않습니다: 일반적인 구현은 개별적으로 할당된 고정 크기 배열들의 시퀀스와 추가적인 부기 작업을 사용하며, 이는 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 요구 사항을 충족합니다.

템플릿 매개변수

반복자 무효화

무효화 참고 사항

• deque의 양쪽 끝에 삽입할 때, 참조는 insert 와 emplace 에 의해 무효화되지 않습니다.
• push_front , push_back , emplace_front 및 emplace_back 은 deque의 요소에 대한 어떤 참조도 무효화하지 않습니다.
• deque의 양쪽 끝에서 삭제할 때, 삭제되지 않은 요소에 대한 참조는 erase , pop_front 및 pop_back 에 의해 무효화되지 않습니다.
• 더 작은 크기로 resize 를 호출해도 삭제되지 않은 요소에 대한 어떤 참조도 무효화되지 않습니다.
• 더 큰 크기로 resize 를 호출해도 deque의 요소에 대한 어떤 참조도 무효화되지 않습니다.

멤버 타입

멤버 함수

비멤버 함수

참고 사항

예제

#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

결함 보고서

다음 동작 변경 결함 보고서는 이전에 게시된 C++ 표준에 소급 적용되었습니다.

참고 항목