Skip to main content

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

Comments

Popular posts from this blog

1의 개수 세기 - 해답

벌써 어제 말한 내일이 되었는데 답을 주신 분이 아무도 없어서 좀 뻘쭘하네요. :-P 그리고 어제 문제에 O(1)이라고 적었는데 엄밀히 얘기하자면 O(log 10 n)이라고 적었어야 했네요. 죄송합니다. ... 문제를 잠시 생각해보면 1~n까지의 수들 중 1의 개수를 얻기 위해서는 해당 숫자 n의 각 자리의 1의 개수가 모두 몇개나 될지를 구해서 더하면 된다는 사실을 알 수 있습니다. 예를 들어 13이라는 수를 생각해 보면 1~13까지의 수에서 1의 자리에는 1이 모두 몇개나 되는지와 10의 자리에는 모두 몇개나 되는지를 구해 이 값을 더하면 됩니다. 먼저 1의 자리를 생각해 보면 1, 11의 두 개가 있으며 10의 자리의 경우, 10, 11, 12, 13의 네 개가 있습니다. 따라서 2+4=6이라는 값을 구할 수 있습니다. 이번엔 234라는 수에서 10의 자리를 예로 들어 살펴 보겠습니다. 1~234라는 수들 중 10의 자리에 1이 들어가는 수는 10, 11, ..., 19, 110, 111, ... 119, 210, 211, ..., 219들로 모두 30개가 있음을 알 수 있습니다. 이 규칙들을 보면 해당 자리수의 1의 개수를 구하는 공식을 만들 수 있습니다. 234의 10의 자리에 해당하는 1의 개수는 ((234/100)+1)*10이 됩니다. 여기서 +1은 해당 자리수의 수가 0이 아닌 경우에만 더해집니다. 예를 들어 204라면 ((204/100)+0)*10으로 30개가 아닌 20개가 됩니다. 이런 방식으로 234의 각 자리수의 1의 개수를 구하면 1의 자리에 해당하는 1의 개수는 ((234/10)+1)*1=24개가 되고 100의 자리에 해당하는 개수는 ((234/1000)+1)*100=100이 됩니다. 이들 세 수를 모두 합하면 24+30+100=154개가 됩니다. 한가지 추가로 생각해야 할 점은 제일 큰 자리의 수가 1인 경우 위의 공식이 아닌 다른 공식이 필요하다는 점입니다. 예를 들어 123에서 100의 자리에 해당하는 1의 개수는 ((123/1...

CodeHighlighter plugin test page.

This post is for testing CodeHighlighter plugin which uses GeSHi as a fontifier engine. ((Those code blocks are acquired from Google Code Search .)) ((For more supported languages, go CodeHighlighter plugin or GeSHi homepage.)) C++ (<pre lang="cpp" lineno="1">) class nsScannerBufferList { public: /** * Buffer objects are directly followed by a data segment. The start * of the data segment is determined by increment the |this| pointer * by 1 unit. */ class Buffer : public PRCList { public: Buffer() { ++index_; } PHP (<pre lang="php" lineno="4">) for ($i = 0; $i $value = ord( $utf8_string[ $i ] ); if ( $value < 128 ) { // ASCII $unicode .= chr($value); } else { if ( count( $values ) == 0 ) { $num_octets = ( $value } $values[] = $value; Lisp (<pre lang="lisp">) ;;; Assignment (define-caller-pattern setq ((:star var fo...

C++ of the Day #43 - SQLite3 C++ wrapper #1

The Definitive Guide to SQLite 를 읽다가 공부 겸 해서 C++ wrapper를 만들어 보았습니다. 최대한 C++ 냄새(?)가 나도록 만들어 보았습니다. :-) ((SQLite는 복잡한 관리가 필요없이 사용가능한, 파일이나 메모리 기반의, 라이브러리로 제공되는, 약 250kb 용량의, 대부분의 SQL92문을 지원하는, open source RDB입니다.)) 이 wrapper를 사용하기 위해서는 (당연하게도!) sqlite3 와 (당연하게도?) boost 라이브러리가 필요합니다. 사용 예들을 살펴보는 것으로 설명을 대신합니다. 이번 글에서는 다음과 같은 contacts 테이블이 test.db에 존재한다고 가정합니다. CREATE TABLE contacts ( id INTEGER PRIMARY KEY, name TEXT NOT NULL, phone TEXT NOT NULL, UNIQUE(name, phone) ); Command 먼저 test.db 파일을 사용하기 위해 다음과 같이 파일 이름을 주어 connection 객체를 생성합니다. 생성과 동시에 test.db와 연결이 이루어집니다. ((생성자외에 open() 함수를 사용할 수도 있습니다.)) sqlite3pp::connection conn("test.db"); 다음은 contacts 테이블에 정보를 추가하는 가장 간단한 방법입니다. connection 클래스에서 제공하는 execute 함수를 사용합니다. ((executef 함수를 사용하면 printf와 같은 문법을 사용하여 query문을 작성할 수 있습니다.)) conn.execute("INSERT INTO contacts (name, phone) VALUES ('user', '1234')"); 위와 동일한 작업을 parameterized query를 사용하여 할 수도 있습니다. ((step()함수가 실제 query문을 수행하는 함수입니다. ...