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

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

간략한 소스코드

#include <iostream>
#include <iterator>
#include "myList.h"

int main(void)
{
	using namespace std;

	myList<int> src;

	for(int i = 0;i < 10; i++)
		src.push_back(i);
	
	copy(src.rbegin(), src.rend(), ostream_iterator<int>(cout, " "));
	cout << endl;
	
	system("pause");
	return 0;
}

myList.h

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

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

고쳤다능 ㅠ.ㅠ





소스코드보기










































































#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>

template <class BidirectionalIterator>
void duplex_selection_sort(BidirectionalIterator first, BidirectionalIterator last);

int main(int argc, char *argv[]) {	
    using namespace std;	
    vector<int> array0, array1, array2;	
    ostream_iterator<int> output(cout, " ");	

    for(int i = 1; i <= 10; i++) {		
        array0.push_back(i);                 		
        array1.push_back(i);		
        array2.insert(array2.begin(), i);	
    }	

    random_shuffle(array0.begin(), array0.end());               	

    cout << "before sort" << endl;	
    copy(array0.begin(), array0.end(), output);	
    cout << endl;	
    copy(array1.begin(), array1.end(), output);	
    cout << endl;	
    copy(array2.begin(), array2.end(), output);	
    cout << endl;	
    
    duplex_selection_sort(array0.begin(), array0.end());	
    duplex_selection_sort(array1.begin(), array1.end());	
    duplex_selection_sort(array2.begin(), array2.end());  	

    cout << "\nafter sort" << endl;	
    copy(array0.begin(), array0.end(), output);	
    cout << endl;	
    copy(array1.begin(), array1.end(), output);	
    cout << endl;	
    copy(array2.begin(), array2.end(), output);	
    cout << endl;	

    return EXIT_SUCCESS;
}

template <class BidirectionalIterator>
void duplex_selection_sort(BidirectionalIterator first, BidirectionalIterator last) {	 	
    BidirectionalIterator min, max;
	
    while(last > first)	{		
        min = max = first;
		
        for(BidirectionalIterator i = first; i != last; i++) {			
            if(*min > *i)				
                min = i;
			
            if(*max < *i)				
                max = i;		
        }
		
        if( (max == first) && (min == last - 1) ) {			
            std::iter_swap(first, last - 1);		
        } 
        else if(max == first) {			
            std::iter_swap(max, last - 1);			
            std::iter_swap(first, min);		
        } 
        else {			
            std::iter_swap(min, first);			
            std::iter_swap(max, last - 1);		
        }		
        first++;		
        last--;	
    }
}



Output: 









before sort
5 4 8 9 1 6 3 2 7 10 
1 2 3 4 5 6 7 8 9 10 
10 9 8 7 6 5 4 3 2 1 

after sort
1 2 3 4 5 6 7 8 9 10 
1 2 3 4 5 6 7 8 9 10 
1 2 3 4 5 6 7 8 9 10 

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

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

....작성중임다..(찍 쌌습니다 08/08/22)


2. 반복자 Iterator

2장부터 STL의 주요한 개념들을 하나씩 설명하겠습니다. 이번장에서는 저번에 만들어 봤던 block과 이번에 만들어볼 연결 리스트를 이용해서 반복자의 개념과 필요성에 대해 살펴볼 예정입니다. .....예정만 -_-

반복자란?

STL은 자료구와 알고리즘, 반복자의 집합이라고 말할 수 있다.자료구조와 알고리즘은 그동안 많이 들어왔던 것으로 익숙하기 짝이 없지만......반복자란 뭘까? 내가 생각하기에 반복자는 자료구조와 알고리즘을 연결해주는 일반적인 통로다. 알고리즘은 자료구주에 직접 접근하는것이 아니라 반복자란것을 통해서 자료구조에 접근한다. 대충 아래 그림과 같은 상황이다.

아래 함수를 살펴보면서 반복자가 뭔지 감을 잡아보도록하자.

반복자 개층도

