priority_queue, set의 정렬 기준 커스텀하기

2022년 1월 16일
dohoon
댓글 (6개)
C++, sort, priority_queue, set, compare

priority_queue, set은 비교 조건에 sort 함수 등과는 다르게 함수 객체만 사용할 수 있습니다.

따라서 set<int,[](int x,int y)->bool{return x<y;}> s;와 같은 구문은 실행되지 않습니다. 혹은, 함수 cmp에 대해서 set<int,cmp> s;도 실행되지 않습니다.

이를 해결하기 위해서 일반적으로 새 구조체를 작성하는데, 그럴 경우에 다양한 정렬기준에 대해서 전부 구조체를 작성해야 하므로 번거롭습니다. 하지만 다음과 같이 구현하면 별다른 구조체 없이도 제대로 동작하게 됩니다.

함수와 함수 포인터를 이용한 구현

bool cmp(int x, int y) {
    ...
}
int main() {
    set<int,bool(*)(int,int)> s(cmp);
    priority_queue<int,vector<int>,bool(*)(int,int)> pq(cmp);
}

1번에다가 decltype을 이용한 구현

bool cmp(int x, int y) {
    ...
}
int main() {
    set<int,decltype(&cmp)> s(cmp);
    priority_queue<int,vector<int>,decltype(&cmp)> pq(cmp);
}

람다를 이용한 구현

int main() {
    auto cmp = [](int x, int y) {
            ...
    };
    set<int,bool(*)(int,int)> s(cmp);
    priority_queue<int,vector<int>,bool(*)(int,int)> pq(cmp);
}

3번에다가 decltype를 이용한 구현(C++20 이상부터 지원됨)

int main() {
    auto cmp = [](int x, int y) {
            ...
    };
    set<int,decltype(cmp)> s;
    priority_queue<int,vector<int>,decltype(cmp)> pq;
}

decltype를 소개해주신 palilo님과 jinhan814님께 감사드립니다.

예제

문제 추천 받습니다.

Integers Shop

댓글 (6개) 댓글 쓰기

palilo 2년 전

bool(*)(int,int)은 굉장히 치기 귀찮은 코드입니다.

decltype(cmp)으로 쓰면 더 범용적이고 가독성이 좋습니다.

c++20에서는 뒤의 (cmp)를 뺴고 아래처럼 작성할 수 있습니다.

priority_queue<int, vector<int>, decltype(cmp)> pq;
set<int, decltype(cmp)> s;

dohoon 2년 전

감사합니다! 그런데 혹시 적어주신 코드로 풀은 문제가 있으신가요..? 제가 적어주신 코드로 C++20 환경에서 실행해봤지만 CE가 뜨네요... https://www.acmicpc.net/ceinfo/37642817

palilo 2년 전

앗 람다는 되는 데 함수일 땐 안되네요. 맨날 람다만 써서 몰랐어요.

람다는 잘 컴파일 됩니다.

http://boj.kr/2c4104e69df84e23adf469f722303494

dohoon 2년 전

와 정말 되네요? 감사합니다!

jinhan814 2년 전

전역 함수는 decltype(&Cmp)로 함수 포인터를 넣어주면 동작해요.

(코드 : http://boj.kr/8b2cac25c4a24ab387c1b63fb98c65d6)

template<class type, class container = vector<type>, class cmp = less<typename type>>
class priority_queue {
public:
    priority_queue() = default;
    explicit priority_queue(const cmp& comp) : c(), comp(comp) {}

   ...

private:
    container c{};
    cmp comp{};
};

priority_queue 내부 구조를 보면 템플릿 인자로 받은 cmp 자료형으로 선언된 comp를 비교 함수 객체로 사용합니다.

그래서 decltype(Cmp)로 템플릿 인자를 넣어주면 함수 자체를 생성자에서 대입할 수가 없어서 컴파일 에러를 받고, 함수 포인터를 대입해주는 방식으로 처리하면 돼요.

추가로 람다식이나 함수 포인터처럼 자료형만으로는 () 연산자의 정의를 유추할 수 없는 경우는 매개 변수로 비교 함수 객체를 넘겨줘야 합니다 ㅎㅎ

szszszs2 1년 전

감사합니다.

검색

목록보기

문제

문제

출처

ICPC