std::sort() & Lamda

TIL - Today I Learned : Lamda 함수의 정의와 sort()함수의 Parameter

Lamda는 C#을 배울 때도 서먹한 사이였는데 이젠 좀 막역한 사이가 되고 싶다.. 

 

sort()를 사용하다 오름차순이 아닌 내림 차순으로 정렬 하고 싶을 때가 있는데 

어떤식으로 해야할지 정리해본다. 

 

sort() 함수는 C++의 STL(Standard Template Library : 여러 자료 구조나 알고리즘 등을 제공하는

표준 라이브러리의 한 부분)의 <algorithm>에 있다. 

 

C++17부터 sort()는4개의 Parameter(매개변수)가 있다. 

template<class RandomAccessIterator>
void sort(
    RandomAccessIterator first,
    RandomAccessIterator last);

template<class RandomAccessIterator, class Compare>
void sort(
    RandomAccessIterator first,
    RandomAccessIterator last,
    Compare pred);

template<class ExecutionPolicy, class RandomAccessIterator>
void sort(
    ExecutionPolicy&& exec,
    RandomAccessIterator first,
    RandomAccessIterator last);

template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
void sort(
    ExecutionPolicy&& exec,
    RandomAccessIterator first,
    RandomAccessIterator last,
    Compare pred);

 

ExecutionPolicy : 병렬 알고리즘을 실행하는데 사용되는 정책을 지정한다. 

1. execution::seq : 순차 실행 정책, 알고리즘을 순차적으로 실행함
2. execution::par : 병렬 실행 정책, 알고리즘을 병렬로 실행하여 멀티스레드 환경에서 성능 향상
3. execution::par_unseq : 병렬 및 비순차적 실행 정책, 알고리즘을 병렬로 실행하고,
4. 각 스레드에서 비순차적으로 작업을 수행하여 최대의 성능을 얻음  

정렬하고자 하는 요소들의 범위를 나타내는 반복자로

first : 정렬의 시작 위치를 가리키는 임의 접근 반복자 

last : 정렬의 끝 위치를 가리키는 임의 접근 반복자

 

pred : 비교 함수 (Comparison Function)를 나타내며, 두 요소를 비교하여 정렬 순서를 결정함. 

 

근데 나의 visual studio code는 실행 정책에 대한 파라미터가 없었다. 

  /**
   *  @brief Sort the elements of a sequence.
   *  @ingroup sorting_algorithms
   *  @param  __first   An iterator.
   *  @param  __last    Another iterator.
   *  @return  Nothing.
   *
   *  Sorts the elements in the range @p [__first,__last) in ascending order,
   *  such that for each iterator @e i in the range @p [__first,__last-1),  
   *  *(i+1)<*i is false.
   *
   *  The relative ordering of equivalent elements is not preserved, use
   *  @p stable_sort() if this is needed.
  */
  template<typename _RandomAccessIterator>
    inline void
    sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
    {
      // concept requirements
      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
	    _RandomAccessIterator>)
      __glibcxx_function_requires(_LessThanComparableConcept<
	    typename iterator_traits<_RandomAccessIterator>::value_type>)
      __glibcxx_requires_valid_range(__first, __last);
      __glibcxx_requires_irreflexive(__first, __last);

      std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
    }

  /**
   *  @brief Sort the elements of a sequence using a predicate for comparison.
   *  @ingroup sorting_algorithms
   *  @param  __first   An iterator.
   *  @param  __last    Another iterator.
   *  @param  __comp    A comparison functor.
   *  @return  Nothing.
   *
   *  Sorts the elements in the range @p [__first,__last) in ascending order,
   *  such that @p __comp(*(i+1),*i) is false for every iterator @e i in the
   *  range @p [__first,__last-1).
   *
   *  The relative ordering of equivalent elements is not preserved, use
   *  @p stable_sort() if this is needed.
  */
  template<typename _RandomAccessIterator, typename _Compare>
    inline void
    sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
	 _Compare __comp)
    {
      // concept requirements
      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
	    _RandomAccessIterator>)
      __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
	    typename iterator_traits<_RandomAccessIterator>::value_type,
	    typename iterator_traits<_RandomAccessIterator>::value_type>)
      __glibcxx_requires_valid_range(__first, __last);
      __glibcxx_requires_irreflexive_pred(__first, __last, __comp);

      std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
    }

 

sort()는 정렬을 할 때 기본적으로 오름차순이다. 

만약 튜플처럼 여러가지 데이터를 가진 요소를 정렬할 때면

첫번째 요소를 정렬하고 다시 두번째 요소를 정렬한다. 

 

sort는 Quick Sort 알고리즘을 사용한다. Divide and Conquer (분할 정복) 방식으로 작은 요소로

쪼갠 후 두개의 요소를 비교하여 정렬하고 다시 합치는 정렬 알고리즘이다. 즉 두 요소를 비교하여

true 일 경우 그자리에 두고 false 일 경우 두개의 위치를 바꾼다.

 

정렬의 오름차순을 내림차순으로 변경하고 싶을 때는 두 개의 요소를 비교할 때 내림차순으로

정렬할 수 있도록 해주면 된다. 내가 정렬할 데이터묶음은 int와 char의 pair를 가진 벡터이다. 

 

