0. Strict Weak Ordering

• C++의 set, map, sort 등은 모두 Strict Weak Ordering이라는 규칙을 따름

• 이 규칙은 같은 값끼리 비교했을 때 false를 반환해야한다는 규칙

bool comp(const int& a, const int& b)	// 같은 값 들어왔을 때
{
	// return a <= b;	// true 반환하므로 안 됨
	return a < b;		// false 반환
}

• 만약 true가 나온다면, 어떤 원소가 앞에 있어야하는지 혼동 오며 무한루프에 빠지거나 메모리 범위를 벗어날 수 있음

• 따라서 같은 원소인 경우에는 false를 반환해야 같은 원소임을 인지하고 다음 단계로 넘어감

• 그래서 보통 정렬함수 정의할 때 < 나 >만 사용

1. std::sort

• #include <algorithm>의 sort함수를 통해 정렬하는 방법

• 보통 정렬방법으론 비교함수를 선언/정의하여 사용

bool comp(const int& a, const int& b)
{
	return a < b;
}

sort(vec.begin(), vec.end(), comp);

• a < b는 오름차순 정렬 / a > b는 내림차순 정렬 (옳은 정렬순서가 참을 반환한다고 생각하기)

2. set / map

• set, map같은 자료형은 크게 2가지 방식이 있음

• 그 외에 함수 포인터방식, 람다 통한 방식도 있다

2.1. 함수객체

• 이전에 배운 함수객체를 이용하는 방법

• const를 꼭 사용해서 상수함수로 만들어야함

struct comp
{
	bool operator()(const Node& a, const Node& b) const
    {
    	return a.name < b.name;		// 오름차순
    }
};

set<Node, comp> s;
map<Node, int, comp> s;

• 마찬가지로, true를 반환하는 것이 옳은 정렬순서라 생각하면 편함(a < b는 오름차순)

• 이전 std::sort는 함수포인터였지만, set, map, priority_queue등의 자료형은 함수객체나 람다가 필요함

• 왜냐면, std::sort는 정렬을 한 번 딱 하면 되니까, 정렬함수를 찾는 과정에서 최적화가 딱히 필요하진 않음

• 그러나 해당 자료구조들은 데이터가 삽입/삭제가 일어날 때마다 정렬을 해야하므로, 정렬함수를 호출하는 것 자체가 최적화되어야함

• 정렬함수를 함수포인터로 받아 사용하는 것은 런타임에 불릴 함수를 찾는 과정이라 오래 걸리고, 함수객체로 받는다면 컴파일 타임에 인라인화 하여 최적화가능

2.2. 연산자 오버로딩 (<)

• 구조체나 클래스 내부에 규칙을 정의하는 법

struct Book 
{
    string title;
    int year;

    // 객체 내부에 비교 연산자를 직접 정의
    bool operator<(const Book& other) const 
    {
        if (year != other.year) return year < other.year;
        return title < other.title;
    }
};

set<Book> s; // 별도의 함수 객체 없이 작동

• 자료구조 설계 시 비교 구조체를 생략해도 됨

• 단점으론, 정렬 기준을 딱 하나만 정할 수 있다. (상황에 따라 오름차순, 내림차순을 바꾸기 어려움)

3. priority_queue

• set과 동일한데 정렬기준만 달라짐

• set은 true이면 올바른 정렬이지만, 우선순위큐는 true가 나오면 앞의 원소를 뒤로 보냄

struct comp
{
	bool operator()(const Node& a, const Node& b)
    {
    	return a.name < b.name;		// Max힙
    }
};

priority_queue<Node, vector<Node>, comp> pq;

4. less / greater

• 간단한 비교함수는 이미 표준 라이브러리에서 정의해둠

• less : 앞의 것이 뒤의 것보다 작은가 (a < b)?

• greater : 앞의 것이 뒤의 것보다 큰가 (a > b)?

대상	less<int>	greater<int>
의미	a < b 인가?	a > b 인가?
std::sort	오름차순 (1, 2, 3)	내림차순 (3, 2, 1)
std::set	오름차순 (1, 2, 3)	내림차순 (3, 2, 1)
priority_queue	최대 힙 (큰 게 top)	최소 힙 (작은 게 top)

// less 
sort(v.begin(), v.end(), less<int>()); // 함수 객체이므로 객체 생성해서 넘겨줘야함
set<int, less<int>> s;                 
priority_queue<int, vector<int>, less<int>> pq; 	// Max Heap (큰 게 위로)

// greater
sort(v.begin(), v.end(), greater<int>()); 		// 내림차순 정렬됨
set<int, greater<int>> s;                 
priority_queue<int, vector<int>, greater<int>> pq; // Min Heap (작은 게 위로)

• 다른 구조체도 operator<만 오버로딩 되어 있다면 less<T>나 greater<T>를 사용 가능

struct Book 
{
	string title;
	int year;

    bool operator<(const Book& other) const {
        if (year != other.year) return year < other.year;
        return title < other.title;
    }
};

set<Book, greater<Book>> Library;