작성일자

count, find, binary_search, lower_bound, upper_bound, 그리고 equal_range 를 제대로 파악해 두자.


1 count, find, binary_search, lower_bound, upper_bound, 그리고 equal_range 를 제대로 파악해 두자. #

위에 나열된 알고리즘들은 무언가를 찾으려고 할때 사용 가능한 것들이다. 우선 탐색범위를 알려주는 반복자쌍이 필요하다. binary_search, lower_bound, upper_bound, equal_range 는 정렬된 범위에 사용가능 하며 일반적으로 로그수행시간을 갖는다. 하지만 정렬된 범위가 아니라면 선형시간 알고리즘은 conunt, find 류의 알고리즘을 사용해야 한다.


1.1 정렬되지 않은 범위 #


1.1.1 count #


찾는값이 몇개 존재하는지 리턴. 

list<Object> lw;

…

if(count(lw.begin(), lw.end(), w)) {

    …

}
이런식으로 원하는 값이 존재하는지 판단할때 사용가능하다. 하지만 단지 존재하는지 만을 판단하고 싶을 경우 count는 값이 존재하더라도 몇개인지를 판단하기 위해서 끝까지 검색을 하므로 find를 사용하는것이 좋다.


1.1.2 find #


찾는값의 위치를 리턴. 없다면 end() 반복자를 리턴.
특정 범위에 원하는 값이 존재하는지를 비교하기 위해서 사용된다. 일반적으로 operator== 을 사용하며 find_if 를 사용하여 자신이 원하는 방식으로 비교하는 함수자를 사용하는 find 알고리즘을 사용할수 있다.
list<Object>::iterator i = find(lw.begin(), lw.end(), w);

if(i != lw.end()) {

    … // 컨테이너에 존재하는 경우

}
또한 count 와는 다르게 find의 경우는 리턴되는 반복자를 통해서 검색한 데이타의 위치를 알수 있다. 즉 범위의 끝 반복자(end반복자)와 같은 값이라면 해당 범위에 존재 검색 대상의 데이타가 존재하지 않는것이지만 끝 반복자가 아닐경우는 데이타가 존재하며 위치는 리턴된 반복자인 것이다.


1.2 정렬된 범위 #

특정 영역이나 컨테이너의 정렬은 EffectiveSTL31, EffectiveSTL34 를 참고하며 정렬에 필요한 비교 연산자에 관한 EffectiveSTL19 의 내용도 참고한다.


1.2.1 binary_search #

정렬된 범위에서 어떤 값이 존재하는지를 알아 보는데에 사용한다. C 라이브러리의 bsearch 와는 달리 binary_search는 값이 있는지 없는지만을 bool 값으로 리턴한다. 비교는 동등성 비교(operator==)를 사용.


1.2.2 lower_bound #

값을 찾는데 사용. 이 알고리즘은 원하는 값을 가진 객체의 첫째 사본의 위치를 리턴하던지 못찾았을 경우에는 그 값이 삽입될 적당한 위치를 가리키는 반복자를 리턴한다.
find 와 마찬가지로 lower_bound 의 리턴값이 원하는 값을 가리키고 있는지 검사를 해야 해당 범위안에 있는지 없는지를 판단할수 있다. 하지만 lower_bound는 상등성 비교를 하용하므로 주의할 점이 있다.
vector<Object>::iterator i = lower_bound(vw.begin(), vw.end(), w);

if( i != vw.end() && *i == w )

{

    // 찾은경우

}

else

{

    // 못찾은 경우

}
간단하게 생각할 경우 이런식으로 사용이 가능해 보이지만 상등성 검사이므로 operator== 를 이용해서 비교하면 문제가 생길수 있다.
상등성, 동등성에 대한 내용과 상등성 비교를 제대로 하기 위한 방법은 EffectiveSTL19 를 참조하도록 하자. 주의 할점은 lower_bound 가 사용한 비교함수와 결과검사시 사용하는 비교함수가 동일해야 한다는 점이다.(정렬할때 사용하는것도 동일해야 하지 않나?)


