블로그는 귀차니즘

  예전부터 책을 읽을때 마다 보이는 것이 특질이라는 단어 였습니다. 원어 로는 traits라고 적혀져 있더군요. 그런데 C++ 이라는 언어를 총체적으로 이해를 못해서 그런지 아니면 제가 이해를 잘 못해서 그런지는 몰라도 잘 이해가 되지 않는 부분이었습니다.
  그런데 이 특질이라는 부분이 유용하게 사용되더군요. 이게 무엇인가 하면. 템플릿 특수화를 이용한 데이터 타입의 정의(?)를 통한 사용확장 이라고 생각하시면 될 것 같습니다. 적어도 저는 부족하나마 그렇게 이해했습니다.( 혹시 틀린게 있다면 댓글을 달아주세요. )

type.cpp (Language : cpp)

1. #include <iostream>
2. #include <vector>
4. int main( int argc, char **argv )
5. {
6.     std::vector< int > aaa;
8.     aaa.push_back( 1 );
10.     int a = aaa.front();
11.     std::vector< int >::reference b = aaa.front();
13.     std::cout << a << " " << b;
14. }

  위의 코드를 보면 integer 형태의 변수 a를 통하여 aaa container 의 front 값을 받아올 수도 있고, std::vector< int >::reference 같은 것으로 인하여 데이터를 대신 받을 수 있습니다. 여기서 하나 살펴봐야 할 부분이 std::vector< int >와 같이 선언 부분에서 typename 을 다르게 주면 당연 reference 부분도 함께 바뀌어야 합니다. 그 것이 가능한 까닭은 std::vector 선언 부분을 보시면 알 수 있습니다.

vector.cpp (Language : cpp)

