C++ of the Day #36 - Polymorphic Predicate

오랫만에 올리는 C++ of the Day입니다. :-)

Question

파일 리스트를 필터링하는 기능을 구현하려고 합니다. 필터링에는 다수의 필터가 사용되며 따라서 다음과 같이 구현하려고 합니다. ((이번 글은 STL algorithm member function problem을 가지고 작성되었습니다.))

struct Rule : std::unary_function {
  virtual result_type operator()(const argument_type&) const = 0;
};

// concrete rules are inherited from the Rule class and define the operator() 

typedef boost::shared_ptr  RulePtr;

vector filelist;
// ... fill filelist with a series of file names ...

for(vector::iterator iter = rules.begin(); iter != rules.end(); ++iter) {
  // This is the problem line...
  remove_if(fileList.begin(), fileList.end(), ??);
} 

이 기능을 제대로 구현하려면 어떻게 수정해야 할까요?

Answer

위의 코드는 크게 두가지 문제가 있습니다. 첫째는 remove_if함수의 선언을 보면 알 수 있습니다.

template 
ForwardIterator remove_if(ForwardIterator first, ForwardIterator last, Predicate pred);

여기서 Predicate의 model은 결국 Assignable임을 알 수 있습니다. 따라서 ?? 부분을 **iter와 같이 할 경우 remove_if의 Predicate template parameter는 Rule로 instantiation되며 Rule 클래스는 pure virtual로 Assignable하지 않으므로 에러가 발생합니다.

이를 방지하기 위해 Rule 클래스의 operator()를 다음과 같이 pure virtual이 아닌 default 구현을 제공하는 것으로 바꾼다면 어떻게 될까요?

struct Rule : std::unary_function {
  virtual result_type operator()(const argument_type&) const {
    return true;
  }
};

이 경우, 컴파일은 성공하나 틀린 결과가 나오게 됩니다. remove_if 함수안으로 Rule 클래스로 assign되면서 object slicing이 발생하기 때문입니다.

두번째 문제는 remove_if는 실제로 container안의 element들을 remove하지 못합니다. ((자세한 내용은 Effective STL의 Item 9. Choose carefully among erasing options을 참고하세요.)) 한쌍의 iterator만으론 이런 작업을 할 수 없기 때문이죠. 따라서 remove_if는 지워야 할 element들을 모두 뒤로 모은 다음 지워야 할 element들의 begin, 즉, 지워지지 않은 element들의 end를 리턴합니다.

그럼 이 두가지 문제를 수정해 볼까요? 제가 사용한 방법은 다음과 같습니다. 먼저 다음과 같이 간단한 RuleWrapper 클래스를 구현합니다. ((이 방법은 letter/envelope idiom이라고 할 수 있겠네요.))

class RuleWrap : public std::unary_function
{
public:
  RuleWrap(boost::shared_ptr impl) : impl_(impl) {
  }
  result_type operator()(const argument_type& arg) const {
    return (*impl_)(arg);
  }
private:
  boost::shared_ptr impl_;
};

boost::shared_ptr가 Assignable하기 때문에 이 클래스 역시 Assignable하게 되며 따라서 remove_if 안에서 사용이 가능합니다. 또한 slicing도 발생하지 않지요.

그리고 remove_if에서 다음 필터를 위해 사용될 end는 이전 remove_if에서 리턴된 iterator를 사용함으로써 두번째 문제를 해결할 수 있습니다. 다음 코드를 보세요.

typedef boost::shared_ptr  RulePtr;

rules.push_back(RuleWrap(boost::shared_ptr(new ConcreteRule)));
...

vector filelist;
// ... fill filelist with a series of file names ...

vector::iterator last = filelist.end();

for(vector::iterator iter = rules.begin(); iter != rules.end(); ++iter) {
  // This is the problem line...
  last = remove_if(fileList.begin(), last, *iter);
}

이제 filelist.begin()과 last 사이에 필터링된 파일 리스트가 들어 있습니다. 실제로 filelist에서 필터링에서 걸러진 element들을 삭제하려면 다음과 같이 vector의 erase() 함수를 사용하면 됩니다.

filelist.erase(last, filelist.end());

h2. Answer of the Boost Era

여기까지가 pre-boost 시대의 해결책이라고 한다면 이제 boost 시대의 방법을 알아보죠.

이제 Rule base class나 RuleWrap같은 방법은 모두 필요 없습니다. 우리에겐 boost::function이 있기 때문이죠. :-)

typedef vector > Rules_t;
Rules_t rules;

rules.push_back(ConcreteRule());

//  filtering
vector::iterator last = filelist.end();

for(Rules_t::iterator iter = rules.begin();
   iter != rules.end(); ++iter)
{
   last = remove_if(filelist.begin(), last, *iter)
}

filelist.erase(last, filelist.end());

물론 이 경우에 Rule들은 반드시 functor여야 할 필요가 없습니다. 일반 함수 포인터나 심지어 멤버 function도 가능하죠.

이 방법외에 이전에 구현해 보았던 dynamic_visitor나 mpl 라이브러리를 사용하는 방법, boost::bind를 사용하는 방법등이 있겠으나 여기선 boost::function이 가장 적당한 방법이라 생각되네요. :-)