Ch16_표준 템플릿 라이브러리

01_vector 컨테이너 02_list 컨테이너 03_map 컨테이너와 set 컨테이너 04_알고리즘

01_vector 컨테이너 표준 템플릿 라이브러리(STL: standard template library) 컨테이너(container), 이터레이터(iterator), 알고리즘, 수치 함수 객체(numerics) 등을 포함하며, std 네임스페이스에 속함 비주얼 C++ 6.0에서 최신 STL을 사용하려면 서비스 팩 6 설치를 권장함 컨테이너 STL을 이루고 있는 기본 틀로, 다른 객체를 담을 수 있는 객체 시퀀스 컨테이너(sequence container) vector, list, map, set 연관 컨테이너(associative container) map set vector 전통적인 배열을 대신하여 사용할 수 있으며, 데이터의 크기를 지정하지 않고 push_back( ) 멤버 함수로 데이터를 넣고, 사용할 때는 배열처럼 사용 가능함 각 데이터 요소들이 연속적인 공간에 할당되며, 임의의 요소에 대한 접근이 빠르고, 끝 지점에서 삽입과 삭제가 빠름 저장된 데이터의 크기는 size( ), 현재 할당된 용량은 capacity( ) 멤버 함수로 알 수 있음 용량보다 크게 삽입이 일어나면 메모리 재할당(reallocation)이 일어나며, 이러한 재할당은 vector를 사용할 때 성능 저하의 요인이 됨 reserve( ) 멤버 함수로 미리 메모리 용량을 확보하고 사용하면 재할당이 빈번히 어나는 것을 미리 방지할 수 있음

01_vector 컨테이너 [예제 16-1] vector를 1차원 배열처럼 사용하기 ex16_1.cpp 01 #include <iostream> 02 #include <vector> 03 using namespace std; 04 main() 05 { 06 vector<int> V1; 07 // vector<int> V1(4); // 정수 4개를 저장할 메모리 확보 08 // vector<int> V1(4, 10); // 정수 4개를 저장할 메모리 확보 후 10으로 초기화 09 // V1.reserve(10); // 정수 10개를 저장할 메모리 확보 10 // V1.at(0) = 1; 11 // V1[1] = 2; 12 13 V1.push_back(10); 14 V1.push_back(20); 15 V1.push_back(30); 16 V1.push_back(40); 17 cout << "V1.capacity() = " << V1.capacity() << endl; 18 19 cout << "for:" << endl; 20 for (int i = 0; i < V1.size(); i++) 21 { 22 cout << V1[i] << endl; [예제 16-1] vector를 1차원 배열처럼 사용하기 ex16_1.cpp

01_vector 컨테이너 23 } 24 25 V1.erase(V1.begin() + 2); // 30 삭제 26 23 } 24 25 V1.erase(V1.begin() + 2); // 30 삭제 26 27 cout << endl << "iterator:" << endl; 28 vector<int>::iterator it1; 29 for (it1 = V1.begin(); it1 != V1.end(); it1++) 30 { 31 cout << *it1 << endl; 32 } 33 34 cout << endl << "reverse_iterator:" << endl; 35 36 V1.insert(V1.begin() + 2, 30); // 30 추가 37 38 vector<int>::reverse_iterator it2; 39 for (it2 = V1.rbegin(); it2 != V1.rend(); it2++) 40 { 41 cout << *it2 << endl; 42 } 43 V1.clear(); // V1 벡터 삭제 44 return 0; 45 }

01_vector 컨테이너 결과 V1.capacity() = 4 for: 10 20 30 40 iterator: reverse_iterator: 결과 2행: vector 컨테이너를 사용하기 위한 헤더 파일을 포함한다. 6행: 정수 벡터 컨테이너 V1을 생성한다. V1은 배열과 같이 사용할 수 있다. vector<int> V1(4)는 정수 4개를 저장할 수 있는 메모리 할당한다. vector<int> V1(4, 10)은 정수 4개를 저장할 수 있는 메모리 할당하고, 10으로 초기화한다. 생성자를 통해 메모리가 할당된 후 push_back( )을 사용하면, 맨 뒤에 데이터가 삽입되는 것에 주의해야 한다. 메모리가 할당된 경우는 V1.at(0) = 1과 같이 at( ) 멤버 함수를 사용하여 접근하거나, V1[1] = 2와 같이 배열처럼 사용한다. 13-16행: push_back( ) 멤버 함수를 이용하여 정수 벡터 컨테이너 V1에 정수 10, 20, 30, 40을 넣는다. 17행: capacity( ) 멤버 함수로 재할당된 메모리를 알 수 있다. capacity( )와 size( )의 결과가 항상 같지는 않다. 일반적으로 capacity( )가 크거나 같다.