1.2.3 equal_range #

위의 lower_bound 가 복잡할 경우 equal_range 를 사용하도록 한다. equal_range는 반복자 쌍으로 구성된 pair 객체를 반환하는데, 첫째 반복자는 lower_bound가 반환하는 그것과 같고 둘째 반복자는 upper_bound가 반환하는 찾고자 하는 것과 동등한 값을 가진 범위의 끝의 바로 다음과 같다. 간단하게 동등한 범위를 나타내는 반복자를 리턴한다.
equal_range 의 사용하기 쉬운점은 리턴되는 두개의 반복자가 같은 값일 경우 찾을려고 했던 값이 존재하지 않는 다는 의미이다.
두번째로 distance 를 이용하여 두 반복자 사이의 거리를 구한다면 범위내의 객체의 개수를 얻을수 있다는 것이다.


1.2.4 upper_bound #

upper_bound는 위에서도 언급한 것처럼 lower_bound 와는 반대로 찾고자 하는 것과 동등한 값을 가진 범위의 끝(큰쪽)을 리턴하거나 그 값이 없다면 해당 값이 삽입되기 가장 적당한 위치를 리턴한다.
여때까지는 컨테이너에서 동일한 값을 찾는 경우를 예를 들었지만 사실 시간 같은 경우 특정 값보다 작게 되는 위치라던가 크게 되는 위치등을 찾기를 원할 경우가 있을수 있다. 이 경우 lower_bound, upper_bound 등을 사용하면 쉽게 처리가 가능하다.
Timestamp ageLimit;

…

vt.erase(vt.begin(), lower_bound( vt.begin(),  // vt에서 ageLimit 보다

                                vt.end(),      // 오래된 것을 모두 없앤다.

                                ageLimit));
만약 포함한 것을 없앨 경우
Timestamp ageLimit;

…

vt.erase(vt.begin(), upper_bound( vt.begin(),  // vt에서 ageLimit 보다

                                vt.end(),      // 오래되 거나 동등한

                                ageLimit));    // 것을 모두 없앤다.
또한 upper_bound는 동등한 값을 가진 것들을 삽입된 순서대로 저장되도록 할때 에서 쉽게 사용이 가능하다.
Object obect;

…

lp.insert(upper_bound(lp.begin(),          // newPerson 의 앞에 

                      lp.end(),            // 오든지 동당한 객체중 가장 마지막의

                      newPerson,           // 것 뒤에 newPerson을 삽입한다.

                      PersonNameLess()),

                      newPerson);

1.3 표준 연관 컨테이너 #

위의 lower_bound, equal_range, upper_bound 는 범위를 나타내는 두개의 반복자를 대상으로 모두 동작하며 시퀀스 컨테이너같은 경우 그대로 적용가능 하다. 하지만 연관 컨테이너의 경우는 비슷한 동작을 하는 자체적인 함수를 제공하며 당연히 그 함수들의 성능이 더욱 뛰어나다.
표준 연관 컨테이너에는 위에서 언급한 대부분의 알고리즘들이 존재하지만 binary_search 는 존재하지 않는다. 비슷한 동작을 위해서 count 를 사용할수 있다. 연속 컨테이너에서 처럼 count가 존재하는 모든 데이타를 검색한다고 생각할수 있지만 연관 컨테이너는 자체적으로 정렬되어 있는 형식이기 때문에 연속 컨테이너의 equal_range 처럼 효율적으로 동작하므로 안심하고 사용해도 좋다.


2 정리 #
















































