티스토리 뷰

공부

STL priority queue 활용법

구사과 2014. 9. 13. 18:41

모든 nlgn들의 영웅(?) 같은 priority_queue

존재 그 자체로 멋지지만 정말 멋지게 쓰기 위해서는 제대로 활용할 줄 알아야 할 것이다.


1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <cstdio>
#include <queue>
using namespace std;
 
priority_queue<int> pq;
 
int main(){
    pq.push(3);
    pq.push(1);
    pq.push(4);
    pq.push(1);
    pq.push(5);
    pq.push(9);
    while (!pq.empty()) {
        printf("%d",pq.top());
        pq.pop();
    }
}

출력 결과는 954311 이다.


2.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <cstdio>
#include <queue>
using namespace std;
 
priority_queue<int,vector<int>,less<int> > pq;
 
int main(){
    pq.push(3);
    pq.push(1);
    pq.push(4);
    pq.push(1);
    pq.push(5);
    pq.push(9);
    while (!pq.empty()) {
        printf("%d",pq.top());
        pq.pop();
    }
}

아까와 완전히 동일한 코드이다.

우선순위 큐는 실제로는 priority_queue<자료형, 구현체, 비교 연산자>로 정의하는 것을 알 수 있다.

 * 자료형은 int, double, 선언한 클래스 등등..

 * 구현체는 기본적으로 vector<자료형>으로 정의된다. 이말인 즉슨 우리가 쓰는 priority_queue가 실제로는 vector 위에서 돌아가고 있다는 것이다. vector가 아니더라도 deque<자료형> 등을 넣어도 잘 돌아간다. stl에서 힙을 구현하기에 충분한 자료구조면 다 된다. (random access iterator가 지원되어야 할듯) 근데 굳이 데큐 쓸 이유는 없을 거 같으니 기본값인 vector로 쓰자. 숏코더라면 그냥 priority queue를 쓰지 말자 참고로, 굳이 vector나 deque를 include하지 않아도 잘 돌아간다.

 * 비교 연산자는 기본적으로 less<자료형>으로 정의된다. 저건 stl에서 기본으로 제공하는 비교 연산자 클래스인데 이걸 넣으면 큰 놈부터 나온다. greater<자료형>을 넣으면 작은 놈부터 나오며 출력 결과는 113459가 된다.

이때부턴 std::을 일일히 붙이면 가독성이 많이 떨어지니. using namespace std를 쓰자.

또한, less<int>> 식으로 하면 일부 컴파일러는 이를 비트 연산으로 오해한다고 한다. xcode llvm은 잘 해주는 거 같은데 어쨌든 띄어쓰는 습관을 들이자.


3.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <cstdio>
#include <queue>
using namespace std;
 
struct a{
    int start;
    int end;
    int value;
};
 
bool operator<(a t, a u){
    return t.value < u.value;
}
 
priority_queue<a> pq;

위에서도 얘기했듯이 구조체나 클래스도 비교 연산자를 잘 설정했으면 잘 들어간다.

pair<int,int> 이런것도 물론 잘 들어간다. 얜 비교 연산자가 정의되어 있으니 더 좋다.

비교 연산자를 overloading하려면 < 연산자를 overloading하면 된다. > 연산자는 오버로딩해도 priority_queue가 인식을 못하는 걸로... 알고 있다. 아마.


이 소스는 value가 큰 놈부터 나오는 소스이다.

작은 놈부터 나오게 하려면 -

 * 1. operator< 구현체의 부호를 t.value > u.value로 바꾼다.

 * 2. priority_queue<a,vector<a>,greater<a> > 식으로 priority_queue를 정의한다.


등의 방법이 있다.


4.

less<int> greater<int> 등 만들어준 연산자 클래스를 쓸 수도 있는데 우리가 만들면 더 좋을 거 같다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <cstdio>
#include <queue>
using namespace std;
 
struct a{
    int start;
    int end;
    int value;
};
 
struct cmp{
    bool operator()(a t, a u){
        return t.value < u.value;
    }
};
 
priority_queue<a,vector<a>,cmp> pq;

cmp 클래스를 만들어서 연산자를 저렇게 만들고, priority_queue에 overload하면 저게 less<int> 구실을 대신 해준다.

여러 연산자를 필요할때마다 오버로딩할 수 있어서 유용한 테크닉이다.

'공부' 카테고리의 다른 글