01_vector 컨테이너 20-23행: 정수 벡터 컨테이너 V1의 크기는 V1.size( )로 알 수 있다. V1.size( )는 4이다. 각 데이터는 배열과 같이 V1[i]로 접근할 수 있다. V1[0]= 10, V1[1] = 20, V1[2] = 30, V1[3] = 40이다. 25행: erase( ) 멤버 함수는 벡터의 요소를 삭제한다. 인수로 삭제하려는 이터레이터 포인터를 전달해야 한다. V1.begin( )+2는 30이 저장된 곳을 가리킨다. 28행: 정수 벡터 컨테이너 V1의 각 요소를 가리키기 위한 이터레이터 it1을 선언한다. 이터레이터는 포인터를 관리하는 템플릿으로, 이를 이용하면 컨테이너의 요소를 매우 편리하게 접근할 수 있다. 29-32행: [그림 16-1]과 같이 V1.begin( )은 V1의 시작 요소(10이 저장되어 있는 요소)를 가리키며, V1.end( )는 V1의 맨 마지막 요소(40) 다음을 가리킨다. 이터레이터를 이용하여 벡터 V1의 마지막에 도달했는지를 조건 it1 ! = V1.end( )로 확인한다. it1++는 이터레이터를 다음 요소로 이동시킨다. 이와 같은 방식을 이용하면 벡터의 크기에 관련 없이 요소를 매우 효율적으로 접근할 수 있다. 이터레이터가 가리키는 값은 *it1로 알 수 있다. 30이 삭제되었기 때문에 10, 20, 40이 출력된다. 36행: 벡터 V1에 10, 20, 40이 있을 때, V1.begin( )+2 위치에 30을 추가하면 [그림 16-2]와 같이 해당 벡터에는 10, 20, 30, 40이 존재한다. 벡터에서 삽입과 삭제가 많이 발생하면 속도 저하가 일어날 수 있다.

01_vector 컨테이너 38행: 벡터의 뒤에서부터 앞으로 움직이는 역방향 이터레이터의 인스턴스 it2를 선언한다. ⑪ 39-42행: [그림 16-3]과 같이 V1.rbegin( )은 V1의 마지막 요소(40)를 가리킨다. V1.rend( )는 V1의 처음 요소 다음을 가리킨다. it2를 이용하여 뒤에서부터 앞으로 하나씩 이터레이터를 이동한다. ⑫ 43행: V1의 데이터를 삭제한다. V1.erase(V1.begin( ), V1.end( ))와 같다. V1.clear( )를 실행하면 V1.size( )=0이 된다. ⑬ 9행: reserve( ) 멤버 함수로 메모리를 확보해 두고 사용하면 빈번한 재할당으로 인한 속도 저하를 방지할 수 있다.

01_vector 컨테이너 [예제 16-2] vector를 2차원 배열처럼 사용하기 ex16_2.cpp 01 #include <iostream> 02 #include <iomanip> 03 #include <vector> 04 using namespace std; 05 main() 06 { 07 // vector< vector<int> > M1(3, vector<int>(2, 0) ); 08 vector<int> V1(2, 0); 09 vector< vector<int> > M1(3, V1); 10 11 M1[0][0] = 0; 12 M1[0][1] = 1; 13 M1[1][0] = 10; 14 M1[1][1] = 11; 15 M1[2][0] = 20; 16 M1[2][1] = 21; 17 18 cout << "M1.size() = " << M1.size() << endl; 19 cout << "M1[0].size() = " << M1[0].size() << endl; 20 21 cout << endl << "for 문 사용:" << endl; 22 for (int i = 0; i < M1.size(); i++) 23 { [예제 16-2] vector를 2차원 배열처럼 사용하기 ex16_2.cpp

01_vector 컨테이너 24 for (int j = 0; j < M1[i].size(); j++) 25 { 25 { 26 cout << setw(2) << M1[i][j] << " "; 27 } 28 cout << endl; 29 } 30 31 vector< vector<int> >::iterator it1; 32 vector<int>::iterator it2; 33 cout << endl << "이터레이터 사용:" << endl; 34 for (it1 = M1.begin(); it1 != M1.end(); it1++) 35 { 36 for (it2 = (*it1).begin(); it2 != (*it1).end(); it2++) 37 { 38 cout << setw(2) << *it2 << " "; 39 } 40 cout << endl; 41 } 42 } M1.size() = 3 M1[0].size() = 2 for 문 사용: 0 1 10 11 20 21 결과

01_vector 컨테이너 이터레이터 사용: 0 1 10 11 20 21 8행: 정수 벡터 V1을 크기 2, 초기 값 0으로 생성한다. 9행: 정수 벡터를 요소로 포함하는 벡터 M1을 크기 3, 초기 값 V1로 생성하면, M1.size( )=3이 되고, M1[0].size( ), M1[1].size( ), M1[2].size( )는 모두 2가 된다. 11-16행: M1[0][0] = 0과 같이 2차원 배열처럼 접근할 수 있다. 22-29행: for 문으로 2차원 배열처럼 M1[i][j]를 접근하여 출력할 수 있다. setw(2)에 의해 cout은 내용을 두 자리로 출력한다. 31행: M1에 해당하는 이터레이터 it1을 선언한다. 32행: M1의 각 요소가 정수 벡터이므로 이에 해당하는 이터레이터 it2를 선언한다.

