[C++11] 인덱스 정보를 유지하면서 효율적으로 정렬하기

정렬은 컴퓨터 알고리즘에서 매우 자주 쓰이는 중요한 알고리즘입니다. 그래서 대부분의 프로그래밍 언어들은 정렬하는 방법을 언어 문법 차원에서든 기본 라이브러리로든 반드시 제공합니다. 언어 차원에서 제공해주는 정렬 함수는 대체로 최적화가 잘 되어 있어 빠르므로, 컴공 과제를 푸는게 아닌 이상은 정렬을 직접 구현해서 쓸 일은 거의 없지요. 그러나 종종 기본적으로 제공되는 정렬 함수만으로는 부족함을 느낄 때가 있습니다. 바로 인덱스 정보를 유지하면서 정렬을 해야하는 경우입니다.

배열을 정렬할 때 원본의 인덱스 정보를 유지하는 작업은 생각보다 자주 필요하다.

위의 그림에서와 같이 총 5개의 문자열로 이뤄진 배열을 정렬하는데, 정렬 후 배열의 각 요소들이 원래 어느 위치에 있었는지를 함께 파악해야하는 경우가 있습니다. 배열과 관련된 다양한 문제를 해결하다보면 생각보다 자주 필요한 작업인데요, 이에 대한 기능을 자체적으로 제공해주는 언어는 거의 없습니다. 왜냐면 사실 몇 가지 손질만 하면 기본 정렬 함수를 통해 위의 문제를 해결할 수 있거든요. 가장 간단한 방법은 배열의 각 요소들을 직접 정렬하는 대신 (요소, 인덱스) 형태의 튜플의 배열을 만든 뒤, 이를 정렬하는 것입니다. 그리고 다시 요소와 인덱스를 떼어서 필요한 곳에 쓰면 대성공이지요.

그런데 C++을 사용하는 개발자 입장에서는 이 방법이 영 탐탁지 않을지 모릅니다. 왠지 이 방법이 가장 빠른 방법이 아닐것 같거든요. 그래서 이번 포스팅에서는 C++11을 기준으로, 인덱스 정보를 유지하면서 효율적으로 배열을 정렬하는 방법에 대해서 고민해보았습니다.

문제 상황 정의 

먼저 우리가 최적화하여 해결해보고자 하는 문제를 명확히 정의해보도록 하겠습니다. 1) 정렬가능한 타입 T의 값 n개가 연속한 메모리 공간에 위치해 있습니다. 2) n개의 T값을 inplace^[각주:1]로 정렬하고, 추가로 각 T의 요소들의 원래 위치를 구하여 함께 반환해야 합니다. 

장황하게 적어놨지만 아주 명확한 요구사항이죠? 이 요구사항에 맞춰서 바로 떠올릴 수 있는 구현은 다음과 같은 모양일 겁니다.

가장 기본적인 방법

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

#include <vector> #include <algorithm>     using namespace std;   template<class A> // 임의의 타입 A에 대해 vector<size_t> sortBaseline(vector<A>& v) // vector<A> v를 입력 받아서 {     vector<pair<A, size_t>> t;     vector<size_t> ret;     // 임시 벡터 t에 A와 그 인덱스 번호 쌍을 함께 입력     for(size_t i = 0; i < v.size(); ++i)     {         t.emplace_back(v[i], i);     }       // 임시 벡터 t를 대신 정렬하고     sort(t.begin(), t.end());     // A의 정렬 결과를 다시 v에 쓰고, 원본의 인덱스들은 ret에 쓴다     for(size_t i = 0; i < v.size(); ++i)     {         v[i] = t[i].first;         ret.emplace_back(t[i].second);     }     return ret; }

