[STL] std::sort와 비교함수 오버라이딩

C++의 STL에서는 자바의 Collection.sort 와 같은 std::sort라는 아주 막강한 정렬함수가 존재합니다.

 

함수의 형태는 다음과 같이 두가지가 있으며 algorithm 헤더파일 안에 정의되어 있습니다.

1. std::sort(시작주소, 끝주소)

   • ex). sort(begin(vec), end(vec)); // vec은 벡터를 의미합니다. 

2. std::sort(시작주소, 끝주소, 비교함수*)  

   • ex). sort(vec.begin(), vec.end(), compare);
     • // vec.begin() 과 begin(vec)은 결과가 같습니다. compare는 사용자 정의 비교함수를 가리키는 포인터로 함수는 함수명 자체로 포인터이기 때문에 이름만 적어주셔야만 합니다.

 

1번과 2번을 나눈 이유는 무엇일까요?

 

cpp reference 의 말을 빌리자면, sort함수가 하는 일이

Sorts the elements in the range [first, last) in ascending order.  [시작주소, 끝주소) 범위의 요소들을 오름차순 정렬합니다.

라고 적혀있네요. sort 함수는 기본적으로 요소들을 오름차순 정렬하도록 구현되어 있나봐요.

그렇다면, 정수배열에 숫자를 막 담아본다음에 sort함수를 사용하여 정렬을 시켜보도록 하겠습니다.

 

[0]. 준비물

 

#include <string>

#include <iostream>

#include <algorithm>

using namespace std; 를 꼭 코드 상단에 입력해주고 실습을 진행해주세요~

 

[1]. built-in 타입의 오름차순 정렬

int arr[] = { 5, 4, 3, 1, 2 };
sort(begin(arr), end(arr), compare);
	
for (size_t i = 0; i < sizeof(arr)/4; i++)
{
	cout << arr[i] << " ";
}
cout << endl;

 

출력해보시면, 1, 2, 3, 4, 5 로 오름차 된 결과물을 얻으실 수 있으실 겁니다.

 

내림차순 정렬을 하기위해서는 지금부터 compare 함수를 우리가 직접 정의해줘야합니다.

---

(간단히 양의 정수만을 정렬시킨다면 -를 곱해서 넣은다음 sort 시키고 -를 붙여서 출력시에 -를 한 번더 곱해주면 되겠지만..., (다익스트라 알고리즘의 우선순위 큐에서 많이 사용하는 방법이죠? ))

---

객체의 경우에는 조금있다 다시 설명드리겠지만, '<' 연산자 오버로딩을 통해 compare 함수와 같은 기능을 수행하게 할 수 있습니다. 이 경우에는 첫 번째 함수를 사용하면 자동으로 적용이 됩니다.

 

아래와 같은 함수를 작성하고 함수의 이름을 두 번째 sort함수의 세번째 인자로 주고 실행해봅시다.

 

[2]. 비교함수 구현 규칙

bool compare(const int & a, const int & b) // 반환값이 true 이면, 왼쪽이 오른쪽보다 작다고 생각한다.
{
	return a < b;
}

int arr[] = { 5, 4, 3, 1, 2 };
sort(begin(arr), end(arr), compare);

for (size_t i = 0; i < sizeof(arr)/4; i++)
{
	cout << arr[i] << " ";
}
cout << endl;

이 경우엔 내림차순 정렬된 모습을 확인하실 수 있어요~

 

왜 그렇게 나오는 지에 대해선 sort함수의 구현 규칙을 이해해야합니다.

함수명과 매개변수 명은 자유입니다. 그러나 다음의 규칙을 따라주셔야합니다.

1). 반환타입: bool 

2). 매개변수: 같은 타입의 매개변수 두개

3). return 값의 의미:

    true 이면 sort함수는 왼쪽이 오른쪽보다 먼저 나오게 해줍니다.

 

따라서 내림차 정렬을 하기 위해서는 return 문의 비교연산자 방향을 반대로 해주시면 되겠습니다. 

return a >= b 로 바꾸고 실행해보세요~

 

 

[3]. 객체를 정렬하는 방법

 

자, 여기까지 기본타입들에게만 적용되는 방법을 알아보았는데요.

실제로는 기본타입뿐만 아니라 컨테이너 안의 객체들을 정렬해야할 상황이 올 수도 있으므로 

컨테이너의 객체들을 정렬하는 방법을 알아보겠습니다. 

여기서부터는 사전지식이 필요합니다.

바로 연산자 오버로딩에 관한 내용인데요. 이를 먼저 학습하시고 오신다음 읽으시는 것을 추천드립니다.

 

 

방법은 총 2가지가 있습니다.

 

1). 클래스 안에서 < 연산자 오버로딩하기

2). 위에서 살펴본 것처럼 compare 함수를 만들어서 인자로 주기

 