모든 반복자는 상위 개념의 반복자가 가지는 특징을 상속받아야함

               명백한 반복자

입력 반복자                출력 반복자

               전진 반복자

             양방향 반복자

           임의 접근 반복자

명백한 반복자 Trivial Iterator

모든 반복자가 가져야할 일반적인 특징들, STL에서는 개념적으로만 정의되어 있음

입력 반복자 Input Iterator

단일 패스이며 read-only한 반복자

출력 반복자 Output Iterator

단일 패스이며 write-only한 반복자

* 연산을 사용해 값을 대입하면 값이 써짐

전빈 반복자 Foward Iterator

단일 패스이며 읽기와 쓰기가 모두 가능하지만 단일 패스임

양방향 반복자 Bydirection Iterator

읽기와 쓰기가 모두 가능하고 포인터 산술 연산의 --가 정의되어 있음

임의 접근 반복자 Random Access Iterator

일기와 쓰가가 모두 가능하고 포인터 산술 연산의 p + n과 []연산이 정의되어 있음

이 글은 스프링노트에서 작성되었습니다.

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

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

1. 템플릿

 Standard Template Library라는 이름에서 알 수 있듯이 STL은 C++의 템플릿이라는 기능을 이용하여 제네릭 프로그래밍을 실현하고 있다.  STL의 모든것은 템플릿으로 작성되어 있기 때문에 STL을 이해하려면 템플릿에 대해 어느정도 이해가 필요하다.템플릿에 대해잘 알고 있는 사람은 이번장을 건너뛰어도 관계가 없심.

 템플릿이란?

 간단하게 말해서 템플릿은 여러 타입에 대해 동작하는 일반 클래스와 함수를 만들 수 있게 해주는 유용한 도구인거심. 많은 책과 문서들이 탬플릿을 설명하는데 max함수의 예를들어 설명하고 있고 이게 상당히 적절함으로 우리도 max함수를 살펴보면서 이야기를 진행하도록 하겠삼

1. int max(int a, int b)
2. {
   1. if(a > b)
      
      1. return a;
   2. return b;
3. }

함수 템플릿

어려운 방법

 여러 타입의 변수에대해 동작하는 max함수를 만드는데는 3가지 방법이 있는데, 하나는 define 매크로를 이용하는 것임다. 가장 어려운 방법이고 가장 인기없는 방법이삼.

1. #include <iostream>
2.  
3. #define define_max(type) type max(type a, type b) { \
   
   1. if(a > b)       \
      
      1. return a;    \
   2. return b;       \
4. }
5.  
6. define_max(int);
7. define_max(double);
8. define_max(char);
9. int main(void)
10. {
    
    1. using namespace std;
    2.  
    3. double f = max(3.5, 8.7);
    4. int i = max(100, 800);
    5. char ch = max('A', 'Q');
    6. .....어쩌구 저쩌구....
    7. return 0;
11. }

위의 소스코드는 잘 동작하지만 define 매크로를 이용하는 방법은 큰 함수에서는 문제가 생긴다. 디버깅이 어렵도 매크로를 작성하기도 어렵다. 그래서 보통은 max함수를 오버로딩하는 방법을 선택한다.

1. int o_max(int a, int b)
2. {
   
   1. if(a > b)
      
      1. return a;
   2. return b;
3. }
4. double o_max(double a, double b)
5. {
   
   1. if(a > b)
      
      1. return a;
   2. return b;
6. }
7. ...어쩌구 저쩌구...

이 방법도 작 동작한다. 위 두가지 방법의 문제는 새로운 타입의 max함수를 사용할 때 마다 매크로를 호출하거나 새로운 함수를 만들어야 한다는 것이다. 특히 오버로딩을 하는 사용하면 필요한 모든 경우에 대해 일일히 함수를 작성해야 한다. 참으로 화나는 일이다. -_-;;

편한 방법

 템플릿을 사용하면 위에서 언급된 문제점들을 피할 수 있고 무엇보다 편함. 좋은게 좋은거임  >.<

