[C++][STL Container] 컨테이너 어뎁터

컨테이너 어뎁터란?

• 컨테이너 어뎁터(Container Adapters)는 C++에서 제공하는 STL 컨테이너 종류(시퀀스 컨테이너, 연관 컨테이너, 컨테이너 어뎁터) 중 하나로, 기존 컨테이너(deque, vector, list 등)를 감싸서 "특정 용도로 변형한" 컨테이너이다.

 

컨테이너 어뎁터 종류

• 스택(stack)
• 큐(queue)
• 우선순위 큐(priority queue)

 

컨테이너 어뎁터 공통 제약 사항

initializer_list 생성자 없음

• 컨테이너 어뎁터는 공통적으로 initializer_list 생성자를 가지고 있지 않는다. 따라서 아래와 같이 초기화할 수 없다.

queue<int> q = {1, 2, 3, 4, 5}; // X

• initializer_list 생성자를 사용하고 싶다면, 기본 컨테이너를 initializer_list로 초기화 한 다음, 해당 컨테이너를 넘겨줘야 한다.

deque<int> dq = {1, 2, 3, 4, 5};
queue<int> q(dq);

queue<int> q({1, 2, 3, 4, 5}); // 이것도 가능

 

clear() 없음

• 컨테이너 어뎁터에서 clear가 없으므로, 아래와 같이 빈 컨테이너를 저장하는 방식을 사용해야 한다.

queue<int> q({1, 2, 3, 4, 5}); 
q = queue<int>(); // 빈 큐를 저장한다.

 

반복자(iterator)를 제공하지 않음

• 컨테이너 어뎁터는 앞 / 뒤로만 접근하는 것이 적절하기 때문에 순차접근이 가능한 반복자를 제공하지 않는다.
• 따라서, begin(), end() 멤버 함수를 제공하지 않으며, 반복자 raged for based for문 또한 사용할 수 없다.

---

스택(stack)이란?

스택 예시

• stack은 나중에 들어온 원소(데이터)가 먼저 나가는 LIFO 구조인 자료 구조이다.
• deque를 기반 컨테이너로 사용하지만, 원하면 vector로 변경할 수 있다.

 

스택 멤버함수

 

원소 접근 관련(Element access)

top	맨 앞 원소에 접근(가장 최근에 들어온 원소)

 

 

수정 관련(Modifiers)

push()	맨 앞에 원소 삽입
pop()	맨 앞에 원소 삭제
emplace()	맨 앞에 원소 삽입(push()와 유사. 사용 추천 X)
swap()	지정한 stack과 swap한다.

 

 

크기 관련(Capacity)

empty()	stack의 size가 0인지 확인한다.(bool 타입 반환)
size()	stack의 크기(원소의 개수) 반환

 

 

자세한 내용은 아래 참고

https://en.cppreference.com/w/cpp/container/stack

std::stack - cppreference.com

 

---

큐(queue)란?

큐 예시

• queue는 먼저 들어온 원소(데이터)가 먼저 나가는 FIFO 구조인 자료 구조이다.
• deque를 기반 컨테이너로 사용하지만, 원하면 list로 변경할 수 있다.

 

큐 멤버함수

 

 

원소 접근 관련(Element access)

front()	맨 앞 원소에 접근 (가장 나중에 들어온 원소)
back()	맨 뒤 원소에 접근 (가장 최근에 들어온 원소)

 

 

수정 관련(Modifiers)

push()	맨 뒤에 원소 삽입
pop()	맨 앞에 원소 삭제
emplace()	맨 뒤에 원소 삽입(push()와 유사. 사용 추천 X)
swap()	지정한 queue와 swap한다.

 

 

크기 관련(Capacity)

empty()	queue의 size가 0인지 확인한다.(bool 타입 반환)
size()	queue의 크기(원소의 개수) 반환

 

 

자세한 내용은 아래 참고

https://en.cppreference.com/w/cpp/container/queue

std::queue - cppreference.com

 

---

우선순위 큐(priority_queue)란?

우선순위 큐 예시

• 우선순위 큐는 각 원소가 우선순위를 가지고 있으며, 우선순위가 높은 원소가 먼저 처리되는 큐이다.
• 우선순위 큐는 vector를 기반 컨테이너로 사용하지만, 원하면 deque를 기반 컨테이너로 변경할 수 있다.
• 내부 구조로 힙을 “활용”하고 있으며(힙에 대한 자세한 내용은 여기 참고), 우선순위 큐는 아래와 같은 특성을 가진다.
  • 원소의 검색(top())은 O(1)의 시간복잡도를 가진다.
  • 원소의 삽입(push()) / 삭제(pop())는 O(logN)의 시간복잡도를 가진다.
  • 원소들은 정렬되어 있지 않지만, 우선순위가 존재한다. (우선순위 기준의 기본값은 less <_Key>로, 낮은(less) 값이 우선순위가 낮다.)