저는 공부할 때 잘 와닿지 않았는데. 코드를 통해 확인해보니 이해가 갔으며, 둘 다 쓸 수 있게 연습해둬야 겠다는 생각을 했습니다. 같이 따라해봐요!

 

class User
{
public:
	pair<string, string> m_info;
	User(string name, string id)
	{
		m_info.first = name;
		m_info.second = id;
	}
};

크게 복잡한 클래스는 아니죠? 페어객체가 달랑 하나 들어있는 User 라는 클래스일뿐입니다. 겁먹지 마세요!

info 라는 페어객체에는 사용자 이름과 아이디가 들어가 있습니다.

 

이제 이 친구를 벡터에 세개 정도 넣어서 이름을 사전순으로 정렬해서 출력해보려고 해요. 

(string 클래스에는 < 비교 연산자가 오버로딩 되어 있습니다. 사전순 비교가 가능하니 C string에 익숙하신 분들은 오해없으시길 바랍니다 ㅎㅎ)

 

앞서 두 가지 방법이 있다고 했었는데. 두 번째 방법을 앞에서 사용해 봤으니 그걸로 먼저 해보도록 할까요?

 

이름이 같은 친구들도 존재할 수 있을 것이라 생각해서 id는 유일하니, id의 사전 순서가 더 빠른 친구를 먼저 나타나게 하려면 다음과 같이 프로그래밍을 할 수 있을 것 같아요.

bool compareObject(const User & a, const User & b)
{
	if (a.m_info.first < b.m_info.first) return true;
	else
	{
		if (a.m_info.first == b.m_info.first) return a.m_info.second < b.m_info.second;
		else return false;
	}
}

a와 b를 비교하는데, info.first 는 이름이었죠? a의 이름이 더 빨리 나오는 경우는 바로 true 라고 해주면 되지만,

a와 b의 이름이 동일한 경우에는 아이디가 더 빠른 친구가 앞으로 오게 해달라는 의도가 담긴게 두 번째 if문 입니다.

그렇지 않은 경우에는 더 뒤에 나오면 되니 false를 반환하면 되겠죠?

 

저는 다음과 같은 데이터를 가지고 실험을 해보았습니다. 출력도 함께 해보죠.

User a("백윤기","1");
User b("김태원", "3");
User c("김태원", "2");
	
vector<User> vec;
vec.push_back(a);
vec.push_back(b);
vec.push_back(c);

sort(begin(vec), end(vec), compareObject);

for (const auto & user : vec)
{
	cout << user << " ";
}

a,b,c 중에서 이름이 가장 빠른 친구는 김태원 친구이지만 동일한 인물이 존재하고 아이디가 더 빠른 사람이 앞으로 오겠죠? 그리고 백윤기라는 친구는 이름이 다른 친구들보다 뒤에 나오니 가장 마지막에 나타나게 됩니다.

 

그리고, User객체를 출력하기 위해서는 다음과 같이 << 연산자를 클래스 안에서 오버로딩 해야합니다.

friend ostream& operator << (ostream& out, const User & rhs)
{
	out << rhs.m_info.first << "(" << rhs.m_info.second << ")";
	return out;
}

 

이제 마지막으로 연산자 오버로딩을 통한 비교함수 구현을 해보고 포스팅을 마무리 하도록 하겠습니다.

방법은 간단 합니다. 위에서 작성한 비교함수의 내용을 그대로 복사해주시면 되는데요. 변수명이 조금 바뀌는 것 빼고는 차이점이 없습니다.

bool operator < (User & rhs)
{
	if (m_info.first < rhs.m_info.first) return true;
	else
	{
		if (m_info.first == rhs.m_info.first) return m_info.second < rhs.m_info.second;
		else return false;
	}
}

 

연산자 오버로딩에 대한 이해가 부족하신 분은 미리 공부해 오신다면, 손 쉽게 이해할 수 있으실 겁니다.

이렇게 클래스 내부에서 < 연산자 오버로딩이 되면, 다음과 같이 sort 함수에서 세 번째 인자를 적어주지 않으셔도 됩니다.

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

for (const auto & user : vec)
{
	cout << user << " ";
}

 

이상으로 sort 함수의 compare 함수를 오버로딩하여 컨테이너와 배열을 정렬하는 방법에 대해 살펴보았습니다.

연산자 오버로딩에 대한 이해가 부족하신 분들은 이번 포스팅이 많이 어려울 수 있을 것이라 생각합니다.

그런 분들을 위해서 유튜브 강좌 링크를 제공하오니, 도움이 되셨으면 좋겠습니다.

 

긴 글 읽어주셔서 감사드리고

질문과 피드백은 언제나 환영입니다.

즐거운 코딩 되세요 ^^

 

유튜브 링크