인프런 커뮤니티 질문&답변
작성한 질문수
operator< ???
작성
·
518
0
우선순위 큐에서의 구조체
struct Edge{
int e;
int val;
Edge(int a, int b){
e=a;
val=b;
}
bool operator<(const Edge &b)const{ //
return val>b.val;
}
};
벡터를 sort 하기 위한 목적의 구조체
struct Edge{
int s;
int e;
int val;
Edge(int a, int b, int c){
s=a;
e=b;
val=c;
}
bool operator<(Edge &b){
return val<b.val;
}
};
선생님 구조체 안의 bool operator라는 함수를 쓰는것은 처음봐서 저것이 어떻게 동작할수 있는지 이해가 잘 가지 않습니다.
1.이것에 대해 이해하려면 어떤 것을 공부 해야하는지요
2. 둘다 최소 cost를 찾기 위해 정렬하는 것인데
벡터에서는 operator< 가
return val<b.val;의 결과를 반환 해야하고
우선순위 큐에서는 operator< 안의 내용이 왜
return val>b.val;의 결과를 반환 해야하는지요?
답변 1
6
두 객체의 대소비교를 위해 bool operator< 같이 사용하는 것을 연산자 오버로딩이라고 합니다.
저도 STL의 sort 함수가 내부적으로 어떻게 연산자 오버로딩을 하고 있는지 모릅니다. 많은 STL책을 봤지만 그런 내용은 없더라구요. 그래서 그냥 저 나름대로 아래와 같이 기준을 잡고 외워서 메뉴얼처럼 사용하고 있습니다.
▣ 구조체형의 벡터를 잡고 sort()함수를 사용할 때
벡터는 선형자료구조입니다.
sort()함수는 선형 자료구조를 오름차순 또는 내림차순으로 일렬로 나열할 때 사용하는 함수입니다.
구조체형의 벡터를 정렬할 때 sort()함수를 쓴다면
bool operator<( Edge &b){
return val > b.val;
}
operator 함수의 return val > b.val;에서 val은 함수를 호출한 객체의 값으로 일렬로 나열할 때 앞에 자료, b.val은 함수를 호출할 때 인자가 되는 객체의 값으로 일렬로 나열할 때 뒤에 자료로 생각하고 기준을 잡으시면 됩니다.
return val > b.val; 은 "앞에 자료가 크고 뒤에 자료가 작은 형태로 정렬하라" 이렇게 생각하면
내림차순으로 정렬됩니다.
반면 return val < b.val; 은 "앞에 자료가 작고 뒤에 자료가 크게 정렬하라" 라고 생각하면 오름차순 정렬입니다.
▣ priority_queue에 구조체를 사용할 때
우선순위 큐는 선형자료구조가 아니라 이진트리 자료구조입니다.
우선순위 큐에서 구조체의 operator함수가 작동할 때는 push()나 pop()이 사용될 때 입니다.
즉 우선순위 큐라는 자료구조에 자료를 넣거나 꺼낼 때 operator 함수가 작동하여 최대힙을 만들거나
최소힙을 만든다고 생각하시면 됩니다.
push()됬을 때와 pop()됬을 때 최대힙을 유지하는 과정은 73번 영상에 있습니다.
bool operator<( Edge &b){
return val > b.val; //최소힙
}
에서 매개변수로 넘어온 b.val 값이 기준값이 되어 이 값이 호출객체의 값인 val보다 작으면 최소힙, val보다 크면 최대힙이 된다고 생각하고 사용하면 좋겠습니다.
bool operator<( Edge &b){
return val < b.val; //최대힙
}