Skip to main content

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

자. 그럼 지난 번 글에 이어 boost::iterator 라이브러리를 사용하여 sorted_view의 iterator를 구현해 보겠습니다.

먼저 sorted_view의 내부 구현에는 vector가 사용되었으므로 sorted_view의 iterator도 random access traversal iterator로 구현하겠습니다. 한가지 주의할 점은 sorted_view는 const_iterator만 제공하고 iterator는 제공하지 않는다는 점입니다. 이유는 sorting된 컨테이너의 iterator를 가지고 값을 변경하면 그 컨테이너는 더이상 sorting되지 않은 상태가 될 수 있기 때문입니다. ((std::set이나 std::map의 키가 const 타입인 이유와 같습니다.))

이 두 가지를 염두에 두고 우리가 사용할 boost::iterator_facade에 대해서 살펴보죠. 먼저 이름에서 Facade design pattern을 사용했다는 것을 알 수 있습니다. 즉, 여러 subsystem들의 복잡성을 좀 더 사용하기 쉬운 하나의 인터페이스로 감추어 주는 역할이라는 것이죠.

iterator_facade 클래스의 선언을 보면 다음과 같습니다.
template <
  class Derived
  , class Value
  , class CategoryOrTraversal
  , class Reference  = Value&
  , class Difference = ptrdiff_t
>
class iterator_facade {
...
여기서 Derived는 iterator_facade를 상속받는 iterator 클래스 자신입니다. ((즉, iterator_facade는 CRTP를 사용합니다.)) Value는 iterator가 사용할 value_type이고 CategoryOrTraversal은 이름 그대로 iterator가 지원하기를 원하는 category를 지정합니다. 나머지 Reference와 Difference는 이름에서 그 용도를 알 수 있으며 대개의 경우 default 값인 Value&와 ptrdiff_t를 그대로 사용할 수 있습니다.

따라서 우리가 만들 sorted_view의 iterator는 다음과 같이 시작하며 sorted_view 클래스의 nested class로 만들어 집니다.
class sv_iterator
  : public boost::iterator_facade<
    sv_iterator,
    C_value_type const,
    boost::random_access_traversal_tag
    >
{
  typedef typename std::vector<c_iter>::const_iterator S_const_iter;
public:
  explicit sv_iterator(S_const_iter p)
    : curr_(p) {}
private:
  S_const_iter curr_;
};
먼저 sv_iterator가 내부적으로 사용할 iterator 타입을 S_const_iter라는 이름으로 typedef 하였습니다. 여기서 C_iter나 C_value_type과 같은 타입은 sorted_view 클래스에 있는 typedef들입니다. 여기서 눈여겨 볼 부분은 Value 인자로 C_value_type **const**가 사용되었다는 점입니다. 따라서 이 iterator는 value를 변경할 수 없는 const_iterator가 됩니다.

sv_iterator은 S_const_iter 타입으로 curr_라는 멤버 변수를 가지고 있으며 생성자는 단순히 이 값을 받아 채워주는 역할을 합니다.

그럼 이제 중요한 iterator들의 여러 기능들을 구현할 차례입니다. 우리가 구현하고자 하는 random access traversal iterator는 많은 요구 사항들이 있습니다. 그 중 몇 가지만 예로 들면 다음과 같습니다.
  • *i
  • (*i).m
  • i->m
  • i == j
  • ++i
  • i + n
  • i < j