1. template<class _Ty,
2.     class _Ax>
3.     class vector
4.         : public _Vector_val<_Ty, _Ax>
5.     {   // varying size array of values
6. public:
7.     typedef vector<_Ty, _Ax> _Myt;
8.     typedef _Vector_val<_Ty, _Ax> _Mybase;
9.     typedef typename _Mybase::_Alty _Alloc;
10.     typedef _Alloc allocator_type;
11.     typedef typename _Alloc::size_type size_type;
12.     typedef typename _Alloc::difference_type _Dift;
13.     typedef _Dift difference_type;
14.     typedef typename _Alloc::pointer _Tptr;
15.     typedef typename _Alloc::const_pointer _Ctptr;
16.     typedef _Tptr pointer;
17.     typedef _Ctptr const_pointer;
18.     typedef typename _Alloc::reference _Reft;
19.     typedef _Reft reference;
20.     typedef typename _Alloc::const_reference const_reference;
21.     typedef typename _Alloc::value_type value_type;
22. .
23. .
24. .
25. 생략

  바로 template 를 통한 객체의 선언에 대한 한 벌의 해석이 만들어 질 때, typedef 를 통하여 _Alloc::reference 를 Reference 로 정의해줍니다. 그럼 밖에서는 해당 클래스 내부의 refernce 로 접근을 하거나 value_type으로 접근하면 값에 대한 접근이 가능하죠. _Alloc 이라는 부분 상세한 것 까지는 저도 잘 모르는 부분이고 계속하여 보고 있는 부분이기 때문에 곧 원인이 나올 것 같습니다.
  이런 부분에 대하여 typedef 가 이루어지는 것을 볼 수 있는데, 한 가지 의문이 생깁니다. 과연 이러한 많은 Container를 지원하는 함수를 만들어야 하고, 그 함수 안에서 변수를 임시로 담는다거나 하는 부분에 대해서는 어떻게 구현을 해야 하는가 입니다. 어려울 것 같지만 간단하게 구현할 수 있습니다.

xutility (Language : cpp)

1. template<class _Iter>
2.     struct iterator_traits
3.     {   // get traits from iterator _Iter
4.     typedef typename _Iter::iterator_category iterator_category;
5.     typedef typename _Iter::value_type value_type;
6.     typedef typename _Iter::difference_type difference_type;
7.     typedef difference_type distance_type;  // retained
8.     typedef typename _Iter::pointer pointer;
9.     typedef typename _Iter::reference reference;
10.     };
12. template<class _Ty>
13.     struct iterator_traits<_Ty *>
14.     {   // get traits from pointer
15.     typedef random_access_iterator_tag iterator_category;
16.     typedef _Ty value_type;
17.     typedef ptrdiff_t difference_type;
18.     typedef ptrdiff_t distance_type;    // retained
19.     typedef _Ty *pointer;
20.     typedef _Ty& reference;
21.     };
22. .
23. .
24. .
25. 생략

  std:: 표준 헤더에 이렇게 iterator_traits 가 선언되어있더군요. 템플릿 특수화를 사용하여 여러경우에 대하여 대처해놓은 것을 알 수 있습니다. 그럼 이 것으로 뭘 하면 될까요??

SimpleTese.cpp (Language : cpp)

1. #include <iostream>
2. #include <vector>
4. template< typename T >
5. void print( T T1 )
6. {
7.     std::iterator_traits< T >::value_type Value1 = *T1;
9.     std::cout << Value1;
10. }
12. int main( int argc, char **argv )
13. {
14.     std::vector< int > aa;
15.     aa.push_back( 1 );
17.     print( aa.begin() );
18. }

  코드를 위와 같이 사용했을 경우 std::vector< int > 라던가 std::vector< char > 라던가 어떠한 데이터 타입에 대한 Container에 대해서 함수가 의존성을 가지지 않게 됩니다. 함수가 더욱 확장성이 있어지는 것이죠. 전의 RLE8, LZSS 인코딩 같은 경우 그 특성상 BYTE 인코딩을 전제하고 있었으므로 char 타입으로 고정시켰습니다.
  하지만 이 경우는 좀 다르겠죠^^? 똑같은 코드를 바꿔서 치는 것만큼 어리석은 일은 없을거라고 생각하기 때문에 이런 방법들을 사용하여 뭔가 더욱 활용성 있고 확장성 있는 함수를 만들 수 있을것 같습니다.

크리에이티브 커먼즈 라이센스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.

  std::vector, std::list 등의 간단한 데이터 컨테이너나 std::map 같은 1:1 매칭 컨테이너를 사용하면 한 가지 아쉬울 때가 있습니다. 바로 1:Many 매칭 구조에서 자료를 쉽게 사용할 수 없다는 것인데요. 잘 모르는 분은 구현
을 위해서 std::pair 등을 사용하여 구현하기도 합니다만 이 것은 큰 낭비라고 할 수 있죠.

vectorPair.cpp (Language : cpp)

1. #include <vector>
3. int main( int argc, char **argv )
4. {
5.     std::vector< std::pair< int, double > > Abc;
6.     Abc.push_back( std::make_pair( 1, 1.1 ) );
7.     Abc.push_back( std::make_pair( 1, 2.1 ) );
8.     Abc.push_back( std::make_pair( 1, 3.1 ) );
9.     Abc.push_back( std::make_pair( 2, 4.1 ) );
10.     Abc.push_back( std::make_pair( 4, 5.1 ) );
12.     for( std::vector< std::pair< int, double > >::const_iterator Iter = Abc.begin(); Iter != Abc.end(); ++Iter ){
14.         std::pair< int ,double > Data = *Iter;
15.         // Data.fisrt 가 같을 경우 처리..
16.     }
18.     return 0;
19. }

  이렇게 작성할 수도 있지만 이 것은 std::pair 에 대한 불필요한 값이 복사되는 cost가 발생함으로 비효율적인 코드가 될 수 있습니다. 그래서 기본적으로 지원하는 Container로써 std::multimap이 존재하죠. 물론 추가적으로 std::map 이 std::hash_map으로 확장되어 비표준 Container로써 지원되듯이 std::multimap 또한 std::hash_multimap 으로 확장되어 비표준으로 지원되긴 합니다. 하지만 간단히 std::multimap을 살펴보면 다음과 같이 사용할 수 있습니다.

multimap.cpp (Language : cpp)

1. #include <map>
3. int main( int argc, char **argv )
4. {
5.     std::multimap< int, double > Abc;
6.     Abc.insert( std::make_pair( 1, 2.1 ) );
7.     Abc.insert( std::make_pair( 1, 2.1 ) );
8.     Abc.insert( std::make_pair( 1, 3.1 ) );
9.     Abc.insert( std::make_pair( 2, 4.1 ) );
10.     Abc.insert( std::make_pair( 4, 5.1 ) );
12.     std::multimap< int, double >::const_iterator StartIter  = Abc.lower_bound( 1 );
13.     std::multimap< int, double >::const_iterator EndIter    = Abc.upper_bound( 1 );
15.     while( StartIter != EndIter )   {
17.         // StartIter->first 가 같은것에 대한 second 값 처리
18.     }
20.     return 0;
21. }

  다음과 같이 된다면 불필요한 값 뿐만 아니라 loop 에 있어서 모든 부분을 참조하지 않아도 되기 때문에 그 만큼의 비용이 절감된다고 생각할 수 있습니다. 그리고 추가적으로 hash_map, hash_multimap 같은 경우는 비표준이기 때문에 들어있는 namespace가 달라질 수 있습니다. 예를 들면 VS.net 2003 같은 경우 std에, VS.net 2008 같은 경우 stdext 에 들어있죠. 때에 따라 알맞은 Container를 사용하여 cost를 줄이는게 좋을것 같습니다.

크리에이티브 커먼즈 라이센스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.

  새삼스럽게 적는 것 네요. 많은 분들이 알고 계실거라 생각하고 있지만 의외로 주위에 후위연산을 주로 사용하던 사람들은 이에 대한 차이를 모르는 경우가 많더군요. 그래서 생각 나는김에 한 번 포스팅 해봅니다.
  STL 컨테이너를 비롯하여 많은 Iterator 사용소스를 보면 후위( a++ )연산자를 사용하지 않고 전위 연산자를 주로 사용하는 것을 보실 수 있으실 겁니다. 그 것은 바로 효율성 면에서 차이가 발생하기 때문에 그렇습니다. 간단히 integer형 변수 같은 경우엔 전위 연산이나 후위 연산이나 선수를 제외한 성능에 대한 차이는 발생하지 않습니다.

Compile.cpp (Language : cpp)

1. #include <iostream>
3. int main( int argc, char **argv )
4. {
5.     int a = 0;
6.     ++a; 혹은 a++;
7.     return 0;
8. }

후위연산.cpp (Language : asm)

1. 00401196    E8 65FEFFFF CALL TestPost.main
2. 0040119B    83C4 0C  ADD ESP,0C
3. 0040119E    8BF0        MOV ESI,EAX
4. 004011A0    8975 D8  MOV DWORD PTR SS:[EBP-28],ESI
5. 004011A3    397D E4  CMP DWORD PTR SS:[EBP-1C],EDI
6. 004011A6    75 06      JNZ SHORT TestPost.004011AE
7. 004011A8    56    PUSH ESI
8. 004011A9    E8 9C010000 CALL TestPost.exit

전위연산.cpp (Language : asm)

1. 00401196    E8 65FEFFFF CALL TestPost.main
2. 0040119B    83C4 0C  ADD ESP,0C
3. 0040119E    8BF0        MOV ESI,EAX
4. 004011A0    8975 D8  MOV DWORD PTR SS:[EBP-28],ESI
5. 004011A3    397D E4  CMP DWORD PTR SS:[EBP-1C],EDI
6. 004011A6    75 06      JNZ SHORT TestPost.004011AE
7. 004011A8    56    PUSH ESI
8. 004011A9    E8 9C010000 CALL TestPost.exit

  위를 보시면 간단히 Compile.cpp를 전위연산과 후위연산을 적용하여 컴파일을 해보았습니다만 생성된 실행코드에서 차이점이 발견되지 않습니다. 결국 성능상의 차이가 없다는 말이 되겠죠? 물론 CPU 아키텍쳐상으로 깊게 들어가서 ++연산이 어떠한 명령어 중간에 사용 되었을 때, 파이프라이닝에 대한 성능차이가 발생할 수 있다고 생각을 하시는 분도 계시겠지만 여기서 그 부분 까지는 생각할 것이 아니라고 생각합니다.
  그런데 왜 STL Iterator 는 성능 차이가 발생할 수 있을까요? 답을 아시는 분은 다 알고 계시겠지만 Operator Overloading 이라는 문법때문에 생기는 문제입니다. 간단히 std::vector 클래스를 살펴보면 내부 클래스로 Iterator 클래스가 존재하고 그 안에 ++, -- 연산자에 대한 오버로딩 소스가 존재합니다.

vector (Language : cpp)

1. const_iterator& operator++()
2. {   // preincrement
3.     ++_Myptr;
4.     return (*this);
5. }
7. const_iterator operator++(int)
8. {   // postincrement
9.     const_iterator _Tmp = *this;
10.     ++*this;
11.     return (_Tmp);
12. }

  바로 위 소스죠. STL 벤더들 마다 구현이 약간씩 다르므로 꼭 이 것과 동일하다고 생각할 수는 없습니다. 하지만 일반적으로는 이러한 형태를 띄고 있죠. 그런데 ++ 연산자에 대하여 두 개의 오버로딩이 존재하죠?? 이 것은 전위, 후위 연산을 구별하기 위한 C++ 컴파일러의 한 가지 방법입니다. 인자에 아무것도 존재하지 않으면 전위연산, int 형 인자가 하나 전달되면 후위 연산이라고 정의되기 때문이죠.
  그런데 여기서 차이가 어떻게 생기냐?? 눈치 빠르신 분들은 코드를 먼저 보고 답을 알아내셨을지도 모르겠네요. 그 것은 객체 하나의 차이입니다. 보시다시피 전위연산은 _MyPtr을 하나 증가 시킨다음 그 에 해당하는 값을 바로 리턴하는데 반해 후위연산은 임시로 필요한 객체를 하나 생성하고 전위연산을 이용하여 증가시키는 작업 후 임시객체에 저장해놓았던 것을 리턴한다는 사실이죠. 결과적으로 보면 더 복잡해지는 것입니다. 그리고 Cost도 늘어나는셈이구요.
  사실 이 토픽은 스캇 마이어스저 Effective C++ 부분을 보면 자세히 나와있는 부분이기도 합니다. 이 것 말고도 많은 테크닉들이 존재하죠. 그 많은 테크닉을 하나하나 올바른 곳에 사용하는 방법을 아는 것이 중요하다고 생각이 듭니다.

크리에이티브 커먼즈 라이센스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.

1. 문제링크 : http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=37
   
2.  의   견   : 명령어 파싱에 대한 연습을 하는 문제라고 생각합니다. 한 가지 언어 특성상 Pointer를 이용한 List 형식으로 코드를 작성할 때 구현에 있어 난이도가 조금 있을 것입니다. 그리하여 STL을 부분적으로 사용했었고
   , 아마 지금 재작성 한다면 table을 비롯하여 모든 부분을 STL으로 작성할 것 같습니다.
   
3. 소스
   
   101.cpp (Language : cpp)

   1. #include <iostream>
   2. #include <deque>
   3. #include <string>
   5. using namespace std;
   7. deque< int > *table;
   8. int *link;
   9. int BlockNum;
   11. void returning( int index );
   12. void moving( int index1, int index2 );
   13. void piling( int index1, int index2 );
   14. void print();
   16. int main( int argc, char **argv )
   17. {
   18.     cin >> BlockNum;
   19.     if( 0 < BlockNum && BlockNum < 25 ) {
   20.         table = new deque< int >[ BlockNum ];
   21.         link = new int[ BlockNum ];
   22.         for( int i = 0; i < BlockNum; i++ ) {
   23.             link[ i ] = i;
   24.             table[ i ].push_back( i );
   25.         }
   26.         string cmd1;
   27.         int a;
   28.         string cmd2;
   29.         int b;
   30.         while( true ) {
   31.             cin >> cmd1;
   32.             if( cmd1 == "quit" ) {
   33.                 print();
   34.                 break;
   35.             }
   36.             cin >> a >> cmd2 >> b;
   37.             if( a != b && link[ a ] != link[ b ] && 0 <= a && a < BlockNum && 0 <= b && b < BlockNum ) {
   38.                 if( cmd1 == "move" ) {
   39.                     if( cmd2 == "onto" ) {
   40.                         // move A onto B
   42.                         returning( a );
   43.                         returning( b );
   44.                         moving( a, b );
   45.                     }
   46.                     else if( cmd2 == "over" ) {
   47.                         // move A over B
   48.                         returning( a );
   49.                         moving( a, b );
   50.                     }
   51.                 }
   52.                 else if( cmd1 == "pile" ) {
   53.                     if( cmd2 == "onto" ) {
   54.                         // pile A onto B
   56.                         returning( b );
   57.                         piling( a, b );
   59.                     }
   60.                     else if( cmd2 == "over" ) {
   61.                         // pile A over B
   62.                         piling( a, b );
   63.                     }
   64.                 }
   65.             }
   66.         }
   67.         delete [] table;
   68.         delete [] link;
   69.     }
   70.     return 0;
   71. }
   73. void returning( int index )
   74. {
   75.     int BlockIndex = link[ index ];
   76.     while( table[ BlockIndex ].back() != index ) {
   78.         int Block = table[ BlockIndex ].back();
   79.         table[ Block ].push_back( Block );
   80.         table[ BlockIndex ].pop_back();
   81.         link[ Block ] = Block;
   82.     }
   83. }
   85. void moving( int index1, int index2 )
   86. {
   87.     int a = link[ index1 ];
   88.     int b = link[ index2 ];
   89.     table[ b ].push_back( table[ a ].back() );
   90.     table[ a ].pop_back();
   91.     link[ index1 ] = link[ index2 ];
   92. }
   94. void piling( int index1, int index2 )
   95. {
   96.     deque< int > temp;
   97.     int BlockIndex1 = link[ index1 ];
   98.     while( table[ BlockIndex1 ].back() != index1 ) {
   99.         temp.push_back( table[ BlockIndex1 ].back() );
   100.         table[ BlockIndex1 ].pop_back();
   101.     }
   102.     temp.push_back( table[ BlockIndex1 ].back() );
   103.     table[ BlockIndex1 ].pop_back();
   104.     int BlockIndex2 = link[ index2 ];
   105.     while( !temp.empty() ) {
   106.         int linkTemp = temp.back();
   107.         temp.pop_back();
   108.         table[ BlockIndex2 ].push_back( linkTemp );
   109.         link[ linkTemp ] = link[ index2 ];
   110.     }
   111. }
   113. void print()
   114. {
   115.     deque< int >::iterator prt;
   116.     for( int i = 0; i < BlockNum; i++ ) {
   117.         cout << i << ":";
   118.         prt = table[ i ].begin();
   119.         while( prt != table[ i ].end() ) {
   120.             cout << " " << *prt;
   121.             prt++;
   122.         }
   123.         cout << endl;
   124.     }
   125. }

크리에이티브 커먼즈 라이센스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.