02_list 컨테이너 list 전통적인 포인터를 이용한 이중 연결 리스트를 대신하여 사용할 수 있음 데이터가 연속으로 할당되지는 않으며, 임의의 위치에서 삽입과 삭제가 빠름 push_back( ) : 리스트의 끝 부분에 데이터를 삽입함 push_front( ) : 리스트의 처음 부분에 데이터를 삽입함 front( ) : 리스트의 맨 앞에 있는 멤버를 반환함 pop_front( ) : 리스트의 맨 앞에 있는 멤버를 삭제함 back( ) : 리스트의 맨 뒤에 있는 멤버를 반환함 pop_back( ) : 리스트의 맨 뒤에 있는 멤버를 삭제함 size( ) : 리스트가 담고 있는 요소의 개수를 반환함 01 #include <iostream> 02 #include <list> 03 using namespace std; 04 main() 05 { 06 list<int> L1; 07 L1.push_back(20); // 20 08 L1.push_front(10); // 10 20 09 L1.push_back(30); // 10 20 30 [예제 16-3] 단순 정수 리스트 ex16_3.cpp

02_list 컨테이너 10 L1.push_back(40); // 10 20 30 40 11 12 L1.insert(L1.begin(), 5); // 5 10 20 30 40 13 cout << "L1.size() = " << L1.size() << endl; 14 15 list<int>::iterator it; 16 for (it = L1.begin(); it != L1.end(); it++) 17 cout << *it << " "; 18 cout << endl; 19 20 cout << "L1.front() = " << L1.front() << endl; 21 L1.pop_front(); 22 23 cout << "L1.back() = " << L1.back() << endl; 24 L1.pop_back(); 25 26 for (it = L1.begin(); it != L1.end(); it++) 27 cout << *it << " "; 28 cout << endl; 29 30 L1.clear(); 31 return 0; 32 }

02_list 컨테이너 결과 L1.size() = 5 5 10 20 30 40 L1.front() = 5 L1.back() = 40 10 20 30 결과 6행: 정수 데이터를 저장할 수 있는 리스트 L1을 생성한다. 7행: 리스트 L1의 맨 뒤에 20을 추가한다. 8행: 리스트 L1의 맨 앞에 10을 추가한다. 리스트 L1에는 데이터가 10, 20 순서로 들어가 있다. 9-10행: 리스트 L1의 뒤에 30, 40을 차례로 추가하면, 리스트 L1에는 데이터가 10, 20, 30, 40 순서로 들어가 있다. 12행: insert( ) 멤버 함수로 L1의 맨 앞에 5를 추가하면, 리스트 L1에는 데이터가 5, 10, 20, 30, 40 순서로 들어가 있다. 13행: L1.size( )는 리스트 L1이 담고 있는 요소의 개수 5를 반환한다. 20-24행: L1.front( )는 리스트 L1의 맨 앞에 있는 요소 5를 반환한다. pop_front( ) 멤버 함수는 리스트의 맨 앞에 있는 요소 5를 삭제한다. back( ) 멤버 함수는 리스트의 맨 뒤에 있는 요소 40을 반환한다. pop_back( ) 멤버 함수는 리스트의 맨 뒤에 있는 요소 40을 삭제한다.

02_list 컨테이너 [예제 16-4] 클래스 인스턴스를 리스트에 추가하기 ex16_4.cpp 01 #include <iostream> 02 #include <list> 03 using namespace std; 04 class CPoint 05 { 06 int x; 07 int y; 08 public: 09 CPoint(int x = 0, int y = 0); // 생성자 10 CPoint(const CPoint &); // 복사 생성자 11 ~CPoint() { cout << "Destructor\n"; }; 12 void SetPt(int x, int y); 13 int GetX() { return x; } 14 int GetY() { return y; } 15 CPoint &operator=(const CPoint &pt); 16 friend ostream & operator <<(ostream &out, CPoint &pt); 17 }; 18 19 CPoint::CPoint(int x, int y) // 생성자 20 { 21 this->x = x; 22 this->y = y; 23 } [예제 16-4] 클래스 인스턴스를 리스트에 추가하기 ex16_4.cpp

02_list 컨테이너 24 25 CPoint::CPoint(const CPoint &pt) // 복사 생성자 26 { 26 { 27 cout << "Copy constructor" << endl; 28 x = pt.x; 29 y = pt.y; 30 } 31 32 void CPoint::SetPt(int x, int y) 33 { 34 this->x = x; 35 this->y = y; 36 } 37 38 CPoint& CPoint::operator=(const CPoint &pt) 39 { 40 this->x = pt.x; 41 this->y = pt.y; 42 return *this; 43 } 44 45 ostream & operator<<(ostream &out, CPoint & pt) // 프렌드 함수 46 { 47 out << "(" << pt.x << ", " << pt.y << ") ";

