13.1 개요 13장과 14장에서는 표준 라이브러리가 제공하는 generic 알고리듬에 대해 설명한다. 아래 표는 13장에서 설명할 알고리듬의 이름과 용도를 요약해 놓은 것이며, 알고리듬들을 용도별로 분류하였다. 이름 용도 초기화 알고리듬 - 13.2절 fill 시퀀스를 초기값으로 채우기 fill_n n개의 자리를 초기값으로 채우기 copy 시퀀스를 다른 시퀀스에 복사하기 copy_backward 시퀀스를 다른 시퀀스에 복사하기 generate 생성기(generator)를 사용하여 시퀀스를 초기화하기 generate_n 생성기(generator)를 사용하여 n개의 자리를 초기화하기 swap_ranges 두 병렬 시퀀스의 내용 뒤바꾸기 검색 알고리듬 - 13.3절 find 인자값과 일치하는 원소 찾기 find_if 조건을 만족하는 원소 찾기 adjacent_find 연달아 중복된 원소 찾기 find_first_of 시퀀스내에서 다른 시퀀스에 속하는 멤버중 가장 먼저 발견되는 것 착지 find_end 시퀀스내에서 서브시퀀스의 마지막 발생 찾기 search 시퀀스내에서 서브 시퀀스 찾기 max_element 시퀀스에서 최대값 찾기 min_element 시퀀스에서 최소값 찾기 mismatch 두 시퀀스를 비교하여 불일치되는 곳 찾기 in-place 변환 - 13.4절 reverse 시퀀스의 원소 뒤집기 replace 특정값들을 다른 값으로 치환 replace_if 조건을 만족하는 원소들을 치환 rotate 한 점을 중심으로 원소들을 순환 partition 원소들을 두그룹으로 쪼개기 stable_partition 순서를 그대로 유지하며 쪼개기 next_permutation 다음 순열 생성하기 prev_permutation 이전 순열 생성하기 inplace_merge 두개의 이웃한 시퀀스를 하나로 합치기 random_shuffle 시퀀스 내의 원소들을 임의로 재배치하기 삭제 알고리듬 - 13.5절 remove 조건을 만족하는 원소 삭제 unique 중복되는 원소들 중 첫번째 것만 남기고 모두 삭제 스칼라 생성 알고리듬 - 13.6절 count 값과 일치하는 원소들을 카운트 count_if 조건을 만족하는 원소들을 카운트 accumulate 시퀀스로부터 스칼라값 얻기 inner_product 두 시퀀스의 내적 equal 두 시퀀스의 상등 검사 lexicographical_compare 두 시퀀스를 비교 시퀀스 생성 알고리듬 - 13.7절 transform 각 원소들을 변환 partial_sum 부분합들의 시퀀스를 생성 adjacent_difference 인접차들의 시퀀스를 생성 기타 연산 - 13.8절 for_each 콜렉션내의 원소 각각에 대해 함수를 적용 이 장에서는 각각의 알고리듬을 설명할 때, 간단한 예제를 들어 설명할 것이다. 13.1.1 Include 화일 generic 알고리듬을 사용하려면 적절한 헤더 화일을 포함시켜야 한다. 대다수의 함수가 algorithm 헤더화일에 정의되어 있다. accumulate(), inner_product(), partial_sum(), adjacent_difference()는 numeric 헤더화일에 정의되어 있다. #include #include 13.2 초기화 알고리듬 가장 먼저 다루게 될 알고리듬들은 새로 생성한 시퀀스를 특정값으로 초기화할 때 사용되는 것들이다. 13.2.1 시퀀스를 초기값으로 채우기 fill()과 fill_n() 알고리듬은 시퀀스를 정해진 값으로 초기화하거나 재초기화하는데 사용된다. 프로토타입은 다음과 같다. void fill(ForwardIterator first, ForwardIterator last, const T&); void fill_n(OutputIterator, Size, const T&); [Image] 초기화 알고리듬들간의 차이점 다음 예제 프로그램은 이들 알고리듬의 다양한 사용법을 보여주고 있다. void fill_example() { // 예1, 배열을 초기화한다. char buffer[100], * bufferp = buffer; fill(bufferp, bufferp + 100, '\0'); fill_n(bufferp, 10, 'x'); // 예2, list를 초기화한 뒤, 추가로 덧붙인다. list aList(5, "nothing"); fill_n(inserter(aList, aList.begin()), 10, "empty"); // 예3, list내의 값들을 덮어쓴다. fill(aList.begin(), aList.end(), "full"); // 예4, 콜렉션의 일부를 채운다. vector iVec(10); generate(iVec.begin(), iVec.end(), iotaGen(1)); vector::iterator & seven = find(iVec.begin(), iVec.end(), 7); fill(iVec.begin(), seven, 0); } 예1에서는 문자 배열을 선언하였다. fill() 알고리듬을 호출하여 이 배열을 모두 널문자들로 초기화한다. 이중 처음 10자리를 문자 'x'로 치환하기 위해서 fill_n() 알고리듬을 사용한다. fill() 알고리듬은 시작 반복자와 past-the-end 반복자를 인자로 요구하지만, fill_n() 알고리듬은 시작 반복자와 초기화할 갯수를 인자로 사용한다. 예2는 삽입 반복자(2.4절 참고)와 fill_n() 알고리듬을 사용하여 list와 같은 가변길이 컨테이너를 초기화하고 있다. 위 예에서 list는 처음에 5개의 원소를 가지고 있고, 이들 모두 "nothing"이라는 문자열로 초기화되어 있다. 그 다음, fill_n()을 호출하여 문자열 "empty"를 10개 삽입하였다. 결과적으로 list는 15개의 원소를 가지게 된다. 예3과 예4는 fill() 사용하여 컨테이너의 값들을 변화시키는 법을 설명하고 있다. 예3은 예2에서 생성한 list의 모든 원소들(총15개)을 문자열 "full"로 덮어쓴다. 예4는 list의 일부만 덮어쓰는 것을 보여준다. 우선 generate() 알고리듬과 iotaGen 함수 객체(3.3절 참고)를 사용하여, 1 2 3 ... 10으로 vector를 초기화한다. 그리고나서, find() 알고리듬(13.3.1절)을 사용하여 원소 7를 찾아, vector 타입의 반복자에 해당 위치를 저장한다. 그 다음에, fill()을 호출하여 처음부터 원소 7 바로 앞까지를 모두 0으로 치환한다. 이 결과 vector는 처음 여섯개는 0을, 그 다음에는 7, 8, 9, 10의 값을 가지게 된다. fill()과 fill_n() 알고리듬은 표준 라이브러리가 제공하는 모든 컨테이너 클래스에 사용할 수 있다. set과 같은 정렬 컨테이너는 삽입 반복자와 함께 사용해야 한다. 13.2.2 시퀀스를 다른 시퀀스에 복사하기 [Image] 여러개의 복사본을 덧붙이는 방법 copy()와 copy_backward() 알고리듬은 기능이 다양하여 여러 용도로 사용된다. 아마 표준 라이브러리에서 가장 많이 사용되는 알고리듬일 것이다. 이들의 프로토타입은 다음과 같다. OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result); BidirectionalIterator copy_backward (BidirectionalIterator first, BidirectionalIterator last, BidirectionalIterator result); 복사 알고리듬은 다음과 같은 용도에 주로 사용된다. * 전체 시퀀스를 새로운 시퀀스에 복사한다. * 현 시퀀스의 부시퀀스를 생성한다. * 시퀀스에 원소를 추가한다. * 입력에서 출력으로 시퀀스를 복사한다. * 시퀀스를 다른 형태로 바꾼다. 다음 예제 프로그램은 이 두 알고리듬을 설명하고 있다. void copy_example() { char *source = "reprise"; char *surpass = "surpass"; char buffer[120], *bufferp = buffer; // 예1, 그냥 단순한 복사 copy(source, source + strlen(source) + 1, bufferp); // 예2, 자기 자신으로의 복사 copy(bufferp + 2, bufferp + strlen(buffer) + 1, bufferp); int buflen = strlen(buffer) + 1; copy_backward(bufferp, bufferp + buflen, bufferp + buflen + 3); copy(surpass, surpass + 3, bufferp); // 예3, 출력으로 복사 copy(bufferp, bufferp + strlen(buffer), ostream_iterator(cout)); cout << endl; // 예4, copy()를 사용하여 배열을 list로 바꾼다. list char_list; copy(bufferp, bufferp + strlen(buffer), inserter(char_list, char_list.end())); char *big = "big "; copy(big, big + 4, inserter(char_list, char_list.begin())); char buffer2[120], *buffer2p = buffer2; *copy(char_list.begin(), char_list.end(), buffer2p) = '\0'; cout << buffer2 << endl; } 예1에서는 copy()를 호출하여 변수 source가 가리키는 문자열을 buffer로 복사하고, 따라서 buffer는 "reprise"를 가지게 된다. 복사가 끝나는 지점은 마지막 널문자를 지나서이고, 따라서 널문자도 복사된다. copy() 연산은 자기 자신에게로의 복사를 허용한다. 단, 목적지 반복자가 소스 반복자 구간에 속하지 않아야 한다. 예2에서 복사는 buffer의 2번 위치에서 시작하여 끝까지 진행되고, 문자들은 buffer의 맨앞으로 복사된다. 결과적으로 buffer는 "prise"를 가지게 된다. "그림"[copy_backward()] 예2의 뒷부분은 copy_backward() 알고리듬을 설명하고 있다. 이 함수는 copy() 알고리듬과 같은 작업을 수행하지만, 시퀀스의 끝에서부터 앞쪽으로 복사를 거꾸로 해 나간다. 위 예에서는 buffer에 "priprise"가 남게 된다. 그리고 나서, 다음에 이어지는 copy() 연산에 의해 처음 3개의 문자가 "sur"로 수정되어, buffer에 "surprise"가 남게 된다. [Image] copy_backward() 예3은 copy()를 사용하여 값을 출력 스트림으로 옮기는 것을 설명한다(2.3.2절 참고). 이 경우에 목적지는 출력 스트림 cout에 대해 생성된 ostream_iterator이다. 입력도 이와 비슷한 방법을 사용할 수 있다. 예를 들어, 입력 스트림에 들어있는 모든 단어를 list로 복사하는 방법은 copy() 알고리듬을 아래와 같이 호출하면 된다. list words; istream_iterator in_stream(cin), eof; copy(in_stream, eof, inserter(words, words.begin())); // words.begin()보다는 words.end()가 좋을 것 같은데... 이 기법은 8.3절에서 설명한 철자 검사기에서 사용된다. 복사는 스트림을 다른 타입으로 바꾸는데 사용할 수도 있다. 예를 들어, 예4에서의 호출은 문자 배열, buffer에 담긴 문자들을 문자 list로 복사한다. inserter()를 호출하여, 삽입 반복자를 만들고, 이를 이용하여 list에 값들을 삽입한다. copy()의 첫번째 호출은 2번 예제에서 생성한 "surprise" 문자열을 list에 삽입한다. copy()의 두번째 호출은 "big " 문자열을 list의 앞에 삽입한다. 따라서, list에는 "big surprise"가 담기게 된다. copy()의 마지막 호출은 이전과는 반대로 list내의 문자들을 문자 buffer로 복사한다. 13.2.3 발생기가 생성한 값으로 시퀀스 초기화하기 발생기(generator)는 연속적인 호출을 통해 일련의 값들을 리턴하는 함수이다. 아마 가장 익숙한 발생기로 난수 발생기를 들 수 있을 것이다. 그러나, 이외에도 시퀀스를 초기화하는 등의 여러가지 용도에 맞도록 발생기를 구성할 수 있다. fill()과 fill_n()과 같이 generate()과 generate_n()은 시퀀스를 초기화하거나 재초기화하는데 사용된다. 그러나, 이들 알고리듬은 고정된 인자값대신에 발생기가 생성한 값들을 사용한다. 이 두 알고리듬의 프로토타입은 다음과 같다. void generate(ForwardIterator, ForwardIterator, Generator); void generate_n(OutputIterator, Size, Generator); 다음 예는 시퀀스를 초기화하는 generate() 알고리듬의 다양한 사용예를 보여주고 있다. // 'L_ddd' 형태의 유일한 라벨을 생성하는 발생기 string generateLabel() { static int lastLabel = 0; char labelBuffer[80]; ostrstream ost(labelBuffer, 80); ost << "L_" << lastLabel++ << '\0'; return string(labelBuffer); } void generate_example() { // 예1, 라벨의 list를 생성 list labelList; // list 선언시 사이즈를 명시하지 않았으므로 삽입반복자를 사용 generate_n(inserter(labelList, labelList.begin()), 4, generateLabel); // 예2, 정수들의 시퀀스를 생성 vector iVec(10); // vector 선언시 사이즈를 명시했으므로 일반 반복자를 사용 generate(iVec.begin(), iVec.end(), iotaGen(2)); generate_n(iVec.begin(), 5, iotaGen(7)); } 발생기는 한개 이상의 정적 변수에 이전 상태를 저장하는 간단한 함수로 구현할 수 있다. 위 예의 맨 앞에 있는 generateLabel() 함수가 그 예이다. 이 함수는 유일한 라벨을 생성한다(컴파일러에서 이와 비슷한 작업을 한다). generateLabel() 함수를 호출할 때마다, 유일한 번호를 가지는 L_ddd 형태의 새로운 라벨을 만들어 낸다. lastLabel이란 이름을 가진 변수는 static으로 선언되었기 때문에, 이 변수의 값은 다음번 호출시에도 그대로 남게 된다. 예1은 발생기와 generate_n()알고리듬을 사용하여 list를 네개의 라벨로 초기화하고 있다. 3장에서 설명한 바와 같이, 표준 라이브러리에서의 함수는 함수호출 연산자(operator())에 반응하는 객체이다. 이 사실을 이용하면, 클래스를 함수로 만들어 버릴 수 있다. 3.3절에서 설명한 iotaGen 클래스가 그 예이다. iotaGen 함수 객체는 정수 시퀀스를 만드는 발생기를 생성한다. 예2는 이 시퀀스를 사용하여 vector를 2에서 11까지의 정수값으로 초기화한 뒤, generate_n() 함수를 호출하여 vector의 처음 다섯자리를 7부터 11까지의 값으로 덮어쓰고 있다. 결과적으로, vector에는 7 8 9 10 11 7 8 9 10 11을 포함하게 된다. 13.2.4 두개의 구간에 속한 원소들 서로 뒤바꾸기 템플릿 함수 swap()은 타입이 동일한 두 객체의 값을 교환하는데 사용된다. swap()은 다음과 같이 정의되어 있다. template void swap(T& a, T& b) { T temp(a); a = b; b = temp; } iter_swap() 함수는 swap()을 보다 일반화한 것으로 교환할 값을 반복자로 가리킨다. swap_ranges() 알고리듬은 교환의 적용범위를 전체 시퀀스로 확장한 것이다. 첫번째 시퀀스에 속하는 값들을 두번째 시퀀스에 속하는 값들과 교환한다. swap_ranges() 알고리듬의 프로토타입은 다음과 같다. ForwardIterator swap_ranges (ForwardIterator first, ForwardIterator last, ForwardIterator first2); [Image] 병렬 시퀀스 두번째 시퀀스를 나타내는 구간은 시작 반복자로만 명시한다. 두번째 구간은 적어도 첫번째 구간만큼의 원소를 가져야 한다. 예제 프로그램에서 이 두함수를 설명한다. void swap_example() { // 먼저 두개의 시퀀스를 생성 int data[] = {12, 27, 14, 64}, *datap = data; vector aVec(4); generate(aVec.begin(), aVec.end(), iotaGen(1)); // swap()과 iter_swap() swap(data[0], data[2]); vector::iterator last = aVec.end(); last--; iter_swap(aVec.begin(), last); // 시퀀스 전체를 교환 swap_ranges(aVec.begin(), aVec.end(), datap); } 13.3 검색 연산 이번에 살펴볼 알고리듬들은 시퀀스에서 주어진 조건을 만족하는 원소를 찾을 때 사용되는 것들이다. 보통 검색의 결과는 복사(13.4.4절 참고), 분할(13.2.2절 참고), in-place 합병(13.4.6절 참고)과 같은 연산의 인자로 다시 사용된다. 이 절에서 설명할 검색 알고리듬들은 검색 조건을 만족하는 첫번째 원소를 가리키는 반복자를 리턴한다. 이 값은 보통 다음과 같이 반복자 변수에 저장한다. list::iterator where; where = find(aList.begin(), aList.end(), 7); 검색 조건을 만족하는 '모든' 원소를 찾으려면, 루프를 작성해야 한다. 이 루프에서 이전 검색의 결과값에서 하나 전진하고(안그러면, 이전검색의 결과를 다시 얻게 된다), 이번 검색의 결과값은 다음번 검색의 시작점으로 사용된다. 예를 들어, adjacent_find() 예제 프로그램(13.3.2절)에서 따온 다음 루프는 인자로 주어진 string에서 연속적으로 반복되는 문자들을 모두 출력한다. [Image] 검색 결과의 검사 while ((where = adjacent_find(where, stop)) != stop) { cout << "double " << *where << " in position " << where - start << endl; ++where; // 검색결과값을 하나 전진시켜 다음번 검색에 사용 } 많은 검색 알고리듬들이 원소 비교에 사용할 함수를 인자로 가지는데, 만약 이 인자가 생략된다면, 컨테이너에 속한 원소 타입의 상등 연산자(== 연산자)를 사용한다. 앞으로 알고리듬을 설명할 때 생략가능한 인자는 각진 브래킷내([])에 쓰기로 한다. 13.3.1 조건을 만족하는 원소 찾기 find()와 find_if() 두 알고리듬은 조건을 만족하는 첫번째 원소를 찾는데 사용한다. 이 두 알고리듬의 프로토타입은 다음과 같다. InputIterator find_if(InputIterator first, InputIterator last, Predicate); // 조건자를 사용 InputIterator find(InputIterator first, InputIterator last, const T&); // 인자값을 사용 find_if() 알고리듬은 조건자를 인자로 취하는데, 조건자는 불값을 리턴하는 함수라면 모두 가능하다(3.2절). find_if() 알고리듬은 조건을 만족하는 첫번째 원소를 가리키는 반복자를 리턴한다. 조건을 만족하는 원소를 찾지 못하면, 두번째 인자로 넘겨준 past-the-end 반복자를 리턴한다. 결과값이 반복자이기 때문에, 실제값을 얻기 위해서는 반드시 참조 연산자(* 연산자)를 사용해야 한다. 이는 예제 프로그램에서 설명할 것이다. find() 알고리듬은 조건자 대신에 특정값을 인자로 사용하고, 이 인자값과 동일한 시퀀스내의 첫번째 원소를 찾아 리턴하고, 이때 주어진 데이터 타입의 상등 연산자(== 연산자)를 사용하여 비교를 한다. [Image] set과 map의 검색 다음은 이들 알고리듬을 사용한 예제 프로그램이다. void find_test() { int vintageYears[] = {1967, 1972, 1974, 1980, 1995}; int *start = vintageYears; int *stop = start + 5; int *where = find_if(start, stop, isLeapYear); if (where != stop) cout << "first vintage leap year is " << *where << endl; else cout << "no vintage leap years" << endl; where = find(start, stop, 1995); if (where != stop) cout << "1995 is position " << where - start << " in sequence" << endl; else cout << "1995 does not occur in sequence" << endl; } 13.3.2 연속적으로 중복된 원소 찾기 adjacent_find() 알고리듬은 시퀀스내에서 바로 다음에 따라오는 원소와 일치하는 첫번째 원소를 찾는데 사용된다. 예를 들어, 시퀀스가 1 4 2 5 6 6 7 5를 담고 있다면, adjacent_find() 알고리듬은 첫번째 6을 가리키는 반복자를 리턴할 것이다. 조건을 만족하는 원소가 없으면, end-of-sequence 반복자를 리턴한다. 알고리듬의 프로토타입은 다음과 같다. ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last [, BinaryPredicate ] ); 처음 두개의 인자는 검색이 이루어지는 시퀀스를 명시한다. 세번째 인자(생략가능)는 반드시 이항 조건자이어야 한다(불값을 리턴하는 이항 함수). 만약에 세번째 인자가 주어지면, 이항 함수를 사용하여 이웃하는 원소들을 검사하고, 주어지지 않으면, 상등 연산자(== 연산자)를 사용한다. 예제 프로그램은 텍스트 문자열에서 이웃하는 문자를 찾는 것이다. 예제 텍스트에서는 5, 7, 9, 21, 37번 위치에서 중복되는 문자들이 나타난다. 같은 위치가 반복해서 리턴되지 않도록 루프내에 증가 연산이 필요하게 된다. void adjacent_find_example() { char *text = "The bookkeeper carefully opened the door."; char *start = text; char *stop = text + strlen(text); char *where = start; cout << "In the text: " << text << endl; while ((where = adjacent_find(where, stop)) != stop) { cout << "double " << *where << " in position " << where - start << endl; ++where; } } 13.3.3 시퀀스로부터 어떤 값의 첫번째 발생 찾기 find_first_of() 알고리듬은 시퀀스에서 다른 시퀀스에도 속해 있는 첫번째 원소를 찾는데 사용한다. ForwardIterator1 find_first_of (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2 [, BinaryPredicate pred ] ); 이 알고리듬은 [first1, last1)에 포함되어 있는 원소들 중, [first2,last2)에도 포함되어 있는 첫번째 원소를 가리키는 새 반복자를 리턴한다. 원소를 찾지 못하면, 두번째 인자를 리턴한다. 결과값이 반복자이므로, 참조 연산자(* 연산자)를 사용하여 값을 구해야 한다. 이는 예제 프로그램에 설명되어 있다. [Image] Searching Sets and Maps 다음 예제 프로그램은 이 알고리듬을 설명하고 있다. void find_test() { int vintageYears[] = {1967, 1972, 1974, 1980, 1995}; int requestedYears[] = [1923, 1970, 1980, 1974 }; int *start = vintageYears; int *stop = start + 5; int *where = find_first_of (start, stop, requestedyears,requestedyears+4 ); if (where != stop) cout << "first requested vintage year is " << *where << endl; else cout << "no requested vintage years" << endl; } // The output would indicate 1974. 두개의 시퀀스를 다루는 많은 알고리듬과는 달리 이들 알고리듬은 첫번째 시퀀스에 대해서뿐만 아니라, 두 시퀀스 모두에 대해 시작 반복자와 끝 반복자를 사용한다. equal()과 mismatch() 알고리듬과 마찬가지로, find_first_of()의 또 다른 버전은 이항 조건자를 인자로 취하여, 두개의 시퀀스로부터 원소를 비교하는데 사용한다. 13.3.4 시퀀스에서 부시퀀스 찾기 search()와 search_n() 알고리듬은 시퀀스내에서 특정 부시퀀스의 시작위치를 찾는데 사용된다. 이해하기 가장 쉬운 예로 문자열에서 특정 부문자열을 찾는 문제를 들 수 있겠다. 인자들은 적어도 순방향 반복자이어야 한다. ForwardIterator search (ForwardIterator first1, ForwardIterator last1, ForwardIterator first2, ForwardIterator last2 [, BinaryPredicate ]); [Image] Speed of Search 예를 들어 "dreams and aspirations"라는 문자열에서 "ration" 문자열의 위치를 찾는다고 하자. 이 문제에 대한 해결책은 예제 프로그램에 나와 있다. 원하는 문자열을 찾을 수 없으면, 첫번째 시퀀스의 past-the-end 반복자를 리턴한다. void search_example() { char *base = "dreams and aspirations"; char *text = "ration"; char *where = search(base, base + strlen(base), text, text + strlen(text)); if (*where != '\0') cout << "substring position: " << where - base << endl; else cout << "substring does not occur in text" << endl; } 두개의 시퀀스를 다루는 알고리듬과는 달리 이 알고리듬은 첫번째 시퀀스뿐만 아니라 두번째 시퀀스에 대해서도 시작 반복자와 끝 반복자를 모두 사용한다. equal()과 mismatch() 알고리듬과 마찬가지로, search()의 다른 버전은 두개의 시퀀스를 비교할 때 사용할 이항 조건자를 취한다(생략가능). 13.3.5 부시퀀스의 마지막 발생 찾기 find_end() 알고리듬은 시퀀스 내에서 특정 부 시퀀스가 마지막으로 나타나는 시작점을 찾는데 사용한다. 가장 이해하기 쉬운 예로, 문자열에서 특정 부문자열을 찾는 문제를 들 수 있다. 인자는 적어도 순방향 반복자이어야 한다. ForwardIterator find_end (ForwardIterator first1, ForwardIterator last1, ForwardIterator first2, ForwardIterator last2 [, BinaryPredicate ]); [Image] Speed of Find_end 예를 들어, "The road less traveled" 문자열에서 "le" 문자열이 마지막으로 나타나는 위치를 찾는다고 하자. 이 문제의 해결방법은 예제 프로그램에 나타난다. 원하는 문자열을 찾지 못하면, 첫번째 시퀀스의 past-the-end 반복자를 리턴한다. void find_end_example() { char *base = "The road less traveled"; char *text = "le"; char *where = find(base, base + strlen(base), text, text + strlen(text)); if (*where != '\0') cout << "substring position: " << where - base << endl; else cout << "substring does not occur in text" << endl; } 두개의 시퀀스를 다루는 다른 알고리듬과는 다르게, 이 알고리듬은 첫번째 시퀀스뿐만 아니라, 두번째 시퀀스에 대해서도 시작 반복자와 끝 반복자를 모두 사용한다. find_first_of(), search()와 마찬가지로, find_end()의 다른 버전은 두 시퀀스의 원소를 비교할 때 사용하는 이항 조건자를 인자로 취하며, 생략가능하다. 13.3.6 최대 또는 최소 원소 찾기 max()와 min() 함수는 두 값의 최대값과 최소값을 알아내는데 사용한다. 이들 함수는 less-than 연산자(< 연산자) 대신에 사용할 비교 함수로 세번째 인자를 사용한다. template const T& max(const T& a, const T& b [, Compare ] ); template const T& min(const T& a, const T& b [, Compare ] ); max()와 min() 함수를 보다 일반화시킨 max_element()와 min_element() 알고리듬은 시퀀스 전체에 적용이 가능하다. 이들 함수들의 인자는 입력 반복자들이다. ForwardIterator max_element (ForwardIterator first, ForwardIterator last [, Compare ] ); ForwardIterator min_element (ForwardIterator first, ForwardIterator last [, Compare ] ); [Image] Largest and Smallest Elements of a Set 이 알고리듬들은 각각 시퀀스내에서 최대값과 최소값을 가리키는 반복자를 리턴한다. 최대값 또는 최소값이 하나 이상일 경우에는 첫번째 값이 리턴된다. 두 알고리듬 모두 세번째 인자로 디폴트 연산자 대신 사용할 비교 연산자를 취하며, 생략가능하다. 예제 프로그램은 이들 알고리듬을 사용하는 예를 보인 것이다. split() 함수(12.3절 참고)를 사용하여 문자열을 단어들로 쪼개고 있다. randomInteger() 함수는 2.2.5절에 설명되어 있다. void max_min_example() { // make a vector of random numbers between 0 and 99 vector numbers(25); for (int i = 0; i < 25; i++) numbers[i] = randomInteger(100); // print the maximum vector::iterator max = max_element(numbers.begin(), numbers.end()); cout << "largest value was " << * max << endl; // example using strings string text = "It was the best of times, it was the worst of times."; list words; split(text, " .,!:;", words); cout << "The smallest word is " << * min_element(words.begin(), words.end()) << " and the largest word is " << * max_element(words.begin(), words.end()) << endl; } 13.3.7 병렬 시퀀스에서 처음으로 일치하지 않는 원소 찾기 mismatch() 알고리듬은 이름에서 알 수 있듯이, 두개의 시퀀스가 서로 같은지를 판별하는 equal() 알고리듬(13.6.4절)과 반대되는 함수이다. 대신에, mismatch() 알고리듬은 반복자들의 pair를 리턴하는데, 이들 반복자는 각각 두 시퀀스에서 다른 원소가 나타나는 첫번째 위치를 나타낸다(pair 구조에 대해서는 9.1절 참고). 두번째 시퀀스는 끝 반복자 없이 시작 반복자로만 표시하며, 두번째 시퀀스는 적어도 첫번째 시퀀스만큼의 원소를 가지고 있어야 한다(이는 알고리듬내에서 검사하지 않는다). 일치하지 않는 원소를 찾기도 전에 첫번째 시퀀스가 끝이 나면, 결과값으로 리턴되는 pair에는 첫번째 시퀀스의 끝 반복자와 두번째 시퀀스에서 맨 마지막으로 살펴본 원소를 가리키는 반복자가 담기게 된다.(두번째 시퀀스는 모두 조사될 필요가 없다.) mismatch()의 인자와 리턴값은 다음과 같다. pair mismatch (InputIterator first1, InputIterator last1, InputIterator first2 [, BinaryPredicate ] ); 원소들은 병렬적으로 하나씩 검사하며, 두 시퀀스가 달라지는 지점을 발견하면, 두개의 다른 원소의 위치를 가리키는 반복자를 담은 pair를 구성하여 리턴한다. 일치하지 않는 원소를 찾기도 전에 첫번째 시퀀스가 끝이 나면, 결과값으로 리턴되는 pair에는 첫번째 시퀀스의 끝 반복자와 두번째 시퀀스에서 맨 마지막으로 조사된 원소를 가리키는 반복자가 담기게 된다.(두번째 시퀀스는 모두 조사될 필요가 없다.) 예제 프로그램은 이 알고리듬의 사용예를 보여주고 있다. mismatch_test() 예제함수는 두개의 string을 인자로 취한다. 이들은 사전식으로 비교되어 서로의 상대적인 순서를 표시하는 메시지가 출력된다(?). mismatch() 알고리듬은 두번째 시퀀스가 첫번째 시퀀스만큼은 되어야 하므로, 두 string의 길이를 비교한뒤 두번째 문자열이 첫번째보다 짧으면 인자를 바꾼다. mismatch()를 호출한 뒤에는 결과 pair의 각 필드값을 적절한 변수에 할당하여, 이들의 상대적인 순서를 결정하는데 쓰인다. void mismatch_test(char *a, char *b) { pair differPositions(0, 0); char *aDiffPosition; char *bDiffPosition; if (strlen(a) < strlen(b)) { // make sure longer string is second differPositions = mismatch(a, a + strlen(a), b); aDiffPosition = differPositions.first; bDiffPosition = differPositions.second; } else { differPositions = mismatch(b, b + strlen(b), a); // note following reverse ordering aDiffPosition = differPositions.second; bDiffPosition = differPositions.first; } // compare resulting values cout << "string " << a; if (*aDiffPosition == *bDiffPosition) cout << " is equal to "; else if (*aDiffPosition < *bDiffPosition) cout << " is less than "; else cout << " is greater than "; cout << b << endl; } mismatch() 알고리듬의 두번째 형태는, 원소들을 비교할 때 == 연산자 대신에 사용할 이항 함수를 네번째 인자로 취한다. 13.4 In-Place 변환 이번에 설명할 알고리듬들은 원래의 저장 위치로부터 이동하지 않고 시퀀스를 수정하고 변환하는데 사용되는 것들이다. replace()와 같은 몇몇 루틴들은 본래의 in-place 변환 알고리듬뿐만 아니라 복사 버전들을 가지고 있다. 어떤 루틴들은 원래의 시퀀스를 유지할 필요가 있다면, 시퀀스가 복사본을 먼저 생성하고 나서, 변환을 적용해야한다. 예를 들어, 다음은 vector를 뒤집은 것을 새롭게 할당된 vector에 배치하는 방법을 보여주고 있다. vector newVec(aVec.size()); copy(aVec.begin(), aVec.end(), newVec.begin()); // first copy reverse(newVec.begin(), newVec.end()); // then reverse transform()(13.7.1절 참고)이나 partial_sum()(13.7.2절)과 같은 시퀀스 생성 연산 알고리듬들은 입력과 출력을 같은 반복자로 명시하여 직접 시퀀스를 직접 수정하는데 사용한다. 13.4.1 시퀀스내의 원소 뒤집기 reverse() 알고리듬은 시퀀스내의 원소들을 뒤집어, 마지막 원소를 첫번째 원소로 만들고, 첫번째 원소를 마지막 원소로 만든다. 인자들은 양방향 반복자이어야하고, 값은 리턴되지 않는다. void reverse (BidirectionalIterator first, BidirectionalIterator last); 예제 프로그램은 이 알고리듬의 두가지 용도을 설명하고 있다. 처음것은 문자 배열을 뒤집는 것이다. reverse() 알고리듬은 두번째 예에서 보는 바와 같이 list에도 사용할 수 있다. list는 먼저 2에서 11까지의 값으로 초기화 되고(이는 3.3절에서 소개한 iotaGen 함수 객체를 사용하였다.), 이어서 뒤집기를 하여, list는 11부터 2까지의 값을 가지게 된다. 그러나, list 데이터 구조는 reverse() 멤버 함수도 가지고 있음을 기억하기 바란다. void reverse_example() // illustrate the use of the reverse algorithm { // example 1, reversing a string char *text = "Rats live on no evil star"; reverse(text, text + strlen(text)); cout << text << endl; // example 2, reversing a list list iList; generate_n(inserter(iList, iList.begin()), 10, iotaGen(2)); reverse(iList.begin(), iList.end()); } 13.4.2 어떤 값을 특정 값으로 치환하기 replace()와 replace_if() 알고리듬은 특정 원소들을 새로운 값으로 교체하는데 사용한다. 두 알고리듬 모두 아무리 교체가 많이 일어나도, 교체되는 원소들은 결국 같은 값을 가진다. replace() 알고리듬은 특정 값과 같은 값들은 모두 새로운 값으로 교체한다. replace_if()?주어진 조건자를 만족하는 모든 원소들을 새로운 값으로 교체한다. 인자로 주어지는 반복자는 순방향 반복자이어야 한다. replace_copy()와 replace_copy_if()들은 replace(), replace_if()들과 비슷하지만, 전자들은 원래 시퀀스들은 그냥 건드리지 않으며, 갱신된 값들은 새 시퀀스(타입이 달라도 됨)에 배치한다는 점이 다르다. void replace(ForwardIterator first, ForwardIterator last, const T&, const T&); void replace_if(ForwardIterator first, ForwardIterator last, Predicate, const T&); OutputIterator replace_copy(InputIterator, InputIterator, OutputIterator, const T&, const T&); OutputIterator replace_copy(InputIterator, InputIterator, OutputIterator, Predicate, const T&); 예제 프로그램에서, vector는 먼저 0 1 2 3 4 5 4 3 2 1 0 으로 초기화된다. replace()를 호출하여 3을 7로 바꾸어 0 1 2 7 4 5 4 7 2 1 0 이 되게 한다. 이번에는 replace_if()를 호출하여 짝수를 모두 9로 교체하여 9 1 9 7 9 5 9 7 9 1 가 되게 한다. void replace_example() // illustrate the use of the replace algorithm { // make vector 0 1 2 3 4 5 4 3 2 1 0 vector numbers(11); for (int i = 0; i < 11; i++) numbers[i] = i < 5 ? i : 10 - i; // replace 3 by 7 replace(numbers.begin(), numbers.end(), 3, 7); // replace even numbers by 9 replace_if(numbers.begin(), numbers.end(), isEven, 9); // illustrate copy versions of replace int aList[] = {2, 1, 4, 3, 2, 5}; int bList[6], cList[6], j; replace_copy(aList, aList+6, &bList[0], 2, 7); replace_copy_if(bList, bList+6, &cList[0], bind2nd(greater(), 3), 8); } 예제 프로그램은 replace_copy() 알고리듬의 사용법도 설명하고 있다. 먼저 2 1 4 3 2 5 의 값들을 담은 배열을 생성한다. 2를 7로 교체하여 7 1 4 3 7 5 로 만든다. 다음에 3보다 큰 모든 값들을 8로 교체하여 8 1 8 3 8 8 로 수정한다. 후자의 경우에는 bind2nd() 어댑터를 사용하여 이항 함수인 greater-than 함수의 두번째 인자를 3으로 고정시켜 x > 3를 의미하는 단항 함수로 만들었다. 13.4.3 중간지점을 중심으로 원소들 돌리기 시퀀스를 순환한다는 것은 시퀀스를 두분으로 나누고, 이두부분의 위치를 바꾸어 두부분내의 원소들의 상대적인 순서는 유지되도록 하는 것이다. 예를 들어, 다음 1부터 10까지의 시퀀스를 생각해보자. 1 2 3 4 5 6 7 8 9 10 원소 7 주위로 순환을 하려면, 7부터 10까지의 값들을 앞쪽으로 옮기고, 1부터 10까지의 값들을 뒤쪽으로 옮기면 된다. 결과는 다음과 같다. 7 8 9 10 1 2 3 4 5 6 rotate() 알고리듬을 호출할 때는 시작점, 중간점, past-the-end 위치를 순방향 반복자로 명시한다. void rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last); 앞부분은 시작점부터 중간점 바로 앞까지이며, 뒷부분은 중간점부터 past-the-end까지이다. 바로 앞에 예에서 알 수 있듯이, 앞부분과 뒷부분의 길이가 같을 필요는 없다. void rotate_example() // illustrate the use of the rotate algorithm { // create the list 1 2 3 ... 10 list iList; generate_n(inserter(iList, iList.begin()), 10, iotaGen(1)); // find the location of the seven list::iterator & middle = find(iList.begin(), iList.end(), 7); // now rotate around that location rotate(iList.begin(), middle, iList.end()); // rotate again around the same location list cList; rotate_copy(iList.begin(), middle, iList.end(), inserter(cList, cList.begin())); } 예제 프로그램은 먼저 1부터 10까지의 정수를 담은 list를 생성하고, find() 알고리듬(13.3.1절)을 사용하여 원소 7의 위치를 찾는다. 이결과를 순환의 중간점으로 사용한다. rotate()의 두번째 형태는 원래 시퀀스내에서 돌리지 않고, 원소들을 새로운 시퀀스에 복사하는 것이다. 이는 위 예제프로그램에서 다루고 있는데, 중간점(이번에는 3을 가리키고 있다.)을 중심으로 다시한번 순환시키고 있다. 결과는 3 4 5 6 7 8 9 10 1 2가 된다. iList에 담긴 값들은 전혀 변하지 않는다. 13.4.4 시퀀스 둘로 쪼개기 분할(partition)은 주어진 조건을 만족하는 모든 원소들을 시퀀스의 한쪽끝으로 옮기는 것이다. 원소를 분할하는 것은 qucksort와 같은 정렬 알고리듬에서는 기본적인 단계이다. BidirectionalIterator partition (BidirectionalIterator, BidirectionalIterator, Predicate); BidirectionalIterator stable_partition (BidirectionalIterator, BidirectionalIterator, Predicate); 표준라이브러리가 지원하는 분할의 형태에는 두가지가 있다. 첫번째는 partition()이 제공하는 것으로 원소들을 두부분으로 나누는 것에만 책임을 진다. 결과값으로 두 그룹사이의 마지막(?) 중간점을 나타내는 반복자를 리턴한다. 이 중간점은 첫번째 그룹의 끝을 하나 지난 곳이다. [Image] Partitions 예제 프로그램에서 vector는 처음에 1부터 10까지의 값을 순서대로 담고 있다. 분할을 수행하여, 짝수 원소들을 앞쪽으로, 홀수 원소들을 뒤쪽으로 옮기게 된다. vector는 10 2 8 4 6 5 7 3 9 1 을 가지게 되고, 결과값으로 중간점(원소 5)을 가리키는 반복자를 반환한다. void partition_example() // illustrate the use of the partition algorithm { // first make the vector 1 2 3 ... 10 vector numbers(10); generate(numbers.begin(), numbers.end(), iotaGen(1)); // now put the even values low, odd high vector::iterator result = partition(numbers.begin(), numbers.end(), isEven); cout << "middle location " << result - numbers.begin() << endl; // now do a stable partition generate (numbers.begin(), numbers.end(), iotaGen(1)); stable_partition (numbers.begin(), numbers.end(), isEven); } 분할로 나누어진 각 영역에 속하는 원소들의 상대적인 순서가 분할 이전의 순서와 다를 수도 있다. 예를 들어, 분할 이전에 4가 8앞에 있었지만, 분할 이후에는 8이 앞으로 올 수 있다는 것이다. 분할의 두번째 형태는 stable_partition()에 의해 제공되는데 이 알고리듬은 분할 이후에도 분할 이전의 순서들을 그대로 유지한다. 예를 들어, 위 예에서는 2 4 6 8 10 1 3 5 7 9 가 된다. stable_partition()은 partition() 알고리듬보다 조금 느리며, 더 많응 메모리를 필요로 한다. 따라서, 원소들의 순서가 별 상관이 없다면, partition()을 사용해야 한다. 13.4.5 시퀀스내에 순열 생성하기 [Image] Ordering Permutations 순열(permutation)은 값들의 재배치이다. 서로 비교가 가능한 값들이라면(정수, 문자, 단어 등등), 시퀀스의 순열을 모두 만들수 있다. 예를 들어, 값이 2개면 2개의 순열을, 3개면 6개를, 4개면 24개의 순열을 만들 수 있게 된다. 순열을 만들어내는 알고리듬은 다음 프로토타입을 가진다. bool next_permutation (BidirectionalIterator first, BidirectionalIterator last, [ Compare ] ); bool prev_permutation (BidirectionalIterator first, BidirectionalIterator last, [ Compare ] ); 예제 프로그램에서의 두번째 예는 정수 대신에 문자 배열의 포인터를 사용한 것만 다를뿐, 설명하고자 하는 내용은 같다. 단 이 경우에는 비교함수로 다른 것을 사용해야 한다. 디폴트 비교 연산자는 포인터 주소 자체를 비교하기 때문이다. bool nameCompare (char * a, char * b) { return strcmp(a, b) <= 0; } void permutation_example () // illustrate the use of the next_permutation algorithm { // example 1, permute the values 1 2 3 int start [] = { 1, 2, 3}; do copy (start, start + 3, ostream_iterator (cout, " ")), cout << endl; while (next_permutation(start, start + 3)); // example 2, permute words char * words = {"Alpha", "Beta", "Gamma"}; do copy (words, words + 3, ostream_iterator (cout, " ")), cout << endl; while (next_permutation(words, words + 3, nameCompare)); // example 3, permute characters backwards char * word = "bela"; do cout << word << ' '; while (prev_permutation (word, &word[4])); cout << endl; } 에제 프로그램의 3번 예는 역 순열 알고리듬을 설명하고 있는데, 이는 순열을 거꾸로 생성한다. 이 예제에서는 순열의 중간에서 시작하는데, "bela"의 나머지 순열들은 beal, bale, bael, aleb, albe, aelb, aebl, able, abel이다. 13.4.6 두개의 이웃하는 시퀀스를 하나로 합치기 병합(merge)은 두개의 ordered 시퀀스를 하나의 ordered 시퀀스로 합치고, 필요하다면 원소들을 끼워넣어 새로운 list를 만들어 낸다. inplace_merge() 알고리듬은 시퀀스가 이웃하는 두부분으로 나눠져있어야 하고, 각각은 정렬되어 있어야 한다. 병합을 통해 두부분을 하나로 합치고, 필요하다면 원소들을 이동시킨다.(merge() 알고리듬은 별도의 두 시퀀스를 하나로 합칠때 사용한다) inplace_merge()에 대한 인자들은 양방향 반복자이어야 한다. void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last [, BinaryFunction ] ); 예제 프로그램은 vector, list에 대해 inplace_merge() 알고리듬을 사용하는 예를 보이고 있다. vector는 0 2 4 6 8 1 3 5 7 9의 시퀀스를 가지고 있다. find()(13.3.1절)을 호출하여 홀수가 시작하는 위치를 찾는다. inplace_merge()를 사용하여 두개의 시퀀스를 하나로 합친다. void inplace_merge_example() // illustrate the use of the inplace_merge algorithm { // first generate the sequence 0 2 4 6 8 1 3 5 7 9 vector numbers(10); for (int i = 0; i < 10; i++) numbers[i] = i < 5 ? 2 * i : 2 * (i - 5) + 1; // then find the middle location vector::iterator midvec = find(numbers.begin(), numbers.end(), 1); // copy them into a list list numList; copy(numbers.begin(), numbers.end(), inserter (numList, numList.begin())); list::iterator midList = find(numList.begin(), numList.end, 1); // now merge the lists into one inplace_merge(numbers.begin(), midvec, numbers.end()); inplace_merge(numList.begin(), midList, numList.end()); } 13.4.7 시퀀스내의 원소들을 임의로 재배치하기 random_shuffle() 알고리듬은 시퀀스내의 원소들을 임의로 재배치한다. 정확히 n번의 교체가 수행되며, 여기서 n번은 시퀀스가 담고 있는 원소의 갯수를 나타낸다. 물론, 결과는 예측할 수 없다. 인자들은 임의 접근 반복자들이어야 하므로, 이 알고리듬은 vector, deque 또는 일반 포인터들하고만 사용이 가능하다. list, set, map과는 함께 사용할 수 없다. void random_shuffle (RandomAccessIterator first, RandomAccessIterator last [, Generator ] ); 이 알고리듬의 다른 버전은 세번째 인자를 추가로 제공하며, 생략이 가능하다. 이 값은 반드시 난수 발생기이어야 한다. 이 발생기는 인자로 양수 m을 취하고, 0과 m-1 사이의 값을 반환한다. generate() 알고리듬에서처럼, 이 난수 함수는 함수 호출 연산자를 가지는 임의의 객체이면 된다. void random_shuffle_example () // illustrate the use of the random_shuffle algorithm { // first make the vector containing 1 2 3 ... 10 vector numbers; generate(numbers.begin(), numbers.end(), iotaGen(1)); // then randomly shuffle the elements random_shuffle (numbers.begin(), numbers.end()); // do it again, with explicit random number generator struct RandomInteger { { operator()(int m) { return rand() % m; } } random; random_shuffle (numbers.begin(), numbers.end(), random); } 13.5 삭제 알고리듬 [Image] What is a Name? 다음 두 알고리듬은 처음 보게 되면 다소 혼란스러울 것이다. 둘다 시퀀스에서 특정 값들을 제거해야 한다. 하지만, 실제로 이들 알고리듬은 시퀀스의 사이즈를 감소시키지 않는다. 이 두 알고리듬은 삭제대상이 아닌 값들을 시퀀스의 앞쪽으로 몰고, 이 값들의 끝을 가리키는 반복자를 리턴한다. 이 반복자의 뒷부분에 있는 값들은 원래 시퀀스에 있던 값들이고 아무런 변경도 가해지지 않은 것들이다. generic 알고리듬은 자신이 어떤 컨테이너에 대해 작업을 하는지를 알지 못하기 때문에 이러한 일들이 필요하다. 알고리듬은 오직 generic 반복자만을 가지고 있을 뿐이다. 이는 generic 알고리듬을 사용할 때 감수해야 할 부분이다. 대부분의 경우 사용자는 리턴값으로 얻은 반복자를 해당 컨테이너의 erase() 멤버함수의 인자로 사용하여 반복자가 가리키는 값부터 시퀀스의 끝까지 모두 삭제한다. 간단한 예를 통해 설명해 보자. 1 2 3 4 5 6 7 8 9 10와 같이 시퀀스에서 짝수들을 삭제한다고 하자. remove_if() 알고리듬을 수행하고 나면 시퀀스는 다음과 같이 된다. 1 3 5 7 9 | 6 7 8 9 10 중간에 표시된 막대기는 remove_if() 알고리듬이 리턴하는 반복자의 위치이다. 막대기 앞쪽에 있는 5개의 원소는 우리가 원하는 결과이고, 막대기 뒤쪽에 있는 5개의 원소는 그냥 원래 시퀀스에서 동일한 위치에 있던 값들이다. 이 반복자와 end-of-sequence 반복자를 erase()의 인자로 넘겨주어서, 필요없는 값들을 삭제하고 원하는 결과를 얻을 수 있게 된다. 지금 설명한 알고리듬들은 둘다 복사 버전을 따로 가지고 있다. 이들 알고리듬의 복사버전은 원래 시퀀스는 그대로 놔두고, 삭제하고 남게 되는 값들을 다른 시퀀스로 출력한다. 13.5.1 필요없는 원소 삭제하기 remove() 알고리듬은 시퀀스로부터 필요없는 값들을 삭제한다. find() 알고리듬과 같이 이 알고리듬도 특정 값을 명시하거나, 조건을 명시할 수 있다. 프로토타입은 다음과 같다. ForwardIterator remove (ForwardIterator first, ForwardIterator last, const T &); ForwardIterator remove_if (ForwardIterator first, ForwardIterator last, Predicate); remove() 알고리듬은 삭제대상에서 제외되는 값들을 시퀀스의 앞쪽으로 이동시키며, 이때 이미 앞쪽에 있던 원소들을 덮어쓰게 된다. 삭제되지 않는 원소들은 상대적인 순서를 그대로 유지한다. 일단 모든 원소들을 한번 훑고 나면, 시퀀스의 나머지 부분은 전혀 변경되지 않는다. 알고리듬의 결과로 리턴되는 반복자는 새 시퀀스의 끝을 가리킨다. 예를 들어, 시퀀스 1 2 4 3 2 로부터 원소 2를 삭제하면, 시퀀스 1 4 3 3 2 가 되고, 결과로 리턴되는 반복자는 두번째 3을 가리키게 된다. 이 반복자를 erase() 멤버 함수의 인자로 사용하여 나머지 값(3과 2)들을 삭제하게 된다. 알고리듬의 복사 버전은 값들을 출력 시퀀스로 복사하며, 원래 시퀀스는 전혀 손을 대지 않는다. OutputIterator remove_copy (InputIterator first, InputIterator last, OutputIterator result, const T &); OutputIterator remove_copy_if (InputIterator first, InputIterator last, OutputIterator result, Predicate); remove()의 사용은 다음 프로그램에서 볼 수 있다. void remove_example () // illustrate the use of the remove algorithm { // create a list of numbers int data[] = {1, 2, 4, 3, 1, 4, 2}; list aList; copy (data, data+7, inserter(aList, aList.begin())); // remove 2's, copy into new list list newList; remove_copy (aList.begin(), aList.end(), back_inserter(newList), 2); // remove 2's in place list::iterator where; where = remove (aList.begin(), aList.end(), 2); aList.erase(where, aList.end()); // remove all even values where = remove_if (aList.begin(), aList.end(), isEven); aList.erase(where, aList.end()); } 13.5.2 비슷한 값들의 런(run) 삭제하기 unique() 알고리듬은 선형 시퀀스를 훑어가면서, 연속적으로 같은 원소들이 나타나는 그룹을 발견하면 첫번째 원소만 남겨두고 나머지 원소들을 모두 삭제한다. 시퀀스는 순방향 반복자를 사용하여 인자로 넘겨준다. ForwardIterator unique (ForwardIterator first, ForwardIterator last [, BinaryPredicate ] ); 알고리듬은 콜렉션을 훑어가면서, 연산 결과를 시퀀스의 앞쪽으로 옮기고, 이미 앞쪽에 있던 원소들은 덮어쓰게 된다. 일단 작업이 끝나게 되면, 시퀀스의 나머지 원소들은 건드리지 않고 그냥 내버려 두게 된다. 예를 들어, 1 3 3 2 2 2 4와 같이 구성된 시퀀스는 1 3 2 4 | 2 2 4 로 바뀌게 된다. 막대기는 결과값으로 리턴되는 반복자의 위치를 나타내며, 중복이 제거된 시퀀스의 끝이자 오른쪽에 남겨진 원소들의 시작을 가리킨다. 대부분의 컨테이너에서처럼 알고리듬이 리턴하는 값은 뒤따라 오는 연산의 인자로 사용되는데, erase() 멤버 함수의 인자로 사용하여 필요없는 원소들을 삭제하게 된다. 이는 예제 프로그램에서 잘 나타나 있다. 알고리듬의 복사 버전은 중복이 제거된 원소들을 출력 반복자로 옮기고, 원래 시퀀스는 전혀 건드리지 않는다. list나 multiset을 변환할 때는 삽입 연산자를 사용하여, 출력 반복자의 복사 연산을 삽입 연산으로 바꿀 수 있다. OutputIterator unique_copy (InputIterator first, InputIterator last, OutputIterator result [, BinaryPredicate ] ); 이들은 다음 예제 프로그램에서 살펴 볼 수 있다. void unique_example() // illustrate use of the unique algorithm { // first make a list of values int data[] = {1, 3, 3, 2, 2, 4}; list aList; set aSet; copy (data, data+6, inserter(aList, aList.begin())); // copy unique elements into a set unique_copy (aList.begin(), aList.end(), inserter(aSet, aSet.begin())); // copy unique elements in place list::iterator where; where = unique(aList.begin(), aList.end()); // remove trailing values aList.erase(where, aList.end()); } 13.6 Scalar-Producing Algorithms 이번에 설명할 알고리듬은 전체 시퀀스로부터 하나의 스칼라 값을 얻어내는 알고리듬들이다. 여기서 accumulate()와 inner_product() 알고리듬은 다른 알고리듬처럼 algorithm 헤더 화일에 포함되어 있지 않고, numeric 헤더 화일에 포함되어 있다는 것을 기억하기 바란다. 13.6.1 조건을 만족하는 원소의 갯수 세기 count()와 count_if() 알고리듬은 각각 주어진 값 또는 주어진 조건을 만족하는 원소의 갯수를 알아내는데 사용한다. 각각의 알고리듬은 두가지 형태가 있는데, 하나는 일치되는 원소를 리턴값으로 반환하고, 다른 하나는 카운트 변수(대부분 정수)에 대한 레퍼런스를 인자로 받아서, 이 변수의 값을 증가시킨다(이 경우에는 값을 리턴하지 않는다). (후자의 경우 최근 표준에 남아 있는지를 확인할 것!) 전자의 경우는 최근 표준에서 채택되었고, 후자는 예전에 사용되던 것으로 두가지 이유때문에 아직도 남아있게 되었다. 첫째 이유는 backward compatibility 때문이고, 두번째 이유는 전자에 해당하는 알고리듬이 partial specialization을 필요로 하는데, 아직은 이를 지원하는 컴파일러가 거의 없기 때문이다. iterator_traits::distance_type count (InputIterator first, InputIterator last, const T& value); iterator_traits::distance_type count_if (InputIterator first, InputIterator last, Predicate pred); void count (InputIterator first, InputIterator last, const T&, Size &); void count_if (InputIterator first, InputIterator last, Predicate, Size &); (후자의 경우 표준에서 채택되었는지 확인할 것!) [Image] The Resulting Count 다음 예제 프로그램은 예전의 count() 알고리듬을 사용한 예이다. count()를 호출하여 주어진 문자열에서 'e'의 갯수를 알아내고, count_if()를 호출하여 모음의 갯수를 알아내고 있다. void count_example() // illustrate the use of the count algorithm { int eCount = 0; int vowelCount = 0; char *text = "Now is the time to begin"; count(text, text + strlen(text), 'e', eCount); count_if(text, text + strlen(text), isVowel, vowelCount); cout << "There are " << eCount << " letter e's " << endl << "and " << vowelCount << " vowels in the text:" << text << endl; } 13.6.2 시퀀스를 하나의 값으로 유추하기 accumulate() 알고리듬이 생성하는 결과값은 시퀀스의 각 원소 사이에 이항 연산자를 놓아 얻어낸 값이다. 디폴트 연산자는 덧셈 연산자(+)이고, 이것은 다른 이항 함수로 바꿀 수 있다. 초기값(항등원)은 반드시 제공해야 한다. 이 값은 빈 시퀀스에 알고리듬을 적용했을 때의 리턴되는 값에 해당하며, 첫번째 계산할 때의 왼쪽 인자로 사용된다. ContainerType accumulate (InputIterator first, InputIterator last, ContainerType initial [, BinaryFunction ] ); 예제 프로그램은 accumulate()를 사용하여 정수 vector에 담긴 값들의 합과 곱을 생성한다. 합의 경우에는 초기값(항등원)으로 0을, 디폴트 연산자 +를 사용하면 되고, 곱의 경우에는 초기값(항등원)으로 1을, 곱셉 연산자(times)를 4번째 인자로 별도로 명시하면 된다. void accumulate_example () // illustrate the use of the accumulate algorithm { int numbers[] = {1, 2, 3, 4, 5}; // first example, simple accumulation int sum = accumulate (numbers, numbers + 5, 0); int product = accumulate (numbers, numbers + 5, 1, times()); cout << "The sum of the first five integers is " << sum << endl; cout << "The product is " << product << endl; // second example, with different types for initial value list nums; nums = accumulate (numbers, numbers+5, nums, intReplicate); } list& intReplicate (list& nums, int n) // add sequence n to 1 to end of list { while (n) nums.push_back(n--); return nums; } 초기값(항등원)이나 이항 함수의 리턴값이 반드시 컨테이너 타입과 일치할 필요는 없다. 이는 위의 2번 예에서 볼 수 있다. 여기서 초기값은 공 list이다. 이항 함수(위 예제의 끝에 정의되어 있음)는 list와 정수값을 인자로 취하고, list에 반복적으로 값들을 삽입한다. 삽입되는 값들은 인자로 주어진 정수값부터 1까지의 값을 포함하는 시퀀스이다. 예를 들어, 1 2 3 4 5를 입력으로 받으면, 1 2 1 3 2 1 4 3 2 1 5 4 3 2 1 가 결과 list가 된다. 13.6.3 일반화된 내적 n개의 원소를 가지는 두개의 시퀀스가 있다고 하고, 각각 a1, a2, ..., an과 b1, b2, ..., bn이라고 하자. 두 시퀀스의 내적은 대응되는 원소끼리 곱해서 이를 더한 것으로 a1*b1 + a2*b2 + ... + an * bn 으로 계산된다. 내적은 많은 과학 계산에서 나타난다. 예를 들어, 행과 열의 내적은 행렬곱 알고리듬의 핵심 연산이다. 일반화된 내적은 기본적으로 같은 계산과정을 사용하지만, 합과 곱 연산자를 다른 이항 함수로 바꿀 수 있다. 표준 라이브러리는 내적을 계산하기 위해 다음 알고리듬을 제공한다. ContainerType inner_product (InputIterator first1, InputIterator last1, InputIterator first2, ContainerType initialValue [ , BinaryFunction add, BinaryFunction times ] ); inner_product() 알고리듬의 처음 3개의 인자는 두개의 입력 시퀀스를 정의한다. 두번째 시퀀스는 시작 반복자만 명시하고, 적어도 첫번째 시퀀스만큼의 원소를 가지고 있어야 한다. 그 다음 인자는 합 연산자의 초기값(항등원)이다. 이것은 accumulate() 알고리듬에서 사용하는 항등원과 유사하다. 일반화된 내적 함수에서는 마지막 두개의 인자는 각각 덧셉 연산자와 곱셉 연산자 대신에 사용할 이항 함수가 된다. 예제 프로그램에서의 두번째 예는 인자로 함수를 사용하는 예를 보이고 있다. 곱셈 연산을 상등 검사로 바꾸고, 덧셈은 논리합(or)로 바꾸었다. 따라서, 같은 쌍이 하나라도 있으면 참이고, 그렇지 않으면 거짓을 리턴하게 된다. or 대신에 and를 사용하면 모든 쌍이 같을 때만 참을 리턴하게 되어, 다음에 설명할 equal() 알고리듬과 똑같은 효과를 가지게 된다. void inner_product_example () // illustrate the use of the inner_product algorithm { int a[] = {4, 3, -2}; int b[] = {7, 3, 2}; // example 1, a simple inner product int in1 = inner_product(a, a+3, b, 0); cout << "Inner product is " << in1 << endl; // example 2, user defined operations bool anyequal = inner_product(a, a+3, b, true, logical_or(), equal_to()); cout << "any equal? " << anyequal << endl; } 13.6.4 쌍별로 두개의 시퀀스를 비교하기 equal() 알고리듬은 각 쌍별로 두 시퀀스의 상등여부를 판별하는데 사용한다. 이항 조건자를 바꿈으로써, 두 시퀀스의 상등 여부를 다양하게 판별할 수 있다. 인자는 단순히 입력 반복자이면 된다. bool equal(InputIterator first, InputIterator last, InputIterator first2 [, BinaryPredicate] ); [Image] Equal and Mismatch equal()은 알고리듬은 두번째 시퀀스가 첫번째 시퀀스만큼의 원소를 가지고 있다고 가정한다. 각각 대응되는 값들끼리 상등 검사를 하여 모두 같을 때 참을 리턴한다. 이 알고리듬은 상등 테스트 대신에 다른 이항 함수를 사용하여 모든 쌍이 이항 함수를 통해 주어진 조건을 만족하면 참을 리턴한다. 예제 프로그램에서는 greater_equal() 함수를 사용하고 있으며, 첫번째 시퀀스의 값들이 두번째 시퀀스내에 대응되는 값보다 항상 크거나 같을 때만 참을 리턴하게 된다. void equal_example () // illustrate the use of the equal algorithm { int a[] = {4, 5, 3}; int b[] = {4, 3, 3}; int c[] = {4, 5, 3}; cout << "a = b is: " << equal(a, a+3, b) << endl; cout << "a = c is: " << equal(a, a+3, c) << endl; cout << "a pair-wise greater-equal b is: " << equal(a, a+3, b, greater_equal()) << endl; } 13.6.5 사전식 비교(lexical comparison) 두 시퀀스의 사전식 비교의 아주 흔한 예로 두개의 단어를 비교하여 사전상에 나타난 순으로 배치하는 것을 들 수 있다. 두개의 단어를 비교할 때는 각 시퀀스의 원소(즉, 문자)들을 상대 시퀀스에 대응되는 문자와 비교한다. 두문자가 일치하면, 알고리듬은 다음 문자를 살피게 되고, 일치하지 않으면, 더 앞에 있는 문자를 포함하는 단어가 사전상으로 앞에 위치하게 된다. 예를 들어, everybody는 everything 보다 작게 되는데, 이는 everybody의 b가 everything의 t보다 작기 때문이다. 둘중의 한 시퀀스가 다른 시퀀스보다 먼저 끝나게 되면 끝나는 시퀀스가 다른 시퀀스보다 작은것으로 결정한다. 예를 들어, every는 everybody와 everything 보다 앞에 있게 되고, eve 뒤에 오게 된다. 마지막으로, 두 시퀀스가 동시에 끝나고 모든 문자들이 서로 같으면, 두 단어를 같은 것으로 결정한다. lexicographical_compare() 알고리듬은 이것을 구현한 것으로, 첫번째 시퀀스가 두번째 시퀀스보다 순서상으로 앞에 있으면 참, 그렇지 않으면 거짓을 리턴한다. 이 알고리듬은 어떤 시퀀스에라도 적용할 수 있으며, array, string, vector, list 또는 표준 라이브러리가에서 사용되는 다른 데이터 구조에도 사용할 수 있다. bool lexicographical_compare (InputIterator first1, InputIterator last1, InputIterator first2, InputIterator last2 [, BinaryFunction ] ); lexicographical_compare() 알고리듬은 두개의 시퀀스를 인자로 취하는 대부분의 다른 알고리듬과는 달리 두 시퀀스에 대해서 시작 반복자와 past-the-end 반복자를 모두 사용한다. 생략 가능한 5번째 인자로는 두 시퀀스의 원소를 서로 비교할 때 사용하는 이항 함수를 취한다. 예제 프로그램은 이 알고리듬을 문자열과 정수 배열에 적용한 예를 보이고 있다. void lexicographical_compare_example() // illustrate the use of the lexicographical_compare algorithm { char *wordOne = "everything"; char *wordTwo = "everybody"; cout << "compare everybody to everything " << lexicographical_compare(wordTwo, wordTwo + strlen(wordTwo), wordOne, wordOne + strlen(wordOne)) << endl; int a[] = {3, 4, 5, 2}; int b[] = {3, 4, 5}; int c[] = {3, 5}; cout << "compare a to b:" << lexicographical_compare(a, a+4, b, b+3) << endl; cout << "compare a to c:" << lexicographical_compare(a, a+4, c, c+2) << endl; } 13.7 시퀀스 생성 알고리듬 이 절에서 설명할 알고리듬은 모두 변환을 수행하여 주어진 시퀀스로부터 새로운 시퀀스를 생성하는데 사용되는 것들이다. 대부분의 경우 출력 시퀀스는 출력 반복자를 통해 가리키는데, 이는 이들 알고리듬을 사용하여 주어진 시퀀스(예, vector)를 덮어 쓸 수도 있다는 것을 의미한다. 또는, 삽입 연산자(2.4절)를 사용하여, set이나 list와 같은 가변 길이 구조에 새 원소들을 삽입하는 것도 가능하다. 마지막으로, 종종 어떤 경우에는 출력 반복자가 입력 반복자로 지정된 시퀀스와 같을 수가 있는데 이렇게 되면, in-place 변환을 하게 된다. 다른 함수들이 대부분 algorithm 헤더화일에 선언되어 있는 것과는 달리, partial_sum()과 adjacent_difference() 함수는 numeric 헤더 화일에 선언되어 있다. 13.7.1 한개 또는 두개의 시퀀스 변환하기 transform() 알고리듬은 하나의 시퀀스를 변환시키는데 사용할 수도 있고, 두개의 시퀀스에 원소들의 쌍별로 이항 함수를 적용하여 새로운 시퀀스를 만들어 내기도 한다. 프로토타입은 다음과 같다. OutputIterator transform (InputIterator first, InputIterator last, OutputIterator result, UnaryFunction); OutputIterator transform (InputIterator first1, InputIterator last1, InputIterator first2, OutputIterator result, BinaryFunction); 첫번째 형태는 시퀀스 각각의 원소에 단항 함수를 적용하는 것이다. 아래 주어진 예제 프로그램에서는 이를 사용하여 연결 list에 담긴 값들과 부호가 반대인 값들로 이루어진 vector를 만들어낸다. 입력 반복자와 출력 반복자를 같게 하면, 변환은 in-place로 적용되며, 예제 프로그램의 2번째 transform()이 이런식으로 사용되고 있다. 두번째 형태는 두개의 시퀀스를 인자로 받아서, 쌍별로 이항 함수를 적용한다. 이때 두번째 시퀀스는 적어도 첫번째 시퀀스만큼의 원소를 가지고 있어야 한다. 출력 반복자로 명시되는 결과 시퀀스는 두개의 입력 시퀀스중의 하나거나 또는, 제삼의 다른 시퀀스도 가능하다. int square(int n) { return n * n; } void transform_example () // illustrate the use of the transform algorithm { // generate a list of value 1 to 6 list aList; generate_n (inserter(aList, aList.begin()), 6, iotaGen(1)); // transform elements by squaring, copy into vector vector aVec(6); transform (aList.begin(), aList.end(), aVec.begin(), square); // transform vector again, in place, yielding 4th powers transform (aVec.begin(), aVec.end(), aVec.begin(), square); // transform in parallel, yielding cubes vector cubes(6); transform (aVec.begin(), aVec.end(), aList.begin(), cubes.begin(), divides()); } 13.7.2 부분합(partial sum) 시퀀스의 부분합이란 바로 앞에 있는 원소들의 값을 모두 더하여 새로운 원소를 만들고, 이들 원소들로 구성된 새로운 시퀀스를 만들어내는 것이다. 예를 들어, vector 1 3 2 4 5 의 부분합은 새 vector 1 4 6 10 15가 된다. 원소 4는 1 + 3으로 계산되었으며, 원소 6은 1 + 3 + 2로 게산된 것이다. 알고리듬 이름에 'sum'이란 단어가 사용되었지만, 실제로 이항 함수는 덧셈연산뿐만 아니라 임의의 이항함수가 모두 가능하다. 예제 프로그램에서는 부분곱으로 이를 설명하고 있다. 프로토타입은 다음과 같다. OutputIterator partial_sum (InputIterator first, InputIterator last, OutputIterator result [, BinaryFunction] ); 입력 반복자와 출력 반복자를 같게 함으로써 부분합 연산을 in-place 변환 연산으로 바꿀 수 있다. void partial_sum_example () // illustrate the use of the partial sum algorithm { // generate values 1 to 5 vector aVec(5); generate (aVec.begin(), aVec.end(), iotaGen(1)); // output partial sums partial_sum (aVec.begin(), aVec.end(), ostream_iterator (cout, " ")), cout << endl; // output partial products partial_sum (aVec.begin(), aVec.end(), ostream_iterator (cout, " "), times()); } 13.7.3 인접차(adjacent difference) 시퀀스의 인접차(adjacent difference)는 시퀀스의 현재 원소와 바로 앞 원소와의 차를 새로운 시퀀스의 원소로 만드는 것이다. 새로운 시퀀스의 첫번째 원소는 바뀌지 않는다. 예를 들어, (1, 3, 2, 4, 5)와 같은 시퀀스는 (1, 3-1, 2-3, 4-2, 5-4)로 변환되고, 이런식으로 하여 (1, 2, -1, 2, 1)와 같은 시퀀스를 얻게 된다. partial_sum() 알고리듬에서와 마찬가지로, 임의의 이항 함수가 사용될 수 있으므로, 'difference'라는 단어가 그리 정확한 것은 아니다. 예를 들어, 이 시퀀스의 인접합(adjacent sum)은 (1, 3+1, 2+3, 4+2, 5+4)가 된다. 인접차 알고리듬의 프로토타입은 다음과 같다. OutputIterator adjacent_difference (InputIterator first, InputIterator last, OutputIterator result [, BinaryFunction ]); 입력 반복자와 출력 반복자를 같게 하여, 공차 연산을 in-place 변환으로 바꿀 수 있다. void adjacent_difference_example() // illustrate the use of the adjacent difference algorithm { // generate values 1 to 5 vector aVec(5); generate (aVec.begin(), aVec.end(), iotaGen(1)); // output adjacent differences adjacent_difference (aVec.begin(), aVec.end(), ostream_iterator (cout, " ")), cout << endl; // output adjacent sums adjacent_difference (aVec.begin(), aVec.end(), ostream_iterator (cout, " "), plus() ); } 13.8 기타 알고리듬 마지막으로 이절에서는 나머지 알고리듬을 설명한다. 13.8.1 콜렉션 내의 모든 원소에 함수 적용하기 for_each() 알고리듬은 3개의 인자를 취한다. 처음 2개는 계산에 쓰일 시퀀스를 나타내는 반복자이고, 3번째 인자는 한개의 인자를 가지는 함수이다. for_each() 알고리듬은 시퀀스내의 값에 함수를 적용하는데, 이때 시퀀스내의 담긴 각각의 값을 적용할 함수의 인자로 넘겨주게 된다. 프로토타입은 다음과 같다. Function for_each (InputIterator first, InputIterator last, Function); 예를 들어, 다음 코드는 print_if_leap() 함수를 사용하여 1900년과 1997년 사이에 나타나는 윤년을 출력한다. cout << "leap years between 1990 and 1997 are: "; for_each (1990, 1997, print_if_leap); cout << endl; [Image] Results Produced by Side Effect 인자로 주어지는 함수는 시퀀스내의 각 원소에 대해 단 한번씩만 호출되어야 한다. for_each() 알고리듬은 3번째 인자를 결과로 리턴하지만, 보통 잘 쓰이지 않는다. 다음 예는 포도주의 양조 년도를 나타내는 정수값의 배열을 훑어가면서, 윤년에 해당하는 것을 출력하는 코드이다. int vintageYears[] = {1947, 1955, 1960, 1967, 1994}; ... cout << "vintage years which were also leap years are: "; for_each(vintageYears, vintageYears + 5, print_if_leap); cout << endl; side effect가 반드시 출력일 필요는 없다. 대문자의 갯수를 세는 countCaps() 함수를 가지고 있다고 하자. int capCount = 0; void countCaps(char c) { if (isupper(c)) capCount++; } 다음 예제는 문자열에 포함된 대문자의 갯수를 세고 있다. string advice = "Never Trust Anybody Over 30!"; for_each(advice.begin(), advice.end(),countCaps); cout << "upper-case letter count is " << capCount << endl;