우리가 궁금한것 사용할 알고리즘 사용할 멤버 함수
정렬되지 않은 범위 정렬된 범위 set 이나 map multiset 이나 multimap
원하는 값이 있는가? find binary_search count find
원하는 값이 있다면
첫번째 객체는 어디에?		 find equal_range find find 또는 lower_bound
원하는 값의 앞에 있지 않는 값을
가진 첫째 객체는 어디에 있나요?		 find_if lower_bound lower_bound lower_bound
원하는 값의 뒤에 있는 값을
가진 첫째 객체는 어디에 있나요? 		find_if upper_bound upper_bound upper_bound
원하는 값을 가진 객체는 몇개 인가요? count equal_range count count
원하는 값을 가진 객체는 모두 어디에 있나요? find(계속 호출) equal_range equal_range equal_range

작성일자

같은 이름을 가진 것이 있다면 일반 알고리즘 함수보다 멤버 함수가 더 낫다.

만약 컨테이너에 알고리즘을 적용할때 일반적인 알고리즘을 적용한다면 컨테이너의 특성을 고려하지 않고 동작하게 된다. 하지만 멤버함수의 경우 각 컨테이너의 구현 방식에 따른 동작을 수행하기 때문에 좀더 효율적인 수행을 할수 이다.

예를 들어 연관 컨테이너인 set에 아이템이 100만개 들어있고 find를 실행한다면 일반 알고리즘인 find는 순처적으로 검색해 나가는 반면 맴버함수인 find는 set의 기본을 이루고 있는 트리구조에 기반한 검색을 할것이다. 성능은 전자는 평균 50만. 최악의 경우 100만번의 비교가 필요하지만 후자는 최악이라 해도 40번 안쪽으로 종료가 가능하다.

또한 연관 컨테이너에서 비교에 근간을 이루고 있는 동등성과 상등성에 관한것도 일반 알고리즘을 적용시 동일하게 적용시키지 못한다.(EffectiveSTL19 참고)
게다가 map, multimap 같은 경우 일반적으로 키값만을 비교하기 원하겠지만 일반 알고리즘은 pair를 이루고 있는 아이탬 전체를 비교하여 결과값이 달라질수 있다.(물론 그걸 원할수도 있기는 하지만)

순차 컨테이너의 하나인 list의 경우 일반 알고리즘은 아이탬의 동작에 있어서 노드 단위의 복사를 수행하는 경우가 많지만 list 맴버함수는 포인터의 조작을 통해서 동작한다. 즉 효율성에서 차이가 나게 된다. 또한 동작 자체가 약간 다른 경우도 존재한다.
일반 알고리즘의 remove, remove_if는 실제로 삭제를 실행하지 않고 위치를 바꿀 뿐이며(EffectiveSTL32 참고) 실제 삭제를 위해서는 erase를 호출해야 하지만 list의 remove, remove_if, unique등의 함수는 자신이 실제로 객체를 삭제한다.

위와 같은 사실을 생각해 볼때 특정 알고리즘을 적용할 경우 컨테이너에서 제공하는 알고리즘이 존재한다면 그것을 사용하는 것이 바람직하다.

작성일자

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

알고리즘은 본질적으로 루프다.

class Object{

public:

    …

    void redraw() const;

    …

};


//…


list<Object> lw;


// 루프

for( list<Object>::iterator i=lw.begin(); i != lw.end(); i++ ){

    i->redraw();

}


// 알고리즘

for_each(lw.begin(), lw.end(), mem_fun_ref(&Object::redraw));
위의 코드와 같이 대부분 루프로 가능한 일은 알고리즘으로 구현이 가능하다. 하지만 몇가지 이유에서 가능하다면 알고리즘을 사용하는것이 더 좋을때가 많다. 이유는 대략 셋






  • 효율 : 알고리즘은 프로그래머가 직접만든 루프보다 일반적으로 더 효율적이다.
  • 정확성 : 루프를 직접작성하면 알고리즘보다 에러가 일어나기 쉽다.
  • 유지보수성 : 알고리즘이 좀더 깨끗하며 간결한 코드로 작성된다.