02_list 컨테이너 48 return out; 49 } 50 51 main() 52 { 49 } 50 51 main() 52 { 53 list<CPoint> L; 54 CPoint pt(10, 20); 55 56 L.push_back(pt); // 복사 생성자 호출 57 58 pt.SetPt(10, 30); 59 L.push_back(pt); // 복사 생성자 호출 60 61 pt.SetPt(10, 40); 62 L.push_back(pt); // 복사 생성자 호출 63 64 list<CPoint>::iterator it; 65 cout << "Using (*it).GetX(), (*it).GetY()" << endl; 66 for (it = L.begin(); it != L.end(); it++) 67 cout << "(" << (*it).GetX() << ", " << (*it).GetY() << ") "; 68 cout << endl; 69 70 cout << endl << "operator << friend function!" << endl; 71 for (it = L.begin(); it != L.end(); it++)

02_list 컨테이너 72 cout << *it << " "; // 프렌드 연산자 << 호출 73 cout << endl; 74 75 return 0; 76 } Copy constructor Using (*it).GetX(), (*it).GetY() (10, 20) (10, 30) (10, 40) operator << friend function! Destructor 결과 53행: CPoint를 요소로 포함하는 리스트 L을 선언한다. 56, 59, 62행: CPoint 인스턴스 pt를 push_back할 때 CPoint 클래스의 복사 생성자가 호출되어 복사된 객체가 리스트 L에 추가된다. 64, 66-67행: CPoint 리스트 L에 대한 이터레이터 it를 선언한다. for 문으로 이터레이터 it를 리스트 L.begin( )부터 L.end( )까지 움직이면서 리스트의 데이터를 *it로 참조한다. 72행: 연산자 중복 함수 <<로 데이터를 출력한다. 비주얼 C++ 6.0에서는 #include <iostream>와 using namespace std를 사용하는 이 예제를 컴파일하면 오류가 발생할 수 있지만, 서비스 팩 6을 설치하면 오류가 발생하지 않는다.

03_map 컨테이너와 set 컨테이너 map 컨테이너 map은 키(key)와 데이터(data)를 연결하여 키를 이용해서 데이터를 빠르게 찾을 수 있는 컨테이너로, 키에 따라 정렬된 순서로 데이터를 유지함 키는 유일(unique)해야 하며, 숫자, 문자열 등 순서가 있는 (즉, 비교 연산자를 적용할 수 있는) 자료형이면 모두 키가 될 수 있음 키는 첫 번째(first) 멤버에, 데이터는 두 번째(second) 멤버에 저장됨 01 #include <iostream> 02 #include <string> 03 //#include <utility> // make_pair() 04 #include <map> 05 using namespace std; 06 07 int main() 08 { 09 map<int, string> student; 10 student[11] = "홍길동"; 11 student[12] = "손오공"; 12 // student[10] = "김철수"; 13 student.insert(pair<int, string> (10, "김철수")); 14 // student.insert(make_pair<int, string>(10, "김철수")); [예제 16-5] 정수 키, 문자열 데이터 맵 ex16_5.cpp

03_map 컨테이너와 set 컨테이너 15 16 cout << "student[10] = " << student[10] << endl << endl; 17 cout << "student.size() = " << student.size() << endl; 18 map<int, string>::iterator it; 19 for (it = student.begin(); it != student.end(); it++) 20 cout << (*it).first << ": " << (*it).second << endl; 21 it = student.find(10); // 검색 키 10 22 if (it != student.end()) 23 cout << "Found: (" << (*it).first << ", " << (*it).second << ")" << endl; 24 else 25 cout << "Not Found" << endl; 26 27 return 0; 28 } student[10] = 김철수 student.size() = 3 10: 김철수 11: 홍길동 12: 손오공 Found: (10, 김철수) 결과 9행: 정수 키, 문자열 데이터를 담는 맵 student를 생성한다. string은 typedef basic_string<char> string과 같이 자료형이 정의된 문자열 관련 템플릿 클래스이다.

03_map 컨테이너와 set 컨테이너 [예제 16-6] 문자열 키, 정수 데이터 맵 ex16_6.cpp 10-11행: 키 11, 데이터“홍길동”과 키 12, 데이터“손오공”을 student 맵에 저장한다. 13행: pair 템플릿을 사용하여 키 10, 데이터“김철수”에 대한 객체를 만들고, insert( ) 멤버 함수를 이용하여 student 맵에 저장한다. make_pair 함수를 사용하려면 utility 헤더를 추가해야 한다. 16-17행: student[10]과 같이 키 10으로 student 맵을 검색하면 문자열“김철수”가 검색된다. student.size( )는 데이터의 개수 3을 반환한다. 20행: 이터레이터 it를 사용하여 student 맵을 차례로 출력하면 정수 키에 따라 정렬되어 저장된 것을 확인할 수 있다. 21행: find( ) 멤버 함수를 이용하여 키가 10인 요소를 찾는다. 반환 값을 저장한 이터레이터 it가 student.end( )가 아니면 해당 요소가 맵에 있는 것이다. 01 #include <iostream> 02 #include <string> 03 #include <map> 04 using namespace std; 05 main() 06 { 07 map<string, int> student; 08 student["홍길동"] = 11; 09 student["김철수"] = 10; 10 student.insert(std::pair<string, int>("손오공", 12)); 11 12 cout << "student[홍길동] = " << student["홍길동"] << endl << endl; 13 cout << "student.size() = " << student.size() << endl; [예제 16-6] 문자열 키, 정수 데이터 맵 ex16_6.cpp

03_map 컨테이너와 set 컨테이너 14 15 map<string, int>::iterator it; 16 for (it = student.begin(); it != student.end(); it++) 17 { 18 cout << (*it).first << ": " << (*it).second << endl; 19 } 20 it = student.find("김철수"); //search key = "김철수" in student 21 if (it != student.end()) 22 cout << "Found: (" << (*it).first << ", " << (*it).second << ")" << endl; 23 else 24 cout << "Not Found" << endl; 25 return 0; 26 } student[홍길동] = 11 student.size() = 3 김철수: 10 손오공: 12 홍길동: 11 Found: (김철수, 10) 결과 7행: 문자열 키, 정수 데이터를 담는 student 맵을 생성한다. string에는 문자열 비교 연산자가 정의되어 있다. 8-9행: 키“홍길동”, 데이터 11과 키“김철수”, 데이터 10을 student 맵에 저장한다.

03_map 컨테이너와 set 컨테이너 10행: pair 템플릿을 사용하여 키“손오공”, 데이터 12인 객체를 만들고, insert( ) 멤버 함수를 통해 student 맵에 저장한다. 11행: student“[ 홍길동”]으로 검색하면 데이터 11을 찾는다. 맵을 사용하면 문자열을 마치 배열의 첨자와 같이 사용하여 검색할 수 있다. 18행: 이터레이터 it를 사용하여 student 맵을 차례로 출력하면, 문자열 키에 따라 정렬되어 저장된 것을 확인할 수 있다. 01 #include <iostream> 02 #include <map> 03 #include <string.h> // strcmp() 04 using namespace std; 05 struct compare_str // 키 비교 06 { 07 bool operator()(char *str1, char *str2) 08 { 09 return strcmp(str1, str2) < 0; // 오름차순 10 // return strcmp(str1, str2) > 0; // 내림차순 11 } 12 }; 13 14 main() 15 { [예제 16-7] 문자 포인터 키, 정수 데이터, 비교 연산자 함수를 포함하는 맵 ex16_7.cpp

03_map 컨테이너와 set 컨테이너 16 map<char *, int, compare_str> student; 18 student.insert(pair<char *, int> ("홍길동", 11)); 19 student.insert(make_pair<char *, int> ("김철수", 10)); 20 student.insert(map<char *, int>::value_type("손오공", 12)); 21 22 cout << "student[홍길동] = " << student["홍길동"] << endl << endl; 23 cout << "student.size() = " << student.size() << endl; 24 25 map<char *, int, compare_str>::iterator it; 26 for (it = student.begin(); it != student.end(); it++) 27 { 28 cout << (*it).first << ": " << (*it).second << endl; 29 } 30 return 0; 31 } student[홍길동] = 11 student.size() = 3 김철수: 10 손오공: 12 홍길동: 11 결과 5-12행: 구조체 compare_str에 문자 포인터 str1과 str2가 가리키는 두 문자열을 비교할 수 있는 연산자 ( )를 정의한다. string.h 헤더에 선언된 strcmp 함수를 이용하여 비교한다.