• 다른 컨테이너 어뎁터와 다르게, 내부 컨테이너 타입을 넘겨주는 방식으로 초기화할 수 없다. 대신 아래와 같이 반복자를 넘겨주는 방법은 가능하다.

std::priority_queue<int, std::vector<int>> pq(v1.begin(), v1.end());

 

우선순위 큐 멤버함수

 

원소 접근 관련(Element access)

top	맨 앞 원소에 접근(가장 우선순위가 높은 원소에 접근)

 

 

수정 관련(Modifiers)

push()	원소 삽입
pop()	맨 앞 원소 삭제
emplace()	원소 삽입(push()와 유사. 사용 추천 X)
swap()	지정한 priority_queue와 swap한다.

 

 

크기 관련(Capacity)

empty()	priority_queue의 size가 0인지 확인한다.(bool 타입 반환)
size()	priority_queue의 크기(원소의 개수) 반환

 

 

자세한 내용은 아래 참고

https://en.cppreference.com/w/cpp/container/priority_queue

std::priority_queue - cppreference.com

 

알아두어야 할 점

비교 함수 만들기

• less <>, greater <>와 같은 함수 객체를 이용한 비교함수가 있지만, 제공되는 비교함수 중 적합한 비교함수가 없다면 사용자가 직접 비교 함수를 만들어야 한다. 비교 함수를 만드는 방법은 많지만 대표적으로 아래 2 가지 방법이 있다.
  • 구조체 내부에 operator < 오버로딩
  • functor를 세 번째 템플릿 인자로 넘겨주기
• 주의해야 할 점은 우선순위 큐에서 비교 함수는 리턴 값이 true일 때 해당 원소를 낮은 우선순위로 판단한다는 것이다. 따라서 생각하는 것과 반대로 less <> 면 가장 높은 값이, greater <>이면 가장 낮은 값이 맨 앞으로 올라온다. (가장 우선순위가 높은 값이 위로 올라온다.) 이 때문에 비교 함수를 만든다면 항상 반대로 생각해야 한다.
• 예를 들어, 10 > 9 > 8과 같은 순서로 우선순위를 정했다면 a < b로, 1 < 2 < 3과 같은 순서로 우선순위를 정했다면 a > b로 정의해야 한다.

비교 함수 정의 방법 1. 구조체 내부에 operator < 오버로딩

struct Pair{
    pair<int, int> p; // (오름차, 내림차)
    bool operator<(const Pair& t) const {
        if (p.first == t.p.first) {
            return p.second < t.p.second; // "높은 값"이 위로 (내림차)
        }
        return p.first > t.p.first; // "낮은 값"이 위로 (오름차)
    }
};

int main(void){
    priority_queue<Pair> pq;

    pq.push(make_pair(3, 10));
    pq.push(make_pair(1, 5));
    pq.push(make_pair(3, 7));
    pq.push(make_pair(2, 8));
  
    while (!pq.empty()) {
      cout << "(" << pq.top().p.first << ", " << pq.top().p.second << ") ";
      pq.pop();
    }
  
    // 실행 결과
    // (1, 5) (2, 8) (3, 10) (3, 7) 
}

 

 

비교 함수 정의 방법 2. functor를 세 번째 템플릿 인자로 넘겨주기

struct cmp {
    bool operator()(const pair<int, int>& p1, const pair<int, int>& p2) {
        if (p1.first == p2.first) {
            return p1.second < p2.second; // "높은 값"이 위로
        }
        return p1.first > p2.first; // "낮은 값"이 위로
    }
};

int main(void){
    priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq; // (오름차, 내림차)
    
    pq.push(make_pair(3, 10));
    pq.push(make_pair(1, 5));
    pq.push(make_pair(3, 7));
    pq.push(make_pair(2, 8));
    
    while (!pq.empty()) {
        cout << "(" << pq.top().first << ", " << pq.top().second << ") ";
        pq.pop();
    }
    
    // 실행 결과
    // (1, 5) (2, 8) (3, 10) (3, 7) 
}

 

 

비교 함수에 대한 더 자세한 내용은 아래 참고

https://blog.naver.com/jinhan814/222406827641

[PS 팁] 우선순위 큐에서 비교함수 쓰기

 

---

참고 자료

https://en.cppreference.com/w/cpp/container/queue

https://en.cppreference.com/w/cpp/container/priority_queue

https://blog.naver.com/jinhan814/222406827641

https://covenant.tistory.com/224