우선 효율면에서 어째서 알고리즘이 더 좋은지를 살펴보면 루프에서 자주 호출되는 lw.end() 같은 반복자 관련 함수 호출을 생각할수 있다. 우선 이런 불필요한 함수 호출을 알고리즘 내에서는 최대한 줄이고 있다.
또한 알고리즘 자체가 STL을 만든 사람에 의해서 만들어졌으므로 좀더 STL의 구현 원리와 코드를 직접적으로 사용할수 있다. 게다가 일반 프로그래머가 따라가기 힘든 훨씬 세련된 컴퓨터 공학적인 코드로 구현되어 있다.(연속메모리 컨테이너에서 몇개의 객체를 제거하는 등의 평범한일(erase-remove 합성)조차 알고리즘이 더 효율적이라 한다.)

정확성에 관한것은 책참조
배열에 있는 값을 41씩 더해서 deque에넣는 작업을 루프와 알고리즘으로 구현.
간단히 요약하면 반복자 무효화에 대한 처리, 삽입 위치 처리, 기타 등등 루프에서 처리할게 많다! 라는 내용임
EffectiveSTL09, EffectiveSTL30 참조.

유지보수 및 명확성은 코드레벨에서 얼마나 알아보기가 쉬운가에 대한 내용이다. 즉 알고리즘은 알고리즘 이름만으로 대충 어떤 역할을 하는지 알수 있지만 루프는 루프의 코드를 보고 내용을 파악해야만 한다는 것이다.

물론 위의 내용은 상황에 따라 달라질수 있다. 알고리즘으로 구현하기 위해서는 어댑터등을 비비꼬아 사용해야 하지만 루프로는 간단히 구현 가능하다면 루프가 좋은 선택이다. 하지만 대부분의 경우에서 성능이나 명확성에 있어 알고리즘이 좀더 우위에 있다고 한다.

작성일자

less는 operator< 의 의미임을 꼭 알아두자

특정 객체에 무게와 속도라는 두가지 맴버변수가 있다고 가정하자.

bool operator<(const Object& lhs, const Object& rhs)

{

    return lhs.weight() < rhs.weight();

}
으로 operator<가 구현되어 있다고 할때 map, set을 사용한 map<Object>의 정렬 기준역시 operator< 를 사용한다. 즉 less<Object>는 bool operator<(const Object& lhs, const Object& rhs)를 사용한다. 라고 할수 있다.
그런데 map의 정렬기준을 무게가 아닌 속도로 정하고 싶다면 어떻게 해야 할까?
위에서 less<Object>를 언급했기 때문에
template<>

struct std::less<Object> : public::std::binary_function<Object,Object,bool>

{

    bool operator()(const Object& lhs, const Object& rhs) const

    {

        return lhs.Speed() < rhs.Speed();

    }

};
으로 less 객체를 템플릿 한정(specialize)하는 방법을 생각할수 있지만 위의 방법은 정상적으로 동작하지 않는 경우가 생길수 있다. 일반적으로 std내의 STL 컴포넌트를 수정하는 일은 금지 되어 있다.
(책에 less를 한정시켜 사용하는 경우로 스마트포인터 관련 예제가 나온다. 이 경우는 operator< 와 다른 동작을 취하도록 수정한것이 아닌 진찌 포인터 값처럼 동작하게 수정해준것에 불과하다.)
위의 방법은 C++프로그래머가 일반적으로 생각하는 less는 operator<와 동일하다고 생각하는 가정을 져버린다.

그런가?

사실 STL에서 map등의 정렬 기준을 바꾸는 일은 간단히 함수 객체를 만들어 map의 템플릿 인자로 넘겨주면 간단히 구현가능하다.
struct SpeedCompare :

    public binary_function<Object, Object, bool>

{

    bool operator()(const Widget& lhs, const Widget& rhs) const

    {

        return lhs.Speed() < rhs.Speed();

    }

};


//…


multiset<Object, SpeedCompare> objects;

less는 반드시 operator<의 의미를 갖도록 하자.

작성일자

ptr_fun, mem_fun, mem_fun_ref 의 존재에는 분명한 이유가 있다.

컨테이너에 for_each 를 적용시키는 상황을 생각해보자.

