C++ vector, priority_queue 정렬 정리

C++의 STL에는 vector와 queue 등 아주 좋은 친구들이 많다.

그 중 PS 에서 많이 쓰는 vector와 priority_queue 의 정렬 기능에 대해 정리하고자 한다.

 

1. vector

algorithm STL 을 이용해 sort 함수로 vector를 쉽게 정렬할 수 있다. (단순 배열도 가능)

sort(vec.begin(), vec.end()) 가 기본 사용법이며, vec의 처음부터 끝까지를 기본적으로 오름차순으로 정렬한다. 

역순 정렬을 하고자 하면 sort(vec.rbegin(), vec.rend()) 와 같이 사용 가능하다. 

 

하지만 이는 int, float, pair<int, int> 등 기본 타입에만 적용이 된다. 

따라서 operator 가 정의되지 않은 데이터 타입 (struct 로 직접 만든 데이터 타입 등) 은 operator를 직접 만들어 주어야 한다. 

 

만드는 방법은 간단하다.

bool compare(const &DATA d1, const &DATA d2) {...} 와 같이 ... 에 비교하고자 하는 내용을 작성 후, 

sort(vec.begin(), vec.end(), compare) 와 같이 사용하면 된다. 

이 때 ... 에 들어가는 내용은 sort가 기본적으로 오름차순이므로 

예를 들어 DATA {int n, int m} 으로 정의되어 있고, n 을 먼저 오름차순, m 을 오름차순 으로 정렬하고자 한다면

if(d1.n == d2.n) return d1.m < d2.m; else return d1.n < d2.n 으로 정의하면 된다. 

(자세한 예시는 아래 쪽에)

 

2. priority_queue

priority_queue 는 기본적으로 내림차순으로 동작하는 최대 힙으로 구성되어 있다.

즉, int 등 기본 타입에 대해 pop 한다면 가장 큰 값부터 pop이 된다. 

오름차순을 원한다면, 기본타입의 경우, pq 선언 시, 

priority_queue<T, vector<T>, greater<T>> 와 같이 greater 옵션을 줄 수 있다.

 

하지만 위와 같이 직접 만든 struct 등에 대해서는 compare struct를 구성해주어야 한다. 

sort와의 차이로는 sort의 경우, compare가 함수이지만, 여기서는 struct로 구성 후, 그 내부에 operator() 를 짜주어야 한다. 

 

기본구조가 sort는 오름차순, pq는 내림차순이므로 x < y 가 true 일 때, sort는 x1 < x2 < x3 < ... 와 같이 구성되고, 왼쪽이 first 값, pq는 오른쪽이 top으로 생각하면 된다.  

 

구체적인 예시는 다음과 같다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct edge {
	int node1;
	int node2;
	int weight;
};

bool compare_vec(const edge &e1, const edge &e2)
{
	// 정렬 기준 : weight, node1, node2
	// vec은 기본적으로 오름차순 
	if(e1.weight == e2.weight) {
		if(e1.node1 == e2.node1) {
			return e1.node2 < e2.node2;
		}
		return e1.node1 < e2.node1;
	} 
	return e1.weight < e2.weight;
}

struct compare_pq{
	// pq 는 기본적으로 내림차순 
	// 정렬 기준 : weight, node1, node2 
	bool operator()(const edge &e1, const edge &e2) {
		if(e1.weight == e2.weight) {
			if(e1.node1 == e2.node1)
				return e1.node2 < e2.node2;
			return e1.node1 < e2.node2;
		}
		return e1.weight < e2.weight;
	}
};

int main()
{
	edge e1 = {1,2,3};
	edge e2 = {1,3,1};
	edge e3 = {2,3,0};
	edge e4 = {1,2,2};
	edge e5 = {3,2,1};
	edge e6 = {3,1,2};
	
	vector<edge> vec;
	vec.push_back(e1);
	vec.push_back(e2);
	vec.push_back(e3);
	vec.push_back(e4);
	vec.push_back(e5);
	vec.push_back(e6);
	
	sort(vec.begin(), vec.end(), compare_vec);
	
	cout << "vector sort\n";
	for(auto v : vec) {
		cout << v.node1 << " " << v.node2 << " " << v.weight << "\n";
	}
	cout << "\n===========\n";
	
	vec.clear();
	vec.push_back(e1);
	vec.push_back(e2);
	vec.push_back(e3);
	vec.push_back(e4);
	vec.push_back(e5);
	vec.push_back(e6);
	
	// 역순 정렬 
	sort(vec.rbegin(), vec.rend(), compare_vec);
	
	cout << "vector reverse sort\n";
	for(auto v : vec) {
		cout << v.node1 << " " << v.node2 << " " << v.weight << "\n";
	}
	cout << "\n===========\n";
	
	priority_queue<edge, vector<edge>, compare_pq> pq;
	pq.push(e1);
	pq.push(e2);
	pq.push(e3);
	pq.push(e4);
	pq.push(e5);
	pq.push(e6);
	
	cout << "priority queue\n";
	while(!pq.empty()) {
		edge e = pq.top();
		pq.pop();
		
		cout << e.node1 << " " << e.node2 << " " << e.weight << "\n";
	}
	cout << "\n===========\n";
}