http://dev.log.mumbi.net/497

1. 알고리즘( algorithm )의 일반화.
  알고리즘의 일반화라는 것은 어떠한 컨테이너( container )도 그 알고리즘을 사용할 수 있게 만드는 것이다.

이 때, 그 알고리즘은 대상 컨테이너를 순회하기 위해서 컨테이너의 반복자를 사용한다. 보통, 시작을 가리키는 반복자와, 끝을 가리키는 반복자를 사용하고 끝을 가리키는 반복자는 순회에 포함되지 않고 컨테이너의 마지막 요소 다음을 가리킨다.

여기서 중요한 사실은 STL( Standard Template Library )이 제공하는 알고리즘이 제공하는 컨테이너 뿐 아니라 기본 배열에도 사용할 수 있게 C++ 표준이 지정되었다.

특정한 형을 사용하는 알고리즘을 일반화 시켜보면..

1. int 형 배열의 모든 원소의 합을 구하여 반환하는 함수.
 int Sum( int* _pFirst, int* _pLast )
{
    int sum = *_pFirst++;
 
    while( _pFirst != _pLast )
        sum += *_pFirst++;
 
    return sum;
}

배열의 첫 요소의 주소와 마지막 요소의 다음 주소를 인자로 받아 각 요소들을 순회하면서 합을 구한다.

2. 배열을 비롯한 모든 컨테이너에서 사용하기 위해 템플릿( template )을 적용한 일반화된 함수.
 template< class IteratorType >
 Sum( IteratorType _first, IteratorType _last )
{
    ???? sum = *_first++;
 
    while( _first != _last )
        sum += *_first++;
 
    return sum;
}

컨테이너에서는 포인터( pointer )를 일반화한 반복자( iterator )를 사용하기 때문에 시작을 가리키는 반복자와 끝을 가리키는 반복자를 인수로 받아 각 요소들을 순회하면서 합을 구한다.

그런데 요소들의 타입( type )을 모르기 때문에 그 합의 타입도 알 수 없다.

3. 반복자가 가리키는 타입 알려주는 value_type으로 일반화한 함수.
 template< class IteratorType >
typename IteratorType::value_type Sum( IteratorType _first, IteratorType _last )
{
    typename IteratorType::value_type sum = *_first++;
 
    while( _first != _last )
        sum += *_first++;
 
    return sum;
}

컨테이너의 반복자는 value_type이라는 타입을 제공한다. 반복자의 value_type은 반복자가 가리키는요소의 타입이다.

하지만 컨테이너의 반복자는 value_type을 제공하지만 기존의 포인터는 객체가 아니기 때문에 value_type을 제공하지 않으므로 배열에 대해서는 일반화되지 않았다.

배열의 포인터로 어떻게 요소의 타입을 알 수 있을까?

2. 템플릿 부분 특수화( partial specialization ).
배열의 요소 타입을 알아 내기 위해 템플릿의 부분 특수화를 알아야 한다.

[C++] 템플릿 특수화 ( template specialization )

STL 은 부분 특수화를 통해 iterator_traits 를 제공한다.

 template<class _iter="">
    struct iterator_traits      // 포인터가 아닐 경우( 반복자 ).
    {   // get traits from iterator _Iter
    typedef typename _Iter::iterator_category iterator_category;
    typedef typename _Iter::value_type value_type;      // <--
    typedef typename _Iter::difference_type difference_type;
    typedef difference_type distance_type;  // retained
    typedef typename _Iter::pointer pointer;
    typedef typename _Iter::reference reference;
    };
 
template<class _ty="">
    struct iterator_traits<_Ty *> // 포인터일 경우.
    {   // get traits from pointer
    typedef random_access_iterator_tag iterator_category;
    typedef _Ty value_type;         // <--
    typedef ptrdiff_t difference_type;
    typedef ptrdiff_t distance_type;    // retained
    typedef _Ty *pointer;
    typedef _Ty& reference;
    };

위의 코드는 MSVC9 에서 제공하는 STL의 iterator_traits 이다.

부분 특수화를 이용해 포인터일 경우와 반복자일 경우의 value_type을 다르게 하여 제공한다.

3. iterator_traits.
결론적으로 iterator_traits 는 반복자 특질이라고 번역되지만 사실, 반복자와 배열의 포인터를 구분하기 위해서 만들어진 것이다.

알고리즘을 구현하고 있다면 iterator_traits 가 무엇인지 반드시 알아야 한다.

iterator_traits Class 

Visual Studio 2005

Other Versions

A template helper class used to specify all the critical type definitions that an iterator should have.

template<class Iterator>
   struct iterator_traits {
   typedef typename Iterator::iterator_category iterator_category;
   typedef typename Iterator::value_type value_type;
   typedef typename Iterator::difference_type difference_type;
   typedef typename Iterator::pointer pointer;
   typedef typename Iterator::reference reference;
   };
template<class Type>
   struct iterator_traits<Type*> {
   typedef random_access_iterator_tag iterator_category;
   typedef Type value_type;
   typedef ptrdiff_t difference_type;
   typedef Type *pointer;
   typedef Type& reference;
   };
template<class Type>
   struct iterator_traits<const Type*> {
   typedef random_access_iterator_tag iterator_category;
   typedef Type value_type;
   typedef ptrdiff_t difference_type;
   typedef const Type *pointer;
   typedef const Type& reference;
   };

Remarks

---

The template class defines the member types

• iterator_category: a synonym for Iterator::iterator_category.

• value_type: a synonym for Iterator::value_type.

• difference_type: a synonym for Iterator::difference_type.

• pointer: a synonym for Iterator::pointer.

• reference: a synonym for Iterator::reference.

The partial specializations determine the critical types associated with an object pointer of type Type * or const Type *.

In this implementation you can also use several template functions that do not make use of partial specialization:

template<class Category, class Type, class Diff>
C _Iter_cat(const iterator<Category, Ty, Diff>&);
template<class Ty>
    random_access_iterator_tag _Iter_cat(const Ty *);

