[Effective STL] 43. 루프 vs 알고리즘

항목 43. 어설프게 손으로 작성한 루프보다는 알고리즘이 더 낫다

 

 

 

알고리즘은 루프

• 모든 알고리즘은 보통 최소 두 개의 반복자(시작 반복자, 끝 반복자)를 받는다.
• 즉, 내부적으로 보면 알고리즘은 루프이다.

class Widget
{
public:
    ...
    void redraw() const;
    ...
};


list<Widget> lw;
...
// 다음 작업은..
for(list<Widget>::iterator i = lw.begin() ; i != lw.end() ; ++i)
{
    i->redraw();
}
// 알고리즘으로 똑같이 할 수 있다.
for_each(lw.begin(), lw.end(), mem_fun_ref(&Widget::redraw));

 

 

 

루프보다 알고리즘이 나은 이유

• 효율(Effeciency)
  • 알고리즘은 프로그래머가 만든 루프보다 자주 훨씬 효율적이다.
• 정확성(Correctness)
  • 루프를 직접 작성하면 알고리즘을 호출하는 경우보다 에러가 일어나기 쉽다.
• 유지보수성(Maintainability)
  • 직접 만든 루프와 비교해서, 알고리즘은 훨씬 깨끗하고 간명한 코드로 만들어져 있는 경우가 많다.

 

 

 

효율과 정확성과 유지보수성

• 첫 번째 이점으로, 라이브러리 제작자가 컨테이너 구현 방식을 훨씬 잘 알기 때문에 컨테이너 횡단(traversal) 코드를 훨씬 효율적으로 구현한다.
• 두 번째 이점으로, 알고리즘은 훨씬 컴퓨터 공학적인(세련된) 알고리즘을 사용한다.
  • 사용자가 짜면, 반복자 무효화를 신경써야 하기까지 하다.

  • size_t fillArray(double* pArray, size_t arraySize);
    double data(maxNumDoubles);
    ... // data에 maxNumDoubles 수만큼의 값을 넣는다.
    
    deque<double> d;
    size_t numDoubles = fillArray(data, maxNumDoubles);
    
    // 사용자가 처음 작성한 코드
    for(size_t i = 0 ; i < numDoubles ; ++i)
    {
        d.insert(d.begin(), data(i) + 41); // d의 앞에 data[i] + 41을 계산한 값을 넣는다
        // 하지만.. d.begin()에 삽입하므로 역순으로 앞에 쌓이게 되는 버그가 있다.
    }
    
    // 그럼 사용자는 아래처럼 고칠 것이다.
    deque<double>::iterator insertLocation = d.begin();
    for(size_t i = 0 ; i < numDoubles ; ++i)
    {
        d.insert(insertLocation++, data[i] + 41); // 수정
        // 하지만, d.insert가 동작하면서 모든 반복자를 무효화시키므로
        // insertLocation++ 코드는 크래시를 발생시킨다..
    }
    
    // 결국 마지막 수정의 결과
    deque<double>::iterator insertLocation = d.begin();
    for(size_t i = 0 ; i < numDoubles ; ++i)
    {
        insertLocation = d.insert(insertLocation, data[i] + 41)
        ++insertLocation;
    }
    
    // 이 모든 과정이 아래보다 아름답진 않다.
    transform(data, data + numDoubles, inserter(d, d.begin(), bind2nd(plus<int>(), 41));

• 부가적인 이점으로, 루프에 비해 알고리즘이 반복자 호출 함수(begin, end)를 덜 호출한다.

  • for(list<Widget>::iterator i = lw.begin() ;
        i != lw.end() ; // 루프마다 계속 호출되는 반복자 호출 함수
        ++i)
    {
        i->redraw();
    }
    
    for_each(lw.begin(),
             lw.end(), // 단 한번만 호출된다.
             mem_fun_ref(&Widget::redraw));

  • 물론 이 함수들이 많이 호출됨을 알기 때문에 최대한 효율적으로 구현되어 있다.
  • 그렇지만 여러번 호출하는 것보다는 한번만 호출하는 게 더 효율적인 것은 분명하다.
• 알고리즘을 사용하면 직관적이지 않은 것은 사실이다.
  • transform을 사용한 위 예시에서도 bind2nd 같은 바인더를 바로 알아보고 이해하긴 보통은 힘들다.
  • 하지만, 루프 역시 무슨 일을 하는지 자세히 훑어봐야 하는 것은 동일하다.
  • 알고리즘은 이름만 보면 뭘 하는지 대충은 알아볼 수 있다.
  • 즉, 알고리즘은 이름이 자신의 동작을 그대로 말해 주지만, 루프문은 그렇지 않다.

 

 

 

루프가 알고리즘보다 명확할 수 있는 경우

vector<int> v;
int x, y;
...

// 원하는 값을 찾거나 v.end()를 가리키도록 한다.

// 루프로 처리
vector<int>::iterator i = v.begin();
for( ; i != v.end() ; ++i)
{
    if (*i > x && *i < y) break;
}

// 알고리즘으로 처리
// 명확성이 떨어진다..
vector<int> iterator i = find_if(v.begin(), v.end(), compose2(logical_end<bool>(),
                                                     bind2nd(greater<int>(), x),
                                                     bind2nd(less<int>(), y)));
                                                     
// 값 검사 로직을 분리하여 명확성을 늘린 알고리즘
// 템플릿을 굳이 만들어야 한다..
// find_if가 찾고자 하는 상세 사항이 해당 코드에 없다.
template<typename T>
class BetweenValues
{
public:
    BetweenValues(const T& lowValue, const T& highValue) : lowVal(lowValue), highVal(highValue)
    {}
    bool operator()(const T& val) const
    {
        return val > lowVal && val < highVal;
    }
private:
    T lowVal;
    T highVal;
};
...
vector<int> iterator i = find_if(v.begin(), v.end(), BetweenValues<int>(x, y));

// 모던 C++에서는 람다를 사용하여 이 약점을 극복할 수 있다.
// 체크 로직이 코드에 포함되며, 가독성이 있다.
vector<int> iterator i = std::find_if(v.begin(), v.end(), [x, y](const int& val)
{
    return val > x && val < y;
});