C++에서 정렬을 할 때, 기본 타입들의 오름차순, 내림차순 정렬 말고도
다양한 방식으로 정렬이 필요할 때가 있다.
또 사용자 정의 클래스를 만들어서 사용하는 경우에 직관적으로 코드를 작성할 수 있지만 직접 정렬 또는 비교함수를 재정의 해줘야한다.
필자는 보통 C++로 알고리즘,자료구조 문제를 풀 때,
조금 복잡해지거나 헷갈리는 상황에서는
보통 pair, tuple을 사용하는 것보다는 커스텀 클래스(또는 구조체)를 만들어서
묶어서 보기 좋게 관리하는 것을 선호하다보니, 정렬 기준을 직접 정해야 하는 경우가 많다.
지금은 보통 클래스를 만들면 bool operator<을 재정의 하는 방법을
가장 선호하는데, 이 방법을 쓰기 전이나 커스텀 클래스를 직접 안만들고
정렬 기준을 변경하는 등의 경우도 있다보니 생각할 경우가 많아졌다.
그래서 C++에서 가능한 여러가지 방법들을 모아서 정리해보았다.
(그리고 C언어와 C++은 커스텀 정렬 방식이 다르기 때문에 링크를 참고)
먼저 커스텀 클래스는 아래와 같이 가정하고 진행하겠다.
class Person {
public:
int age;
string name;
};
vector<Person> v;
v.push_back({ 3,"a"});
v.push_back({ 1,"b"});
v.push_back({ 2 ,"c"});1. compare 구조체 만들기
아마 C++로 알고리즘 문제를 풀면서 검색해봤을 때 예전에 가장 처음 접했던
방식이였던 것 같다.
아래는 나이순 오름차순 정렬 방식이다
struct compare {
bool operator()(const Person& p1, const Person& p2) {
return p1.age < p2.age;
}
};
sort(v.begin(), v.end(), compare());만약 사용자 정의 클래스 없이 일반 타입도 같은 방법으로 구현할 수 있다는 장점이 있다.
예를들어 숫자(int타입) 내림차순 정렬을 구현한다면
struct compare {
bool operator()(const int& a1, const int& a2) {
return a1 > a2;
}
};
vector<int> v1 = { 3, 1, 2 };
sort(v1.begin(), v1.end(), compare());이렇게 하면 정수형 내림차순을 구현할 수 있다.
그리고 compare이 아닌 compare()을 전달해야하는 이유는, 함수를 전달해야하기 때문이다.
사실 이렇게 안해도 아래 4번에서 정렬함수 전달 부분처럼 전달 해도 됨.
하지만 이 방법은 우선순위큐(PriorityQueue)에서도 같은 방식으로 사용할 수 있다는 장점이 있다.
priority_queue<Person, vector<Person>, compare> pq;
for (const auto& p : v) {
pq.push(p);
}
while (!pq.empty()) {
Person p = pq.top();
cout << p.age << " " << p.name << endl;
pq.pop();
}단, <>안에 들어갈 때는 ()를 붙이지 않아야한다
-> 함수를 전달하는게 아니라 클래스(타입)을 전달하는 것.
그리고 그 클래스를 operator()을 이용해서 함수 객체로 만들어서 비교에 사용한다.
2. bool operator< 재정의
이거는 커스텀 클래스 (구조체)를 만들었을 때 사용할 수 있는 방법이다.
클래스 안에다가 정의하기 때문에 한번 적어 놓으면 정렬 함수를 호출할 때마다
따로 뭘 안넘겨줘도 된다는 점이 큰 장점이다.
class Person {
public:
int age;
string name;
bool operator<(const Person& other) const {
return this->age > other.age; // age순 내림차순
}
};
int main() {
vector<Person> v;
v.push_back({ 3,"a"});
v.push_back({ 1,"b"});
v.push_back({ 2 ,"c"});
sort(v.begin(), v.end());
for (const auto& person : v) {
cout << person.age << " " << person.name << endl;
}
}const 두개를 꼭 붙여줘야한다. 붙여주지 않으면 sort()를 하기도 전에
컴파일 오류가 발생한다.
(런타임오류가 아니라 컴파일 타임에 오류가 발생한다.
sort()는 템플릿 함수인데 타입 실체화 과정에서 형 검증에 실패하는 것 같다)
3. 우주선 연산자 사용 (C++20 이상)
C++20 이상의 버전을 사용한다면 제일 좋은 방법이다.
"<"방향만 정해도
"<",">","=",">=","<=", "!="
총 6가지 비교 연산이 자동으로 정의된다
특히 default 키워드를 이용하면, 클래스에 있는 멤버 정의 순서대로
정렬 기준을 오름차순으로 넣어준다.
class Person {
public:
int age;
string name;
auto operator<=>(const Person& other) const = default;
};
int main() {
vector<Person> v;
v.push_back({ 3,"a"});
v.push_back({ 2,"c"});
v.push_back({ 2 ,"b"});
sort(v.begin(), v.end());
for (const auto& person : v) {
cout << person.age << " " << person.name << endl;
}
/*출력
2 b
2 c
3 a
*/
}멤버 정의 순서대로 정렬 기준이 적용된다고 했는데,
만약 나이가 같으면 그 다음 이름을 기준으로 오름차순으로 정렬한다는 것.
마치 pair나 tuple의 디폴트 정렬 방식과 비슷하다.
이건 default로 설정했을 때의 얘기고, 당연히 직접 정렬 기준을 설정할 수 있다.
이게 정말 처음 공부했을 때 특이하고 유용했던 것 같다.
만약 vector<Person>을 정렬하고 싶은데 이름은 전혀 신경 안쓰고
오직 나이순으로만 오름차순 정렬하고 싶다고 하면
class Person {
public:
int age;
string name;
auto operator<=>(const Person& other) const {
return age <=> other.age;
}
};이렇게 하면 되고,
만약 내림차순이라면
age <=> other.age;
을
other.age <=> age;
로 바꿔주면 된다
조금 더 응용해서,
"나이순 내림차순을 하되, 나이가 같다면 이름순 오름차순 정렬"을 한다고 하면
class Person {
public:
int age;
string name;
auto operator<=>(const Person& other) const {
if (other.age <=> age == 0) {
return name <=> other.name;
}
return other.age <=> age;
}
};이렇게 해볼 수 있다
4. 정렬 함수 전달
가장 익숙한 형태인 것 같다
class Person {
public:
int age;
string name;
};
bool compare(const Person& a, const Person& b) {
if (a.age == b.age) {
return a.name < b.name;
}
return a.age < b.age;
}
int main() {
vector<Person> v;
v.push_back({ 3,"a"});
v.push_back({ 2,"c"});
v.push_back({ 2 ,"b"});
sort(v.begin(), v.end(),compare);
for (const auto& person : v) {
cout << person.age << " " << person.name << endl;
}
}(이름순 오름차순 후 나이순 오름차순)
5. 람다함수 사용
람다함수를 이용해서도 정렬할 수 있다.
class Person {
public:
int age;
string name;
};
int main() {
vector<Person> v;
v.push_back({ 3,"a"});
v.push_back({ 2,"c"});
v.push_back({ 2 ,"b"});
sort(v.begin(), v.end(),
[](const Person& a, const Person& b) {
if (a.age == b.age) {
return a.name < b.name;
}
return a.age < b.age;
});
for (const auto& person : v) {
cout << person.age << " " << person.name << endl;
}
}(이름순 오름차순 후 나이순 오름차순)
참고로, 우선순위큐에 커스텀 정렬 함수를 사용하고 싶다면
람다함수 + decltype을 이용한 방법도 가능하다
(
class Person {
public:
int age;
string name;
};
int main() {
auto compare = [](const Person& a, const Person& b) {
if (a.age == b.age) {
return a.name > b.name; // Sort by name if ages are equal
}
return a.age > b.age; // Sort by age in descending order
};
priority_queue<Person,vector<Person>,decltype(compare)> pq(compare);
vector<Person> v = {
{3, "a"},
{2, "b"},
{2, "c"}
};
for (const auto& person : v) {
pq.push(person);
}
while (!pq.empty()) {
Person p = pq.top();
pq.pop();
cout << "Age: " << p.age << ", Name: " << p.name << endl;
}
}6.ranges::sort() + Projection (C++20이상)
정확한 동작 방식은 아직 제대로 모르겠으나,
마치 자바에서 메소드 참조 하듯이 정렬이 가능하다
#include<ranges> // C++20 이상
class Person {
public:
int age;
string name;
};
int main() {
vector<Person> v = {
{2, "a"},
{2, "b"},
{3, "c"}
};
ranges::sort(v, std::less{},&Person::age);
for (const auto& person : v) {
cout << person.age << " " << person.name << endl;
}
}