template<class Category, class Ty, class Diff>
Ty *_Val_type(const iterator<Category, Ty, Diff>&);
template<class Ty>
    Ty *_Val_type(const Ty *);

template<class Category, class Ty, class Diff>
Diff *_Dist_type(const iterator<Category, Ty, Diff>&);
template<class Ty>
    ptrdiff_t *_Dist_type(const Ty *);

which determine several of the same types more indirectly. You use these functions as arguments on a function call. Their sole purpose is to supply a useful template class parameter to the called function.

Example

---

// iterator_traits.cpp
// compile with: /EHsc
#include <iostream>
#include <iterator>
#include <vector>
#include <list>

using namespace std;

template< class it >
void
function( it i1, it i2 )
{
   iterator_traits<it>::iterator_category cat;
   cout << typeid( cat ).name( ) << endl;
   while ( i1 != i2 )
   {
      iterator_traits<it>::value_type x;
      x = *i1;
      cout << x << " ";
      i1++;
   };   
   cout << endl;
};

int main( ) 
{
   vector<char> vc( 10,'a' );
   list<int> li( 10 );
   function( vc.begin( ), vc.end( ) );
   function( li.begin( ), li.end( ) );
}

Output

struct std::random_access_iterator_tag
a a a a a a a a a a 
struct std::bidirectional_iterator_tag
0 0 0 0 0 0 0 0 0 0 

Requirements

---

Header: <iterator>

See Also

---

Reference

<iterator> 
Thread Safety in the Standard C++ Library 
Standard Template Library 

http://blog.daum.net/coolprogramming/93

4, 삽입 반복자

삽입 반복자(insert iterator)는 알고리즘에서 반복자가 가리키는 위치에 값을 "덮어"(overwrite)쓰지 않고 "삽입"(insert)할 수 있도록 바꿔주는 반복자입니다.

STL은 3 가지의 삽입 반복자를 제공합니다.

• back_insert_iterator : push_back 멤버 함수를 사용하여 삽입

  • 시퀀스 컨테이너(string, vector, list, deque)는 push_back 멤버 함수를 제공하므로 사용 가능

• front_insert_iterator : push_front 멤버 함수를 사용하여 삽입

  • list와 deque만 push_front 멤버 함수를 제공하므로 사용 가능

• insert_iterator : insert 멤버 함수를 사용하여 삽입

  • 모든 컨테이너는 insert 멤버 함수를 제공하므로 사용 가능

반복자를 이용한 덮어쓰기와 삽입을 그림으로 보입니다.

1) 덮어쓰기 모드

2) 삽입 모드

일반적으로 알고리즘은 덥어쓰기로 동작하므로 알고리즘을 사용하기 전에 저장할 원소의 size가 존재해야 합니다.

간단한 copy 알고리즘을 예로 사용합니다.

1. 10 20 30

v1.begin()~v2.end()까지의 원소를 모두 v2에 저장합니다. 이때 v2는 저장할 개수만큼의 size를 가지고 있어야합니다. 여기서는 3개입니다.

만약 size를 가지고 있지 않다면 실행 오류가 발생합니다.

v2의 size는 0 입니다.

1. 안녕~~!

v2의 size가 0이므로 copy 알고리즘에서 실행 오류가 발생합니다.

이것은 해결하려면 copy 알고리즘에 삽입 반복자를 전달하면 됩니다.

insert_iterator를 사용한 예제입니다.

1. 10 20 30

inserter는 insert_iterator를 생성합니다. 이 삽입 반복자는 insert() 멤버 함수를 사용하여 삽입니다.

inserter는 템플릿 함수로 insert_iterator를 반환합니다. 첫 번째 인자에 컨테이너를 두 번째 인자에 삽입할 위치의 반복자를 지정하면 됩니다.

또 다른 예제입니다.

1. 10 20 30 100 200 300

v2가 3개의 원소(100,200,300)를 가지고 있고 v2.begin()에 삽입 위치를 지정했으므로 앞쪽에 삽입됩니다.

back_insert_iterator를 사용한 예제입니다.

1. 100 200 300 10 20 30

back_inserter는 back_insert_iterator를 생성합니다. 이 삽입 반복자는 push_back() 멤버 함수를 사용하여 삽입(추가)합니다.

back_inserter는 템플릿 함수로 back_insert_iterator를 반환합니다. 함수의 인자에 컨테이너 지정하면 됩니다.

vector는 push_front 멤버 함수가 없으므로 front_insert_iterator는 사용할 수 없습니다.

1. 안녕~~!


에러입니다. front_inserter는 템플릿 함수로 front_insert_iterator를 반환하지만 vector는 push_front() 멤버 함수가 없으므로 front_insert_iterator를 사용할 수 없습니다.

list는 push_front 멤버 함수를 가지고 있으므로 front_insert_iterator를 사용할 수 있습니다.

1. 30 20 10 100 200 300

push_front 멤버 함수를 사용하여 정수를 삽입합니다.

5, 입,출력 스트림 반복자

입,출력 스트림 반복자(input,output stream iterator)는 I/O 스트림에 연결된 조금 특별한 반복자입니다. 알고리즘에서 스트림 입출력을 쉽게 수행할 수 있도록 제공합니다. 입력 스트림 반복자는 istream_iterator 클래스를 출력 스트림 반복자는 ostream_iterator 클래스를 사용합니다.

copy 알고리즘에서 출력 스트림 반복자를 사용한 예제입니다.

1. 10 20 30 40 50
   10, 20, 30, 40, 50,

ostream_iterator는 템플릿 클래스로 출력 반복자를 추상화한 클래스입니다. 템플릿 인자는 출력 타입이며(int) 생성자의 첫 번째 인자는 출력 스트림 객체, 두 번째 인자는 출력 값들 사이에 출력될 문자열입니다.

다음은 istream_iterator의 간단한 예제입니다.

