Post on 04-Jul-2020
transcript
13 준 플 라 브러 1
1. STL 개
준 플 라 브러 (Standard Template Library)
n
Ø 컨 너 클래스 : 료 조 (stack, queue, vector, …)
Ø : 든 료 조 원 에 한 동 한 접근 제공
ü 포 사!
Ø 고 즘 : 함수 (sort, swap, find, …)
n 라 브러 (generic library)라고
Ø 본적 객체지향 프 그래 지
Ø sort라는 함수가 특정 료 조 함수가 니 든 료 조에 해
동 한 사 제공함
순
n vector 클래스 list 클래스 사
n 개념 필
n vector 클래스 list 클래스에 한 고 즘 적
n 고 즘과 컨 너 클래스 종
13 준 플 라 브러 2
2. vector 클래스 사
vector
n 1차원 열
n 수행 중에 원 개수
경 가능
n <vector> 헤 파 포함
: 5개 원 가진 int
열
#include <iostream>#include <vector>using namespace std;
int main(void){
int i;vector<int> intV(5);
for (i = 0; i < 5; i++) {cout << "값 력 : ";cin >> intV[i];
}
intV[2] = 100;
for (i = 0; i < 5; i++) {cout << intV[i] << "\t";
}cout << endl;
return 0;}
원 5개 int 열
열처럼 사 !
13 준 플 라 브러 3
2. vector 클래스 사
vector 클래스 객체 생
n vector<int> intV(5); // 5개 원 가진 int 열
n vector<int> intV; // 0개 원 가진 int 열???
n vector<CPoint> pointV(3); // 3개 원 가진 CPoint 열
push_back 함수 사 : 지 원 다 에 새 원 가
int main(void){
int i, value;vector<int> intV;
for (i = 0; i < 5; i++) {cout << "값 력 : ";cin >> value;intV.push_back(value); // 마 막 원 에 새로 원 추가
}
for (i = 0; i < 5; i++) {cout << intV[i] << "\t"; // i번째 원 값 출력
}cout << endl;
return 0;}
열 크 (원 개수) 내는
size() 함수
intV.resize(intV.size() + 1); // 원 개수 1 증가
13 준 플 라 브러 4
2. vector 클래스 사
: CPoint 클래스 객체 원 갖는 vector 객체
class CPoint{private :
int x, y;
public :CPoint(int a = 0, int b = 0) : x(a), y(b) { }void Print() { cout << "(" << x << ", " << y << ")" << endl; }
};
int main(void){
int i;vector<CPoint> cAry(5); // 경 폴트 생 필 !
for (i = 0; i < 5; i++) cAry.push_back(CPoint(i + 1, i + 1)); // 새로 CPoint 객체 추가
for (i = 0; i < 10; i++) // 총 10개 원 존cAry[i].Print();
return 0;}
vector 클래스 또 다 함수들
- insert, erase, clear => 함께 동
à 4절에
13 준 플 라 브러 5
3. list 클래스 사
단 향 크드 스트 향 크드 스트
list 클래스
n 스트 쉽게 다룰 수 만든 컨 너 클래스
n 치 열과 사하게 사 가능 (내 조는 스트)
n <list> 헤 파 포함
13 준 플 라 브러 6
3. list 클래스 사
list 클래스 사
#include <iostream>#include <list>using namespace std;
int main(void){
int i;list<int> MyList; // int형 list 생
for (i = 0; i < 5; i++) MyList.push_back(i + 1); // 마 막 원 다 에 원 삽
cout << MyList.front() << endl; // 첫 번째 원cout << MyList.back() << endl; // 마 막 원
return 0;}
* list는 [] 연산 제공하고 지
- 열 : 원 에 한 빠 접근à [ ]
- 스트 : 치 사 빠 삽 , 삭제
* 사 한다 사하게사 할 수 à다 절
13 준 플 라 브러 7
4. 해
열과 스트
n 특정 원 가 키는 ?
Ø 열과 스트에 동 한 필 ß 특정 고 즘(함수) 열과
스트에 동 한 식 적 하 해 .
à (iterator)
Ø포 사
Ø vector 경 포 는 동 한 개념
13 준 플 라 브러 8
4. 해
: 포 한 vector 원 값 처
int main(void){
int i;vector<int> intV(5); // 5개 원 를 갖는 배열int *pV = &intV[0]; // 첫 번째 원 를 가리킴
for (i = 0; i < 5; i++) {cout << "값 력: ";cin >> (*pV);pV++; // 다 원 를 가리킴
}
pV = &intV[0];for (i = 0; i < 5; i++) {
cout << *pV << "\t";pV++;
}cout << endl;
return 0;}
포 수 사 하여
vector 객체 원 처 가능
list 객체에 해 는 포
다 원 에 한 접근 가능 (p++)
à list에 적합한 포 필 !
13 준 플 라 브러 9
4. 해 : 원 해
vector 클래스 vector 클래스 클래스n MyVector(편 상 5개 원 제한), VectorIterator
#include <iostream>using namespace std;
template <typename T>class VectorIterator {private :
T *ptr;
public :VectorIterator(T *p = 0) : ptr(p) { } // 초 화, 포 터로 주 가리킴T &operator*() { return (*ptr); } // 역참조 연산void operator++(int) { ptr++; } // 후 가 연산void operator=(T *p) { ptr = p; } // 연산
};
template <typename T>class MyVector {private :
T ary[5];
public : typedef VectorIterator<T> iterator; // iterator 름 로 사 가능T *begin() { return &ary[0]; }
};
내 적 포 포함
13 준 플 라 브러 10
4. 해 : 원 해
vector 클래스 vector 클래스 클래스 (계 )
int main(void){
int i;MyVector<int> intV;MyVector<int>::iterator vIter(intV.begin()); // VectorIterator<int> 객체
for (i = 0; i < 5; i++) {*vIter = i;vIter++;
}
vIter = intV.begin();for (i = 0; i < 5; i++) {
cout << *vIter << endl;vIter++;
}
return 0;}
존 포 사 과 동
13 준 플 라 브러 11
4. 해 : 원 해
list 클래스 list 클래스 클래스
n MyList(단 향 크드 스트 가정), ListIterator
template <typename T>struct Node { // 하나 노드 : 터 + 다 노드에 한 포 터
T data;Node<T> *next;Node(T d, Node<T> *n = NULL) : data(d), next(n) { }
};
template <typename T>class ListIterator {private :
Node<T> *ptr; // 특정 노드에 한 포 터
public :ListIterator(Node<T> *p = 0) : ptr(p) { }void operator++(int) { ptr = ptr->next; }T &operator*() { return ptr->data; }void operator=(Node<T> *p) { ptr = p; }
};
다 원
원 값
13 준 플 라 브러 12
4. 해 : 원 해
list 클래스 list 클래스 클래스 (계 )
template <typename T>class MyList {private :
Node<T> *start;Node<T> *last;
public :MyList() : start(NULL), last(NULL) { }typedef ListIterator<T> iterator;Node<T> *begin() { return start; }void push(T d) { // 새로 노드 추가
Node<T> *temp = new Node<T>(d, NULL);if (start == NULL) {
start = temp;last = temp;
}else {
last->next = temp;last = temp;
}}
};
첫 째 원 지 원
13 준 플 라 브러 13
4. 해 : 원 해
list 클래스 list 클래스 클래스 (계 )
int main(void)
{
int i;
MyList<int> intL;
MyList<int>::iterator lIter; // 원 하나를 가리킬 터레 터 생
for (i = 0; i < 5; i++)
intL.push(i);
lIter = intL.begin(); // 첫 번째 원 를 가리킴
for (i = 0; i < 5; i++) {
cout << *lIter << endl;
lIter++;
}
return 0;
}
13 준 플 라 브러 14
5. 사
vector list 클래스 ( ) 함수들
함수
begin 첫 째 원
end지 원 다 미하는 . 지 원
지나쳤 감지할 수
rbegin 지 원
rend 첫 째 원 미하는
insert가 가 키는 특정 치에 원 삽 . 특정 치란
가 가 키는 원 전 원 사 미함
erase(iterator pos) pos가 가 키는 원 제거
erase(iterator first,iterator last)
first 가 가 키는 원 last 가 가 키는 원전 원 지 든 원 제거
비 연산개 컨 너 클래스 객체가 같 지(==), 다 지(!=), 또는
비 할 수 는 비 연산 가 준비
연산obj1 = obj2 같 하나 컨 너 클래스 객체 다 컨 너 클래스객체 . obj1 obj2 원 개수 각 원 값 같 짐
함수에 지정
func(first, last) 경
[first 상, last 미만) 미
13 준 플 라 브러 15
5. 사
vector 클래스에 한 사
void PrintVector(vector<int> intV, char *name){
vector<int>::iterator iter;
cout << ">> " << name << " : ";for (iter = intV.begin(); iter != intV.end(); iter++) // 각 원 에 접근
cout << *iter << " ";cout << endl;
}intV1.insert(intV1.begin() + 2, 100);intV1.insert(intV1.end(), 101);PrintVector(intV1, "intV1");
intV1.erase(intV1.begin() + 2);PrintVector(intV1, "intV1");
intV2 = intV1;PrintVector(intV2, "intV2");if (intV1 == intV2) {
cout << "intV1과 intV2는 동 하다" << endl;}
return 0;}
int main(void){
int i;vector<int> intV1(5);vector<int> intV2;vector<int>::iterator iter
= intV1.begin();
for (i = 0; i < 5; i++) {*iter = i;iter++;
}
PrintVector(intV1, "intV1");PrintVector(intV2, "intV2");
13 준 플 라 브러 16
5. 사
reverse_iterator 사
n rbegin, rend 함께 사 : iter++ 경 전 원 동
n : 역순 원 값
int main(void){
int i;vector<int> intV(5);vector<int>::iterator f_iter = intV.begin();vector<int>::reverse_iterator r_iter;
for (i = 0; i < 5; i++) {*f_iter = i;f_iter++;
}
for (r_iter = intV.rbegin(); r_iter != intV.rend(); r_iter++) // 역순 접근cout << *r_iter << " ";
cout << endl;
return 0;}
13 준 플 라 브러 17
5. 사
list 클래스에 한 사 (p.15 vector 동 한지 )
void PrintVector(list<int> intV, char *name){
list<int>::iterator iter;
cout << ">> " << name << " : ";for (iter = intV.begin(); iter != intV.end(); iter++)
cout << *iter << " ";cout << endl;
}
int main(void){
int i;list<int> intV1(5);list<int> intV2;list<int>::iterator iter = intV1.begin();
for (i = 0; i < 5; i++) {*iter = i;iter++;
}
13 준 플 라 브러 18
5. 사
list 클래스에 한 사 (계 )
PrintVector(intV1, "intV1");PrintVector(intV2, "intV2");
iter = intV1.begin();iter++; iter++;intV1.insert(iter, 100); // 번째 번째 원 사intV1.insert(intV1.end(), 101); // 마 막 원 다PrintVector(intV1, "intV1");
iter = intV1.begin();iter++; iter++;intV1.erase(iter); // 번째 원PrintVector(intV1, "intV1");
intV2 = intV1; // PrintVector(intV2, "intV2");if (intV1 == intV2) {
cout << "intV1과 intV2는 동 하다" << endl;}
return 0;}
vector 차 점
list 는 vector 달
(intV.begin() + 2) 같 + 연산 제공하지
list 특 : 순차 접근 (비 -vector : 접근)
에 종 가 !!!
13 준 플 라 브러 19
6. 종
허 능에 종
n (InputIterator)
n (OutputIterator)
n 전 (ForwardIterator)
n 전 (BidirectionalIterator)
n 접근 (RandomAccessIterator)
능 사 가능 연산
n vector : 접근
n list : 전
능 전 전 접근
= *p = *p = *p = *p
쓰 *p = *p = *p = *p =
1 증가, 감 ++ ++ ++ ++, -- ++, --
접근 +, -, +=, -+, []
13 준 플 라 브러 20
6. 종
ostream_iterator 클래스 사
n <iterator> 헤 파 포함
#include <iostream>#include <vector>#include <iterator>using namespace std;
int main(void){
vector<int> values;values.push_back(1);values.push_back(2);values.push_back(3);values.push_back(4);values.push_back(5);
ostream_iterator<int> output(cout, "\n");
for (int i = 0; i < 5; i++)*output = values[i];
return 0;}
“\n” 동
포 해 값 하듯
가능
고 즘 하는 종 가 다 !!!
13 준 플 라 브러 21
7. 고 즘 해
sort 고 즘(함수) 적
n 프 타Ø void sort(RandomAccessIterator first, RandomAccessIterator last);
Ø void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
n first, last : 적 [first 상, last 미만)
n comp : 정 준 함수
n 접근 에만 적 가능
n <algorithm> 헤 파 포함
#include <iostream>#include <vector>#include <algorithm>using namespace std;
void PrintVector(vector<int> intV, char *name){
vector<int>::iterator iter;
cout << ">> " << name << " : ";for (iter = intV.begin(); iter != intV.end(); iter++)
cout << *iter << " ";cout << endl;
}
13 준 플 라 브러 22
7. 고 즘 해
sort 고 즘(함수) 적 (계 )
내 차순 정
int main(void){
int i;vector<int> intV(5);
cout << "5개 정수 력 : ";for (i = 0; i < 5; i++)
cin >> intV[i];PrintVector(intV, "정렬 전");
sort(intV.begin(), intV.end()); // 모든 원 들에 해 정렬 수행PrintVector(intV, "정렬 후");
return 0;}
bool IntCompare(int a, int b){
return (a > b) ? true : false; }
sort(intV.begin(), intV.end(), IntCompare);
13 준 플 라 브러 23
7. 고 즘 해
vector 객체 원 가 클래스 객체 경 sort 함수 적
n 준에 한 함수 사 또는 < 연산 사
class CPoint {private :
int x, y;
public :CPoint(int a = 0, int b = 0) : x(a), y(b) { }friend ostream &operator<<(ostream &out, CPoint &Po);friend bool Compare(CPoint &Po1, CPoint &Po2);
};
ostream &operator<<(ostream &out, CPoint &Po){
out << "(" << Po.x << ", " << Po.y << ")";return out;
}
bool Compare(CPoint &Po1, CPoint &Po2) // x, y 합 객체가 앞에 치{
if (Po1.x + Po1.y < Po2.x + Po2.y)return true;
elsereturn false;
}
13 준 플 라 브러 24
7. 고 즘 해
vector 객체 원 가 클래스 객체 경 sort 함수 적 (계 )
void PrintVector(vector<CPoint> intV, char *name){
vector<CPoint>::iterator iter;
cout << ">> " << name << " : ";for (iter = intV.begin(); iter != intV.end(); iter++)
cout << *iter << " ";cout << endl;
}
int main(void){
vector<CPoint> intV(5);
intV[0] = CPoint(5, 3);intV[1] = CPoint(2, 9);intV[2] = CPoint(1, 1);intV[3] = CPoint(2, 5);intV[4] = CPoint(3, 7);PrintVector(intV, "정렬 전");
sort(intV.begin(), intV.end(), Compare); // Compare 모든 원 정렬PrintVector(intV, "정렬 후");
return 0;}
13 준 플 라 브러 25
7. 고 즘 해
vector 객체 원 가 클래스 객체 경 sort 함수 적 (계 )
n < 연산 CPoint 클래스에 포함시키는 경
Compare 함수 하지
bool operator<(CPoint &Po) {
if (x + y < Po.x + Po.y)
return true;
else
return false;
}
13 준 플 라 브러 26
8. 고 즘 종
고 즘 종 적 고 즘
고 즘 사
종 고 즘
경 가시퀀스 연산
for_each 내 원 에 해 지정한 함수 수행
find 특정 값 가진 첫 째 원
count 특정값 가진 원 개수
경 가능시퀀스 연산
rotate 전 원 들 동 (circular)
random_shuffle 전 내 원 들 순 정
reverse 전 역순 정
정연산
sort 접근 정
void PrintVector(vector<int> intV, char *name){
vector<int>::iterator iter;
cout << ">> " << name << " : ";for (iter = intV.begin(); iter != intV.end(); iter++)
cout << *iter << " ";cout << endl;
}
13 준 플 라 브러 27
8. 고 즘 종
고 즘 사 (계 )
void Print(int val){
cout << val * val << " ";}
int main(void){
int i;vector<int> intV(10);vector<int>::iterator iter;
cout << "10개 정수 력 : ";for (i = 0; i < 10; i++)
cin >> intV[i];PrintVector(intV, "알고리 적 전");
cout << "for_each : ";for_each(intV.begin(), intV.end(), Print); // 모든 원 에 해 Print 적cout << endl;
13 준 플 라 브러 28
8. 고 즘 종
고 즘 사 (계 )
cout << "find : ";iter = find(intV.begin(), intV.end(), 5); // 값 5 원 치 반환cout << *iter << endl;
cout << "count : ";cout << count(intV.begin(), intV.end(), 5) << endl;// 값 5 원 개수
rotate(intV.begin(), intV.begin() + 1, intV.end());// 로 1씩 동PrintVector(intV, "rotate");
reverse(intV.begin(), intV.end()); // 역순 로 정렬PrintVector(intV, "reverse");
random_shuffle(intV.begin(), intV.end()); // 순 로 정렬PrintVector(intV, "random_shuffle");
return 0;}
13 준 플 라 브러 29
9. 컨 너 클래스 종
컨 너 클래스 종
n 시퀀스 컨 너 : 원 들 사 순 개념 포함
n 컨 너 : 순 개념, 시퀀스 컨 너 만듦
Ø stack, queue ß deque, priority_queue ß vector
n 결합 컨 너 : (값 + 키) 원 저
종 컨 너 클래스 능
시퀀스컨 너
vector 열 미 신 삽 , 삭제
deque double_ended 큐 또는 미에 신 삽 , 삭제
list doubly-linked 스트 치에 신 삽 , 삭제
컨 너
stack LIFO 조 스택 스택
queue FIFO 조 큐 큐
priority_queue 순 가진 큐 순 큐
결합컨 너
set 집합 신 검색, 중 허
multiset 중 허 집합 신 검색, 중 허
map 키-값 연결 신 검색, 중 허
multimap 키-값들 연결 신 검색, 중 허
13 준 플 라 브러 30
9. 컨 너 클래스 종
multimap 클래스 사
n 에 는 물건 저 : ( , 물건) 저
n 키( ) 하나에 값(물건)들 존 à multimap
#include <iostream>#include <map>#include <string>using namespace std;
int main(void){
multimap<int, string> Room;
Room.insert(pair<int, string>(101, "chair")); // 원 추가Room.insert(pair<int, string>(102, "computer"));Room.insert(pair<int, string>(101, "desk"));Room.insert(pair<int, string>(101, "book"));Room.insert(pair<int, string>(102, "notebook"));
, 물건
13 준 플 라 브러 31
9. 컨 너 클래스 종
multimap 클래스 사 (계 )
cout << "모든 방과 물건: ";
multimap<int, string>::iterator iter;
for (iter = Room.begin(); iter != Room.end(); iter++)
cout << (*iter).first << "-" << (*iter).second << " ";
cout << endl;
cout << "101호에 는 물건 개수: " << Room.count(101) << endl;
pair<multimap<int, string>::iterator,
multimap<int, string>::iterator> range = Room.equal_range(101);
for (iter = range.first; iter != range.second; iter++)
cout << (*iter).second << " ";
cout << endl;
return 0;
}
특정 키에 해당하는
값들