[4기 신촌 백재현] C++ algorithm 헤더의 sort()를 사용하여 struct를 정렬해보자.

안녕하세요 신촌멤버십 22기 백재현입니다.

이번 글에서는 C++에서 제공하는 algorithm 헤더의 sort 메소드를 사용하여 struct를 정렬하는 방법에 대해 알아보고자 합니다.

정말 단순하게 '사용법'만 알려드리기 보다는 원리를 파헤치며 조금 더 깊이 있게 다뤄보도록 할테니, 호기심이 가득한 독자님께서는 가능하면 내용을 정독해 주시기 바랍니다!

우선 sort 메소드에 대해 알아보겠습니다.

sort 메소드는 std 네임스페이스에 속해있으며, algorithm 헤더에 정의 되어 있습니다.

Visual Studio에서 sort 메소드를 사용하려고 할 때 기본 적으로 뜨는 설명은 아래와 같습니다.

qsort 메소드에 비해 좋은점은 연속되는 주소값을 가지는 컨테이너(Random Access Iterator)라면 무엇이건간에 정렬이 가능하다는 점입니다.

sort 메소드는 _First 부터 _Last 까지의 범위에 있는 데이터를 오름차순으로 정렬하는 것을 기본으로 합니다.

가장 기본적으로 배열을 정렬하는 예시를 한번 보겠습니다.

결과 값은 [0,1,2,3,4,5,6,7,8,9]가 나옵니다.

이렇듯 배열간의 비교는 당연한듯 보입니다.

이제 오늘의 주제인 struct를 sort메소드를 통해 정렬해 보도록 하겠습니다.

1. < 연산자를 오버로딩하기

위의 소스 코드는 컴파일이 될까요? 당연하게도 되지 않습니다.

왜냐면 struct edge끼리의 비교가 불가능 하기 때문이죠. 당장에 e[0] > e[1]만 해도 서로 비교가 불가할 것입니다. 이것을 해결하기 위한 가장 쉬운 방법은??

바로 struct edge가 서로 비교 가능하게 하는 것이지요!

C++을 조금이라도 배웠다면 떠올릴 수 있는 방법, 바로 연산자 오버로딩을 사용하면 됩니다.

그렇다면 >를 오버로딩 해야할까요? <를 오버로딩 해야할까요?

바로 < 연산자를 오버로딩 해야합니다.

sort 메소드의 구현부를 보면 다음과 같습니다.

우선적으로 주석의 using operator< 를 통해 <로 정렬하는 것을 알 수 있습니다. 당연히 더 깊숙히 내려가보면 <를 통해 오름차순 정렬 하는 코드를 확인 할 수 있습니다.(직접 확인 해보시길 바랍니다.)

위 처럼 struct edge의 < 오퍼레이터를 오버로딩하여 struct edge 간의 비교가 가능하도록 하면 sort 메소드에서 정상적으로 사용 될 수 있습니다.(여담이지만 왜 연산자 오버로딩은 이름이 연산자 오버로딩인지 잘 모르겠네요. 엄밀히 말하면 기존 기능을 덮어 버리는 것인데.. 연산자 오버라이딩이라고 해야 맞지 않을까요? ㅎㅎ 여담이었습니다~ 이에 대한 해답을 아는 분은 코멘트로좀 알려주세요!)

2. 술어를 사용하기

sort 메소드의 마지막 세번째 인자를 보면 _Pr _Pred 인 것을 확인 할 수 있습니다. 이는 술어(Predicate)라고 합니다.

sort에 우클릭 하여 Go to Definition으로 구현부를 계속 찾아가다보면 퀵소트 알고리즘에서 mid 값 추출을 위해 사용하는 _Unguarded_partition 함수를 찾을 수 있습니다.

함수의 내용이 길어서 여기엔 첨부하지 않겠지만, 관심 있는 분들은 직접 열어 보시기 바랍니다.

해당 함수는 Pair<a,b>를 리턴하는데, 이 때 a와 b 값이 어느 값이 리턴 되냐에 따라 이 함수를 호출하는 _sort 함수가 오름 차순으로 정렬 할 지 내림 차순으로 정렬 할 지 결정하게 됩니다.

_Unguarded_partition 함수 내에서 두 원소를 비교하는 방법은 _Pred를 사용하는 것입니다.

이와 같은 형태로 _Pred를 통해 원소를 비교합니다.

다른 구문에서도 _Pred를 통해 비교 하는 것을 확인 할 수 있습니다. _Pred의 리턴 값은 bool이 좋겠죠?

_Pred의 형태가 _Pred(a, b)형태로 쓰인 것으로 보아, 우리가 sort 함수를 사용하기 위해 _Pred로 제공해야 하는 인자의 형태는 bool Predicate(a, b) 임을 확인 할 수 있습니다.

2-1. 비교 함수 제공

가장 많이 쓰이는 방법 일 것입니다. 비교 함수를 제공하는 것입니다.

위에서 얘기했 듯이 bool Predicate(a, b) 형태의 함수를 만들었습니다. 해당 함수에서는 struc edge의 value값을 비교하여 < (오름차순)일 경우 true를 리턴 하도록 하였습니다. 만약 내림차순으로 하고 싶다면 <를 >로 바꿔주기면 하면 됩니다.

이의 전체 소스는 아래와 같습니다.

해당 소스를 컴파일 하고 돌리면 결과 값이 정상적으로 출력 되는 것을 확인 할 수 있습니다.

2-2. () 연산자를 오버로딩 하는 방법(개그용)

이 방법은 정말 변태같은 방법이며 현업 개발자가 본인의 솔루션에 이와 같은 코드를 삽입 할 경우 가독성을 해치며 협업하는 다른 개발자의 욕을 먹을 수도 있는 방법임을 미리 말씀드립니다(...)

알아도 쓸모도 없고 사용할 일도 없는 방법이지만, 우리는 개발자가 아닙니까? 한번 소개해 보도록 하겠습니다.

위의 _Unguarded_partition 함수를 보면 !_Pred(*_Pfirst, *(_Pfirst - 1)) 같은 표현을 찾을 수 있습니다.

정상적인 개발자라면 위의 2-1 방법 형태로 _Pred를 제공하겠지만, 변태같은 개발자라면 위의 코드를 보고 다른 방법을 생각 할 수도 있습니다. 바로 () 연산자를 오버로딩 한 술어를 제공하는 것입니다.

바로 위와 같이 제공합니다.

이제 struct comp의 객체들은 ()를 사용할 수 있습니다. 바로 아래와 같이 말이죠(...)

(※주의※)현업에서는 구타를 유발 할 수도 있으니 절대 사용하지 마시기 바랍니다.

이를 sort함수에서 쓰려면 sort(e, e+10, c) 이런 형태로 쓰거나 sort(e, e+10, comp()) 형태로 사용하면 됩니다.

2-2는 쉬어가는 코너였습니다(__)

설명을 쭈욱 보면 아시겠지만, 가장 유용한 코드는 2-1의 술어를 사용하는 방법입니다.

단순히 사용법만 알기 보다는 STL의 구조를 알고, template을 직접 분석하여 동작 원리를 안다면 더욱 즐거운 프로그래머가 되리라 생각합니다 :)

이상으로 sort()를 사용하여 struct를 정렬하는 방법에 대한 강의를 마칩니다.

궁금한 점이 있으시면 언제든지 코멘트 달아주세요.

감사합니다 :)