Skip to main content

C++ of the Day #25 - Boost::Iterator 라이브러리 사용하기 #1

이번 시리즈에선 boost::iterator 라이브러리를 소개합니다.

만약 stl에서 제공하지 않는 컨테이너를 만들 필요가 있다면 이 컨테이너에서 stl과 호환되는 iterator를 제공하는 것이 컨테이너의 사용자들에겐 큰 도움이 됩니다. 가장 간단한 이유는 stl의 알고리즘들을 그대로 사용할 수 있기 때문이죠.

하지만 이런 iterator 클래스를 만드는 것이 만만치 않은 작업인데 이를 도와주는 것이 바로 boost::iterator 라이브러리입니다. ((boost::iterator에는 이외에도 새로운 concept의 iterator_traits등 다른 목적들도 있습니다.))

이번 글을 위해 만들어 볼 컨테이너가 하나 필요한데 여기서는 실제 컨테이너에 대해 sorting된 view를 제공하는 sorted_view 컨테이너를 설계해 보겠습니다.

실제로 copy에 들어가는 비용이 높은 element를 가진 컨테이너를 sorting하는 것은 성능에 문제가 될 수 있습니다. 이 컨테이너의 iterator만을 가지고 따로 컨테이너를 만들어 sorting을 하는 방법을 사용하면 실제 copy는 iterator에 대해서만 일어나므로 이 문제를 해결할 수 있습니다. 문제는 이 iterator를 가지고 만든 컨테이너의 사용법이 원래 컨테이너와 달라진다는 것입니다. 그럼 시작해 보실까요?

완성된 sorted_view의 사용법은 다음과 같습니다.
using namespace std;
using namespace boost::lambda;

list<int> li;
li.push_back(3);
li.push_back(0);
li.push_back(1);
li.push_back(4);
li.push_back(2);

for_each(li.begin(), li.end(), cout << _1 << " ");
cout << endl;

typedef sorted_view<list<int>::iterator> sv_t; // (1)

sv_t sv1(li.begin(), li.end());
for_each(sv1.begin(), sv1.end(), cout << _1 << " "); // (2)
cout << endl;

sv_t sv2(li.begin(), li.end(), greater<int>()); // (3)
for_each(sv2.begin(), sv2.end(), cout << _1 << " ");
cout << endl;

sv_t::const_iterator i = sv2.begin();
i += 2; // (4)
cout << *i << endl;
cout << i - sv2.begin() << endl;

// output
// 3 0 1 4 2 
// 0 1 2 3 4 
// 4 3 2 1 0 
// 2
// 2
일반 컨테이너와 같은 방법으로 사용할 수 있음을 알 수 있습니다.(2) 게다가 list는 bidirectional traversal iterator만을 제공하는데 비해 sorted_view의 iterator는 random access traversal iterator를 제공하고 있습니다.(4) ((현재 표준에서는 bidirectional iterator 혹은 random access iterator라고 부르고 있으나 boost::iterator 라이브러리는 이 category를 traversal에 관한 것과 value access의 orthogonal한 두 타입에 대해 분류하고 있습니다.)) 또한 두번째 sorted_view의 생성자에서 알 수 있듯이 iterator pair외에 sorting시 비교에 사용할 function object를 optional 인자로 가지고 있습니다.(3) ((이 라인은 boost::lambda를 사용하여 다음과 같이 쓸 수 있습니다.
sv_t sv2(li.begin(), li.end(), _1 > _2);
)) 마지막으로 sorted_view의 template parameter는 실제 컨테이너의 iterator 타입입니다.(1) 여기서 template parameter를 바로 컨테이너 타입을 받을 수도 있었으나 다음과 같이 컨테이너가 아닌 일반 배열을 가지고도 사용할 수 있도록 iterator 타입을 받도록 했습니다.
int data[] = { 3, 0, 1, 4, 2 };
int const N = sizeof(data) / sizeof(data[0]);

sorted_view<int*> sv3(data, data + N);
for_each(sv3.begin(), sv3.end(), cout << _1 << " ");
cout << endl;