1. #include <iostream>
2.  
3. template<typename kind>
4. kind t_max(kind a, kind b)
5. {
   
   1. if(a > b)
      
      1. return a;
   2. return b;
6. }
7. int main(void)
8. {
   1. using namespace std;
   2.  
   3. int a = t_max(1, 8);
   4. char ch = t_max('A', 'Q');
   5. double d = t_max(1.5, 8.9);
   6.  
   7. ...어쩌구 저쩌구...
   8.  
   9. return 0;
9. }

이제 문제는 해결 됐다. 필요한 버젼의 max함수가 알아서 생성되니 우리는 사용만 하면 되는거심. 우리가 max함수에 사용하는 타입이 operator>를 지원하기만 하면 각종 버젼의 max함수를 만들지 않아도 되니 좋지 아니할수가 없심다.

그런데 여기서도 한가지 문제가 생겼으니 문자열에 관한 max함수 인거심. char* 타입은 단순히 > 연산을 사용해서 크기를 비교 할 수 없으니 우리의 템플릿 max함수가 제대로 동작할 수 없심. 이때 사용하는것이 바로 전문화란 것으로 특정한 버젼의 max함수를 명시적으로 선언하는 것이 되겠심다.

1. char *t_max(char *a, char *b)
2. {
   
   1. if(strcmp(a, b) < 0)
      
      1. return a;
   2. return b;
3. }

이제 max함수는 char* 타입에 대해서도 정확히 동작하게 되었습니다.

클레스 템플릿

템플릿 함수를 만드는 것 처럼 클래스에도 템플릿을 적용할 수 있다. 클래스 탬플릿은 함수 템플릿보다 조금 더 복잡하지만 선언은 더 쉽다. 간단한 클래스를 만들어 보겠심다. 아래 소스 코드는 cpp파일에 넣지말고 block.h 따위의 해더 파일을 만들어서 따로 include하기 바랍니다. 그리고 템플릿 클래스의 메소드는 아래처럼 몽땅 inline화 시켜야 합니다.

1. template<typename T>
2. class block {
   
   1. public:
      
      1. T &operator[](int n) {
         
         1. return arr[n];
      2. }
   2. private:
      
      1. T arr[10];
3. };

종류는 알 수 없지만 아무튼 T라는 타입의 크기 10짜리 배열을 가지고 []연산자를 통해서 접근할 수 있는 클래스임다. 간단하게 배열을 클래스화 시키고 템플릿을 사용해서 어려 타입에 관한 버젼을 만들었심니다. 간단하고 잘 작동하는 훌륭한 클래스 인거심다. 함수 탬플릿과 마찬가지로 클래스 탬플릿도 전문화 할 수 있지만 여기서는 다루지 않겠심다. 이렇게 만든 템플릿 클래스는 다음과 같이 사용합니다.

1. int main(void)
2. {
   
   1. using namespace std;
   2. block<int> arr;
   3. arr[3] = 5;
   4. cout << arr[3] << endl;
   5. return 0;
3. }

클래스의 이름을 쓰고 <>안에 타입의 이름을 써주면 템플릿 클래스를 인스턴스화 할 수 있습니다. 아래처럼 한 템플릿에 여러가지 타입을 사용할 수도 있습니다.

1. template<typename T, typename K>
2. ...어쩌구 저쩌구...

이런 경우에도 선언시 <>안에 타입의 이름을 적어주면 됨니다.

1. block<int, char> arr;

#비타입 인수

템플릿의 인수는 타입만이 가능한것이 아니라 비 타입인자(상수)나 다른 템플릿도 가능합니다. 비 타입인자를 사용해 우리의 block 클래스를 더 좋게 만들어 보겠습니다.

1. template<typename T, int n>
2. struct block {
   
   1. T& operator[](int n) {
      
      1. return arr[n];
   2. }
   3. T arr[n];
3. };