1. 10 20 30 40 50^Z
   10,20,30,40,50,

예제는 입력 스트림 객체(cin)에서 입력되는 정수들을 스트림 끝까지 입력 받아 출력하는 예제입니다.

istream_iterator<int>( cin )은 cin(입력 스트림 객체)을 통해 입력되는 정수 값을 입력 받는 반복자를 istream_iterator<int>( )은 입력 스트림 반복자의 끝 표시기(end marker)를 역할을 하는 입력 반복자를 의미합니다.

여기까지 C++, STL QS1을 모두 마무리합니다. ㅠ.ㅠ...

10개월 동안 해오던 일을 마무리하니 시원함? 아쉬움? 뿌듯함? 허탈함?이 모두 공존합니다.

아직 못 다한 고급(?)적인 내용은 C++, STL QS2에서 공부합니다. QS2는 조금 어려운 내용이 될 수도...

수고하셨습니다. 꾸벅!

http://cmlife.blogspot.com/2007_02_01_archive.html

auto_ptr

 http://blog.naver.com/uleena?Redirect=Log&logNo=80042072372

#include <iostream>

#include <string>

#include <functional>

using namespace std;

#include <ctime>

#include <bitset>

// unique 한랜덤을만들어내는함수객체

template<int MAX> class URandom

{

        bitset<MAX> bs;

        bool recycle;

public:

        URandom(bool b = false) : recycle(b)

        {

               srand(time(0)); // 난수초기화

               bs.set();       // 모든비트를1로

        }

        int operator()()

        {

               if ( bs.none() )   // 모두0인경우

               {

                       if ( recycle == false) // 재사용안하는경우

                              return -1;

                       else

                              bs.set();  // 모두1로

               }

               int n = -1;

               while ( !bs.test( n = (rand() % MAX) ));

               bs.reset(n);

               return n;

        }

};

int main()

{

        URandom<5> r;

        for ( int i = 0; i < 15;++i)

               cout << r() << endl;

}

// 3. bitset : 비트의집합

#include <bitset>

int main()

{

        bitset<10> bs;

        bs.reset(); // 모두0

        // 각비트를조작하는법

        bs.set(4);

        bs[5] = true;

        bs[6].flip();

        // 비트조사

        if ( bs.test(4) ) cout << "비트4가set" << endl;

        if ( bs[5]      ) cout << "비트5가set" << endl;

        unsigned long n = bs.to_ulong();

        cout << n << endl;

        string s = bs.to_string();

        cout << s << endl;

}

// 2. set : 순서를가지고요소를저장한다. (대부분의STL구현물은RB-Tree사용)

#include <set>

int main()

{

        typedef set<int, greater<int>> SET;

        //set< int, greater<int> > s;

        SET s;

        s.insert(10);

        s.insert( 5);

        s.insert(15);

        s.insert(30);

        s.insert(4);

        pair< SET::iterator, bool> ret = s.insert(10); // 중복? 허용될까?

        if ( ret.second == false )

               cout << "이미요소가있습니다." << endl;

        ostream_iterator<int> os(cout, " ");

        copy( s.begin(), s.end(), os);

}

// 1. pair의개념

template<typename T1, typename T2> struct pair

{

        T1 first;

        T2 second;

        pair(T1 a = T1(), T2 b = T2() ) :first(a), second(b) {}

};

pair<int, int> foo()

{

        // 이안에서2개의값을리턴해주고싶다.

}

int main()

{

        // TR1(또는boost)에는pair에개선된버전인tuple이있다.

        tuple<> none;

        tuple<int> one;

        tuple<int, int> two;

        tuple<int, int, int> three;

        tuple<int, int, int, int> n;

        pair<int, pair<int, int>> p2;

        pair<int, double> p1(1,3.4);

        cout << p1.second << endl; // ?

}

typename 을 써야 하는 순간

http://blog.naver.com/spinx85?Redirect=Log&logNo=140112304004

http://dev.log.mumbi.net/497

STL / 컨테이너

http://cpu815.blog.me/110035113430

http://blog.naver.com/infopub?Redirect=Log&logNo=100024418644

http://blog.daum.net/coolprogramming/90

 1, 함수자

operator() 연산자를 중복하고 있는 클래스의 객체를 함수 객체( function object) 혹은 함수자(functor)라 합니다.

그래서 함수자는 함수처럼 사용할 수 있습니다.

함수자는 02. C++, STL QS2의 함수 포인터와 함수자를 참고하세요.

아래는 간단한 세가지 함수류(함수, 함수 포인터, 함수자)를 사용한 예제 코드입니다.

1 함수, 2 함수 포인터, 3 함수자를 사용한  두 정수의 합 예제입니다.

1. 30
   30
   30

 위 예제를 보면 함수, 함수 포인터, 함수자의 인터페이스는 모두 같다는 것을 알 수 있습니다.

함수자를 사용하면 아래와 같은 장점이 있습니다.

• 컴파일 시에 함수자를 알고리즘의 인자로 전달할 수 있다.
• 함수 호출을 인라인(inline)화해서 효율성을 향상시킬 수 있다.
• 함수자의 정보를 캡슐화하여 지역화(locally)할 수 있다.

 2, STL 함수자

STL 함수자는 크게 두 가지로 나눌 수 있습니다.

• 1, 일반 함수자 : 특정 기능을 수행하는 함수자.

  • 산술 연산 함수자 : 산술 연산 기능을 수행.
  • 비교 연산 함수자 : 비교 연산 기능을 수행.

  • 논리 연산 함수자 : 논리 연산 기능을 수행.

     

• 2, 함수 어댑터 : 함수류(함수와, 함수 포인터, 함수자)를 인자로 받아 새로운 함수자를 생성.

  • 바인더(binder) : 이항 함수자를 단항 함수자로 변환하는 함수자.
  • 부정자(negator) : 조건자(predicate)를 반대로 변환하는 함수자.
  • 함수 포인터 어댑터(adaptors for pointersto functions) : 함수 포인터를 라이브러리가 필요로 하는 함수자로 변환하는 함수자
  • 멤버 함수 포인터 어댑터(adaptors for pointers to member functions) : 멤버 함수 포인터를 라이브러리가 필요로 하는 함수자로 변환하는 함수자