// output
// 0 1 2 3 4 
그럼 이제 sorted_view를 구현해 볼까요?
template <class Iter>
class sorted_view
{
  typedef Iter C_iter;
  typedef typename boost::iterator_value<c_iter>::type C_value_type;
  typedef boost::function<bool (C_value_type const&, C_value_type const&)> Compare;
public:
  sorted_view(C_iter first, C_iter last, Compare comp = std::less<c_value_type>())
      : comp_(comp) {
    using namespace boost::lambda;

    for (C_iter i = first; i != last; ++i) {
    data_.push_back(i);
  }

  std::sort(data_.begin(), data_.end(), bind(comp_, *_1, *_2));
}
private:
  std::vector<c_iter> data_;
  Compare comp_;
};
먼저 클래스는 세개의 typedef로 시작합니다. 이중 Compare는 비교를 위해 사용될 function object를 저장하기 위한 boost::function 타입입니다. 그리고 sorted_view의 생성자를 보면 이 Compare 인자의 default value는 std::less<> 임을 알 수 있습니다. 그리고 생성자의 body에서는 간단하게 먼저 입력된 iterator pair를 사용해서 vector를 만들고 이 vector를 사용해 sort()를 호출하고 있습니다. 여기서 data_의 value_type 자체가 C_iter이기 때문에 *_1과 *_2를 사용하여 C_iter 자체가 아닌 C_iter의 value_type, 즉 *C_iter 타입으로 sorting하고 있음을 알 수 있습니다. ((여기서 사용된 bind, _1, _2 같은 문법은 boost::lambda를 사용한 것입니다.)) 이제 sorting된 iterator의 vector를 가진 sorted_view가 완성되었습니다. 다음으로 할 일은 이 컨테이너에 begin()과 end()를 제공하여 다음과 같은 코드가 동작하도록 하는 것입니다.
for_each(xx.begin(), xx.end(), cout << _1 << " ");

for (i = xx.begin(); i != end(); ++i) {
cout << *i << " ";
}
그럼 다음과 같이 간단히 sorted_view가 가지고 있는 vector의 iterator를 사용자에게 주는 것은 어떨까요?
template <class Iter>
class sorted_view
{
  ...
  typedef typename std::vector::const_iterator const_iterator;

  const_iterator begin() const {
    return data_.begin();
  }

  const_iterator end() const {
    return data_.end();
  }
  ...
이 경우 위에서 살펴봤던 코드는 컴파일 에러가 발생합니다. 이유는 이 iterator의 value_type은 원래 컨테이너의 iterator이기 때문이죠. 따라서 위의 코드를 굳이 사용하겠다면 다음과 같이 수정해 주어야 합니다.
for_each(xx.begin(), xx.end(), cout << *_1 << " ");

for (i = xx.begin(); i != end(); ++i) {
  cout << **i << " ";
}
일반 컨테이너와는 iterator를 dereference하는 방법이 다르네요. 일반 컨테이너는 *를 하나만 쓰면 되지만 이 경우에는 두개의 *를 써주어야 합니다. 게다가 element의 멤버 함수를 -> 를 사용해서 부르려면 일반 컨테이너의 i->p() 와는 다르게 (*i)->p() 라고 써야 합니다.

이제 왜 iterator 클래스가 필요한지 확인했습니다. 이미 이번 글은 너무 길어졌네요. 다음 글에서 sorted_view의 iterator를 구현해 보도록 하겠습니다. ;-)

Comments

Popular posts from this blog

1의 개수 세기

저도 간단한 알고리즘 문제 하나... :-)

어떤 수 n이 주어졌을때 1~n까지의 수를 쭈욱 썼을때 나오는 1의 개수를 구하는 문제입니다.

예를 들어 13이라는 수가 주어지면 1~13까지의 수 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13에서 1은 1, 10, 11, 12, 13에 나오며 그 개수는 6이 됩니다. 즉, f(13)=6.