void test(Widget& w);    // Widget에 대해 적용되는 전역함수

…

vector<Widget> vw;      // Widget 컨테이너

…

for_each(vw.begin(), vw.end(), test);
함수객체로 실행하지 않는 경우 위와 같은 형태의 코드가 만들어 질것이다. 간단하게 생각해 볼때 for_each는
template<typename InputIterator, typename Function>

Function for_each(InputIterator begin, InputIterator end, Function f)

{

    while( begin != end ) f(*begin++);

}
와 같은 형태로 수행된다. 즉 전역함수 test를 넘긴것이나 함수객체의 operator()를 오버라이드 해서 넘기는 형태인 function(item) 의 수행을 한다. 물론 당연해 보이는 구현이고 당연한 소리같다.
하지만 for_each를 사용해서 함수를 적용시킬때 전역함수나 함수객체가 아닌 클래스의 맴버함수를 적용시키고 싶다면 어떻게 해야 할까?
이때 사용할수 있는 것이 mem_fun_ref라는 함수 어뎁터이다.
// Widget 에 test라는 맴버함수가 있다고 하자

// for_each로 컨테이너의 모든 항목에 test를 적용하고 싶다.

list<Widget> lw;

…

for_each(lw.begin(), lw.end(), mem_fun_ref(&Widget::test) );
위와 같은 코드를 쓸수 있다. 즉 mem_fun_ref는 x.test() 로 호출되는 함수 형태를 test(x)로 호출가능한 형태로 바꿔주는 역할을 하는 것이다.(자세한 내용은 책참조..)
그렇다면 x->test() 는?? 즉 컨테이너가 객체의 포인터를 가지고 있는데 맴버함수를 적용시키고 싶다면 어떻게 해야 할까? 이럴때 쓰는것이 mem_fun 어뎁터이다.
// Widget 에 test라는 맴버함수가 있다고 하자

// for_each로 컨테이너의 모든 항목에 test를 적용하고 싶다.

list<Widget*> lpw;

…

for_each(lpw.begin(), lpw.end(), mem_fun(&Widget::test) );

ptr_fun의 경우는 EffectiveSTL40에도 언급되었는데 언제쓰고 언제쓰는지 헷갈린다면 함수객체가 아닌 함수포인터를 넘길경우는 모두 사용한다고 생각하면 편하다.

추가로 mem_fun 과 mem_fun_ref 의 어뎁터 이름이 이해하기 힘들게 정해진 이유는 책참조.

정리하자면









  • f(x) 형태의 함수 f를 컨테이너 전체등 STL 컴포넌트에서 사용할경우
    -> 그냥 사용하거나 ptr_fun(f) 로 넘길것

  • x.f() 형태인 맴버함수를 컨테이너 전체등 STL 컴포넌트에서 사용할경우
    -> mem_fun_ref(&CALSS::f) 로 넘길것

  • x->f() 형태로 호출될 포인터의 컨테이너에 적용될 맴버함수를 컨테이너 전체등 STL 컴포넌트에서 사용할경우
    -> mem_fun(&CLASS::f) 로 넘길것

작성일자

함수자 클래스는 어댑터 적용이 가능하게(adaptable) 만들자.

list<Widget*> widgetPts;

bool isInteresting(const Widget* pw);
위와 같은 컨테이너와 함수가 있을때 find 알고리즘을 이용해서 isInteresting가 true를 반환하는 Widget 포인터 객체를 찾을수 있다.
list<Widget*>::iterator i = find_if( widgetPtrs.begin(),

                                    widgetPtrs.end(),

                                   isInteresting);

if( i != widgetPtrs.end() )

{

    ….

}
만약 not1 어댑터를 적용하여 isInteresting가 false를 반환하는 첫번째 포인터 값을 얻기 위해서는
list<Widget*>::iterator i = find_if( widgetPtrs.begin(),

                                    widgetPtrs.end(),

                                    not1(isInteresting));
