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를 구현해 보도록 하겠습니다. ;-)