원래 문제는 f(n)=n이 되는 1이 아닌 가장 작은 수를 구하는 문제인데 이 문제의 경우에는 처음부터 쭈욱 세어나가면 되기 때문에 간단히 다음과 같이 구현을 하면 됩니다. ((한가지 주의할 점은 이전에 찾았던 n-1값을 사용하지 않고 다시 처음부터 n까지 값을 계산하면 시간이 너무 많이 걸린다는 점입니다. 위의 코드에서는 static 변수를 사용하여 이전 값에 계속 더해나가는 방법을 사용했습니다.))


#include

int count1(int n)
{
static int cnt = 1; // not 0 because n starts from 2. see main.

while (n > 0) {
if ((n % 10) == 1) ++cnt;
n /= 10;
}

return cnt;
}

int main()
{
using namespace std;

int n = 2;

while (count1(n) != n) ++n;
cout << n << endl;
}


좀 재미가 없죠? 그래서 이번 문제는 어떤 수 n에 대해서 f(n)을 O(1)시간에 구하는 알고리즘을 만드는 것입니다. 관심있으신 분들은 한번 풀어보세요. 제가 만든 코드는 내일 올려보겠습니다.

C++ of the Day #9 - Boost.Python 사용하기 #1

Python은 가장 인기있는 interpret 언어중의 하나입니다. Python의 장점 중 하나는 C/C++ 모듈과 쉽게 연동할 수 있다는 점입니다. 물론 손으로 일일히 wrapper를 만드는 것은 손이 많이 가고 에러를 만들수 있는 작업이나 SWIG등과 같은 도구를 사용하면 쉽게 python 모듈을 만들 수 있습니다.

Boost.Python은 이런 SWIG와 같이 python 모듈을 쉽게 만들 수 있도록 도와주는 라이브러리로 순수 C++만을 사용한다는 점이 SWIG와 다른 점입니다. 그리고 개인적으로는 Boost 라이브러리에 포함되어 있는 것들이 왠지 좀 더 믿음직스러워서... :-)

이번 글에서는 Boost.Python 문서에 나와 있는 예제를 가지고 간단하게 python 모듈을 만드는 방법에 대해서 알아보겠습니다.

Requirements리눅스
이 글에서는 리눅스 환경에서의 사용 방법을 설명한다.Boost.Python 라이브러리 (1.33.1)
Boost 라이브러리를 다운로드받아 아래와 유사한 명령으로 라이브러리를 빌드한다.
bjam -sTOOLS=gcc -with-python install

bjam의 --prefix 옵션으로 라이브러리가 설치될 위치를 변경할 수 있다.Python 라이브러리 (2.4.3)
Python을 다운로드 받아 빌드하여 설치한다.
위의 경우와 유사하게 configure의 --prefix 옵션으로 설치될 위치를 변경할 수 있다.

Write C++ Code다음과 같이 코드를 작성한다.

// greet.cpp #include <stdexcept> char const* greet(unsigned x) { static char const* const msgs[] = { "hello", "Boost.Python", "world!" }; if (x > 2) throw std::range_error("greet: index out of range"…

Hello Wordpress, again.

한 두주일 정도 Textpattern을 사용해봤는데 다시 Wordpress로 돌아오기로 결정했습니다. 무엇보다 스킨 변경이 너무 복잡하고 사용자층이 Wordpress에 비해 너무 앏네요. 원하는 plugin도 찾기 어렵고... :-|

그동안 Textpattern에 썼던 글들은 모두 Wordpress로 옮겼습니다. 2개 있던 댓글도 옮겼는데 그중의 하난 제가 쓴... ;-)

애초에 wp-dokuwiki plugin이 무거워서 옮겼던 것이라 이 plugin은 설치를 안할 예정인데 몇가지 아쉬운 점이 있네요.

첫째는 code highlighting 기능인데 이 기능은 예전에 만들어 놨던 것을 조금 수정해서 쓰려고 준비중입니다. 두번째는 Footnote 기능인데 찾아보니 Footnotes 0.9 Plugin for WordPress 2.0.x라는게 있네요.

이정도면 비록 wiki syntax에 비할바는 아니지만 쓸만할 것 같습니다. :-)