어댑터의 인자로 사용되는 함수자는 아래 요구 사항을 지켜야 합니다.

• 단항 함수자는 반드시 argument_type, result_type이 정의되어 있어야 한다. 각각은 함수의 인자 타입과 리턴 타입이다.
• 이항 함수자는 반드시 first_argument_type, second_argument_type, result_type이 정의되어 있어야 한다. 각각은 함수의 첫번째 인자 타입과 두 번째 인자 타입, 리턴 타입이다.

어댑터들은 인자로 받는 함수자의 위 정의 타입을 이용하여 컴파일 시간에 타입들을 검사합니다.

이러한 타입 정의를 쉽게하기 위해 STL은 기본 클래스 unary_function과 binary_function을 제공한다. 그래서 위 타입들을 직접 작성할 필요는 없습니다. 어댑터는 무조건 위 기본 클래스를 상속받아 만들면 됩니다. ㅡㅡ;

또 함수류(함수, 함수 포인터, 함수자) 중에서 bool형을 리턴하는(비교에 사용되는) 함수자를 predicate(조건자, 술어 구문)라 합니다.

2.1, 일반 함수자

일반 함수자에는 산술 연산, 비교 연산, 논리 연산 등을 수행하는 함수자들이 있습니다.

2.1.1, 산술 연산 함수자

 산술 연산자에는 plus, minus, multiplies, divides, modulus, negate가 있습니다. 모두 템플릿입니다.

plus의 간단한 예제입니다.

1. 30
   30

두 인자를 받아 합을 리턴하는 함수자입니다.

그렇다면 이런 함수자를 어디에 써먹나? ㅡㅡ;;

STL은 함수자없이는 동작할 수 없을 정도로 많은 곳에 함수자가 사용됩니다. 

plus 함수자를 사용하는 실제 예제를 보도록 하겠습니다.

plus 함수자를 사용한 trasform 알고리즘입니다.

1. 10 20 30
1 2 3
11 22 33


 v1.begin()~v1.end()까지의 원소와 v2의 원소를 함수자(plus<int>())로 연산하여 리턴 결과를 다시 v1.begin()부터 순서대로 저장하는 예제입니다.

그림으로 보면 아래와 같습니다.

STL plus를 사용하지 않고 사용자 Plus 함수자를 만들어 보도록 하겠습니다.

직접 작성한 Plus 함수자 예제입니다.

1. 10 20 30
   1 2 3
   11 22 33

 결과는 같습니다. 직접 작성한 Plus 함수자를 사용했습니다.

STL의 plus처럼 어떤 타입의 합도 계산할 수 있도록 일반화 시키려면 템플릿 클래스로 만들면 됩니다.

다음은 Plus를 템플릿 클래스로 바꾼 예제입니다.

1. 10 20 30
   1 2 3
   11 22 33

단순히 템플릿 클래스로 변환한 것 외에 다른 것은 없습니다.

마지막으로 2, STL 함수자에서 언급했던 것처럼 만약 위에서 작성한 Plus<> 함수자 클래스를 어댑터 적용이 가능하도록 하려면 이항 함수자이므로 first_argument_type, second_argument_type, result_type을 정의해야 합니다. 가장 간단하게 정의할 수 있는 방법은 binary_function 기본 클래스를 상속받는 것입니다. 위 정의 타입이 필요한 이유는 어댑터에서 컴파일 시간에 타입 검사를 할때 위 정의 타입이 필요하기 때문입니다.

어댑터에 자세한 내용은 아래쪽에서 공부합니다.

다음은 binary_function을 상속받은 Plus<> 함수자 클래스입니다.

1. 10 20 30
   1 2 3
   11 22 33

지금 예제에는 어댑터를 사용하지 않기 때문에 굳이 필요하지는 않지만 다음을 위해서 어댑터 적용이 가능하도록 미리 binary_function을 상속받았습니다.

간단한 예제를 보이도록 하겠습니다.(binder1st<> 어댑터 사용)

1. 10 20 30
   110 120 130

v.begin()~v.end()까지의 모든 원소를 네 번째 함수자의 인자로 전달하고 리턴한 결과를 다시 v.begin()부터 순서대로 저장합니다.

 binder1st<>는 이항 연산자를 단항 연산자로 바꾸는 바인더 어댑터입니다. 위 예제의 transform이 단항 연산자를 필요로 하기때문에 이항 연산이 가능한 plus 함수자를 오른쪽 항을 100으로 고정시키고 왼쪽항만 인자로 받을 수 있는 단항 연산자 함수자로 변환합니다.

어댑터는 아래쪽에서 다시 자세히 공부합니다. 지금은 위와 같은 어댑터에 사용하는 plus 함수자는 binary_function 기본 클래스를 상속받아야 한다는 것에 집중하시면 됩니다.

우리가 만든 Plus<>가 binary_function을 상속받지 않으면 무시무시한(?) 에러가 발생합니다.

1. error C2039: 'second_argument_type' : 'Plus<T>'의 멤버가 아닙니다.
   1>        with
   1>        [
   1>            T=int
   1>        ]
   1>        c:\...\main.cpp(28) : 컴파일 중인 클래스 템플릿 인스턴스화 'std::binder1st<_Fn2>'에 대한 참조를 확인하십시오.
   1>        with
   1>        [
   1>            _Fn2=Plus<int>
   1>        ]
2. ....

무서버~!

binary_function 기본 클래스를 상속받으면 쉽게 해결됩니다.

1. 10 20 30
   110 120 130

 간단합니다.

우리가 직접 first_argument_type, second_argument_type, result_type을 정의해도 해결됩니다.

1. 10 20 30
   110 120 130

