STL Tips
dll + STL
dll 에서 hash_set 을 멤버로 가진 클래스를 만들려다가 nested class 인 _Hash 라든지 hash_compare 등등을 모두 dllexport 하라길래 포기하고 PIMPL 패턴으로 해결해야만 했다.
boost::lambda
아래의 mem_fun_if 류와 비슷한 역할을 하는 것이 바로 boost::lambda 라이브러리다. 일단 아래처럼 포인터 컨테이너를 순회하면서 NOT NULL 일 경우에 특정 멤버 함수를 호출하는 예제를 살펴보자.
for_each(l.begin(), l.end(), if_then(_1 != constant((A*)NULL), bind(&A::print, _1)));
lambda 라이브러리를 사용하면 위와 같이 간단한 코드로 표현이 가능하다. 대신 컴파일 속도는... ㅠㅠ
mem_fun_if
일반적으로 포인터 컨테이너를 순회하면서 특정 조건을 만족할 경우 멤버 함수를 호출하는 패턴을 위한 자작 adapter function 이다. (물론 const 버전과 파라미터 1개를 받는 버전, 합쳐서 총 4개의 클래스와 4개의 함수를 만들어야 하지만... 시간상 생략)
template<class _Pred, class _Result, class _Ty>
class mem_fun_if_t : public unary_function<_Ty *, _Result>
{
public:
explicit mem_fun_if_t( _Pred pred, _Result (_Ty::*_Pm)())
: _pred(pred), _Pmemfun(_Pm), _count(0)
{
}
// 단점이라면 멤버함수의 리턴값은... 도무지 캐치불가능...
bool operator()(_Ty *_Pleft) const
{
if ( _pred(_Pleft) )
{
((_Pleft->*_Pmemfun)());
_count++;
return true;
}
return false;
}
int count() const { return _count; }
private:
_Pred _pred; // predicate
_Result (_Ty::*_Pmemfun)(); // the member function pointer
mutable int _count;
};
template<class _Pred, class _Result, class _Ty>
inline
mem_fun_if_t<_Pred,_Result, _Ty>
mem_fun_if(_Pred pred,_Result (_Ty::*_Pm)())
{
return (mem_fun_if_t<_Pred,_Result, _Ty>(pred,_Pm));
}
이를 이용한 샘플이다.
using namespace std;
class A
{
public :
explicit A( const string & s ): str(s) {}
void print() { cout <<str <<endl; }
string str;
};
#define not_null(T) bind2nd( not_equal_to<T*>(), (T*)0)
int _tmain(int argc, _TCHAR* argv[])
{
list<A*> l;
l.push_back( new A("Hello") );
l.push_back( NULL );
l.push_back( new A("World") );
l.push_back( NULL );
l.push_back( new A("!") );
for_each( l.begin(), l.end(), mem_fun_if( bind2nd( not_equal_to<A*>(), (A*)0 ), &A::print ) );
for_each( l.begin(), l.end(), mem_fun_if( not_null(A), &A::print ) );
return 0;
}
if_not_null
다음은 포인터 컨테이너에서 NOT NULL 인 갯수를 찾는 코드이다.
count_if( l.begin(), l.end(),
bind2nd( not_equal_to<A*>(), (A*)0 ) );
ptr_fun and not1, not2
ptr_fun 은 말 그대로 pointer to function 이다.
template<class Arg, class Result>
pointer_to_unary_function<Arg, Result>
ptr_fun(Result (_*pfunc)(Arg));
template<class Arg1, class Arg2, class Result>
pointer_to_binary_function<Arg1, Arg2, Result>
ptr_fun(Result (_*pfunc)(Arg1, Arg2));
not1 은 unary_function 의 negate 이며, not2 는 binary_function 의 negate 이다.
template<class UnaryPredicate>
unary_negate<UnaryPredicate> not1(
const UnaryPredicate& _Pred
);
template<class Predicate>
class unary_negate
: public unary_function<
typename Predicate::argument_type,
bool>
{
public:
explicit unary_negate(const Predicate& _Func);
bool operator()(const typename Predicate::argument_type& _Left) const;
};
template<class BinaryPredicate>
binary_negate<BinaryPredicate> not2(
const BinaryPredicate& _Func
);
template<class Operation>
class binary_negate
: public binary_function <
typename Operation::first_argument_type,
typename Operation::second_argument_type,
bool>
{
public:
explicit binary_negate(
const Operation& _Func
);
bool operator()(
const typename Operation::first_argument_type& _Left,
const typename Operation::second_argument_type& _Right
) const;
};
그럼 그동안 배운 것을 토대로 다음 MSDN 샘플을 살펴보자.
not1( bind2nd( ptr_fun(strcmp), "pearly" ) )
만약 1초만에 strcmp(X,"pearly")==0 임을 인지해 냈다면 당신은 STL의 고수... ㅠㅠ
mem_fun vs. mem_fun_ref
EffectiveSTL 에도 나오는 이야기이니, 책을 가지신 분은 43 아이템을 참고하라.
나를 비롯한 대부분의 프로그래머들은 이런 코드를 사랑한다.
for ( list<GameObject*>::iterator itr = gameObjects.begin() ; itr != gameObjects.end() ; itr ++ )
{
GameObject * pObject = *itr;
pObject->Update();
}
너무나도 직관적인 코드이지만, 사실 mem_fun 을 사용하면 한 줄로 해결이 가능하다.
for_each( gameObjects.begin(), gameObject.end(), mem_fun(&GameObject::Update) );
코드는 간단해졌지만 익숙하지 않은 관계로 팀원들이 싫어할 지도 모른다. 그러나, 타이핑하는 글자수도 적으면서 성능도 훨씬 더 좋다는데... 그 누가 안 쓸수 있으랴? (대신 디버깅할 때에는 멤버함수에다가 breakpoint 를 걸어야 하는 단점이 있을 수도 있다 
)
포인터의 컨테이너일 경우에는 mem_fun 을, 객체의 컨테이너라면 mem_fun_ref 를 사용하면 된다. 만약 멤버함수에 파라미터를 넘겨야 한다면, 아래와 같이 bind 함수를 사용할 것.
for_each( gameObjects.begin(), gameObject.end(), bind2nd( mem_fun(&GameObject::SetHP),100) );
bind1st vs. bind2nd
우선 bind 함수를 알아보기에 앞서, unary_function 과 binary_function 에 대해서 알아보자. 이들은 단지 파라미터와 리턴타입에 대한 typedef 만을 담는 template structure 일 뿐이다. 즉 이들은 혼자서는 아무런 기능도 하지 않지만, 이를 상속받은 하위 클래스에서 타입 정보를 적절히 참조하기 좋도록 디자인된 베이스 클래스라는 뜻이다.
template<class Arg, class Result>
struct unary_function {
typedef Arg argument_type;
typedef Result result_type;
};
template<class Arg1, class Arg2, class Result>
struct binary_function {
typedef Arg1 first_argument_type;
typedef Arg2 second_argument_type;
typedef Result result_type;
};
기본적으로 STL 알고리즘에서 사용되는 Predicate 등의 함수들은 unary_function 의 형태를 띄어야 한다. 쉽게 말하면, find(), for_each(), count() 의 마지막 인자가 해당 컨테이너 내부의 객체 하나만을 인자로 받는 함수 객체라는 뜻이다.
가령 list
class GreaterThan10
{
public :
bool operator() ( int i ) { return i>= 10; }
};
사실 이렇게 짜면 너무 코드가 범용적이지 못하므로, 대부분의 경우에는 이렇게 구현할 것이다.
class GreaterThanN
{
public :
GreaterThenN( int N ) : m_N(N) {}
bool operator() ( int i ) { return i>= m_N; }
private :
int m_N;
};
이걸 STL 적인 생각으로 다시 구현한 것이 바로 bind 함수들이다. bindN(A,B) 은 binary_function A 의 N 번째 파라미터로 parameter B 을 바인딩해서, unary_function 을 만들어주는 놈이다. 얘네들을 잘 활용하면 단순 함수들은 간단히 한줄로 구현할 수 있게 된다.
- bind1st( BINARY_FUNC, PARAM ) : PARAM 을 BINARY_FUNC의 1st 파라미터로 바인딩한다.
bind1st( greater, 10 ) --> 10 > N - bind2nd( BINARY_FUNC, PARAM ) : PARAM 을 BINARY_FUNC의 2nd 파라미터로 바인딩한다.
bind2nd( greater, 10 ) --> N > 10
bind1st( greater, 10 ) 이 어떻게 10 > N 이라는 함수로 바뀌는지 자세히 살펴본다면...
- greater는 binary_function 이다.
template<class Type>
struct greater : public binary_function <Type, Type, bool>
{
bool operator()(
const Type& _Left,
const Type& _Right
) const;
};
- bind1st(A,B) 는 binder1st 객체를 리턴한다.
template<class Operation, class Type>
binder1st <Operation> bind1st(
const Operation& _Func,
const Type& _Left
);
binder1st<A>는 A의 두번째 파라미터를 파라미터로 받고, A의 리턴값을 리턴하는 함수 객체이다. 이때 이 클래스의 생성자의 인자 목록을 유심히 살펴보면, binary_function 하나와 이놈의 하나의 파라미터는 받고 있다. (나머지 하나는 당연히 container 에서 받게 된다.)
template<class Operation>
class binder1st
: public unary_function <
typename Operation::second_argument_type,
typename Operation::result_type>
{
public:
typedef typename Operation::second_argument_type argument_type;
typedef typename Operation::result_type result_type;
binder1st(
const Operation & _Func,
const typename Operation::first_argument_type& _Left
);
result_type operator()(
const argument_type& _Right
);
result_type operator()(
const argument_type& _Right
) const;
protected:
Operation op;
typename Operation::first_argument_type value;
};
SafeDeleter
템플릿 클래스 버전을 사용할 경우, 매번마다 타입을 지정해줘야 하지만, 템플릿 멤버함수 버전을 사용하면 타입 없이도 사용할 수 있다. 아직까지 이걸 몰랐다니.. ㅠㅠ 쑥갓군 땡큐~
/// template class version
template <class T>
class SafeDeleter
{
public :
void operator () ( T * & ptr ) const
{
SAFE_DELETE(ptr);
}
};
for_each( a.begin(), a.end(), SafeDeleter<A>() );
/// template member function version
class SafeDeleter2
{
public :
template <class T>
void operator () ( T * & ptr ) const
{
SAFE_DELETE(ptr);
}
};
for_each( a.begin(), a.end(), SafeDeleter2() );
Static Key vs. Dynamic Key
class Object
{
KeyType_t Key;
....;
};
map<KeyType_t,Obj*> orderedObjects;
위와 같이 객체의 특정 필드의 값으로 정렬된 map이 있다고 하자. 일단 map에 객체를 넣고 난 다음에 Key 값을 변경하면 map 내부의 트리가 깨지므로 바꿔서는 곤란해진다. 그러나, 때로는 Key 값이 바뀌어야 할 필요가 있다. 언제나 실시간으로 바꿔주려면 map 에서 객체를 빼낸 다음 Key 값을 바꾸고 다시 넣어야 하는데, 항상 넣었다 뺐다 하기에는 성능적인 부분이 걱정되는데...
이럴 경우에는 외부에서 필요할 때마다 새로운 키를 저장한 다음, 적당히 바꿀 타이밍이 되면 객체를 map 에서 빼낸 다음 키값을 업데이트해주면 된다. 특히 아래와 같이, 정적인 메인 키의 맵으로 구성된 객체의 매니저가 내부에 특정 순서로 정렬된 서브 키의 맵을 가진 경우, 위와 같은 패턴을 사용하면 꽤 편하다.
class Object
{
StaticKeyType_t MainKey;
DynamicKeyType_t SubKey;
DynamicKeyType_t NewSubKey;
....;
};
class ObjectManager : public map<StaticKeyType_t,Object*>
{
map<DynamicKeyType_t,Object*> orderedObjects;
void ChangeSubKey( StaticKeyType_t mainKey, DynamicKeyType_t newSubKey );
void UpdateSubMap();
};
어쨌든, map 의 키값을 외부에서 바꿨다가는 큰 낭패를 볼 것이다.
see also:
multixxx::erase(key_type)
일반적인 erase()는 iterator/const_iterator 를 파라미터로 받아서 그 넘을 지우는 역할을 한다. 그런데, multimap/multiset 에서는 key_type 만 넘겨서 해당 값을 지우는 메쏘드를 제공한다. 대체로 이는 잘 동작하지만 predicate 가 명시된 multimap/multiset 에서는 생각대로 동작하지 않는다. 다음 예를 보자.
class TeamInfo
{
public :
TeamInfo ( int point = 0 ) : TeamPoint(point) {}
int TeamPoint;
};
class GreaterTeam
{
public :
bool operator () (const TeamInfo* l, const TeamInfo* r) const
{
return l->TeamPoint> r->TeamPoint;
}
};
void
test_multiset()
{
typedef multiset<TeamInfo*,GreaterTeam> TEAMS;
TEAMS teams;
TeamInfo t1(1);
TeamInfo t2(1);
TeamInfo t3(0);
TeamInfo t4(2);
teams.insert( &t1 );
teams.insert( &t2 );
teams.insert( &t3 );
teams.insert( &t4 );
// erase by key test
teams.erase( &t4 ); assert( teams.size() == 3 );
teams.erase( &t1 ); assert( teams.size() == 1 ); // t1 과 t2 를 지운다. 낭패~
// erase with iterator test
teams.clear();
teams.insert( &t1 );
teams.insert( &t2 );
teams.insert( &t3 );
teams.insert( &t4 );
pair<TEAMS::iterator,TEAMS::iterator> itrs = teams.equal_range(&t1);
teams.erase( find( itrs.first, itrs.second, &t1 ) );
assert( teams.size() == 3 );
assert( *(teams.find(&t1)) == &t2 ); // t1 을 찾으면 t2 가 나온다는 놀라운 사실!
assert( *(teams.find(&t2)) == &t2 );
assert( *(teams.find(&t3)) == &t3 );
assert( *(teams.find(&t4)) == &t4 );
}
여기서 배울 수 있는 교훈은
- 코드상으로는 equal_range(&t1)이라는 것이 t1을 찾는 것처럼 보이지만, 실제로는 key_type과 무관하며 오직 predicate 를 이용해서 검색을 한다!
- multi 시리즈에서는 find()나 erase()에 있어서 항상 동일한 값이 존재할 수 있다!
- predicate 의 비교문에서 >= 을 사용하면 다른 결과가 나온다!
- predicate 관련 변수(m_TeamPoint)와 같이, 비교 로직에 영향을 주는 무언가를 외부에서 바꾸게 되면 multixxx 내부의 트리가 깨지게 된다. 너무나 당연한 사실이지만, Key 를 바꾸는게 아니라서 안전할 거 같아 보이는 것도 사실이다. 이를 방지하려면 일단 container 에서 해당 값을 erase한 다음 값을 수정하고 다시 insert 하는 것을 권장한다.