으로 적용할수가 없다. isInteresting는 not1 이 필요로하는 typedef 문을 제공하지 않기 때문이다. 위의 코드는
list<Widget*>::iterator i = find_if( widgetPtrs.begin(),

                                    widgetPtrs.end(),

                                    not1(ptr_fun(isInteresting)));
으로 수정하여 정상적으로 수행이 가능하다. 즉 ptr_fun은 어댑터의 적용이 가능하도록 typedef를 정의해주는 역할을 하는 것이다.
STL의 4대 표준 함수 어댑터(not1, not2, bind1st, bind2nd)는 모두 특정 typedef가 있어야 하고 STL과 호환하는 비표준 어댑터 역시 마찬가지이다. 어댑터에서 요구하는 typedef를 제공하는 함수객체를 어댑터 적용이 가능하다 라고 표현하며 ptr_fun 은 일반 함수 포인터를 어댑터 적용이 가능한 상태로 바꾸어 주는 역할을 하는 것이다.

일단 어뎁터를 직접만드는 내용은 패스.
어쨋거나 이런 어뎁터를 적용가능한 함수객체를 만드는 방법은 직접 typedef를 써서 만들면 피곤하므로 특정 탬플릿을 상속받아 만들면 된다. 바로 std::unary_function과 std::binary_function 이다.
template<typename T>

class MeetsThreshold : public std::unary_function<Widget, bool>{

private:

    const T threshold;

public:

    MeetsThreshold(const T& threshold);

    bool operator()(const Widget&) const;

    ….

};


struct WigetNameCompare : std::binary_function<Widget,Widget,bool>

{

    bool operator()(const Widget& lhs, const Widget& rhs) const;

};
위의 코드에서 볼수 있듯이 상속하는 unary_function, binary_function 의 탬플릿 매개변수가 상속받는 함수객체의 operator() 함수의 매개변수와 리턴하는 변수형이다.
WigetNameCompare가 구조체인 이유는 일반적으로 내부 상태 데이터가 없는 함수객체의 경우 구조체로 선언하는 것이다.
그리고





binary_function<Widget,Widget,bool>
bool operator()(const Widget& lhs, const Widget& rhs) const;

에서 보는것 처럼 unary_function, binary_function 는 operator()가 받는 매개변수의 타입이 비포인터 타입인 경우 const 와 참조자 표시는 빼는것이 상례이다.
ex) const Widget& -> Widget

그런데 operator()가 포인터를 매개 변수로 받는 경우에는 unary_function, binary_function 의 템플릿 매개변수와 operator()의 매개변수 타입이 동일하다.
struct PtrWidgetNameCompare:

    std::binary_function<const Widget*, const Widget* bool>{

    bool operator()(const Widget* lhs, const Widget* rhs) const;

};

어쨋거나 결론은 함수객체를 만들때는 위와 같은 클래스를 상속받아 어뎁터적용이 가능한 객체를 만드는것이 요긴하다 라는 것이다.

작성일자

술어 구문은 순수 함수로 만들자


  • 술어구문(predicate)이란 bool값을 반환하는 함수를 말한다.
    ex) find_if의 매개변수인 함수 등등

  • 순수 함수란 이 함수가 반환하는 값이 그 함수의 매개변수에 종속된 함수이다.
    ex) f가 순수함수고 x, y 가 객체일때 f(x,y) 의 반환값은 x나 y의 값이 바뀔때만 변한다.

  • 술어 구문 클래스 란 operator()가 술어 구문인 클래스를 말한다.
EffectiveSTL38에 의하면 함수 객체는 값으로 전달되기 때문에 유의 해야 할 사항이 있다. 왜냐 하면 알고리즘에 함수 객체를 넘기면 알고리즘 내부에서도 다른 알고리즘을 호출함으로써 함수객체가 또 다시 복사되는 일이 일어날수 있기 때문이다.
즉 함수객체에 맴버변수가 있고 이 변수를 초기화 하여 알고리즘에 넘겼을때 알고리즘이 실행되는 중간에 이 변수가 변하고 그것이 결과에 영향을 미치는 것일 경우 알고리즘 내부에서 함수객체의 복사가 어디서 몇번이루어 지는지 알수 없기 때문에 문제가 발생할수 있다.

