[ 혼연 정리 ] STL 개요 - 2 [ STL의 구조, 컨터이너 ]

ㅇ STL의 구조

                    

컨테이너 , 알고리즘, 반복자 : 중요한 요소
함수 객체 : 알고리즘의 활용성을 높이는 역할
어뎁터 : 다른 요소들을 약간만 수정하여 형태를 변경
할당기 : 컨테이너의 메모리를 관리하는 객체, 디폴트값이 선언되어 있음

 - 컨테이너 (Container)
 통, 그릇  : 무엇인가를 저장하는 것,  다른말로 컬렉션(Collection) 이라고 함 , 컨테이너는 3가지로 분류 된다.

① 시퀸스 컨테이너 (Sequence Container)
  자료의 선형적인 집합,  삽입되는 자료는 무조건 저장, 입력되는 자료에 특별한 제약이나 관리 규칙 없음
  벡터, 리스트, 데크가 제공된다.

② 연관 컨테이너(Associative Container)
    일정한 규칙에 따라 자료를 조직화하여 관리, 정렬이나 해시 등의 방법을 통해 삽입되는 자료를 일정한 기준(오름차순,해시)에 맞는 위치에 저장
    검색속도가 빠르다.  셋, 맵 등이 제공

③ 어뎁터 컨테이너(Adapter Container)
   시퀀스 컨테이너를 변형하여 자료를 미리 정해진 일정한 방식에 따라 관리, 스텍, 큐, 우선순위 큐 제공

- 컨테이너 사용방법
벡터와 리스트를 통해 일반화된 컨테이너 사용방법을 설명한다.

① 벡터
 쉽게 동적 배열이라고 생각하면됨, 요소의 개수에 맞게 자동으로 재할당하여 크기를 조정한다.

1 #include <iostream>
2 #include <vector>
3 /// STL의구성요소는전부헤더에저장되어있다. 그래서incude해야사용가능
4
5 using namespace std;
6
7 void main()
8 {
9     int num;
10     int i;
11
12     printf(" 배열크기를입력하시오: ");
13     scanf("%d", &num);
14     vector<int>vi(num);
15
16     for( i = 0 ; i < num ; i++ )
17     {
18         vi[i] = i * 2;
19     }
20
21     for( i = 0 ; i < num ; i++ )
22     {
23         printf("vi[%d] = %d \n", i, vi[i]);
24     }
25
26     printf("벡터의크기는%d 입니다. \n", vi.size());
27 }

STL의 구성요소들은 전부 헤더 파일에 선언되어 있다, 그래서 include 해야 쓸수 있음

정적 배열의 크기는 반드시 상수, 벡터는 변수로도 크기 지정가능

벡터의 요소를 참조할때는 정적배열과 마찬가지로 []연산자와 첨자를 사용하면 된다.

1 /// vector요소의동적관리에대한예제
2 #include <iostream>
3 #include <vector>
4 using namespace std;
5
6 void main()
7 {
8     vector<int>_vi;
9
10     for(int nLoop = 0 ; nLoop < 20 ; ++nLoop)
11     {
12         _vi.push_back( nLoop * 2); /// 뒤쪽부터추가
13     }
14
15     for( int nLoop = 0 ; nLoop < 20 ; ++nLoop )
16     {
17         printf("_vi[%d] = %d\n", nLoop, _vi[nLoop]);
18     }
19
20     printf("벡터의크기는%d 입니다.\n", _vi.size());
21 }



push.back은 벡터가 메모릭 부족하면 재할당한다.
벡터는 요소들을 인접한 메모리 위치에 연속적으로 저장한다. ==> 빠르게 읽고 쓸수있고 임의 위치에 접근이 빠름, 단 삽입, 삭제 속도는 느리다.

② 리스트
이중 연결 리스트로 구현, 노드끼리는 링크로 서로 연결되어 있어 요소의 논리적인 순서를 기억, 인접한 위치에 있을 필요없음
삽입, 삭제 할때 노드의 링크만 조작 ==> 속도가 빠르다.  리스트의 요소를 찾을때 링크를 따라 이동해야 하므로 읽기 속도는 느리다.

 list <T> Name;

통상 빈 상태로 생성한다.

중간에 삽입, 삭제를 할때는 insert, erase 멤버 함수를 사용하는데 링크만 조작하므로 삽입 위치에 상관없이 항상 상수 시간에 처리된다.

1 #include <iostream>
2 #include <list>
3
4 using namespace std;
5
6 void main()
7 {
8     int nLoop;
9     list<int> _li;
10    
11     for ( nLoop = 0 ; nLoop < 5 ; ++nLoop )
12     {
13         _li.push_back( nLoop * 2 );
14     }
15
16     list<int>::iterator it; /// 반복자
17     for ( it = _li.begin(), nLoop = 0 ; it != _li.end() ; it++, nLoop ++ )
18     {
19         printf("%d번째= %d\n", nLoop, *it);
20     }
21 }

리스트와 벡터는 상대방의 장점은 곧 자신의 단점과 같아 이 둘은 서로 대체 가능하다.

③ 맵
 두개씩 짝을 이루는 데이터를 저장하는 컨테이너이다.  연관 컨테이너의 일종 ==> 정렬되어 삽입된다.
항상 정렬된 상태로 관리 되며 이분 검색 기법을 사용=> 빠른 검색 가능,

예제 : List

1 #include <iostream>
2 #include <string>
3 #include <map>
4
5 using namespace std;
6
7 struct SProduct 8 {
9     string Name;
10     int Price;
11 } arPro[]={
12     {"맛동산",500},{"박카스",400},{"네스카페",250},{"신라면",450},
13     {"88라이트",1900},{"불티나",300},{"스타킹",700},{"김치",2000},
14     {"신문",500},{"비타",500},{"비타",1000},{"왕꿈틀이",900},
15     {"뽀빠이",200},{"위스퍼",800},{"콘텍",600},{"페리오치약",2200},
16     {"모나미볼펜",90},{"까페라떼",990},{"밧데리",1000},{"쵸코파이",250},
17 };
18
19 void main()
20 {
21     map<string, int>mPro;
22     map<string, int>::iterator it;
23     int nLoop;
24     string _stName;
25
26     for ( nLoop = 0 ; nLoop < sizeof(arPro) / sizeof(arPro[0]) ; nLoop++ )
27     {
28         mPro[arPro[nLoop].Name] = arPro[nLoop].Price;  /// 정렬되어저장된다.
29     }
30
31
32     for(;;)
33     {
34         cout << "상품명을입력하시오(끝날때는'끝'입력) : ";
35         cin >> _stName;
36         if(_stName == "끝" ) break;
37         it = mPro.find(_stName);
38         if(it == mPro.end() )
39         {
40             cout << "그런제품없습니다." << endl;
41         }
42         else
43         {
44             cout << _stName << "의가격은" << it->second << "입니다." << endl;
45         }
46     }
47 }
48

ps : 자세한 내용은  www.WinAPI.co.kr 참고