[C++] Sort / Compare comp

https://cplusplus.com/reference/algorithm/sort/

sort

Sorts the elements in the range [first,last) into ascending order.
first를 포함하여 last 전까지 범위의 요소에 대해 ascending, 오름차순을 따르도록 정렬한다.
The elements are compared using operator< for the first version, and comp for the second.
template1에서는 연산자 '<'를 이용하고, template2에는 comp를 이용해 요소를 비교한다.
Equivalent elements are not guaranteed to keep their original relative order (see stable_sort).
동일한 요소에 대해서는 원본에서의 상대적 순서를 유지하는 것을 보장하지 않는다. (?)

parameters

• first, last
• comp
  • 2개의 element를 받아 bool값을 반환하는 함수.
  • 정의된 order에 따라, 첫 번째 argument가 두 번째 argument보다 앞선 것인지 여부(bool)를 반환한다.

example

// sort algorithm example
#include <iostream>     // std::cout
#include <algorithm>    // std::sort
#include <vector>       // std::vector

bool myfunction (int i,int j) { return (i<j); }

struct myclass {
  bool operator() (int i,int j) { return (i<j);}
} myobject;

int main () {
  int myints[] = {32,71,12,45,26,80,53,33};
  std::vector<int> myvector (myints, myints+8);               // 32 71 12 45 26 80 53 33

  // using default comparison (operator <):
  std::sort (myvector.begin(), myvector.begin()+4);           //(12 32 45 71)26 80 53 33

  // using function as comp
  std::sort (myvector.begin()+4, myvector.end(), myfunction); // 12 32 45 71(26 33 53 80)

  // using object as comp
  std::sort (myvector.begin(), myvector.end(), myobject);     //(12 26 32 33 45 53 71 80)

  // print out content:
  std::cout << "myvector contains:";
  for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}

Output:
myvector contains: 12 26 32 33 45 53 71 80

구조체에 sort 사용하기

예제) idx, vote 변수를 갖는 Board가 있고, 이를 idx가 낮은순으로, 같은 idx 값이라면 vote 값이 큰 순서로 정렬하고 싶을 때.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Board
{
    int idx;
    int vote;
};

bool comp(const Board &b1, Board &b2) {
    return b1.idx < b2.idx;
}

int main()
{
    vector<Board> board;

    board.push_back(Board({1, 4}));
    board.push_back(Board({1, 2}));
    board.push_back(Board({1, 8}));
    board.push_back(Board({2, 1}));
    board.push_back(Board({2, 3}));
    board.push_back(Board({3, 6}));

    sort(board.begin(), board.end(), comp);

    for (int i = 0; i < board.size(); ++i) {
        cout << "{" << board[i].idx << ", " << board[i].vote << "} "; // {1, 4} {1, 2} {1, 8} {2, 1} {2, 3} {3, 6}
    }

    return 0;
}