쉽게 짠 만큼 아주 비효율적인 코드지요. 일단 임시 벡터 t를 쓰는게 마음에 걸립니다. 입력 받은 벡터 v에서 모든 값들을 t에 다 복사해서 옮긴 뒤, 이를 정렬하고, 그 결과를 다시 또 v에 옮기고 있으니깐요. 아주 비효율적입니다. 만약 임의의 타입인 A가 복사하기에 매우 비싸고 거대한 타입이라면 여기서 v에서 t로, t에서 v로 값을 복사하는 데에 아주 큰 오버헤드가 발생할 것입니다. 다행히도 C++11부터는 값을 복사하는 대신 이동시키는 방법이 추가됐죠. 이를 적극 활용해봅시다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

template<class A> vector<size_t> sortMoveBaseline(vector<A>& v) {     vector<pair<A, size_t>> t;     vector<size_t> ret;     for(size_t i = 0; i < v.size(); ++i)     {         t.emplace_back(move(v[i]), i); // move가 추가됐음     }       sort(t.begin(), t.end());     for(size_t i = 0; i < v.size(); ++i)     {         v[i] = move(t[i].first); // 여기도 move가 추가됐음         ret.emplace_back(t[i].second);     }     return ret; }

기본적으로는 sortBaseline과 동일한 함수인데 A 값을 옮길때 move 함수를 덧붙여 값이 복사 대신 이동되도록 한 것만 차이가 있습니다. A를 복사하는 문제는 해결했으나, 이동해야하는 것 역시 찝찝합니다. 꼭 v에서 t로 값을 이동해서 정렬하고, 다시 이걸 역으로 t에서 v로 이동시켜야만하는 걸까요? 그러지 말고 v에다 대고 바로 정렬을 수행할 순 없을까요?

레퍼런스 사용하기

C++에서는 레퍼런스라는 타입을 제공합니다. 포인터처럼 다른 변수를 참조하는 녀석인데, 초기화할때만 참조 대상을 설정할 수 있고, 그 이후에는 해당 변수의 별칭처럼 사용된다는 특징이 있죠.

1 2 3

int a = 10; int& b = a; // b는 a의 별칭 b = 50; // b에 값을 대입하는 건 a에 값을 대입하는 것과 동일한 효력을 지님

그리고 또 레퍼런스 타입은 std::pair 안에 들어갈 수도 있습니다. 그럼 레퍼런스를 이용해서 위의 문제를 풀어볼 수도 있지 않을까요?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

template<class A> vector<size_t> sortReference(vector<A>& v) {     vector<pair<A&, size_t>> t; // A의 레퍼런스와 size_t로 구성된 pair들의 배열     vector<size_t> ret;     // 임시 벡터 t에 A와 그 인덱스 번호 쌍을 함께 입력     for(size_t i = 0; i < v.size(); ++i)     {         t.emplace_back(v[i], i); // A& 레퍼런스가 초기화 된다.     }       // t를 정렬하게 되면, pair<A&, size_t>에 대한 수정 연산들이 적용되는데,     // 이 때 A&에 대한 값의 수정은 A&가 참조하는 원본인 v에 적용될 것     sort(t.begin(), t.end());     // A의 정렬 결과는 이미 v에 반영되어 있을테니, 원본의 인덱스들만 ret에 쓴다     for(size_t i = 0; i < v.size(); ++i)     {         ret.emplace_back(t[i].second);     }     return ret; }

레퍼런스가 별칭을 지어주는것이라는 걸 이해하면, pair<A&, size_t>의 값을 수정하면 결국 A&가 가리키는 대상인 v가 바로 수정된다는 것도 이해할 수가 있습니다. 이렇게해서 정렬을 수행하면, t를 정렬하는게 바로 v에 반영되겠죠. 참 쉽죠?

그런데 사실 위 코드는 제대로 정렬을 수행하지 못합니다. 레퍼런스 타입의 한계 때문입니다. 특정 타입에 대해 정렬이 작동하려면 다음 코드가 문제 없이 작동해야합니다.

1 2 3 4 5

X a, b; // X타입의 변수 a, b가 있다고 가정 X t = a; // a의 값을 t에 넣고 a = b; // b의 값을 a에 넣고 b = t; // t의 값을 다시 b에 넣으면 // 이 시점에서 a와 b는 서로 값이 바뀌어 있어야 함

두 변수의 값을 바꿀 때(swap) 흔히 사용하는 방법이죠. 근데 만약 X자리에 일반 타입이 아닌 레퍼런스 타입 X&가 대신 들어간다면 어떻게 될까요?

1 2 3 4 5

X& t = a; // t는 a의 별칭으로 선언됨. a = b; // b의 값을 a에 넣고 b = t; // t(==a)의 값을 다시 b에 넣으면 // t는 그저 a에 대한 별칭이었기 때문에, a = b;를 수행한 뒤 b = a;를 수행할 꼴. // 결국 두 값이 같아져 버린다!

두 값이 서로 맞바뀌는게 아니라 같아져 버리게 됩니다. 이런!!! 이래서는 제대로 정렬이 수행될 수가 없습니다. 따라서 pair에 A&를 넣더라도, 위와 같이 값을 잠시 저장해둘때에는 레퍼런스(A&) 대신 일반 타입(A)을 사용하도록 해야합니다. std::sort 함수 내부를 뜯어 고쳐야하는 걸까요?

맞춤형 Iterator를 구현하자

다행히도 STL에서 제공하는 algorithm들은 내부를 직접 수정하지 않고도, 입력으로 사용하는 iterator를 조절하여서 그 동작을 맞춤형으로 바꿀 수 있게 구현되어 있습니다. 즉, pair<A&, size_t> 타입에 대한 iterator이지만, 값을 잠시 저장해둘 때는 pair<A&, size_t> 대신 pair<A, size_t>를 사용하도록 하는 맞춤형 iterator를 구현하면 위의 문제를 피해갈 수 있다는 것이죠. 이를 위해 iterator에서는 value_type, reference, pointer 등을 직접 지정할 수 있게 하고 있습니다. 그럼 바로 구현해봅시다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

template<class Iter> // pair<A&, size_t>에 대한 Iterator 타입이라고 가정 class RefIdxIterator : public Iter {     using FirstRefTy = typename Iter::value_type::first_type; // pair<A&, size_t>의 첫번째 타입, 즉 A&     using SecondRefTy = typename Iter::value_type::second_type; // 두번째 타입인 size_t     using FirstValueTy = typename std::remove_reference<FirstRefTy>::type; // A&에서 reference를 뗀 A 타입     using SecondValueTy = typename std::remove_reference<SecondRefTy>::type; // size_t에서는 reference를 떼어봤자 size_t public:       using value_type = pair<FirstValueTy, SecondValueTy>; // pair<A, size_t>이 됨!!!!     // 여기서 위의 value_type만이 일반 iterator와의 유일한 차이점. 일반적인 iterator라면 value_type이 pair<A&, size_t>가 됨.     using reference = pair<FirstRefTy, SecondRefTy>&; // pair<A&, size_t>&이 됨     using pointer = pair<FirstRefTy, SecondRefTy>*; // pair<A&, size_t>&이 됨     using difference_type = typename Iter::difference_type;       // 대부분의 연산들은 부모클래스인 Iter에서 상속받고     // RefIdxIterator에서 쓰일 수 있도록 래핑만 해준다     RefIdxIterator() {}       RefIdxIterator(Iter _p) : Iter{ _p }     {     }       RefIdxIterator operator+(difference_type n) const     {         return { static_cast<const Iter&>(*this) + n };     }       RefIdxIterator operator-(difference_type n) const     {         return { static_cast<const Iter&>(*this) - n };     }       difference_type operator-(const RefIdxIterator& o) const     {         return static_cast<const Iter&>(*this) - static_cast<const Iter&>(o);     } };   // 다음은 임의의 Iterator를 RefIdxIterator로 래핑해주는 헬퍼 함수 template<class Ty> RefIdxIterator<typename std::remove_reference<Ty>::type> makeRefIdxIterator(Ty it) {     return { it }; }

아주 간단한 iterator입니다. 대부분의 기능은 부모인 Iter에서 상속받고, 오직 value_type 부분만 약간 손봐줬습니다. 기존 Iterator를 그대로 가져다가 makeRefIdxIterator 함수에 넣으면 자동으로 RefIdxIterator가 되지요. 이 녀석을 이용해 std::sort를 수행하면 이제 레퍼런스가 포함된 pair도 문제 없이 정렬해낼 수 있습니다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

template<class A> vector<size_t> sortReferenceFixed(vector<A>& v) {     vector<pair<A&, size_t>> t; // A의 레퍼런스와 size_t로 구성된 pair들의 배열     vector<size_t> ret;     // 임시 벡터 t에 A와 그 인덱스 번호 쌍을 함께 입력     for(size_t i = 0; i < v.size(); ++i)     {         t.emplace_back(v[i], i); // A& 레퍼런스가 초기화 된다.     }       // t.begin(), t.end()에 makeRefIdxIterator를 씌워서 sort에 넣는다!     sort(makeRefIdxIterator(t.begin()), makeRefIdxIterator(t.end()));     // A의 정렬 결과는 이미 v에 반영되어 있을테니, 원본의 인덱스들만 ret에 쓴다     for(size_t i = 0; i < v.size(); ++i)     {         ret.emplace_back(t[i].second);     }     return ret; }

참 쉽죠~? 그럼 얼마나 효율적으로 동작하는지 한번 테스트해봅시다. 

Copy와 Move가 호출되는 횟수 비교

위의 방법들을 기준으로 각각 copy와 move가 얼마나 자주 호출되는지를 세어보면, 실제로 이 방법이 효율적인지 아닌지를 확인해 볼 수 있겠죠. 다음과 같이 copy와 move 연산의 횟수를 세어주는 래퍼 템플릿을 하나 정의해보도록 하겠습니다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

template<class Ty> // 임의의 타입 Ty에 대해 class AssignmentCounter : public Ty // Ty를 상속받은 클래스 AssignmentCounter를 선언 {     static size_t copy_cnt, move_cnt; // copy와 move 호출 횟수를 저장할 static 변수 public:     AssignmentCounter() = default;     ~AssignmentCounter() = default;     AssignmentCounter(const AssignmentCounter& o) : Ty{o} {copy_cnt++;} // 복사 생성자     AssignmentCounter(AssignmentCounter&& o) noexcept : Ty{move(o)} {move_cnt++;} // 이동 생성자     AssignmentCounter& operator=(const AssignmentCounter& o) {static_cast<Ty&>(*this) = o; copy_cnt++; return *this;} // 복사 대입연산     AssignmentCounter& operator=(AssignmentCounter&& o) noexcept {static_cast<Ty&>(*this) = move(o); move_cnt++; return *this;} // 이동 대입연산       static void reset() // 카운터 초기화     {         copy_cnt = 0;         move_cnt = 0;     }       static void print(ostream& out) // 출력     {         out << "Copy: " << copy_cnt << ", Move: " << move_cnt << endl;     } };         template<class Ty> size_t AssignmentCounter<Ty>::copy_cnt = 0; template<class Ty> size_t AssignmentCounter<Ty>::move_cnt = 0;

이제 타입 A 대신에 AssignmentCounter<A>를 사용한다면, A의 복사/이동 횟수를 세어볼 수 있습니다. 그럼 테스트를 위해 다음과 같이 A = vector<size_t>로 두고, 이에 대한 정렬을 수행해보겠습니다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

#include <random>   int main() {     constexpr size_t vec_size = 2560; // 총 2560개의 요소를 정렬해볼것     vector<AssignmentCounter<vector<size_t>>> vecs(vec_size), baseline, ref;     vector<size_t> baseline_idx, ref_idx;     mt19937_64 rng;     // 각 벡터에 100개의 랜덤 정수를 삽입     for(auto& v : vecs)     {         for(size_t i = 0; i < 100; ++i) v.emplace_back(rng());     }       baseline = vecs;     AssignmentCounter<vector<size_t>>::reset();     sort(baseline.begin(), baseline.end()); // 인덱스 정보는 고려하지 않는 단순 배열 정렬     AssignmentCounter<vector<size_t>>::print(cout << "[SimpleSort Ops] ");       baseline = vecs;     AssignmentCounter<vector<size_t>>::reset();     baseline_idx = sortBaseline(baseline); // 복사를 이용해 임시 벡터에 값을 옮긴 뒤 정렬     AssignmentCounter<vector<size_t>>::print(cout << "[Baseline Ops] ");       baseline = vecs;     AssignmentCounter<vector<size_t>>::reset();     baseline_idx = sortMoveBaseline(baseline); // 이동을 이용해 임시 벡터에 값을 옮기 뒤 정렬     AssignmentCounter<vector<size_t>>::print(cout << "[MoveBaseline Ops] ");       ref = vecs;     AssignmentCounter<vector<size_t>>::reset();     ref_idx = sortReferenceFixed(ref); // 레퍼런스를 이용해 정렬     AssignmentCounter<vector<size_t>>::print(cout << "[Reference Ops] ");       if(baseline == ref && baseline_idx == ref_idx) // 결과가 동일한 경우     {         cout << "All Result Matched" << endl;     }     else // 동일하지 않은 경우     {         cout << "Error!! Mismatched Result!!" << endl;     }     return 0; }

1 2 3 4 5

[SimpleSort Ops] Copy: 0, Move: 26871 [Baseline Ops] Copy: 5120, Move: 30966 [MoveBaseline Ops] Copy: 0, Move: 36086 [Reference Ops] Copy: 9606, Move: 17265 All Result Matched

좋습니다~ 일단 결과는 일치하는 것으로 잘 나오네요. 확실히 sortBaseline이나 sortMoveBaseline은 불필요한 copy 및 move가 발생하고 있는것을 확인할 수 있구요. 그런데 sortReferenceFixed의 경우 copy 연산이 일부 발생하고 있는 걸 확인할 수 있습니다. 어디서 문제가 발생했을까요? copy 연산 쪽에 디버그 브레이킹포인트를 찍고 살펴보면 다음과 같이 pair의 이동 생성자 쪽에서 복사가 발생하고 있음을 확인할 수 있습니다. (다음은 GCC 4.8에 포함된 STL pair의 구현 중 일부입니다.)

Copy

	template<class _U1, class _U2, class = typename
	enable_if<__and_<is_convertible<_U1, _T1>,
	is_convertible<_U2, _T2>>::value>::type>
	constexpr pair(pair<_U1, _U2>&& __p)
	: first(std::forward<_U1>(__p.first)),
	second(std::forward<_U2>(__p.second)) { }

view raw stl_pair.h delivered with ❤ by emgithub

Copy

	template<class _U1, class _U2>
	pair&
	operator=(pair<_U1, _U2>&& __p)
	{
	first = std::forward<_U1>(__p.first);
	second = std::forward<_U2>(__p.second);
	return *this;
	}

view raw stl_pair.h delivered with ❤ by emgithub

U1이 A& 타입이라면 std::forward 후에도 A&타입이 되므로, 이동 생성자(A(A&&))가 호출되는 대신 복사 생성자(A(const A&))가 호출됩니다. 이 부분을 강제로 std::move로 고칠수 있다면 복사를 피할 수 있겠죠? STL pair의 내부 구현을 고칠 수 있는 방법이 있을까요........? 아쉽게도 그런 방법은 없기 때문에 위와 같은 상황에서 move가 호출되도록 하는 MovingPair를 직접 구현해보았습니다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109

// 기본적인 구현은 표준에 있는 std::pair와 동일하지만, // 주석으로 표시된 3개 함수만 forward 대신에 move를 사용한다는 차이점이 있음 template<class T1, class T2> class MovingPair { public:     T1 first;     T2 second;       using first_type = T1;     using second_type = T2;       constexpr MovingPair() {}       template <class U1 = T1, class U2 = T2,         typename std::enable_if<conjunction<             std::is_convertible<const U1&, U1>, std::is_convertible<const U2&, U2>         >::value, int>::type = 0>     constexpr MovingPair(const T1& _Val1, const T2& _Val2)         : first(_Val1), second(_Val2)     {}       template <class U1 = T1, class U2 = T2,         typename std::enable_if<!conjunction<             std::is_convertible<const U1&, U1>, std::is_convertible<const U2&, U2>         >::value, int>::type = 0>     constexpr explicit MovingPair(const T1& _Val1, const T2& _Val2)         : first(_Val1), second(_Val2)     {}       template <class U1, class U2,         typename std::enable_if<conjunction<         std::is_convertible<U1, T1>, std::is_convertible<U2, T2>>::value,         int>::type = 0>     constexpr MovingPair(U1&& _Val1, U2&& _Val2)         : first(std::forward<U1>(_Val1)), second(std::forward<U2>(_Val2))     {}       template <class U1, class U2,         typename std::enable_if<!conjunction<             std::is_convertible<U1, T1>, std::is_convertible<U2, T2>         >::value, int>::type = 0>     constexpr explicit MovingPair(U1&& _Val1, U2&& _Val2)         : first(std::forward<U1>(_Val1)), second(std::forward<U2>(_Val2))     {}       template <class U1, class U2,         typename std::enable_if<conjunction<             std::is_convertible<const U1&, T1>, std::is_convertible<const U2&, T2>         >::value, int>::type = 0>     constexpr MovingPair(const MovingPair<U1, U2>& o)         : first(o.first), second(o.second)     {}       template <class U1, class U2,         typename std::enable_if<!conjunction<             std::is_convertible<const U1&, T1>, std::is_convertible<const U2&, T2>         >::value, int>::type = 0>     constexpr explicit MovingPair(const MovingPair<U1, U2>& o)         : first(o.first), second(o.second)     {}       template <class U1, class U2,         typename std::enable_if<conjunction<             std::is_convertible<U1, T1>, std::is_convertible<U2, T2>         >::value, int>::type = 0>     constexpr MovingPair(MovingPair<U1, U2>&& o) // 여기         : first(std::move(o.first)), second(std::move(o.second))     {}       template <class U1, class U2,         typename std::enable_if<!conjunction<             std::is_convertible<U1, T1>, std::is_convertible<U2, T2>         >::value, int>::type = 0>     constexpr explicit MovingPair(MovingPair<U1, U2>&& o) // 여기         : first(std::move(o.first)), second(std::move(o.second))     {}       template <class U1, class U2>     MovingPair& operator=(const MovingPair<U1, U2>& o)     {         first = o.first;         second = o.second;         return *this;     }       template <class U1, class U2> // 여기     MovingPair& operator=(MovingPair<U1, U2>&& o)     {         first = std::move(o.first);         second = std::move(o.second);         return *this;     }       template<class U1, class U2>     bool operator<(const MovingPair<U1, U2>& o) const     {         if (first < o.first) return true;         if (o.first < first) return false;         return second < o.second;     }       friend void swap(MovingPair& a, MovingPair& b)     {         using std::swap;         swap(a.first, b.first);         swap(a.second, b.second);     } };

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

// 기본적으로는 위의 sortReferenceFixed 함수와 동일 template<class A> vector<size_t> sortReferenceFixed2(vector<A>& v) {     vector<MovingPair<A&, size_t>> t; // pair 대신 MovingPair 사용     vector<size_t> ret;     for(size_t i = 0; i < v.size(); ++i)     {         t.emplace_back(v[i], i);     }       sort(makeRefIdxIterator(t.begin()), makeRefIdxIterator(t.end()));     for(size_t i = 0; i < v.size(); ++i)     {         ret.emplace_back(t[i].second);     }     return ret; }

그리고 sortReferenceFixed2에서 pair 대신 MovingPair를 사용하게 함으로써 복사생성자가 불필요하게 호출되지 않고 이동생성자만 호출되도록 고칠 수 있습니다.

https://godbolt.org/z/Y1hqo4PM9

작동되는 전체 코드는 위의 링크에서 확인해 볼 수 있어요~!

유용성과 한계

다소 복잡한 과정을 거치긴 했지만, 이제 레퍼런스를 통한 정렬이 가능해졌습니다. 이를 단순히 정렬 전의 인덱스 정보를 계산하는데에만 쓰긴 아깝습니다. 곰곰히 생각해보면 이 기능이 다양한 곳에 유용하게 쓰일 수 있다는 걸 알수 있는데요, 먼저 임의의 배열 2개 이상을 묶어서 함께 정렬하는데에 사용할 수 있죠(아래의 zipped sort 단락 참조). 또 Random Access를 지원하지 않는 Container에 대해서도 각 요소의 reference만 떼어와서 vector로 만들고, 이를 정렬하는 방식으로 빠르게 정렬을 수행하는데에도 쓸 수 있습니다. C++의 레퍼런스 타입은 컴파일 이후 대체로 포인터로 치환되므로 전체 Container를 복사할 필요 없이 포인터 배열만 추가로 사용한다는 점은 최적화 시 큰 이점이 됩니다.

다만 이 방법이 항상 최적은 아닐 수 있습니다. 여기서는 비교적 무거운 타입을 예시로 사용했지만, 단순 정수/실수 타입 등은 레퍼런스/포인터를 통해 간접 참조를 하게 되는게 오히려 성능 상 손해일 수 있습니다. 이 경우는 차라리 전체 값을 복사하는게 더 효율적일 수도 있죠. 이에 대해서는 어떤 방법이 더 효율적인지 구체적으로 실험해볼 필요가 있겠습니다.

Zipped Sort

여기서 다룬, 둘 이상의 배열을 튜플로 엮어서 함께 정렬을 한다는 개념은 Zipped Sort라고 불립니다. 그리고 앞으로 C++ 표준 라이브러리 ranges v3에 들어갈 수 있도록 현재 표준 작업을 진행 중에 있습니다. (참고 링크)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

#include <range/v3/all.hpp> #include <vector> #include <string> #include <iostream>   using namespace ranges;   int main() {     std::vector<std::string> a1{"Kiwi", "Tomato", "Lemon", "Apple", "Orange" };     std::vector<int> a2{ 0, 1, 2, 3, 4 };     sort(view::zip(a1, a2), std::less<>{}, &std::pair<std::string, int>::first);     std::cout << view::all(a1) << '\n'; // [Apple,Kiwi,Lemon,Orange,Tomato]     std::cout << view::all(a2) << '\n'; // [3,0,2,4,1] }

정말 기대되는 기능이죠? 하지만 표준에 들어가서 현업에서 널리 쓰이게 되는 때는 머나먼 미래가 될 것 같네요. 대부분의 컴파일러가 ranges 라이브러리를 완벽하게 지원하게 되어, 이 포스팅과 같은 고민 없이 그냥 ranges를 쓸 수 있으면 제일 좋겠지만, 일단 그 전까지는 위와 같이 우회하는 방법을 고려해봐야겠습니다.

1. 정렬한 결과 값을 입력한 값과 동일한 위치에 쓰는 것을 뜻함. 이 경우 결과값을 별도의 메모리에 저장할 필요가 없기 때문에 메모리 효율적임. [본문으로]