트리의 지름 (Diameter of tree)  (3) 2014.11.01
KOI 2014 - 버스  (3) 2014.10.15
STL priority queue 활용법  (17) 2014.09.13
비트필드와 완전 탐색 최적화 (Bit DP)  (1) 2014.09.07
KOI 2013 - 전봇대  (1) 2014.08.30
서로소 집합 (Union-find tree. Disjoint - set)  (6) 2014.08.23
댓글
  • 프로필사진 chatterboy 와 정말 감사합니다. 좋은 글이에요 ㅠㅠ 2015.09.26 13:41
  • 프로필사진 bitbitter 정리 감사합니다 ~! 2016.01.25 22:57
  • 프로필사진 노기마기 잘 보고 배워갑니다 ㅎㅎ 2016.10.16 07:28
  • 프로필사진 박승원 으어어 bool operator를 미리 알았더라면 좋았을텐데 ㅠㅠ 여튼 감사합니다 2016.12.09 21:33
  • 프로필사진 ㅁㄴㅇㄹ 와 이렇게 핵심 적인 부분만 올려주시니깐 시간 절약이 엄청 납니다!
    다른 문서들은 메소드 정리만 해줄뿐이지 이렇게 사소한것 > 오버로딩은 안된다등 핵심많알려주셔서
    정말 감사합니다.
    2017.10.05 02:13
  • 프로필사진 코딩충 정리 감사합니다~! 좋은 글 굿! 2017.10.13 21:47 신고
  • 프로필사진 빅밴 사랑해요 2018.05.28 14:59
  • 프로필사진 IronTiger 감사합니다!!
    여기서 t와 u는 통상적으로 어떤 단어의 약자로 쓰는건가요?
    2019.02.15 21:05
  • 프로필사진 구사과 그냥 별 생각 없이 썼어요. 요즘은 x, y나 a, b로 쓸 것 같네요. 2019.02.18 16:32 신고
  • 프로필사진 네로렌 깔끔한 정리 감사합니다. 2019.03.19 02:29
  • 프로필사진 장환석 안녕하세요. SHAKE 2019에서 한 번 뵀습니다!

    질문 하나 드릴게요.

    struct cmp{
    bool operator()(a t, a u){
    return t.value < u.value;
    }
    };
    priority_queue<a,vector<a>,cmp> pq;


    위 처럼, operator() 오버로딩말고

    bool operator<(a t, a u){
    return a.value < u.balue;
    }
    priority_queue<a> pq;

    이런식으로 하면 성능에 차이가 있나요?
    2019.07.11 11:36
  • 프로필사진 구사과 잘 모르겠지만, 아마 차이가 없을 것이라고 생각합니다. 2019.07.17 21:47 신고
  • 프로필사진 dhp @장환석
    아래 링크를 참고하면 좋을 것 같습니다.
    https://www.google.com/search?q=c%2B%2B+priority+queue+overload&oq=c%2B%2B+priority_queue+over&aqs=chrome.1.69i57j0l5.10559j1j8&sourceid=chrome&ie=UTF-8
    2019.08.25 18:58
  • 프로필사진 장환석 감사합니다 도움이 됐습니다! 2019.09.06 13:52
  • 프로필사진 탱탱시 감사합니다!!! 잘 참고하고 갑니다. 2019.08.30 18:46
  • 프로필사진 질문잇어욤 안녕하세요 질문 한가지 드립니당... 대부분 priority_queue를 설명하는 글을 전부 봤는데도 답이 나오지 않아 이렇게 글을 써요 ㅠㅠ
    c++ stl을 사용해 priority_queue를 구현할 때 위 방법 모두 사용해봤는데 문제 없이 컴파일 되었습니다.
    다만, 이는 비교함수 cmp 또는 오버라이딩한 함수 operator< 가 int를 비교하는 경우만 컴파일이 되었고 다른 자료형 이를테면 double을
    비교하는 경우에는 컴파일 되지 않았습니다. ㅠㅠ 도저히 왜그런지 모르겠네요 원인을 알고 계신다면 답변 부탁드려요!!
    예시)
    class ex{
    public:
    int x;
    };
    bool operator<(ex a, ex b){return a.x < b.x;} // 정상적으로 컴파일 됨
    class ex{
    public:
    double x;
    };
    bool operator<(ex a, ex b){return a.x < b.x} // 컴파일 에러메시지 출력
    참고로 리눅스 환경에서 g++을 활용했습니다 감사해요ㅠㅠ
    2020.04.26 01:50
  • 프로필사진 구사과 세미콜론이 없는 것 말고는 문제가 없는 것 같습니다. 2020.05.07 22:46 신고
댓글쓰기 폼
공지사항
Total
638,014
Today
106
Yesterday
451