03_map 컨테이너와 set 컨테이너 set 컨테이너 집합을 표현하는 컨테이너로 키와 데이터가 같으며, 동일한 키는 허용하지 않음 16행: char * 키, 정수 데이터를 담는 student 맵을 선언한다. 키의 비교에는 compare_str 구조체의 연산자 ( )를 이용한다. 8-20행: pair, make_pair, value_type을 사용하여 객체를 생성한 다음 insert 멤버 함수로 student 맵에 추가한다. 01 #include <iostream> 02 #include <set> 03 using namespace std; 04 05 main() 06 { 07 /* 08 int nArr[] = { 10, 20, 30, 40}; 09 set<int> S1(nArr, nArr+4); 10 */ 11 set<int> S1; 12 S1.insert(10); 13 S1.insert(20); 14 S1.insert(40); [예제 16-8] 정수 키를 담는 set ex16_8.cpp

03_map 컨테이너와 set 컨테이너 15 S1.insert(30); 16 S1.insert(30); 17 18 set<int>::iterator it; 19 it = S1.find(30); 20 if (it != S1.end()) 21 cout << "30 is a member in set S1" << endl; 22 else 23 cout << "30 is not a member in set S1" << endl; 24 25 for (it = S1.begin(); it != S1.end(); it++) 26 { 27 cout << (*it) << " "; 28 } 29 cout << endl; 30 return 0; 31 } 30 is a member in set S1 10 20 30 40 결과 11행: 정수를 키로 포함하는 집합 S1을 생성한다. 9행: 이와 같이 배열을 이용하여 초기화할 수도 있다. 12-16행: insert 멤버 함수를 이용하여 집합 S1에 정수 10, 20, 30, 40을 정렬된 순서로 삽입한다. 집합에 데이터 30을 2번 삽입해도 한 번만 삽입되는 것을 알 수 있다. 19-20행: find( ) 멤버 함수를 이용하여 집합 S1에 30이 있는지를 확인한다. S1에 30이 있으면 이터레이터 it가 S1.end( )가 아니다.

