C++ STL List에서 Sorting

Intro

list container에서 sort는 어떻게 할까? 다행히도? list container안에는 sort라는 함수가 내장되어 있다.

default는 ascending sort이다. 이번 posting에서는 정수, 문자열, struct 같은 데이터 타입의 sort를 알아보고자 한다.

 

integer sort

sort 함수를 사용하면 된다. 그렇다면, default인 ascending sort 말고 descending sort는 어떻게 할 수 있을까?

먼저, sort 함수가 어떻게 정의되어 있는지를 보는 게 좋다. (C++ template에 익숙하지 않아서, 정확히 이해하지는 못했다.)

 

정의된 template을 보면, sort함수의 파라미터가 클래스구나.

// list.sort()를 하면, default가 less<>임을 알 수 있다.
public:
    void sort() { // order sequence
        sort(less<>{});
    }

// 그리고 sort의 파라미터로 클래스를 받는 template이 있구나도 알 수 있어.
    template <class _Pr2>
    void sort(_Pr2 _Pred) { // order sequence
        auto& _My_data = _Mypair._Myval2;
        _Scary_val::_Sort(_My_data._Myhead->_Next, _My_data._Mysize, _Pass_fn(_Pred));
    }

 

그렇다면, descending sort를 해볼까?

#include <iostream>
#include <list>
using namespace std;

int main()
{
	list<int> li;
	li.insert(li.begin(), 1);
	li.insert(li.begin(), 3);
	li.insert(li.begin(), 4);
	li.insert(li.begin(), 5);
	li.insert(li.begin(), 2); // 2 5 4 3 1

	li.sort(less<int>{});     // 1 2 3 4 5 (ascending sort)
	li.sort(greater<int>{});  // 5 4 3 2 1 (descending sort)
	return 0;
}

 

string sort

integer sort와 별 차이 없다. 같은 맥락이다.

#include <iostream>
#include <list>
#include <string>
using namespace std;

int main()
{
	list<string> li;
	li.insert(li.begin(), "abc");
	li.insert(li.begin(), "abd");
	li.insert(li.begin(), "dce");
	li.insert(li.begin(), "cd");
	li.insert(li.begin(), "fg");

	li.sort();
	return 0;
}

 

struct sort

임의의 struct를 정의하고, sort는 어떻게 할까? integer나 string처럼 sort함수만 쓰면 될까?

아니다!!! 왜냐하면, STL은 임의의 struct를 모르기 때문이다. 그렇다면, 임의의 struct는 어떻게 sort 할 수 있을까?

대소비교 연산자 오버로딩이 필요하다.

 

#include <iostream>
#include <list>
#include <string>
using namespace std;

struct Data
{
	int id;      // name이 같다면, id(unique)가 작은 순서로 정렬
	string name; // abc 순으로 정렬

	bool operator<(const Data &r) const
	{
		if (name != r.name) return name < r.name;
		else return id < r.id;
	}
};

int main()
{
	list<Data> li;
	li.insert(li.begin(), { 1, "abc" });
	li.insert(li.begin(), { 3, "abc" });
	li.insert(li.begin(), { 5, "bdf" });
	li.insert(li.begin(), { 2, "qf" });
	li.insert(li.begin(), { 4, "k" });

	li.sort();
	return 0;
}