[STL] Sort,Queue,Priority_Queue

이번에는 STL의 sort, que, priority_que의 사용법에 대해서 정리해보겠습니다. 사용법은 무지 간단한데, 잊지 안기 위해..!!

Sort

---

sort는 STL중에 가장 많이 쓰는 것 같네요. 진짜 개꿀. 라이브러리는 algorithm입니다.

#include <algorithm>

sort의 사용법은 매우 간단합니다.

sort(정렬할 주소의 첫 번째 값, 정렬할 주소의 마지막 값, 정렬 기준);

정렬할 주소의 첫 번째 마지막 값은 잘 아실테니 넘어가겠습니다. 중요한건 정렬 기준입니다. 간단하게 less, greater가 있습니다.

• less<자료형>() : 이걸 넣을 경우엔 오름차순으로 정렬이 됩니다.
• greater<자료형>() : 이건 반대로 내림차순으로 정렬이 되죠.

물론 이것만 알아도 충분하지만, 스스로 정렬 기준을 정할 수 있습니다.

typedef struct sample{int a,b}SAMPLE;
SAMPLE arr[10] = {{1,9},{2,5},{3,7},{4,1},{5,2},{6,6},{7,3},{8,0},{9,1},{10,2}};

이렇게 배열이 있다고 합시다. 지금 a에 관해서 정렬이 되어 있긴 한데, 이걸 b에 대한 오름차순으로 정렬하고 싶어요.

bool cmp(SAMPLE x, SAMPLE y)
{
    if(x.b < y.b) return true;
    else          return false;
}
sort(arr,arr+10,cmp);

그러면 이렇게 bool 반환형 함수를 정렬 조건으로 사용할 수 있습니다. 정렬은 조건이 false인 경우 일어나게 되는데, 코드를 보면 바로 알겠죠?? 매우매우 유용한 sort였습니다.

 

Queue

---

queue는 BFS나 기타 탐색 알고리즘에서 자주 사용되죠. 라이브러리는 queue입니다.

#include <queue>

queue의 선언은 이렇게 합니다.

queue<자료형> 이름

자료형에는 여러분이 선언한 구조체가 들어갈 수도 있고, 그냥 int, char도 들어갈 수 있습니다. 이름은 여러분 마음데로~~ queue에서 가장 많이 사용되는건 역시 push, pop, empty겠죠.

que.push(넣을 거)
que.pop(), que.front()
que.empty -> true for empty

이렇게 정리할 수 있겠네요. queue에서 중요한 건 push, pop은 void형이라는 것입니다. 반환형이 아니에요. 그래서 pop을 할 적엔 front로 앞에 놈 먼저 불러오고 pop을 해줘야 합니다. queue는 이정도만 알아도 충분 하겠네요.

 

Priority Queue

---

다음은 priority queue입니다. 우선순위 큐죠. queue와 동일하게 queue라이브러리를 사용합니다. 우선순위 큐는 보통 가장 큰, 가장 작은값만 필요할 때 사용되죠. 제가 Dijkstra Algorithm을 설계할 때 사용했었죠. 선언은 이렇게 합니다.

priority_queue<자료형> 이름

pque.push(넣을 거)
pque.pop(), pque.top()
pque.empty -> true for empty

queue와 다른건 맨 앞의 값이 front가 아닌 top이라는 것이겠네요. 우선순위 큐는 기본적으로 내림차순(less) 정렬을 합니다. 그럼 오름차순은 어떻게 할까요?? 이건 위의 sort처럼 greater,less를 사용합니다.

priority_queue<자료형,vector<자료형>,less<자료형>> 이름; // 내림차순
priority_queue<자료형,vector<자료형>,greater<자료형>> 이름; // 오름차순

물론 우선순위 큐도 정렬 기준을 정할 수 있습니다. sort와 비슷하면서도 다르게 정하는데, sort는 정렬 함수를 그냥 설계하면 되지만, priority_queue의 경우는 overloading을 통해서 정렬 기준을 정합니다.

struct cmp
{
	bool opeartor()(자료형 x, 자료형 y)
	{
		sort와 동일
	}
}
priority_queue<자료형,vector<자료형>,cmp>> 이름;

이렇게 사용하면 아까 위에서 처럼 정렬 기준을 설정할 수 있습니다.

 

---

한 가지 유용한 팁이 있습니다. 물론 많은 분들이 알고 있겠지만, swap이라는 함수가 있습니다. 이를 통해서 쉽게 queue를 비울 수 있습니다. 예를 들어서 priority_queue를 비운다고 하면 이렇게 할 수 있어요.

priority_queue<비울 큐와 동일한 조건> empty;
swap(비울 친구, empty);

사실 비우는게 아니라 바꿔치기에 가깝지만 알고 있으면 유용합니다!! 다른 배열들도 가능하니까요.ㅎㅎ 그럼 이만~~~