[C++/STL] STL 사용법 : Container - Deque

deque

Deque(Double-Ended Queue)는 양쪽 끝에서 삽입과 삭제가 가능한 컨테이너입니다.

 

주요 특징

1. 양방향 접근 : 양쪽 끝에서 요소에 접근할 수 있어, 삽입과 삭제가 양쪽 끝에서 가능합니다.
2. 다이나믹 크기 : 동적으로 크기가 조정되므로, 요소가 추가될 때 자동으로 메모리를 재할당합니다.
3. 랜덤 액세스 : 배열처럼 인덱스를 사용하여 요소에 접근할 수 있으며, O(1)의 시간 복잡도로 랜덤 액세스가 가능합니다.
4. 메모리 구조 : 내부적으로는 여러 개의 작은 배열로 구성되어 있어, 중간 삽입/삭제가 효율적입니다.

 

선언

#include <deque>
std::deque< int > dq;

// example
std::deque< int > dq = {1, 2, 3, 4, 5};   // 크기가 5인 deque, 초기값 등록
std::deque< int > dq(10);                 // 크기가 10인 리스트, 기본값으로 초기화
std::deque< int > dq(10, 4);              // 크기가 10인 리스트, 4로 초기화

 

 

함수

Iterators

함수	설명
begin()	첫번째 원소를 가리키는 iterator를 반환
end()	마지막 원소의 다음을 가리키는 iterator를 반환
cbegin()	첫번째 원소를 가리키는 상수 iterator를 반환
cend()	마지막 원소의 다음을 가리키는 상수 iterator를 반환
rbegin()	역 순차열의 첫 번째 원소를 가리키는 iterator를 반환
rend()	역 순차열의 마지막 원소의 다음을 가리키는 iterator를 반환
crbegin()	역 순차열의 첫 번째 원소를 가리키는 상수 iterator를 반환
crend()	역 순차열의 마지막 원소의 다음을 가리키는 상수 iterator를 반환

 

 

기타 접근 또는 사용 관련

함수	설명
front()	첫번째 원소의 값
back()	마지막 원소의 값
at(int N)	N번째 원소 값
empty()	비어있다면 true, 아니라면 false 반환
size()	크기 반환
push_front(T value)	맨 앞에 원소 추가
push_back(T value)	맨 뒤에 원소 추가
pop_front()	맨 앞의 원소 삭제
pop_back()	맨 뒤의 원소 삭제
resize(n)	크기를 n으로 변경 (늘어난 위치의 원소들은 기본값으로 초기화)
swap(deque dq2)	( 길이와 type이 같다면 ) 서로의 배열 원소들을 바꿈
insert(iterator it, T value)	원하는 위치에 원하는 값 삽입
erase(iterator it1, [iterator it2])	원하는 위치, 범위의 원소 삭제

 

 

사용 예시

#include <iostream>
#include <deque>

using namespace std;

int main(void) {
    deque<int> dq;

    for (int i = 0; i < 5; i++) {
        dq.push_back(i + 1);
    }

    // iterator 선언
    deque<int>::iterator it;

    // 반복문 출력
    for (auto it = dq.begin(); it != dq.end(); it++)
        cout << *it << " ";
    cout << endl;
    cout << endl;

    // 앞 뒤 삽입
    dq.push_front(0);
    dq.push_back(6);

    for (auto it = dq.begin(); it != dq.end(); it++)
        cout << *it << " ";
    cout << endl;
    cout << endl;

    // 역으로 출력
    deque<int>::reverse_iterator rit;
    for (auto rit = dq.rbegin(); rit != dq.rend(); rit++)
        cout << *rit << " ";
    cout << endl;
    cout << endl;

    // 중간 삽입, 삭제
    deque<int>::const_iterator cit;
    cit = dq.begin();
    cit += 2;
    dq.insert(cit, 22);

    for (auto it = dq.begin(); it != dq.end(); it++)
        cout << *it << " ";
    cout << endl;
    cout << endl;

    cit = dq.end(); // end는 원소 마지막 다음 값을 가리킴
    cit -= 2;
    dq.erase(cit);

    for (auto it = dq.begin(); it != dq.end(); it++)
        cout << *it << " ";
    cout << endl;
    cout << endl;
}