상속이라는 더 깔끔한 방법이 있으니 binary_function을 상속받는 것이 더 좋겠죠?

minus, multiplies, divides, modulus, negate함수자는 plus와 모두 비슷하므로 생략합니다.

2.1.2, 비교 연산 함수자

 비교 연산자는 equal_to, not_equal_to, greater, less, greater_equal, less_equal이 있습니다. 모두 템플릿 클래스입니다.

 비교 연산 함수자는 모두 predicate입니다. predicate(조건자)는 비교를 수행하는(bool형을 리턴하는 ) 함수류(함수, 함수 포인터, 함수자)을 말합니다.

greater의 간단한 예제입니다.

1. 0
   0
   true

 greater는 두 인자를 받아 첫 번째 인자가 크면 true를 아니면 false를 리턴합니다.

 실제 사용 예제입니다.(sort 알고리즘)

1. 50 20 40 30 10
   10 20 30 40 50
   50 40 30 20 10

 sort는 less를 사용하여 오름차순 정렬을 수행하지만 세 번째 인자로 greater를 전달하면 내림차순 정렬을 합니다.

 다음은 직접 작성한 Greater<>입니다.( 어댑터 적용이 가능하도록 binary_function을 상속 받았습니다.)

1. 50 20 40 30 10
   10 20 30 40 50
   50 40 30 20 10

결과는 같습니다.

나머지 비교 연산 equal_to, not_equal_to, less, greater_equal, less_equal은 greater와 비슷하므로 생략합니다.

2.1.3, 논리 연산 함수자

 논리 연산은  logical_and, logical_or, logical_not가 있습니다.

logical_and의 간단한 예제입니다.(논리 AND 연산을 수행하는 함수자)

1. 1
   0
   true

 두 인자를 입력받아 두 인자 모두 true이면 true를 리턴하고 아니면 false를 리턴합니다. AND 연산!

간단한 사용 예제입니다.

1. false  false  true

 간단하죠?

너머지는 모두 비슷하므로 생략합니다.

 오늘은 여기까지입니다. ^^

...

#include <iostream>
#include <list>
#include <functional>
#include <algorithm>

using namespace std;

class fuctor{

public :
 int m_MemData;
 static int m_data;

public :
 fuctor(int ini) {
  m_MemData = ini;
 }
 fuctor() {
  m_MemData = m_data++;
 }
 int operator+( int data ) const{
  return this->m_MemData + data;
 }
 void show(int data){
  cout<<m_MemData + data<<"\t";
 }

};

int fuctor::m_data = 1;

class IntSequence{

public :
 fuctor operator()(){
  return fuctor();
 }

};

template<typename T1,typename T2>
class plus1 : public binary_function<T1,T2,T1>{
public :
 T1 operator()(const T1 lhs,const T2 rhs) const {
  return  T1(lhs + rhs);
 }
};

int main(){

 list<fuctor> coll2;
 
 generate_n( back_inserter(coll2),10,  IntSequence() );

 transform(coll2.begin(),coll2.end(),coll2.begin(), bind2nd( plus1<fuctor,int>(),10 ) );

 for_each( coll2.begin(),coll2.end(), bind2nd(mem_fun_ref(&fuctor::show) ,100)  );
 
 if(getchar())
  return 0;
}

emplate<typename OP1,typename OP2>
class compose_f_gx_t : public unary_function< typename OP2::argument_type,typename OP1::result_type>
{

private :
 OP1 op1; // op(op2(x)) 를 처리한다
 OP2 op2;
public :
 compose_f_gx_t(const OP1& o1, const OP2& o2) : op1(o1), op2(o2)
 {

 }
 typename OP2::result_type
  operator()(const typename OP2::argument_type& x) const {
   return op1(op2(x));
 }

};

template<typename OP1,typename OP2>
inline compose_f_gx_t<OP1,OP2> compose_f_gx(const OP1& o1, const OP2& o2){
 return compose_f_gx_t<OP1,OP2>(o1,o2);
}

#include <memory>
#include <vector>
#include <list>
#include <Windows.h>
#include <string.h>
#include<iostream>
#include <algorithm>

using namespace std;

 return 0;
}

C++의 STL 표준 라이브러리는 미리 정의된 여러가지 함수 객체들을 제공한다.

이러한 표준 함수객체들을 사용하기 위해서는 #include <functional> 을 포함해야 한다.

이 함수객체들은 알고리즘의 비교,정렬을 위한 기준으로 사용될 수 있다.

less<> 는 알고리즘에서 디폴트 기준으로 사용되는 오름차순 정렬이다.

1. 함수어댑터

함수어댑터란, 함수객체를 특정값 또는 특정함수와 결합시킨 함수객체이다.

이러한 함수어댑터 역시 <functional> 에 정의되어 있다.

find_if(coll.begin(), coll.end(), bind2nd(greater<int>(), 42));

이 코드에서 bind2nd(greater<int>(), 42) 는 정수타입 변수가 42보다 큰지를 판단하는 결합된 함수객체를 생성한다.

bind2nd는 greater<> 와 같은 이항 함수객체를 단항 함수객체로 변형시킨다.

즉, bind2nd의 두번째 인자를 이항 함수객체의 두번째 인자로 사용하는 것이다.

따라서, greater<>는 42를 두번째 인자로 하여 호출한다.

함수어댑터는 스스로가 함수객체이다. 따라서, 함수어댑터를 함수객체와 결합하여 사용할 수 있다.

pos=find_if(coll.begin(), coll.end(), not1(bind2nd(modulus<int>(), 2)));

이 코드에서 bind2nd(modulus<int>(), 2) 는 모든 홀수에 대해 1(참) 을 반환한다.

따라서, 이 표현식은 홀수값을 갖는 첫번째 원소를찾는 기준이된다.

하지만 not1() 은 이 결과를 반전시키므로, 짝수값을 갖는 첫번째 원소의 위치를 반환한다.

