■ STL(Standard Template Library)
- 프로그래머가 자료구조와 알고리즘을 알지 못해도 사용할 수 있도록 한 라이브러리
- 표준 STL은 std namespace 안에 있다.
- 컨테이너(Container) : 특정한 타입의 원소(또는 객체)들을 담아 다루기 위한 객체
ex) list, vector, map, deque, multimap 등
- 반복자(Iterator) : 컨테이너 내부 원소를 순회할 수 있는 객체이며 컨테이너의 특정 위치를 나타냄
- 반복자에 사용되는 멤버함수
begin() : 컨테이너의 첫번쨰 위치를 가리키는 반복자
end() : 컨테이너의 마지막 위치를 가리키는 반복자를 반환하며
이것은 컨테이너의 마지막 원소 ' 다음의 위치를 말한다.
- 반복자에 사용되는 연산자
* 연산자 : 지금 현재 위치의 원소를 반환
++ 연산자 : 다음 원소를 가리키는 역할
-- 연산자 : 이전 원소를 가리키는 역할
= 연산자 : 반복자가 참조하는 원소의 위치를 할당
==,!= 연산자 : 두 반복자가 같은 위치인지를 반환하는 연산자
- 알고리즘(Algorithm) : 컨테이너 객체의 원소를 다루기 위한 여러 알고리즘으로 검색, 정렬, 수정등의 역할
❉ STL : 컨테이너 + 반복자 + 알고리즘
■vector
- vector는 자신의 원소를 동적 배열을 이용하여 관리
- vector는 데이터 추가와 삭제는 빠르지만 삽입은 비교적 늦은
■vector와 list 멤버 함수
- size() : 원소의 개수를 반환하는 함수
- empty() : 컨테이너가 비었는지를 알려줌
- max_size() : 컨테이너가 가질 수 있는 최대 원소의 개수를 반환
- reserve() : 용량을 재할당하는 함수
- insert() : 반복자 위치에 데이터를 삽입
- push_back() : 큰 부분에 데이터를 추가
- pop_back() : 마지막 원소를 제거
- erase() : 반복자 위치의 원소를 제거
- clear() : 모든 원소를 제거
- resize() : 원소릐 개수를 변경
- sort() : 오름차순으로 정 렬
- 백터에 데이터 입력과[]연산자를 이용한 요소의 접근
#include <iostream> #include <vector> using namespace std; int main(int argc, const char * argv[]) { vector<int> Vector;
for(int i = 0; i < 7 ; i++) Vector.push_back(i); //
for(int i = 0; i < Vector.size() ; i++) //size()원소의 개수를 반환 cout<<Vector[i]<<" "; Vector.clear(); return 0; } 결과: 0 1 2 3 4 5 6 |
- 반복자
| #include <iostream>
#include <vector> using namespace std; int main(int argc, const char * argv[]) { vector<int> Vector; vector<int>::iterator pos;
for(int i = 8; i >= 0 ; --i) Vector.push_back(i); //
for(pos = Vector.begin() ; pos!=Vector.end() ; pos++) //begin() 컨테이너의 첫번째 위치를 가리키는 반복자 cout<<*pos<<" "; Vector.clear(); return 0; } 결과: 8 7 6 5 4 3 2 1 0 |
■list
- list는 이중 링크드 리스트(double linked list)
- <list> 헤더를 포함
- 원소를 검색, 처음부터 검색하게 되어 다른 vector에 비해 시간이 다소 걸림
- 빠른 삽입과 삭제는 vector보다 훨씬 빠르다.
- vector의 [] 연산자를 제공하지 않는다.
- 1~10까지 데이터 입력 및 제거 그리고 검색
| #include <iostream>
#include <list> using namespace std; int main(int argc, const char * argv[]) { int nNum; list<int> nLinkedList;
for(int i = 0 ; i< 10 ; i++) nLinkedList.push_back(i);
cout<<"리스트에 입력된 값은 다음과 같다"<<endl; list<int>::iterator pos; for(pos = nLinkedList.begin() ; pos != nLinkedList.end() ; pos++) cout<<*pos<<" ";
cout<<endl<<"0~9까지의 값중에서 삭제할 값은?:"<<endl; cin>>nNum;
for(pos = nLinkedList.begin() ; pos !=nLinkedList.end() ; pos++) { if(*pos == nNum) { nLinkedList.erase(pos); break; } }
cout<<endl<<"삭제한 결과"<<endl; for(pos = nLinkedList.begin() ; pos != nLinkedList.end();pos++) cout<<*pos<<" ";
nLinkedList.clear();
return 0; } 결과: 리스트에 입력된 값은 다음과 같다 0 1 2 3 4 5 6 7 8 9 0~9까지의 값중에서 삭제할 값은?: 8 삭제한 결과 0 1 2 3 4 5 6 7 9 |
- 오름차순 내림차순 정렬
#include <iostream> #include <list> using namespace std; int main(int argc, const char * argv[]) { list<int>nLinkedList;
for(int i = 10; i>0 ; --i) { nLinkedList.push_back(i); }
nLinkedList.sort();
list<int>::iterator pos; for(pos = nLinkedList.begin(); pos!=nLinkedList.end();pos++) cout<<*pos<<" "; cout<<endl;
nLinkedList.reverse(); for(pos = nLinkedList.begin(); pos!=nLinkedList.end();pos++) cout<<*pos<<" "; cout<<endl;
nLinkedList.clear(); return 0; } 결과: 1 2 3 4 5 6 7 8 9 10 10 9 8 7 6 5 4 3 2 1 |
■알고리즘
- min_element() : 최소값을 검색하며 반복자 위치를 반환
- max_element() : 최대값을 검색하며 반복자 위치를 반환
- find() : 값으로 검색하며 있으면 반복자 위치를 반환하고 없으면 범위의 끝을 반환
- reverse() : 역순으로 배열
- sort() : 오름차순으로 정
- vector에 알고리즘 적용
| #include <iostream>
#include <vector> #include <algorithm> using namespace std; int main(int argc, const char * argv[]) { int nSearch; vector<int> Vectors;
vector<int>::iterator pos;
Vectors.push_back(3); Vectors.push_back(7); Vectors.push_back(8); Vectors.push_back(10); Vectors.push_back(6); Vectors.push_back(1); Vectors.push_back(4); Vectors.push_back(2);
for( pos = Vectors.begin() ; pos != Vectors.end() ; pos++) cout << *pos << " " ;
cout << endl << "최소값 : " << *min_element(Vectors.begin(), Vectors.end()) << endl; cout << "최대값 : " << *max_element(Vectors.begin(), Vectors.end()) << endl;
sort(Vectors.begin(), Vectors.end());
cout << "정렬 : ";
for( pos = Vectors.begin() ; pos != Vectors.end() ; pos++) cout << *pos << " " ;
cout << endl << "찾을 값을 입력 :" ; cin >> nSearch;
pos = find(Vectors.begin(), Vectors.end(), nSearch); if( pos != Vectors.end() ) cout << "검색값이 있음" << endl; else cout << "검색값이 없음" << endl;
cout << "내림차순으로 정렬" << endl; reverse(Vectors.begin(), Vectors.end()); cout << "정렬 : "; for( pos = Vectors.begin() ; pos != Vectors.end() ; pos++) cout << *pos << " " ; return 0; } 결과: 3 7 8 10 6 1 4 2 최소값 : 1 최대값 : 10 정렬 : 1 2 3 4 6 7 8 10 찾을 값을 입력 : 8 검색값이 있음 내림차순으로 정렬 정렬 : 10 8 7 6 4 3 2 1 |
-list에 알고리즘 적용
| #include <iostream>
#include <list> #include <algorithm> using namespace std; int main(int argc, const char * argv[]) { list<int> LinkedList; list<int>::iterator pos;
int nSearch;
LinkedList.push_back(10); LinkedList.push_back(7); LinkedList.push_back(3); LinkedList.push_back(1); LinkedList.push_back(12); LinkedList.push_back(5); LinkedList.push_back(2); for( pos = LinkedList.begin() ; pos != LinkedList.end() ; pos++) cout << *pos << " " ;
cout << endl << "최소값 : " << *min_element(LinkedList.begin(), LinkedList.end()) << endl; cout << "최대값 : " << *max_element(LinkedList.begin(), LinkedList.end()) << endl;
LinkedList.sort();
cout << "정렬 : "; for( pos = LinkedList.begin() ; pos != LinkedList.end() ; pos++) cout << *pos << " " ; cout << endl << "찾을 값을 입력 : " ; cin >> nSearch;
pos = find(LinkedList.begin(), LinkedList.end(), nSearch); if( pos != LinkedList.end() ) cout << "검색값이 있음" << endl; else cout << "검색값이 없음" << endl; cout << "내림차순으로 정렬" << endl;
reverse(LinkedList.begin(), LinkedList.end());
cout << "정렬 : ";
for( pos = LinkedList.begin() ; pos != LinkedList.end() ; pos++) cout << *pos << " " ;
return 0; } 결과: 10 7 3 1 12 5 2 최소값 : 1 최대값 : 12 정렬 : 1 2 3 5 7 10 12 찾을 값을 입력 : 7 검색값이 있음 내림차순으로 정렬 정렬 : 12 10 7 5 3 2 1 |