이 문제는 술어구문 클래스의 operator()를 const로 만듬으로써 어느정도 예방이 가능하지만 const 맴버함수라고 해도 이것저것(책참조)에 접근이 가능하며 값을 바꿀수 있기 때문에 순수 함수로 만들어야 하는 것이다.

자세한 코드는 책참조.

작성일자

함수자 클래스는 값으로 전달되도록 설계하자

STL의 함수 객체는 일반적으로 값으로 전달(복사) 된다. 하지만





for_each<vector<Object>::iterator, DoSomething&>(vi.begin(), vi.end(), d);

와 같이 참조를 명시적으로 선언하는 것도 불가능 한것은 아니다. 문제는 제품에 따라서 이런 코드가 컴파일이 되지 않을 수도 있다는 것이다.
함수 객체를 값으로 전달하는 방식 때문에 다형성을 구현하기 어려워 지는 단점이 있지만 이것은 프록시 클래스로 극복이 가능하다.


// 실제 구현부 함수

template<typename T>

class BPFCImpl{

private:

        Widget w;

        int x;

        …


        virtual ~BPFCImpl();

        // 다형성으로 구현된 함수

        virtual void operator()(const T& val) const;

        // 프록시 클래스가 접근가능하게 한다.

        friend class BPFC<T>

};


// 프록시 클래스

template<typename T>

class BPFC: public unary_function<T, void>

{

private:

        BPFCImpl<T> *pImpl;


public:

        void operator()(const T& val) const

        {

                // 실제 구현객체를 호출한다.

                pImpl->operator()(val);

        }

};
크기가 작고 단형성을 유지하면서 많은 데이터의 접근이 가능하며 다형성을 구현할수 있는 방식이다. 위의 방식은 GOF에서 브릿지패턴(BridgePattern)으로 불리고 있다.

위의 내용은 상당히 간략히 구현된 내용이다. 추가적으로 BPFCImpl에 참조카운팅에 관련된 내용과 BPFC의 복사 생성자에 관한 구현 내용을 좀더 고민해 봐야 한다.

작성일자

범위 내의 데이터 값을 요약하거나 더하는 데에는 accumulate 나 for_each를 사용하자

STL 에서는 아래와 같이 특정 범위에 대한 연산을 준비해 놓고 있다.














count 범위 내의 요소 개수를 센다.
count_if 조건에 맞는 요소 개수를 센다.
min_element 범위내의 최소값을 얻는다.
max_element 범위내의 최대값을 얻는다.

하지만 위의 네가지 알고리즘 보다 좀더 융통성 있는 무언가를 해야 할 경우가 있다. 이 경우 accumulate 나 for_each 를 사용 할수 있다. 예를 들어 double 형 리스트의 총합을 알고 싶을 경우 accumulate를 아래와 같이 사용할 수 있다.
list<double> ld;

….

double sum = accumulate(ld.begin(), ld.end(). 0.0);
와 같은 형태로 쓸수 있다. (마지막 인자인 초기값에 주의. 0으로 초기값을 줄 경우 accumulate는 내부적으로 int형으로 동작되어 double 형의 값이 잃어버릴수 있다.) 위와 같은 수치형에서의 간단한 누적 합이외에 특정 클래스의 컨테이너 범위에서 클래스의 요약정보를 얻기 위해서도 사용이 가능하다.
예를 들어 컨테이너 안에 들어있는 string 객체의 문자열 길이의 합을 계산하는데 사용가능하다.
string::size_type

stringLengthSum(string::size_type sumSoFar, const string& s)