block를 클래스가 아닌 구조체로 선언하는 트릭을 사용해서 block을 인스턴스화 할때 배열처럼 {}를 사용한 초기화를 가능하도록 만들었습니다. 아래와 같이 사용하면 됨니다.

1. int main(void)
2. {
   
   1. using namespace std;
   2. block<int ,10> arr;
   3. block<block<int, 10>, 10> arr2;
   4. block<char, 5> chr = {'a', 'b', 'c', 'd', 'e'};
   5. arr[5] = 5;
   6. arr[5][5] = 55;
   7. cout << arr[5] << endl;
   8. cout << arr2[5][5] << endl;
   9. cout << chr[3] << endl;
   10. return 0;
3. }

간단한 트릭으로 block와 배열의 차이점이 없어져 버렸습니다. 오히려 block은 각종 메소드를 추가하면 더욱 강력하게 만들 수 있기 때문에 이제 배열의 시대는 끝난것 처럼 보입니다.

#템플릿의 인스턴스화

마지막으로 템플릿 함수와 클래스가 언제 인스턴스화 되는지를 알아보겠심다.

간단하게 말해서 템플릿은 컴파일이 거의 끝나가는 시점에서 기계어를 만들어내기 직전에 인스턴스화 됨니다. 따라서 위에서 살펴봤던 비 타입인자를 사용할때 소스코드안에 다음과 같은 구문이 있다면

1. block<int, 5> arr;
2. block<int, 10> arr2;

int arr[5]와 int arr[10]을 가지는 block이 컴파일 타임에 만들어 지게 됨니다. 위에서 비 타입인자를 설명할때 '비 타이인자(상수) ' 라고 언급한건 이와 같은 특징 때문입니다. 템플릿에 사용된 비 타입인자들은 모두 컴파일 타임에 결정되기 때문에 상수이외에는 사용할 수 없는 거심다. 바꿔 말하면 비 타입인자를 사용하면 컴파일 타임에 모든것이 결정되기 때문에 고속 라이브러리를 만들 수 있다고 하는데....해보질 못해서 모르겠심다 -_-;

아무튼 이러한 특징 때문에 block는 동적할당을 할 수가 없습니다. 물론 동적할당이 가능하도록 수정할 수는 있지만 그렇게 되면 {} 초기화를 사용할 수 없습니다. 배열은 배열대로 나름 쓸때가 있는 거심다. 안타깝지만 block 클래스는 이대로 내버려 두고 1장을 마침니다.

이 글은 스프링노트에서 작성되었습니다.

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

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

차례

• 발로 쓴 STL 강좌 0 - 강좌 소개
• 발로 쓴 STL 강좌 1 - 템플릿
• 발로 쓴 STL 강좌 2 - 반복자
• 컨테이너
• 알고리즘과 함수 객체
• 실전예제

강좌 소개

 이 강좌의 목적은 독자가 STL의 구조를 어느정도 이해하고 구조의 이해를 바탕으로 라이브러리를 사용하데 있습니다. 이 문서는 구체적인 내용은 다루지 않습니다. -_-;; 업로드는 제가 시간 날때마다 조금씩 할 예정이고 그때 그때 강좌가 공개 됩니다. 그리고 반말과 존대말이 마구 섞여서 사용될태니 이점도 이해해 주시기 바람니다

 총 5회에 걸쳐서 업로드될 예정이며 STL의 근간이 되는 템플릿에 대해 한 회를 할예하고, STL의 중요한 개념인 반복자와 컨테이너에 각각 한회를 할예할 예정입니다. 마지막으로 STL에서 지원하는 알고리즘들을 살펴보면서 함수객체에 대해서 알아보고 실전 예제를 끝으로 강좌가 마무리 될 예정입니다.

STL을 사용함에 있어 제네릭 프로그래밍에 대해서 대충 알아둘 필요가 있으니 구글과 상당해 보시기 바람니다.

이 글은 스프링노트에서 작성되었습니다.