  • ...

이렇게 많은 원래의 요구 사항들을 다 구현하는 대신 boost::facade는 다음 중 해당하는 iterator의 category에 꼭 필요한 함수만을 구현할 것을 요구합니다. facade라는이름이 붙은 이유입니다.
  • dereference
  • equal
  • increment
  • decrement
  • advance
  • distance_to
이름만 봐도 대충 어떤 일을 하는 함수인지 알 수 있죠? 우리의 sv_iterator는 random access traversal iterator이기 때문에 이 함수들을 모두 구현해햐 하지만 만약 구현하는 iterator가 forward traversal iterator라면 이 중 1, 2, 3번만 구현하면 됩니다. 하지만 이 함수들을 구현하려고 하면 한가지 문제가 생깁니다. 만약 이 함수들을 모두 public으로 선언한다면 iterator의 사용자들이 이 함수들을 직접 부르는 것이 가능해진다는 점이죠. 그렇다고 private으로 하자니 이번엔 iterator_facade에서 이 함수들을 사용할 수 없게 됩니다. 따라서 이 두마리 토끼를 모두 잡기 위해 다음과 같은 back door를 설치합니다.
private:
  friend class boost::iterator_core_access;
잠시 생각해 보시면 이 하나의 클래스에 권한을 주어 어떻게 여러개의 함수를 사용할 수 있게 하는지 알 수 있습니다. ((iterator_core_access 클래스는 대략 다음과 같은 구조를 가집니다.
class iterator_core_access
{
public:
  template <class Facade>
  static typename Facade::reference dereference(Facade const& f)
  {
    return f.dereference();
  }
};
간단히 설명하자면 iterator_core_access는 sv_iterator의 friend이므로 f.dereference()와 같이 sv_iterator의 private 함수를 호출할 수 있게 되며 iterator_core_access의 dereference는 public 함수이므로 iterator_facade에서도 호출할 수 있게 되어 결국 iterator_facade에서 원하는 sv_iterator의 private 함수를 호출할 수 있게 되는 것입니다. 실제 코드에선 이 iterator_core_access의 생성자는 private으로 되어 있고 iterator_facade를 friend로 지정해 iterator_facade에서만 이 클래스를 생성할 수 있도록 추가 안전 장치를 가지고 있습니다.)) 그럼 이제 위의 함수들을 하나씩 구현해 볼까요? 우린 이미 vector의 iterator 타입을 가지고 있기 때문에 모든 함수를 다음과 같이 쉽게 vector의 iterator에게 작업을 forwarding하여 구현할 수 있습니다.
void increment() { ++curr_; }
void decrement() { --curr_; }

void advance(typename sv_iterator::difference_type n) {
  std::advance(curr_, n);
}

typename sv_iterator::difference_type distance_to(sv_iterator const& to) const {
  return std::distance(curr_, to.curr_);
}

bool equal(sv_iterator const& other) const
{
  return curr_ == other.curr_;
}

C_value_type const& dereference() const {
  return **curr_;
}
여기서 vector의 iterator로 그냥 forwarding하여 구현하지 않은 함수는 deference함수 하나입니다. 왜냐하면 우리는 sv_iterator를 가지고 바로 실제 컨테이너의 element를 dereference하기를 원하기 때문입니다. 따라서 첫번째로 C_iter를 얻고 이를 가지고 다시 C_value_type을 얻기 위해 **과 같이 dereference operator를 두 번 사용하였습니다. 그럼 이 sv_iterator 클래스를 사용하여 sorted_view에 begin(), end()함수를 만들어 보겠습니다.
typedef sv_iterator const_iterator;

const_iterator begin() const {
  return sv_iterator(data_.begin());
}
const_iterator end() const {
  return sv_iterator(data_.end());
}
간단하죠? :-) 전체 소스 코드는 Downloads 부분에 있습니다. 다음 시간에는 이러한 iterator 구현을 좀 더 간단히 할 수 있는 방법에 대해 알아봅니다. 지금도 충분히 간단한 것 같은데 말이죠. ;-)

Downloads

iterator_ex.zip

Comments

  1. 트랙백 주소가 없어서, 알려 드릴수가 없었습니다. 약간 저에게는 어렵네요. 내공 쌓고 들려서 이해하겠습니다.

    ReplyDelete
  2. 찾기힘든 부스트 관련 유용한 글 작성해주셔서 감사드립니다. 앞으로도 부스트 관련 지식 많이 부탁드립니다.

    ReplyDelete

Post a Comment

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

std::map에 insert하기

얼마전 회사 동료가 refactoring한 코드를 열심히 revert하고 있어서 물어보니 다음과 같은 문제였습니다. 원래 코드와 refactoring한 코드는 다음과 같더군요. nvp[name] = value; // original code nvp.insert(make_pair(name, value)); // refactored 아시겠지만 위의 두 라인은 전혀 다른 기능을 하죠. C++03에 보면 각각 다음과 같이 설명되어 있습니다. 23.1.2/7 Associative containers a_uniq.insert(t): pair<iterator, bool> inserts t if and only if there is no element in the container with key equivalent to the key of t. The bool component of the returned pair indicates whether the insertion takes place and the iterator component of the pair points to the element with key equivalent to the key of t. 23.3.1.2/1 map element access [lib.map.access] T& operator[](const key_type& x); Returns: (*((insert(make_pair(x, T()))).first)).second. 원래 코드는 매번 새 값으로 이전 값을 overwrite했지만 새 코드는 이전에 키가 존재하면 새값으로 overwrite하지 않습니다. 따라서 원래 기능이 제대로 동작하지 않게 된것이죠. 그래서 물어봤죠. "왜 이렇게 했어?" "insert가 성능이 더 좋다 그래서 했지." :-? 사실 Fowler 아저씨는 Refactoring 책에서 refactoring은 성능을 optimizing하기 위한 것이 아니다라

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("