C++ of the Day #21 - multi key sorting

Question

이번 문제는 sorting에 관한 내용입니다. 먼저 아래 코드는 Data의 vector를 sorting하는 코드로 Data의 operator<()을 사용하고 있습니다.

using namespace std;
using namespace boost::lambda;

struct Data
{
  string node;
  int id;
  Data(const string& n, int i) : node(n), id(i) {}
};

bool operator<(const Data& lhs, const Data& rhs)
{
  return lhs.node < rhs.node;
}

ostream& operator<<(ostream& os, const Data& data)
{
  os << setw(5) << left << data.node << " : " << setw(2) << right << data.id;
  return os;
}

int main()
{
  vector<data> vs;
  vs.push_back(Data("CAN2", 2));
  vs.push_back(Data("CAN10", 13));
  vs.push_back(Data("CAN10", 10));
  vs.push_back(Data("CAN1", 1));
  vs.push_back(Data("CAN11", 11));

  stable_sort(vs.begin(), vs.end());

  for_each(vs.begin(), vs.end(), cout << _1 << "n");
}

하지만 위의 코드를 실행시키면 다음과 같이 원하는대로 출력되지 않습니다. (여기서 원하는 순서는 CAN1 -> CAN2 -> CAN10 -> CAN11 이라고 가정하겠습니다.)

CAN1  :  1
CAN10 : 13
CAN10 : 10
CAN11 : 11
CAN2  :  2

그럼 이 코드를 원하는 대로 출력하려면 어떻게 operator<()의 내용을 바꾸어야 할까요? 단 문자열 앞의 세자리는 항상 "CAN"입니다.

Answer

어렵게 하자면 문자열의 앞에서부터 세자리 떼고 atoi로 integer 타입으로 변경한 후 비교하는 방법등 끝도 없겠죠? 여기서는 간단히 문자열의 길이를 sorting 키에 추가하는 방법을 사용하겠습니다. 즉, 문자열의 길이가 짧을수록, 그리고 string의 사전적 순서가 앞일수록 먼저 출력되도록 합니다. 그냥 원시적(?)으로 구현하면 다음과 같습니다.

if (lhs.node.length() == rhs.node.length())
  return lhs.node < rhs.node;
return lhs.node.length() < rhs.node.length();

하지만 std::pair를 사용하면 더욱 쉽게 함수를 구현할 수 있습니다. std::pair는 자신의 first와 second에 대해 사전적 순서를 가지고 구현된 operator<()을 가지고 있기 때문에 이런 구현이 가능합니다.

return make_pair(lhs.node.length(), lhs.node) <
make_pair(rhs.node.length(), rhs.node);

다시 컴파일하여 실행시킨 출력은 다음과 같습니다.

CAN1  :  1
CAN2  :  2
CAN10 : 13
CAN10 : 10
CAN11 : 11

출력을 보니 여기에 다시 id를 키로 넣어 마저 정렬시키고 싶은 생각이 드는군요. ((이 예제를 위해 sort 대신 stable_sort를 사용했답니다. ;-))) 하지만 pair는 두 개의 데이터만을 가질 수 있으므로 사용이 불가능하죠. 여기가 boost::tuple이 등장하는 시간입니다. boost::tuple를 사용하여 간단히 다음과 같이 구현이 가능합니다. ((tuple을 비교하기 위해서는 tuple.hpp 외에 tuple_comparison.hpp 파일도 #include해주어야 합니다.)) boost::tuple 역시 자신의 데이터들에 대해 사전적 순서를 가지고 구현된 operator<()을 가지고 있기 때문에 이런 구현이 가능합니다.

return make_tuple(lhs.node.length(), lhs.node, lhs.id) < 
make_tuple(rhs.node.length(), rhs.node, rhs.id);

드디어 출력이 완성되었네요. ;-)

CAN1  :  1
CAN2  :  2
CAN10 : 10
CAN10 : 13
CAN11 : 11