{

    return sumSoFar+s.size();

}
stringLengthSum은 accumulate가 받아들이는 요약용 함수의 전형이다. 이 함수는 바로 전까지 요약된 값과 현재의 요소를 받아 들여서 새 요약값을 반환한다. 즉 컨테이너안의 string 사이즈의 요약 정보를 얻을때 string::size_type sumSoFar는 이전 까지의 항목까지의 요약 정보고 현재 항목의 string 객체를 받는다. 그리고 다시 요약한 정보를 리턴한다.
set<string> ss;

…

string::size_type lengthSum =

   accumulate(ss.begin(), ss.end(), 0, stringLengthSum);
위와 같은 식으로 사용이 가능하다. 범위 내의 수를 곱하는 것은 더욱 쉽다. STL에 해당 함수가 존재하기 때문이다.
vector<float> vf;

…

float product =

   accumulate(vf.begin(), vf.end(), 1.0, multiplies<float>() );
(곱셉연산이기 때문에 1.0 으로 시작한다.)
사용자 클래스에 대한것 역시 가능하다.
// 사용자 클래스

struct Point{

    Point(double initX, double initY): x(initX), y(initY) {}

    double x,y;

}


// 적용될 함수자. 자세한 내용은 EffectiveSTL40을 참조

class PointAverage : public binary_function<Point, Point, Point> {

public:

    PointAverage() : xSum(0), ySum(0), numPoints(0) {}

   const Point operator() (const Point& avgSoFar, const Point& p)

   {

        ++numPoints;

        xSum += p.x;

        ySum += p.y;

        return Point(xSum/numPoint, ySum/numPoint);

   }


private:

   size_t numPoints;

   double xSum;

   double ySum;

};


// 실제 사용예

list<Point> lp;

…

Point avg =

    accumulate(lp.begin(), lp.end(), Point(0,0) PointAverage());
PointAverage는 자인이 계산에 사용한 Point객체의 개수와 x,y 좌표의 합을 내부적으로 유지해 가며 동작한다. 하지만 위의 PointAverage은 표준안의 26.4.1절의 두번째 단락의 내용인 accumulate에 넘겨지는 함수의 부가적 효과는 없어야 한다에 어긋나는 클래스이다.(실질적으로 문제가 생기지는 않지만 어쩌면 정의되지 않는 동작이 일어날수 있다고 한다.)
위의 문제를 해결하기 위해 for_each를 사용할 수 있다. 이 알고리즘은 범위 내의 데이터를 요약할 수 있는 알고리즘이면서 accumulate가 가진 제한을 받지 않는다. for_each는 범위와 그 범위 내의 요소에 대해 호출할 함수를 받아들이는데, 이 알고리즘에 넘겨지는 함수는 자신이 처리할 단 하나의 요소만을 받아들이며, for_each는 자신의 수행을 마칠때 이 함수의 사본을 반환한다. 


// EffectiveSTL 40 참조

class PointAverage : public unary_function<Point, void> {

public:

    PointAverage() : xSum(0), ySum(0), numPoints(0) {}

    void operator()(const Point& p )

    {

        ++numPoints;

        xSum += p.x;

        ySum += p.y;

    }


    Point result() const

    {

        return Point(xSum/numPoints, ySum/numPoints);

    }


private:

   size_t numPoints;

   double xSum;

   double ySum;

};


// 사용예

list<Point> lp;

…

Point avg = for_each(lp.begin(), lp.end(), PointAverage()).result();

작성일자

copy_if를 적절히 구현해 사용하자

STL에는 여러가지 copy 알고리즘을 제공하지만 copy_if 는 존재하지 않는다. 즉 원하는 것만을 복사를 하는 알고리즘은 직접 구현해야 한다. 


template< typename IIter

        typename OIter,

        typename Predicate>

OIter copy_if(IIterbegin,

                IIter end,

                OIter destBegin,

                Predicate p)

{

        while(begin != end)

        {

                if( p(*begin) ) *destBegin++ = *begin;

                ++begin;

        }

        return destBegin;

}

대략 이런 코드로 구현할수 있다고 한다.