https://en.cppreference.com/w/cpp/container/priority_queue
stack이 후입선출, queue가 선입선출로 데이터를 관리하고, priority_queue는 우선순위를 정하여 해당 우선순위에 맞게 데이터를 관리한다.
기본적으로는 std::less<type>, 즉 값이 작아지도록 정렬되게(내림차순) 지정되어 있으며, 이 우선 순위를 원하는 데로 조종 가능하다.
1. 기본 priority queue.
#include <iostream>
#include <queue>
using namespace std;
int main() {
priority_queue <int> pq;
pq.push(4);
pq.push(7);
pq.push(7);
pq.push(1);
cout << "------------------" << endl;
for (; pq.empty() == false; pq.pop()) {
auto data = pq.top();
cout << data << endl;
}
cout << "-------------------";
return 0;
}
2. std 지원 기능을 가지고 우선순위 변경
#include <iostream>
#include <queue>
using namespace std;
int main() {
priority_queue <int, vector<int>, greater<int>> pq;
pq.push(4);
pq.push(7);
pq.push(7);
pq.push(1);
cout << "------------------" << endl;
for (; pq.empty() == false; pq.pop()) {
auto data = pq.top();
cout << data << endl;
}
cout << "-------------------";
return 0;
}
이렇게 priority_queue를 생성 할 때 마지막 template class에 greater / less를 지정함으로써 내림차순으로 되어 있는 priority_queue를 오름차순으로 변경 가능하다.
중간에 vector는 해당 queue를 어떤 container에서 보관할거냐 물어보는 건데..
https://en.cppreference.com/w/cpp/named_req/SequenceContainer
이 기준을 만족, 즉 위에서 정의해 둔 함수를 모두 가지고 있는 container가 오면 된다고 한다.
다만, 걍 무지성으로 vector 써도 큰 문제는 없을 듯 하다.
3. 원하는 데이터를 넣고, 원하는 방식으로 우선순위 변경
#include <iostream>
#include <queue>
using namespace std;
class myClass {
public:
int data_x;
int data_y;
myClass(int x, int y) : data_x(x), data_y(y) {}
};
int main() {
auto cmpFunc = [](myClass A, myClass B) {
if (A.data_x < B.data_x) return true;
else if (A.data_x == B.data_x && A.data_y < B.data_y) return true;
else return false;
};
priority_queue <myClass, vector<myClass>, decltype(cmpFunc)> pq(cmpFunc);
pq.push(myClass(4,1));
pq.push(myClass(7,2));
pq.push(myClass(7,6));
pq.push(myClass(1,3));
cout << "------------------" << endl;
for (; pq.empty() == false; pq.pop()) {
auto data = pq.top();
cout << data.data_x << ' ' << data.data_y << ' ' << endl;
}
cout << "\n-------------------";
return 0;
}
결국 이 형태를 많이 쓰게 되지 않을까 싶다.
실제 코딩테스트에서도 x,y 좌표를 가지고 정렬해야 할 일이 생긴다거나, 두 개의 값을 이렇게 저렇게 비교하여 줄을 세워야 할 경우가 많을 것이다.
auto cmpFunc = [](myClass A, myClass B) {
if (A.data_x < B.data_x) return true;
else if (A.data_x == B.data_x && A.data_y < B.data_y) return true;
else return false;
};
priority_queue <myClass, vector<myClass>, decltype(cmpFunc)> pq(cmpFunc);
결국 '어떤 기준으로 줄을 세울까' 를 결정하는 함수를 정하는게 제일 중요하다.
여기선 람다 함수를 이용하여 해당 compare function을 정해 주었다.
그리고 compare function 만들 때 아래의 두 가지를 지켜서 만들어주자.
1. 같은 data type으로 두 개의 parameter를 받는다.
2. bool 형태의 return 값을 가져야 한다.
1번 조건은, priority_queue 내부에서 [두 개의 elem을 비교] 하여 줄 세울 때 사용되고
2번 조건은, priority_queue 내부에서 두 개의 elem을 [비교 하여 줄 세울 때] 사용된다.
A, B 이렇게 두 개를 비교할 때,
return true이면 A와 B의 자리를 바꾸고,
return false이면 A와 B의 자리를 바꾸지 않는다.
이 부분을 생각하고 구현하면 쉽게 구현이 가능하다.
사실.. 헷갈리면 그냥 구현 해 보고, 한번 출력하면 맘 편하게 확인 가능하긴 하다.
반대면 부등호 변경하면 되지 뭘.
'C++ > STL' 카테고리의 다른 글
[C++] remove(remove_if) vs erase(erase_if) (0) | 2023.07.11 |
---|---|
[C++20] Span (1) | 2023.07.04 |
[C++17] Optional (0) | 2023.05.28 |
[C++20] Concepts (1) | 2023.05.23 |
[C++] std::async. launch policy (0) | 2023.04.20 |