1. 컨테이너
컨테이너는 같은 타입을 저장, 관리할 목적으로 만들어진 클래스 입니다.
▣ 표준 시퀀스 컨테이너 ( Standard Sequence Container )
- 컨테이너 원소가 자신만의 삽입 위치(순서)를 가지는 컨테이너 ( vector, list, deque : 선형 구조 )
- 삽입되는 순서에 따라 원소의 위치가 결정되고 바뀌지 않습니다.
- 컨테이너 끝에 데이터를 추가하고 제거하기 위한 push_back()과 pop_back() 멤버함수를 가집니다.
▣ 표준 연관 컨테이너 ( Standard Associative Container )
- 저장 원소가 삽입 순서와 다르게 특정 정렬 기준에 의해 자동 정렬되는 컨테이너 ( set, multiset, map, multimap : 비선형 구조 )
- 삽입 순서와 상관없이 정렬 기준 ( default : less )에 따라 원소의 위치가 결정 됩니다.
컨테이너는 데이터를 하나의 연속된 메모리 단위로 저장하느냐에 따라 두가지로 나눕니다.
▣ 배열 기반 컨테이너( Array-based Container ) : 데이터 여러개가 하나의 메모리 단위에 저장됩니다.
- vector, deque
- operator[] 연산자를 이용해 일반 배열처럼 컨테이너 원소에 접근할 수 있습니다.
▣ 노드 기반 컨테이너( Node-based Container ) : 데이터 하나를 하나의 메모리 단위에 저장합니다.
- list, set, multiset, map, multimap
모든 컨테이어는 원소의 개수를 반환하는 size() 멤버 함수를 가집니다.
--------------------------------------------------------------------------------------------------------------------------
2. 반복자
반복자는 컨테이너에 저장된 원소를 순회하고 접근하는 일반화된 방법을 제공합니다.
반복자는 컨테이너와 알고리즘이 하나로 동작하게 묶어주는 인터페이스 역할을 합니다.
특정 컨테이너에 종속적이지 않고 독립적이면서도 언제든지 컨테이너와 결합하여 동작할 수 있습니다.
반복자의 특징
- 컨테이너 내부의 원(객체)를 가리키고 접근할 수 있어야 합니다. ( * 연산자 제공 )
- 다음원소로 이동하고 컨테이너의 모든 원소를 순회할 수 있어야 합니다. ( ++,!=,== 연산자 제공 )
STL에서 컨테어너 원소(객체)의 집합을 순처열( Sequence )이라 하고, 순차열은 하나의 시작과 하나의 끝을 갖습니다. 여기서 반복자는 순차열의 한 원소를 가리킵니다.
STL의 모든 컨테이너는 자신만의 반복자를 갖습니다. 멤버함수 begin()과 end()가 순차열의 시작과 끝을 가리키는 반복자를 반환합니다.
반복자 반복자
begin() end()
A B C D E n
Iterator
※ 순차열 [begin, end) 구간의 원소는 A,B,C,D,E, [begin, iter) 구간의 원소는 A,B [iter, end) 구간의 원소는 C,D,E 입니다.
만일 순차열[p, q)에서 p,q가 가리키는 원소가 같다면 이 순차열은 원소가 없습니다.
◎ 입력 반복자( Input Iterator ) : 현 위치의 원소를 한 번만 읽을 수 있는 반복자
◎ 출력 반복자( Output Iterator ) : 현 위치의 원소를 한 번만 쓸 수 있는 반복자
◎ 순반향 반복자( Forward Iterator ) : 입력, 출력 반복자 기능에 순방향으로 이동(++)이 가능한 재할당될 수 있는 반복자
◎ 양방향 반복자( Bidirectional Iterator ) : 순방향 반복자 기능에 역방향으로 이동(--)이 가능한 반복자
- list, set, multiset, map, multimap
◎ 임의 접근 반복자( Random Access Iterator ) : 양방향 반복자 기능에 +,-,+=,-=,[] 연산이 가능한 반복자
- vector, deque
모든 컨테이너는 양방향 반복자 이상을 제공 합니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | #include <iostream> #include <vector> using namespace std; int main( ) { vector<int> v; v.push_back(10); v.push_back(20); v.push_back(30); v.push_back(40); v.push_back(50); vector<int>::iterator iter=v.begin(); //시작 원소를 가리키는 반복자 cout << iter[0] << endl; // [] 연산자 cout << iter[1] << endl; cout << iter[2] << endl; cout << iter[3] << endl; cout << iter[4] << endl; cout << endl; iter += 2; // += 연산 cout << *iter << endl; // 30 cout << endl; vector<int>::iterator iter2 = iter+2; // + 연산 cout << *iter2 << endl; // 50 system("pause"); return 0; } |
--------------------------------------------------------------------------------------------------------------------------
3. 알고리즘
STL은 순차열의 원소를 조사, 변경, 관리, 처리할 목적으로 알고리즘이라는 구성요소를 제공합니다.
알고리즘은 한 쌍의 반복자([begin, end))을 필요로 하며 알고리즘 대부분은 순방향 반복자를 요구하지만, 몇몇 알고리즘은 임의 접근 반복자를 요구 합니다.
[알고리즘 일곱 가지의 범주로 분류]
◇ 원소를 수정하지 않는 알고리즘
◇ 원소를 수정하는 알고리즘
◇ 제거 알고리즘
◇ 변경 알고리즘
◇ 정렬 알고리즘
◇ 정렬된 범위 알고리즘
◇ 수치 알고리즘
find 알고리즘 : 순방향 반복자를 요구, 순방향 반복자만 지원하는 컨테이너(순차열)이라면, 어떤 컨테이너가 와도 알고리즘 수행가능
1 2 3 4 5 6 7 8 9 10 | #include <algorithm> // find 사용 vector<int>::iterator iter; iter = find(v.begin(), v.end(), 20); //[begin, end)에서 20 찾기 cout << *iter << endl; iter = find(v.begin(), v.end(), 100); //[begin, end)에서 100 찾기 if( iter == v.end() ) // 100이 없으면 iter==v.end() 임 cout << "100이 없음!" << endl; |
sort 알고리즘 : 순차열을 정렬, 임의 접근 반복자를 요구, vector와 deque는 sort알고리즘을 수행할 수 있지만, 다른컨테이너는 불가능합니다. 연관컨테이너는 컨테이너만의 정렬 기준을 가지고 있습니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | #include <vector> #include <list> using namespace std; vector<int> v; v.push_back(50); v.push_back(40); v.push_back(30); v.push_back(20); v.push_back(10); list<int> lt; lt.push_back(10); lt.push_back(20); lt.push_back(30); lt.push_back(40); lt.push_back(50); sort(v.begin(), v.end()); // 정렬 가능(vector는 임의 접근 반복자) // 디폴트 less, 오름차순 정렬 //sort(lt.begin(), lt.end()); // 에러!(list는 양방향 반복자) for( vector<int>::iterator Iter = v.begin(); Iter != v.end(); ++Iter ){ cout<< *Iter <<endl; } |
--------------------------------------------------------------------------------------------------------------------------
4. 함수객체
STL 에서 함수 객체는 클라이언트가 정의한 동작을 다른 구성 요소에 반영하려 할 때 사용 됩니다.
STL 알고리즘이 함수 객체, 함수, 함수 포인터 등의 함수류를 인자로 받아 알고리즘을 유연하게 동작 시킵니다.
1 2 3 | sort(v.begin(), v.end(), less<int>() ); // 오름차순 정렬 sort(v.begin(), v.end(), greater<int>() ); // 내림차순 정렬 |
--------------------------------------------------------------------------------------------------------------------------
5. 어댑터
구성 요소의 인터페이스를 변경합니다.
[ 어댑터 종류 ]
◇ 컨테이너 어댑터 ( Container Adaptor ) : stack, queue, priority_queue
- stack 컨테이너 어댑터는 일반 컨테이너를 LIFO 방식의 스택 컨테이너로 변환합니다.
empty, size, push_back, pop_back, back 인터페이스(멤버함수)를 지원하는 컨테이너는 모두 LIFO방식의 스택으로 변환할 수 있습니다.
시퀀스 컨테이너는 모두 멤버함수를 가지므로 stack 컨테이너 어댑터의 컨테이너로 이용할 수 있습니다.
stack 컨테이너 어댑터의 디폴트 컨테이너는 deque 컨테이너 입니다.
[stack 컨테이너]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | #include <iostream> #include <stack> using namespace std; int main(){ stack<int> s; s.push(10); s.push(20); s.push(30); cout<< s.top() << endl; //30 s.pop(); cout<< s.top() << endl; //20 s.pop(); cout<< s.top() << endl; //10 cout<< s.top() << endl; //10 s.pop(); if( s.empty() ){ cout<<"empty"<<endl; } system("pause"); return 0; } |
[vector 컨테이너를 적용한 stack 컨테이너]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | #include <iostream> #include <vector> #include <stack> using namespace std; void main( ) { stack<int, vector<int> > st; // vector 컨테이너를 이용한 stack 컨테이너 생성 st.push( 10 ); // 데이터 추가(입력) st.push( 20 ); st.push( 30 ); cout << st.top() << endl; // top 데이터 출력 st.pop(); // top 데이터 삭제 cout << st.top() << endl; st.pop(); cout << st.top() << endl; st.pop(); if( st.empty() ) // 스택이 비었는지 확인 cout << "stack이 데이터 없음" << endl; } |
◇ 반복자 어댑터 ( Iterator Adaptor ) : reverse_iterator, back_insert_iterator, front_insert_iterator, insert_iterator
- reverse_iterator는 일반 반복자의 동작 방식을 반대로 동작시키는 역방향 반복자(reverse_iterator)로 변환합니다.
- 역방향 반복자는 반복자가 가리키는 원소와 실제 가리키(참조)는 값이 다르다는 점입니다. 반복자가 가리키는 원소 다음 원소의 값을 참조 합니다. 이렇게 설계한 이유는 알고리즘 수행 시 정방향 반복자와 호환되도록 하기 위해서 입니다.
1 2 3 4 5 6 | //일반 반복자 iterator를 역방향 반복자 reverse_iterator로 변환 reverse_iterator< vector<int>::iterator > riter(v.end()); reverse_iterator< vector<int>::iterator > end_riter(v.begin()); for( ; riter != end_riter ; ++riter ) cout << *riter << " "; |
begin() end()
10 20 30 40 50 n
end_riter( 10을 가르키고, 10앞의 값을 참조) riter( n을 가르키고 50의 값을 참조 )
위의 설계의 장점은
--연산자를 사용하지 않고 ++ 연산자만으로 정방향, 역방향의 순회가 모두 가능 하다는 점입니다. 이는 대부분의 알고리즘이 ++연산자만 으로 구현 되어 있으며 이렇게 이미 구현된 알고리즘에 정방향과 역방향 순회가 모두 가능하게 합니다.
정방향 순회시 순차열 구간의 원소는 반복자 이전까지를 나타내는 것을 생각해보면 역방향시 반복자가 가르키는 원소의 앞의 값을 참조하는것이 역방향으로 순회시 ++연산자로 순회를 가능하게 해주는 것 입니다.
1 2 3 4 5 | // STL 모든 컨테이너는 반복자 어댑터 reverse_iterator를 typedef 타입으로 정의하며 // rbegin(), rend()로 컨테이너의 역방향 반복자를 반환함. vector<int>::reverse_iterator riter(v.rbegin()); for( ; riter != v.rend() ; ++riter ) cout << *riter << " "; |
◇ 함수 어댑터 ( Function Adaptor ) : 바인더( binder ), 부정자( negator ), 함수 포인터 어댑터( adaptor for pointers to functions )
- not2는 조건자 함수 객체(이항)를 NOT(반대)로 변환합니다. ( 조건자는 bool타입을 반환하는 함수류 입니다 )
- not1은 단항 조건자에 사용되며, not2는 이항 조건자에 사용 됩니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | #include <iostream> #include <functional> //not2 사용 using namespace std; int main( ) { //임시 less 객체로 비교 cout << less<int>()(10, 20) << endl; // 1 cout << less<int>()(20, 20) << endl; // 0 cout << less<int>()(20, 10) << endl; // 0 cout << "==============" <<endl; // 임시 객체 less에 not2 어댑터 적용 cout << not2( less<int>() )(10, 20) << endl; // 0 cout << not2( less<int>() )(20, 20) << endl; // 1 cout << not2( less<int>() )(20, 10) << endl; // 1 cout << endl; /** * not2( less<int>() ) 이 구문은 * less함수객체가 < 연산이므로 반대 의미가 있는 >=연산 기능의 함수객체를 반환하게 됩니다. */ less<int> l; cout << l(10, 20) << endl; // less 객체 l로 비교 cout << l(20, 20) << endl; cout << l(20, 10) << endl; cout << "==============" <<endl; cout << not2( l )(10, 20) << endl; // less 객체 l에 not2 어댑터 적용 cout << not2( l )(20, 20) << endl; cout << not2( l )(20, 10) << endl; system("pause"); return 0; } |
--------------------------------------------------------------------------------------------------------------------------
6. 할당기
컨테이너의 메모리 할당 정보와 정책(메모리 할당 모델)을 캡슐화한 STL 구성 요소입니다.
할당기는 템플릿 클래스이며, 모든 컨테이너는 기본 할당기를 사용합니다.
사용자 정의 할당기는 사용자가 직접 메모리 할당 방식을 제어할 수 있게 합니다.
모든컨테이너는 템플릿 매개변수에 할당기를 인자로 받습니다. 기본할당기는 allocator<T>이며, 컨테이너는 템플릿 매개변수에 디폴트 매개변수 값으로 기본 할당기를 지정합니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | #include <iostream> #include <vector> #include <set> #include <map> using namespace std; void main( ) { //vector<typename T, typename Alloc = allocator<T> > // vector<int> 와 같음 vector< int, allocator<int> > v; v.push_back( 10 ); cout << *v.begin() << endl; //set<typename T, typename Pred = less< T >, typename Alloc = allocator<T> > // set<int> 와 같음 set< int, less<int>, allocator<int> > s; s.insert( 10 ); cout << *s.begin() << endl; } |