vector<pair<int, char>> myVector = {{9, 'A'}, {7, 'B'}, {5, 'D'}, {2, 'H'}, {1, 'Z'}, {1, 'K'}};

 

기본 정렬을 사용하면 다음과 같이 요소들이 정렬된다. 

sort(myVector.begin(), myVector.end());

첫번째 요소들이 오름차순으로 정렬됨과 동시에 두번째 요소도 오름차순으로 정렬이 되었다. 

{1, 'Z'} -> {1, 'K'} 이었지만 {1, 'K'} -> {1, 'Z'} 순으로 알파벳도 정렬된 모습을 볼 수 있다. 

 

숫자로 내림차순으로 그리고 문자로 오름차순으로 정렬하는 함수 그리고 벡터의 요소를

하나씩 출력하는 함수를 만들었다. 

// 숫자 내림차순으로 정렬
bool asc_num(const pair<int,char>& a, const pair<int,char>& b)
{
    return a.first > b.first;
}

// 알파벳 오름차순으로 정렬
bool desc_alphabet(const pair<int,char>& a, const pair<int,char>& b)
{
    return a.second < b.second;
}

// 벡터의 요소를 출력
void print(vector<pair<int,char>> myVector)
{
    for(auto v : myVector)
    {
        cout << "first: " << v.first << " second: " << v.second << '\n';
    }
}

 

기존에 정렬의 시작과 끝을 인자로 넘기는 것이 아닌

 

sort(정렬의 시작, 정렬의 끝, 비교함수)을 사용한다. 

 

    sort(myVector.begin(), myVector.end(), asc_num);

    cout << "\nsort ascending by number\n";
    print(myVector);

이런식으로 벡터의 요소들이 정렬이 되었다. 

보면 첫번째 요소인 숫자로 내림차순이 되었고 두번째 요소는 정렬되지 않았다.

{1, 'Z'} -> {1, 'K'}가 {1, 'Z'} -> {1, 'K'}으로 유지됨

 

이상태에서 다시 알파뱃 순서로 오름차순으로 정렬하면 다음과 같이 된다. 

    sort(myVector.begin(), myVector.end(), desc_alphabet);

    cout << "\nsort descending by alphabet\n";
    print(myVector);

 

 

어디선가 많이 해본 듯한 스멜이 난다. 이전에 양방향 링크드리스트를 할때 람다를 사용해서

코드를 간결하게 썼던 것이 기억난다. 나중에 하드를 뒤져서 나오면 따로 정리해보겠다.

 

그래서 C++의 sort()의 비교함수도 한번 람다로 작성해보자

 

C++에서 람다의 기본형식은 다음과 같다. 

[capture](parameters) -> return_type { body }

 

capture : 외부 변수를 람다 함수 내에서 사용할 때 사용하는 옵션,

               외부 변수를 람다 함수 내부로 가져오는데 사용. 

parameters : 람다 함수의 매개변수 목록, 생략 가능.

-> return_type : 람다 함수의 반환 타입. 생략 가능. 

{ } : 함수 바디, 람다 함수에서 수행할 작업. 

 

// 함수를 선언
int sum(int a, int b)
{
    return a + b;
}

// 람다 함수 선언
auto lamda_sum = [](int a, int b)-> int {
    return a + b;
};

// 반환 타입 생략 가능
auto lamda_sum = [](int a, int b){
    return a + b;
};

// 변수를 선언함과 동시에 람다 함수 정의
int result = [](int a, int b){ return a + b; }(3, 4);

 

 

람다 함수를 사용해서 sort()의 비교 함수를 수정한다면 다음과 같이 할 수 있다.

    sort(myVector.begin(), myVector.end(), [](const pair<int,char>& a, const pair<int,char>& b)-> bool{
        return a.first < b.first;
    });

매개변수가 const 인 이유는 정렬을 위해 요소 값을 참조한 후

값을 변경하지 않겠다는 굳은 의지 이다.
람다 함수 바디에서 오름차순으로 정렬할지, 내림 차순으로 정렬할지 정하면 된다. 

 

a와 b는 벡터 내부의 요소를 하나씩 가져와서 비교한다. myVector[0]를 첫번째 요소(a)로

myVector[1]을 두번째 요소(b)로 가져와서 비교하고 비교 값이 True일 경우 위치를 변경하지 않고

false일 경우 위치를 변경 후 다름 요소를 가져와 비교한다. 

 

숫자의 오름 차순으로 정렬하는 람다를 사용한 벡터의 결과는 다음과 같다. 

이때 벡터 요소의 first 만을 비교하여 정렬하였기 때문에 second 값은 정렬되지 않았다. 

 

이제 람다에와 정렬에 대해 알아보았으니 계속 익혀봐야겠다. 

 

 

 

https://learn.microsoft.com/ko-kr/cpp/standard-library/algorithm-functions?view=msvc-170#sort

<algorithm> 함수

 

예제 코드

https://github.com/ChrisP-00/CPP_Practices/blob/main/C%2B%2BPractice/Sort/Sort()/sort.cpp

CPP_Practices/C++Practice/Sort/Sort()/sort.cpp at main · ChrisP-00/CPP_Practices