2. 멤버함수를 위한 함수어댑터

이것은 STL 컨테이너의 각각의 원소들에 대해서 멤버함수를 호출시켜주는 함수 어댑터이다.

#include <iostream>
#include <vector>
#include <functional>
using namespace std;

class person{
 private:
  string name;
 public:
  person(char *nm):name(nm){}
  void print()const{
   cout<<name<<endl;
  }
  void printWithPrefix(string prefix)const{
   cout<<prefix<<name<<endl;
  }
};

int main(){
 vector<person> coll;
 coll.push_back(person("AAAA"));
 coll.push_back(person("BBBB"));
 coll.push_back(person("CCCC"));
 coll.push_back(person("DDDD"));

 //각각의 원소에 대해서 멤버함수 print()를 호출
 for_each(coll.begin(), coll.end(), mem_fun_ref(&person::print));
 
 //각각의 원소에 대해서 멤버함수 printWithPrefix()를 호출
 //"person : " 은 멤버함수 printWithPrefix() 의 인자로 전달
 for_each(coll.begin(), coll.end(), bind2nd(mem_fun_ref(&person::printWithPrefix), "person : "));
}

3. 일반 함수들을 위한 함수어댑터

ptr_fun() 은 기존의 일반 함수들을 함수객체와 같은 형태로 사용하도록 하는 함수객체 어댑터이다.

예를들어, 각각의 인자에 대해 무언가를 검사하는 일반 전역함수를 가지고 있을때

bool check(int elem);

이러한 경우 조건을 만족하는 첫번째 원소를 찾으려면 다음과 같이 호출한다.

pos=find_if(coll.begin(), coll.end(), ptr_fun(check));

조건을 만족하지않는 첫번째 원소를 찾으려면 다음과 같이 사용할 수 있다.

pos=find_if(coll.begin(), coll.end(), not1(ptr_fun(check)));

사용자가 두개의 인자를 사용하는 전역함수를 가지고 있다고 가정한다면

pos=find_if(coll.begin(), coll.end(), not1(bind2nd(ptr_fun(strcmp), "AAA")));

strcmp는 두개의 string이 같을경우 false를 반환한다.

따라서, 이 구문은 "AAA" 와 같은 첫번째 string의 위치를 반환한다.

[ 주의사항 ]

criticalsection 사용시 시스템 메모리가 부족하 경우 제대로 동기화되지 않고 오류가 발생한다

이상황을 방지하기위해서 try-catch 를 사용하거나 InitializeCriticalSectionAndSpinCount 함수를 사용해야한다

자세한사항은 :  http://3dmpengines.tistory.com/1168

출저:  http://blog.naver.com/jeon_sw?Redirect=Log&logNo=110013411452 

윈도우가 쓰레드의 동기화에 Mutex 와 더불어 CRITICAL_SECTION 이라는 객체를 사용하고 있기 때문에 의미상의 오해가 있을 수 있습니다만, 일반적으로 OS 에서 Crtical Section 이라고 하는 것은 서로 다른 쓰레드나 프로세스가 간섭하지 않고 순차적으로 실행되어야 하는 영역을 뜻하고, 보통 임계 영역 이라고 해석합니다.

제목에 포함된 Critical Section 은 이 영역의 제어를 어떻게 할까를 생각해 보자는 뜻으로 붙인겁니다.

Critical Section 의 제어를 어떻게 할지 생각하자?

대부분이 Mutex 나 Semaphore, CRITICAL_SECTION 을 쓰면 되지 않느냐라고 답할겁니다.

당연히 그러면 됩니다. 그걸 몰라서가 아니라, 좀 더 성능을 향상하기 위해서는 약간 더 고려해야 될 부분이 있을 거 같아서 입니다.

고려 대상은 주로 여러개의 CPU 를 사용하는 서버의 경우입니다. Uni-Processor 인 일반 PC 에서 실행되는 어플리케이션의 개발은 그냥 기존의 방법을 사용해도 되니까, 이런 어플리케이션을 주로 사용하시는 분은 지금 바로 과감히 다른 페이지나 게시물로 옮겨 가시기 바랍니다.

그러면, Multi-Processor 상황에서 어떤 경우를 고려해야 하느냐 하면, Critical Section 이 아주 짧은 경우입니다.

OS에 관한 지식이 약간 있으신 분은 spin-lock 과 Busy-waiting 에 대해 말하고 싶은 거다라는 걸 금방 아셨을 겁니다.

spin-lock이 뭔지를 모르시는 분들을 위해 잠시 부가 설명을 하겠습니다.

예를 들어 globalCount 라는 공유메모리가(쓰레드간 또는 프로세스간에 공유되는 값) 있다고 가정할 때,

이 값이 순차적으로 증가, 감소하는 값이라고 하면 이 값의 증가에 일반적으로 다음과 같은 방법을 사용합니다.

EnterCriticalSection(&cs);

globalCount++;

LeaveCriticalSection(&cs);

프로세스간 공유라고 하면,

if (WaitForSingleObject(hMutex, millisec) == WAIT_OBJECT_0)

{

    globalCount++;

    ReleaseMutex(hMutex);

}

주로 이런 방법을 사용할겁니다. 여기까지 생각이 드셨다면 일반적인 프로그래머라고 생각되고,

약간 더 고급 프로그래머라면,

InterlockedIncrement(&globalCount);

를 생각할 수도 있을겁니다.

가장 좋은 방법은 InterlockedIncrement 이지만, 이 함수는 논외로 하겠습니다.

내부적으로 Intel 의 lock inc Instruction-set 을 호출하므로, 이 함수는 정확히 32bit 값에 대해서만 Atomic 처리가 가능하기 때문입니다.(물론 64bit CPU는 64bit입니다만)

지금 예로 든건 편의상 globalCount++ 일 뿐이지, 실제로는 globalCount++; globalCount2--; 일 수도 또는 약간 더 길 수도 있을 겁니다.