04_알고리즘 STL 알고리즘 STL 컨테이너에 담긴 요소들을 대상으로 하는 함수 템플릿 대부분의 알고리즘은 algorithm 헤더 파일에 정의되어 있고, 수치 관련 알고리즘은 numeric 헤더 파일에 정의됨 copy, find, sort, unique 등 유용한 알고리즘이 구현되어 있음 01 #include <iostream> 02 #include <vector> 03 #include <algorithm> 04 using namespace std; 05 void print_data(int value) 06 { 07 cout << value << " "; 08 } 09 10 main() 11 { 12 int nArr[] = { 30, 10, 40, 20, 30 }; 13 vector<int> V1(5); 14 vector<int>::iterator it; 15 [예제 16-9] copy( ), for_each( ) 알고리즘 ex16_9.cpp

04_알고리즘 16 copy(nArr, nArr + 5, V1.begin()); 17 cout << "V1 = ( "; 18 for (it = V1.begin(); it != V1.end(); it++) 19 cout << *it << " "; 20 cout << ")" << endl; 21 22 cout << "V1 = ( "; 23 for_each(V1.begin(), V1.end(), print_data); 24 cout << ")" << endl; 25 } V1 = ( 30 10 40 20 30 ) 결과 13행: 정수 벡터 V1을 선언하고, 정수 5개를 저장할 수 있는 메모리를 할당한다. 16행: 정수 배열 nArr을 벡터 V1에 복사한다. 18-19행: 이터레이터를 사용하여 V1의 데이터를 출력한다. 23행: for_each( ) 알고리즘은 V1.begin( ), V1.end( ) 범위에 있는 모든 요소를 대상으로 print_data( ) 함수를 호출한다.

04_알고리즘 [예제 16-10] find( ), sort( ) 알고리즘 ex16_10.cpp 01 #include <iostream> 02 #include <vector> 03 #include <algorithm> 04 using namespace std; 05 bool greater20(int value) 06 { 07 return value > 20; // count_if value > 20 08 } 09 10 main() 11 { 12 int nArr[] = { 30, 10, 40, 20, 30 }; 13 vector<int> V1(5); 14 vector<int>::iterator it; 15 16 copy(nArr, nArr + 5, V1.begin()); 17 cout << "V1 = ( "; 18 for (it = V1.begin(); it != V1.end(); it++) 19 cout << *it << " "; 20 cout << ")" << endl; 21 22 it = find(V1.begin(), V1.end(), 30); 23 if (it != V1.end()) [예제 16-10] find( ), sort( ) 알고리즘 ex16_10.cpp

04_알고리즘 24 cout << "There is 30 in V1." << endl; 25 else 26 cout << "There is no 30 in V1" << endl; 27 28 int res; 29 res = count_if(V1.begin(), V1.end(), greater20); 30 cout << "count if greater than 20 = " << res << endl; 31 32 vector<int> V2; 33 V2.resize(V1.size()); // 요소들을 위한 공간 할당 34 copy(V1.begin(), V1.end(), V2.begin()); 35 36 cout << "V2.size() = " << V2.size() << endl; 37 cout << "Copyed V2 = ( "; 38 for (it = V2.begin(); it != V2.end(); it++) 39 cout << *it << " "; 40 cout << ")" << endl; 41 return 0; 42 } V1 = ( 30 10 40 20 30 ) There is 30 in V1. count if greater than 20 = 3 V2.size() = 5 Copyed V2 = ( 30 10 40 20 30 ) 결과

04_알고리즘 22행: 벡터 V1에서 데이터 30을 검색한다. 30이 벡터 V1에 있으면 it != V1.end( )가 참이 된다. 29행: 벡터 V1에서 greater20 함수를 조건으로 하여 20보다 큰 정수의 개수를 계산한다. bool greater20( ) 함수는 인수 value가 20보다 크면 참을 반환한다. 32-33행: 정수 벡터 V2를 선언하고, V2의 크기를 V1의 크기로 조정한다. 34행: 벡터 V1을 벡터 V2에 복사한다. 01 #include <iostream> 02 #include <vector> 03 #include <algorithm> 04 using namespace std; 05 bool compare_function(int a, int b) 06 { 07 return a < b; // 오름차순 정렬 08 } 09 10 main() 11 { 12 int nArr[] = { 30, 10, 10, 20, 30 }; 13 vector<int> V1(5); 14 vector<int>::iterator it; 15 16 copy(nArr, nArr + 5, V1.begin()); [예제 16-11] sort( ), unique( ) 알고리즘과 ostream_iterator( ) ex16_11.cpp

