[C++ STL] custom comp 구조체

[어떤 STL을 사용하는지에 따라 return true의 의미가 다르고 구조체/함수 구현해야하는게 다르다]

 

1. priority_queue

struct pq_comp
{
    bool operator()(pair<char, int>& obj1, pair<char, int>& obj2)
    {
        return obj1.second < obj2.second;
    }
};

priority_queue<pair<char, int>, vector<pair<char, int>>, pq_comp> pq;

 

struct comp 구조체 사용 + 내부에 bool operator( ) 정의

return true인게 우선순위가 더 낮음

 

2. set

struct comp 구조체 + 내부에 bool operator( ) 정의 

return true인게 우선순위가 더 높음

 

3. sort (vector에 사용 시)

bool custom_sort(pair<int, int> a, pair<int, int> b) {
	// first가 같으면 second 기준 내림차순
    if (a.first == b.first) {
    	return a.second > b.second;
    }
    // first 기준 오름차순
    return a.first < b.first;
}

vector<int> v;

sort(v.begin(), v.end(), custom_sort);

 

bool comp 함수만 정의 + sort의 세번째 인자로 전달

return true인게 우선순위가 더 높음

 

---

[커스텀 정렬기준 구조체]

struct set_comp {
    bool operator()(const string &s1, const string &s2) const {
        // 글자수가 같으면 사전순
        if (s1.size() == s2.size()) {
            return s1 < s2;
        }
        // 글자수 다르면 짧은순
        return s1.size() < s2.size();
    }
};

struct pq_comp {

	bool operator()(pair<int, int> obj1, pair<int, int> obj2) {
		if (obj1.first == obj2.first) {
        		// 내림차순 정렬
			return obj1.second > obj2.second;
		}
        	// 오름차순 정렬
		return obj1.first < obj2.first;
	}
    
};

struct pq_comp
{
    bool operator()(pair<char, int> obj1, pair<char, int> obj2)
    {
        return obj1.second < obj2.second;
    }
};

 

---

[인자로 참조자& 를 무조건 쓰자]

 

set에 쓰는 comp의 매개변수를 참조자 &로 두냐 안두냐에 따라 시간이 두배 차이가 나서 함 알아봄

 

보통 priority_queue 나 set을 쓸때 커스텀 정렬기준 함수를 인자로 줘야할때가 있음

그때 comp 함수에 참조자(&)를 쓰는게 훨씬 좋음

 

참조자 Reference 사용

struct comp {
    bool operator()(const string &s1, const string &s2) const {
        // 글자수가 같으면 사전순
        if (s1.size() == s2.size()) {
            return s1 < s2;
        }
        // 글자수 다르면 짧은순
        return s1.size() < s2.size();
    }
};

 

[참조자를 사용하면 좋은점]

 

매개변수가 const string &로 전달된다.

따라서 여기서는 실제 s1, s2의 원본 데이터가 복사되지 않고 참조를 통해 전달되므로, 그대로 사용된다

따라서 매개변수가 큰 경우에도 복사 없이 원본데이터를 참조하므로 메모리 사용량이 줄어들고 속도가 더 빨라진다

 

 

[참조자 사용 X 시 문제점]

매개변수가 복사로 전달된다

따라서 여기서는 s1, s2의 복사본이 만들어져 전달된다

문자열이 클수록 복사 비용이 증가하므로, 메모리 사용량이 늘어나고 함수 호출 속도가 느려질 수 있다.

 

참조를 사용하면 복사 비용이 없으므로 메모리 효율성도 높아지며, 함수 호출 시 불필요한 오버헤드를 줄일 수 있다.

따라서, 성능과 메모리 사용 측면에서 참조자를 활용하는게 더 효율적이다.

 

---

이거 공부하기 좋은 문제가 여기있다.

priority_queue + unordered_set 이용해서 풀 수 도 있고

바로 set 이용해서 풀 수 도 있다

 

이 문제로 커스텀 정렬기준 연습할 수 있다

 

https://www.acmicpc.net/problem/1181