그럼, 앞의 두가지 경우를 다시 생각해 보겠습니다.

Mutex 는 CRITICAL_SECTION 에 비해 상대적으로 비용이 비싼 객체이므로 우선 대상은 CRITICAL_SECTION 으로 정하겠습니다.

임계영역에서 실행되는 globalCount++; 는 극히 짧은 연산입니다. 이 연산을 위해서 EnterCriticalSection 을 두 쓰레드가 동시에

호출하게 되면, 하나의 쓰레드는 Sleep 상태로 빠지게 될겁니다. 그리고 Sleep 이 되지 않은 쓰레드가 LeaveCriticalSection 을

호출한 후다시 깨어나서 EnterCriticalSection 을 재시도 하여 성공하면 globalCount++ 를 실행하게 됩니다.

이런 상황은 임계영역이 짧은 경우, 하나의 CPU 를 사용하는 PC에서는 거의 발생하지 않습니다. 왜냐하면, 하나의 CPU를 사용하는

시스템에서 동시에 실행되는 작업이란 없기 때문입니다. 임계영역 내에서 Context-Switch 가 발생하지 않는다면, 절대로 일어날

수 없는 상황입니다.

그러나, 여러개의 CPU로 동작하는 서버의 경우 실제적으로 여러 쓰레드가 동시에 실행되는 상황이 발생합니다. 그러므로, 아무리

임계영역이 짧아도 이 루틴의 호출빈도가 잦다면, 이런 상황이 자주 발생할 수 있습니다.

그러면, 한 쓰레드가 Blocking 됐다가 깨어나는 작업이 왜 문제가 되느냐?

이 작업이 결코 공짜가 아니라는 데에 문제가 있습니다. 잦은 Context-Switching 은 시스템의 성능을 저하시킵니다.

이런 문제를 해결하는 하나의 방법으로 spin-lock 이라는 걸 사용하는 겁니다. 어떻게 동작하느냐 하면,

int nSpins;

for (nSpins = spinCount; nSpins > 0; nSpins--)

    if (TryEnterCriticalSection(&cs))

        break;

if (nSpins == 0)

{

    // 처리불가, Sleep 또는 EnterCriticalSection(&cs)); 호출

}

와 같은 형태로 구성됩니다. spinCount 횟수만큼 임계영역으로 들어갈 수 있는지를 시도해 보는 겁니다.

들어갈 수 있으면 임계영역의 코드를 실행하고, 들어갈 수 없으면 다시 재시도 합니다.

spinCount는 CPU 갯수 - 1 로 최적화 시키는 것이 일반적일 겁니다.(당연히 CPU가 하나뿐인 시스템에는 적용 안합니다)

이유는 현재 쓰레드가 실행되는 CPU 를 제외한 다른 CPU 가 임계영역을 빠져 나오기를 기다리는 것이 가장 합리적이기 때문입니다.

그러므로, 임계영역이 짧은 경우는 일반적인 EnterCriticalSection 보다 이런 형태의 spin-lock 을 사용하는 것이 더 효과적입니다.

CRITICAL_SECTION은 이 처리를 위해 예로 제시한 루프를 돌리지 않아도 윈도우가 자동으로 이 작업을 해 주는 경우가 있습니다.

InitializeCriticalSectionAndSpinCount 로 CRITICAL_SECTION을 초기화할 경우입니다.

그러나, 주의할 점은 임계영역이 긴 경우, 또는 임계영역 내에서 I/O 함수를 호출할 경우, 또는 윈도우 API 를 호출하는 경우 등등의 경우는 이런 방법을 사용하지 않는게 좋습니다.

아니, 사용하지 않는게 좋은게 아니라 절대 사용하면 안됩니다.

앞에서도 언급했지만, 숫자값의 연산과 같은 아주 단순한 처리를 행하는 짧은 임계영역을 사용할 때를 대상으로 하는 겁니다.

쓰레드간의 공유에 대해서는 TryEnterCriticalSection 이나 InitializeCriticalSectionAndSpinCount 로 이런 문제를 해결할 수 있습니다.

그러면, 프로세스간의 공유에 대해서는 어떻게 될까요?

이 문제를 해결하기 위해서는 WaitForSingleObject(hMutex, 0) 을 대신 사용하는 방법밖에 없습니다.

WaitForSingleObject 는 상당히 덩치가 큰 API 입니다. spin-lock 을 처리하기 위해 이렇게 긴 API 를 호출한다는건 조금 비합리적이지 않을까요?

그래서 윈도우 프로그램에서는 일반적으로 프로세스간의 공유에 있어서는 spin-lock 을 잘 사용하지 않습니다.

여기서, POSIX 의 뮤텍스를 잠시 살펴 보면, 뮤텍스 객체가 윈도우와 달리 커널에 존재하지 않습니다. 쓰레드간의 뮤텍스이건 프로세스간의 뮤텍스이건, POSIX 의 뮤텍스는 윈도우의

CRITICAL_SECTION 과 비슷한 형태로 관리되기 때문에 윈도우의 뮤텍스에 비해 훨씬 가볍습니다. 그리고, 이런 형태의 spin-lock 의 처리도 용이합니다.

실제로 Unix 나 Linux 의 어플리케이션은 대부분 락을 걸기 전에 이런 시도를 거치는 경우가 많이 있는데, 윈도우 어플리케이션은 그런 경우를 거의 못본거 같습니다.

윈도우의 경우 클라이언트 어플리케이션이 더 많기 때문일 수도 있을거 같기는 합니다만...

윈도우에서도 단순히 spin-lock 을 통해 Busy-waiting 을 수행할 경우는 OS 의 지원을 받을 필요가 없기 때문에 커널 객체 없이 사용자모드 자체로 구현이 가능합니다.

그래서, 이런 기능을 수행하는 함수를 만들어 봤습니다.

void light_lock(long* _lock)

