리눅스타일

Sort()의 기본적인 형태

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

bool comp(int a, int b) {
	return a > b;
}

int main() {

    vector<int> v = {5, 2, 1, 4, 3, 0};

    // default : 오름차순
	sort(v.begin(), v.end());
    for (int i = 0; i < v.size(); ++i)
    	printf("%d ", v[i]);
    printf("\n");

    // 내림차순
    sort(v.begin(), v.end(), comp);
    for (int i = 0; i < v.size(); ++i)
    	printf("%d ", v[i]);
    printf("\n");

    return 0;
}
/*
실행결과
0 1 2 3 4 5
5 4 3 2 1 0
*/

이전 포스팅에서 살펴본 Priority Queue의 Compare와 반대이다.

즉, comp(a, b)에서 true를 반환할 때의 a가 "strong" order가 되어 우선순위가 높다고 생각하면 될 것 같다.

Ref.

https://www.cplusplus.com/reference/algorithm/sort/

우선순위 큐의 기본적인 사용 형태

// Max heap
priority_queue<int> pq;
priority_queue<int, vector<int>, less<int>> pq;

// Min heap
priority_queue<int, vector<int>, greater<int>> pq;

pq의 3번째 인자인 Compare은

comp(a, b) 가 true를 반환하면, a 가 "weak" order이라는 의미이다.

comp(a, b)의 default 인 less<T>를 살펴보면,

(a < b) 인 경우 true를 반환하므로 a가 "weak" order이 되고 결과적으로 pq는 Max heap이 된다.

구조체와 비교연산자를 정의하여 우선순위 큐의 우선순위를 결정

#include <cstdio>
#include <queue>
using namespace std;

struct s {
	int num;
	char ch;

	// constructor
	s(int _num, char _ch) : num(_num), ch(_ch) {}

	// 방법 1. pq의 default 비교연산자인 less<T>를 사용하는 경우
	bool operator < (const s s2) const {
		if (this->num == s2.num)
			return this->ch < s2.ch;
		else
			return this->num > s2.num;
	}
};

// 방법 2. 새로운 cmp를 정의하는 경우
// 1.num에 대해서 오름차순
// 2.ch에 대해서 내림차순
struct cmp {
	bool operator() (s s1, s s2) {
		if (s1.num == s2.num)
			return s1.ch < s2.ch;
		else
			return s1.num > s2.num;
	}
};

int main() {

	// 방법 1, 2 모두 같은 결과
	priority_queue<s> pq;
	// priority_queue<s, vector<s>, cmp> pq;

	pq.push(s(1, 'a'));
	pq.push(s(1, 'b'));
	pq.push(s(2, 'a'));
	pq.push(s(2, 'b'));
	pq.push(s(3, 'a'));
	pq.push(s(4, 'b'));

	while (!pq.empty()) {
		s cur = pq.top(); pq.pop();
		printf("%d %c\n", cur.num, cur.ch);
	}

	return 0;
}

	/*
	실행 결과
	1 b
	1 a
	2 b
	2 a
	3 a
	4 b
	*/

Ref. http://www.cplusplus.com/reference/queue/priority_queue/