04_알고리즘 17 sort(V1.begin(), V1.end(), compare_function); 18 cout << "Sorted V1 = ( "; 19 for (it = V1.begin(); it != V1.end(); it++) 20 cout << *it << " "; 21 cout << ")" << endl; 22 23 vector<int>::iterator it2; 24 it2 = unique(V1.begin(), V1.end()); 25 // copy(V1.begin(),V1.end( ), ostream_iterator<int> (cout, " ")); 26 27 cout << "copy(V1.begin(), it2) = "; 28 copy(V1.begin(), it2, ostream_iterator<int> (cout, ", ")); 29 cout << endl; 30 31 V1.erase(it2, V1.end()); 32 cout << "unique elements in V1 = "; 33 copy(V1.begin(), V1.end(), ostream_iterator<int> (cout, " ")); 34 cout << endl; 35 return 0; 36 } Sorted V1 = ( 10 10 20 30 30 ) copy(v1.begin(), it2) = 10, 20, 30, unique elements in V1 = 10 20 30 결과

04_알고리즘 [예제 16-12] accumulate( ), InnderProduct( ) ex16_12.cpp 16행: 정수 배열 nArr을 벡터 V1에 복사한다. 17행: 벡터 V1을 compare_function( ) 함수를 사용하여 정렬한다. compare_function( ) 함수는 오름차순으로 정렬한다(두 정수 a, b를 비교하여 a < b를 반환한다). 24행: unique( ) 알고리즘 함수는 연속적인 데이터의 그룹에서 동일한 값에 대하여 한 데이터만 유지한다. 벡터 데이터 전체에 대하여 한 데이터만 유지하려면 먼저 sort( ) 알고리즘 함수를 적용해야 한다. unique( ) 알고리즘 함수를 실행하고 나면 V1.begin( )부터 이터레이터인 it2-1까지 유일한 데이터를 유지한다. 28행: copy( ) 알고리즘 함수를 사용하여 V1.begin( )부터 이터레이터 it2까지(실제는 it2-1까지) ostream_iterator<int> (cout,“ ”)로 복사하면 각 정수 데이터가 cout으로 출력된다. 31행: erase( ) 멤버 함수를 사용하여 unique( ) 알고리즘 함수에서 반환한 it2부터 V1.end( )까지 삭제하면 V1에는 유일한 데이터만 남는다. 01 #include <iostream> 02 #include <vector> 03 #include <algorithm> 04 #include <numeric> 05 using namespace std; 06 main() 07 { 08 int nArr1[] = { 1, 0, 1, 2 }; 09 int nArr2[] = { 2, 1, 0, 2 }; 10 vector<int> V1(4); 11 vector<int> V2(4); [예제 16-12] accumulate( ), InnderProduct( ) ex16_12.cpp

04_알고리즘 12 copy(nArr1, nArr1 + 4, V1.begin()); 14 15 int sum = accumulate(V1.begin(), V1.end(), 0); 16 cout << "sum(V1) = " << sum << endl; 17 18 int inner = inner_product(V1.begin(), V1.end(), V2.begin(), 0); 19 cout << "InnderProduct(V1.V2) = " << inner << endl; 20 return 0; 21 } sum(V1) = 4 InnderProduct(V1.V2) = 6 결과 12-13행: nArr1 배열을 벡터 V1에 복사하고, nArr2 배열을 벡터 V2에 복사한다. 15행: numeric 헤더 파일에 정의되어 있는 accumulate( ) 함수는 합계를 반환한다. 초기 값으로 0을 지정한다. 벡터 V1의 합은 4이고, 벡터 V2의 합은 5이다. 18행: inner_product( ) 함수는 내적을 계산한다. 프로그램을 실행하면 V1과 V2의 내적은 6임을 알 수 있다.

04_알고리즘 01 #include <iostream> 02 #include <vector> 03 #include <set> 04 #include <algorithm> 05 using namespace std; 06 main() 07 { 08 int nArr1[] = { 1, 0, 2 }; 09 int nArr2[] = { 0, 2, 4 }; 10 11 set<int> S1(nArr1, nArr1 + 3); 12 set<int> S2(nArr2, nArr2 + 3); 13 14 cout << "S1 = { "; 15 copy(S1.begin(), S1.end(), ostream_iterator<int> (cout, " ")); 16 cout << "}" << endl; 17 18 cout << "S1 = { "; 19 copy(S2.begin(), S2.end(), ostream_iterator<int> (cout, " ")); 20 cout << "}" << endl; 21 22 vector<int>::iterator itEnd; 23 vector<int> V1(S1.size() + S2.size()); [예제 16-13] set_intersection( ), set_union( ), set_difference( ) 알고리즘 ex16_13.cpp