{

    int a;

    for (;;) {

        __asm {

            mov edx, _lock;

            cmp dword ptr[edx], 0;

            jne retry;

            mov eax, 1;

            xchg eax, dword ptr[edx];

            cmp eax, 0;

            jne retry;

        }

        break;

retry:

        __asm {

            pause;

        }

    }

}

void light_unlock(long* _lock)

{

    *_lock = 0;

}

쓰레드간의 동기화에 있어서는 long 타입의 변수 하나를 선언하고 초기값을 0 으로 설정합니다.

light_lock 을 수행해 성공한 쓰레드는 이 변수를 1 로 설정하고 임계영역으로 들어 갑니다.

그렇지 못한 쓰레드는 pause Instruction 을 호출하여 잠시 대기한 후 다시 시도합니다.

pause 는 펜티엄4 에서 새롭게 기능이 개선된 명령입니다. 이 명령을 수행함으로써 CPU 에게 spin-lock 을 수행한다는 힌트를 주게 됩니다.

프로세스간의 동기화에 있어서는 역시 long 타입의 변수를 공유메모리로 선언합니다. 윈도우는 공유메모리가 파일맵핑 뿐이므로 파일맵핑

메모리로 선언하여 위의 함수를 수행하면 됩니다.

Mutex 와는 비교가 안되고, CRITICAL_SECTION 보다도 더 가볍기 때문에 단순한 동기화가 필요한 경우 활용가치가 높을 거라 생각됩니다.

물론 Busy-waiting 이니까 절대 대기시간이 길지 않은 작업에만 사용해야 겠지만...

아직 실무 적용을 한 소스는 아니고, 일단 시스템 성능 향상을 위해 나름대로 생각해 본 방법입니다.

출처 :http://blog.naver.com/xtelite/50023358990

MFC에서의 Multithread

OS는 구분하지 않지만 MFC는 사용자 편의를 위하여 두 가지 형태로 지원

1.     Worker thread

2.     User Interface thread

Worker thread

::AfxBeginThread() 함수를 이용

CWinThread* ::AfxBeginThread(

       AFX_THREADPROC pfnThreadProc,

       LPVOID pParam,

       int nPriority = THREAD_PRIORITY_NORMAL, // 기본적으로 주 Process와 동일

       UINT nStackSize = 0,

       DWORD dwCreateFlags = 0,                      // 0 또는 CREATE_SUSPENDED

       LPSECURITY_ATTRIBUTES lpSecurityAttrs = NULL

);

우선 Thread를 이용할 함수를 먼저 정의한다

UINT ThreadFunc(LPVOID pParam)

{

       int option = (int)pParam;

       …

}

만약 인자가 많은 경우에는

typedef struct tagPARAMS

{

       ...

} PARAMS;

와 같이 한 후에

PARAMS *pParams = new PARAMS;

CWinThread *pThread = ::AfxBeginThread(ThreadFunc, &pParams);

와 같이 하고

UINT ThreadFunc(LPVOID pParam)

{

       PARAMS *pThreadParams = (PARAMS *)pParam;

       ...

       delete pThreadParams;

       return 0;

}

와 같이 사용하면 된다.

Thread를 잠시 중지시키고 싶을 때는 주 Process에서

pThread->SuspendThread();

다시 돌리고 싶을 때는 주 Process에서

pThread->ResumeThread();

와 같이 하면 된다.(Thread 자신이 호출할 수는 없다.)

또는 경우에 따라서는

Sleep(2000);

과 같이 사용할 수도 있는데 이 경우는 제어권을 다른 Process에 넘겨 주게 된다.

Sleep(0);

와 같이 할 경우에는 우선 순위가 높거나 같은 Process에 넘겨 주고 우선 순위가 높거나

같은 Process가 없을 경우에는 아무 일도 생기지 않는다.

Thread를 종료시키고 싶을 때는 TerminateThread() 함수를 사용하면 되는데 이 경우 Thread 함수가

내부 정리를 하지 못할 수가 있기 때문에 다음과 같은 방법이 많이 사용된다.

static BOOL bContinue = TRUE;

CWinThread *pThread = ::AfxBeginThread(ThreadFunc, &bContinue);

…

UINT ThreadPrintNum(LPVOID pParam)

{

       BOOL *pbContinue = (BOOL *)pParam;

       while ( *pbContinue )

       {

             …

       }

       return 0;

}

와 같이 하고 bContinue 값을 FALSE로 하면 Thread 함수가 종료된다.

Thread가 완전히 종료된 것을 확신해야 하는 경우에는

if ( ::WaitForSingleObject(pThread->m_hThread, INFINITE) )

{

       // 이곳은쓰레드가확실히종료된상태임

}

와 같이 하면 된다. Thread가 죽어 버려서 먹통이 되는 경우까지 대비하려면

DWORD result;

result = ::WaitForSingleObject(pThread->m_hThread, 1000);   // 1초기다림

if ( result == WAIT_OBJECT_0 )

{

       // 이곳은쓰레드가확실히종료된상태임

}

else if ( result == WAIT_TIMEOUT )

{

       // 1초가지나도쓰레드가종료되지않은상태

}

이 방법을 사용해야 한다. 어떤 Thread가 현재 실행 중인지 알고 싶을 때는

if ( ::WaitForSingleObject(pThread->m_hThread, 0 ) == WAIT_TIMEOUT )

{

       // pThread 실행중

}

else

{

       // pThread가실행중이아님

}

와 같이 하면 된다.

User Interface Thread

User interface thread는 그 자체로 윈도우와 메시지 루프를 가지고 있다.

class CUIThread : public CWinThread

{

       DECLARE_DYNCREATE(CUIThread)

public:

       virtual BOOL InitInstance();

};

이 User interface thread는 독자의 윈도우도 가질 수 있다. 일반적으로 전용 Dialog를 띄워

Thread를 처리하는 경우가 많으므로 이 User Dialog를 CMyDialog라고 이름 지었다고 가정하면

IMPLEMENT_DYNCREATE(CUIThread, CWinThread)