04_알고리즘 24 25 itEnd = set_intersection(S1.begin(), S1.end(), S2.begin(), S2.end(), V1.begin()); 26 cout << "Intersection(S1, S2) = { "; 27 copy(V1.begin(), itEnd, ostream_iterator<int> (cout, " ")); 28 cout << "}" << endl; 29 30 itEnd = set_union(S1.begin(), S1.end(), S2.begin(), 31 cout << "Union(S1, S2) = { "; 32 copy(V1.begin(), itEnd, ostream_iterator<int> (cout, " ")); 33 cout << "}" << endl; 34 35 itEnd = set_difference(S1.begin(), S1.end(), S2.begin(), 36 cout << "Difference(S1, S2) = { "; 37 copy(V1.begin(), itEnd, ostream_iterator<int> (cout, " ")); 38 cout << "}" << endl; 39 return 0; 40 } S1 = { 0 1 2 } S1 = { 0 2 4 } Intersection(S1, S2) = { 0 2 } Union(S1, S2) = { 0 1 2 4 } Difference(S1, S2) = { 1 } 결과

04_알고리즘 [예제 16-14] transform( ), 산술 함수 객체 ex16_14.cpp 23행: 집합 S1과 S2의 교집합, 합집합, 차집합을 계산한 결과를 저장할 정수 벡터 V1을 선언하고 저장 공간을 S1과 S2 크기의 합으로 할당한다. 25행: set_intersection( ) 함수는 S1과 S2의 교집합을 계산하여 V1에 저장한다. V1의 논리적인 끝을 나타내는 이터레이터를 반환한다. 30행: set_union( ) 함수는 S1과 S2의 합집합을 계산하여 V1에 저장한다. V1의 논리적인 끝을 나타내는 이터레이터를 반환한다. 35행: set_difference( ) 함수는 S1과 S2의 차집합을 계산하여 V1에 저장한다. V1의 논리적인 끝을 나타내는 이터레이터를 반환한다. 01 #include <iostream> 02 #include <vector> 03 #include <algorithm> 04 #include <numeric> 05 #include <functional> 06 using namespace std; 07 main() 08 { 09 int nArr1[] = { 2, 0, 6, 8 }; 10 int nArr2[] = { 1, 1, 2, 2 }; 11 12 vector<int> V1(nArr1, nArr1 + 4); 13 vector<int> V2(nArr2, nArr2 + 4); 14 vector<int> V3(V1.size()); [예제 16-14] transform( ), 산술 함수 객체 ex16_14.cpp

04_알고리즘 15 16 cout << "V1 = { "; 17 copy(V1.begin(), V1.end(), ostream_iterator<int> (cout, " ")); 18 cout << "}" << endl; 19 20 cout << "V2 = { "; 21 copy(V2.begin(), V2.end(), ostream_iterator<int> (cout, " ")); 22 cout << "}" << endl; 23 24 transform(V1.begin(), V1.end(), V2.begin(), V3.begin(), plus<int> ()); 25 26 cout << "V3 = V1 + V2 = { "; 27 copy(V3.begin(), V3.end(), ostream_iterator<int> (cout, " ")); 28 cout << "}" << endl; 29 30 // V3.assign(V3.size(), 0); 31 transform(V1.begin(), V1.end(), V2.begin(), V3.begin(), minus<int> ()); 32 33 cout << "V3 = V1 - V2 = { "; 34 copy(V3.begin(), V3.end(), ostream_iterator<int> (cout, " ")); 35 cout << "}" << endl; 36

04_알고리즘 37 transform(V1.begin(), V1.end(), V2.begin(), V3.begin(), multiplies<int> ()); 38 cout << "V3 = V1 * V2 = { "; 39 copy(V3.begin(), V3.end(), ostream_iterator<int> (cout, " ")); 40 cout << "}" << endl; 41 42 transform(V1.begin(), V1.end(), V2.begin(), V3.begin(), divides<int> ()); 43 cout << "V3 = V1 / V2 = { "; 44 copy(V3.begin(), V3.end(), ostream_iterator<int> (cout, " ")); 45 cout << "}" << endl; 46 47 transform(V1.begin(), V1.end(), V2.begin(), V3.begin(), greater<int> ()); 48 cout << "V3 = V1 > V2 = { "; 49 copy(V3.begin(), V3.end(), ostream_iterator<int> (cout, " ")); 50 cout << "}" << endl; 51 52 return 0; 53 } V1 = { 2 0 6 0 } V2 = { 1 1 2 2 } V3 = V1 + V2 = { 3 1 8 10 } V3 = V1 - V2 = { 1 -1 4 6 } V3 = V1 * V2 = { 2 0 12 16 } 결과

04_알고리즘 결과 V3 = V1 / V2 = { 2 0 3 4 } V3 = V1 > V2 = { 1 0 1 1 } 12행: 배열 nArr1로 벡터 V1을 초기화한다. 13행: 배열 nArr2로 벡터 V2를 초기화한다. 14행: 연산 결과를 저장할 벡터 V3의 메모리를 V1의 크기만큼 확보한다. 24행: transform( ) 알고리즘은 원본(source) 벡터에 주어지는 각 요소 또는 두 벡터의 각 쌍(pair)에 지정된 함수 객체를 적용한 후에 반환 값을 목적지(destination)에 복사하여 저장한다. 예제에서는 벡터 V1과 V2의 시작부터 대응하는 요소끼리 정수 덧셈(plus<int>( ))을 하여 벡터 V3에 저장한다. 24, 31, 37, 42, 47행: plus<int>( ), minus<int>( ), multiplies<int>( ), divides<int>( ), modulus<int>( ), negate<int>( ), equal_to<int>( ), not_equal_to<int>( ), greater<int>( ), less<int>( ), greater_equal<int>( ), less_equal<int>( ) 등의 미리 정의된 함수 객체는 functional 헤더 파일에 정의되어 있다. plus<float>과 같이 < > 안에 연산을 할 자료형을 지정하면 된다.

Thank You !