제네릭 알고리즘

STL은 STL에 포함된 다양한 데이터 구조에 두루 적용할 수 있는 알고리즘을 다수 제공하고 있다. STL의 알고리즘은 모두 제네릭하다. 즉, 각각의 알고리즘은 단 한 개의 데이터 구조에만 적용할 수 있는 것이 아니라, 여러 가지 다양한 데이터 구조에 사용될 수 있다는 것이다.

 

STL 제네릭 알고리즘들은 각 알고리즘의 의미에 따라, 대략 네 가지 부류로 분류할 수 있다.

1. 변경 불가 시퀀스 알고리즘(nonmutating sequence algorithm) 2. 변경 가능 시퀀스 알고리즘(mutating sequence algorithm) 3. 정렬 관련 알고리즘(sorting-related algorithm) 4. 범용 수치 알고리즘(generalized numeric algorithm)

 

 

1. STL 알고리즘의 기본 구성

STL 알고리즘의 네 가지 부류에 관한 설명을 시작하기에 앞서, 일부 알고리즘에서 있을 수 있는 여러 변형들에 관해 간략히 살펴보고 넘어가도록 하자. 이들 변형에는 크게 세 가지 즉, in-place버전과 복사 버전, 그리고 조건자를 인자로 가지는 버전이 있다.

 

1.1 In-place 버전과 복사 버전

일부 STL 알고리즘에서는 in-place 버전과 복사 버전이 모두 존재한다.

in-place 버전 알고리즘은 출력 결과로 얻어지는 시퀀스가 수행 대상이 되는 컨테이너 내부에 놓이게 된다.

복사 버전 알고리즘엥서는 수행 결과가 다른 컨테이너에 놓이게 되는데, 어떤 경우에는 알고리즘을 적용한 컨테이너와 동일한 컨테이너에 넣기도 한다. 하지만 이 때는 기존에 담겨 있는 원소와 겹치지 않도록 결과를 집어넣어야 한다.

 

STL에서, 특정 알고리즘의 복사 버전을 포함시킬지에 관해서는 시간 복잡도를 고려하여 결정한다. 예를 들어, sort 알고리즘의 복사 버전에 해당하는 sort_copy를 STL에 포함시키지 않은 것은 정렬에 소요되는 비용이 복사 비용보다 훨씬 더 커서, copy를 먼저 호출하고 sort를 호출하는 것이 더 바람직하기 때문이다. 반면에, reverse 알고리즘의 복사버전인 reverse_copy 알고리즘을 STL에 포함시킨 이유는, 복사와 뒤집기를 한꺼번에 하는 것이 copy를 수행하고 난 뒤에 reverse를 수행하는 것보다 거의 두 배 가까이 비용이 절감되기 때문이다.

 

1.2 함수를 인자로 가지는 알고리즘

STL 제네릭 알고리즘들 중에는 함수를 가지고 있는 것들이 많다. 그리고 그 인자는 조건자(predicate)로 쓰이는 경우가 대부분이다.(조건자는 리턴 값이 bool 타입인 함수를 말한다). 예를 들어, 정렬과 관련된 알고리즘들은 모두 이진 조건자를 받아, x와 y 두 값의 크기를 비교하여 순서를 결정하는데 사용한다. 조건자가 달라지면, 결과 시퀀스의 정렬 순서가 바뀔 수도 있다.

 

제네릭 알고리즘으로 함수를 넘겨주는 가장 간편한 방법은 클래스로 정의된 함수 객체를 사용하는 것이다. 클래스로 정의한 함수 객체를 이용하여 함수를 인자로 전달하는 방법은 컴파일시에 함수 전달이 이루어지기 때문에, 매우 효과적인 방법이다.

 

 

2. 변경 불가 시퀀스 알고리즘

변경 불가 시퀀스 알고리즘은 대상 컨테이너를 직접 수정할 수 없는 알고리즘이다. 이러한 알고리즘에는 시퀀스를 검색하여 원하는 원소를 찾아내는 알고리즘, 상등 여부를 검사하는 알고리즘, 시퀀스에 담긴 원소의 원소 개수를 세는 알고리즘 등이 있다.

변경 불가 시퀀스 알고리즘에는 find, adjacent_find, count, for_each, mismach, equal, search가 있다.

 

2.1 find

제네릭 find 알고리즘의 조건자 버전인 find_if는 시퀀스에 담긴 원소 중에서 주어진 조건자를 true가 되게 하는 첫 번째 원소를 찾아낸다.

find와 find_if의 시간 복잡도는 선형적이다.

 

2.2 adjacent_find

adjacen_find 알고리즘은 시퀀스에서 동일한 원소가 서로 이웃하고 있는 쌍을 찾아낸다. 이 알고리즘은 서로 인접한 두 원소가 동일한 부분을 찾아내면, 앞쪽 원소를 가리키는 반복자를 리턴한다.

adjacent_find의 시간 복잡도는 선형적이다.

 

2.3 count

count는 시퀀스를 검색하여 특정 값과 일치하는 원소의 개수를 세는 변경 불가 시퀀스 알고리즘이다.

count_if 알고리즘은 count_if 알고리즘은 count 알고리즘의 단항 조건자 버전으로, 조건과 동일하지 않은 원소의 개수를 계산한다.

count와 count_if 알고리즘의 시간 복잡도는 선형적이다.

 

2.4 for_each

for_each는 시퀀스에 담긴 모든 원소에 함수 f를 적용하는 제네릭 알고리즘이다.

for_each 알고리즘의 시간 복잡도는 선형적이다.

 

2.5 mismatch과 equal

mismatch와 equal 알고리즘은 두 개의 구간을 비교할 때 사용된다.

유의해야 할 점은, equal 알고리즘과 mismatch 알고리즘 중 어떠한 것을 사용해도 두 개의 컨테이너가 완전히 일치하는지를 알 수 없다는 점이다. 왜냐하면, 알고리즘에서 두 컨테이너의 사이즈가 서로 일치하는가에 관해서는 검사를 하지 않기 때문이다.

equal과 mismatch의 시간 복잡도는 선형적이다.

 

2.6 search

제네릭 search 알고리즘은 두 개의 반복자 구간을 인자로 받아, 두 번째 구간에 담겨진 서브 시퀀스를 첫 번째 구간 내에서 찾아 그 위치를 알아낸다.

search 알고리즘을 구현할 때는 첫 번째 구간의 사이즈가 m이고 두 번째 구간의 사이즈가 n인 경우, 시간 복잡도가 O(mn)이 되도록 구현해야 한다.

 

 

3 변경 가능 시퀀스 알고리즘

변경 가능 시퀀스 알고리즘은 알고리즘의 적용 대상이 되는 컨테이너의 내용을 변경할 수 있는 알고리즘을 일컫는다. 예를 들어, unique 알고리즘은 시퀀스로부터 이웃하는 두 원소가 중복되어 있는 경우 중복 원소들을 제거한다. 이러한 알고리즘에는 시퀀스에 저장된 원소들에 대해 copy, fill, generate, partition, shuffle, remove, replace, reverse, swap, transform 등의 연산을 수행하는 알고리즘들이 있다.

 

3.1 copy와 copy_backward

제네릭 copy알고리즘과 제네릭 copy_backward 알고리즘은 특정 구간에 속하는 원소들을 다른 구간으로 복사하고자 할 때 사용한다.

copy와 copy_backward 알고리즘의 시간 복잡도는 선형적이다.

 

3.2 fill과 fill_n

fill과 fill_n 알고리즘은 구간에 속하는 모든 위치를 주어진 값으로 채워 넣는다.

fill과 fill_n 알고리즘의 시간 복잡도는 선형적이다.

 

3.3 generate

generate 알고리즘은 구간 [first, last)에 해당하는 부분을, 함수 gen(세 번째 인자로 넘겨 받은 함수)을 last-first번 연속 호출하여 얻은 값들로 채운다. 여기서 gen 함수는 인자가 없는 함수라고 가정한다.

generate 알고리즘의 시간 복잡도는 선형적이다.

 

3.4 partition과 stable_partition

partition 알고리즘은 한 개의 구간[first, last)와 하나의 단항 조건자 pred가 주어졌을 때, pred를 true가 되게 하는 원소들이 pred를 false가 되게 하는 원소들보다 앞에 위치하도록 구간에 속한 원소들을 재배치한다.

stable_partition 알고리즘은 원소들을 재배치할 때, 앞쪽 그룹과 뒤쪽 그룹 내에서의 원소들의 상대적 위치가 그대로 유지되도록 해준다.

이 두 알고리즘은 리턴 값으로 앞쪽 그룹의 끝이면서 뒤족 그룹의 시작에 해당하는 부분을 가리키는 반복자를 리턴한다.

 

3.5 random_shuffle

제네릭 random_shuffle 알고리즘은 모의 난수(pseudo-random number)를 발생시키는 함수를 이용하여 구간 [first, last) 내의 원소들을 무작위로 뒤섞는다.

random_shuffle이 만들어내는 순열들은 거의 균등한 분포를 이룬다. 즉, 사이즈 N인 구간에 속하는 원소들로 만들 수 있는 N!개 순열들 각각의 확률은 거의 1/N!에 가깝다.

random_shuffle의 시간 복잡도는 선형적이다.

 

3.6 remove

제네릭 remove 알고리즘은 주어진 구간 내에서 특정 값과 일치하는 원소들을 모두 삭제한다(실제로 해당 원소가 없어지는 것은 아니다). 그리고 이 알고리즘은 "stable" 알고리즘에 해당하는데, 다시 말해서, 알고리즘을 수행한 후에 시퀀스에서 삭제되지 않은 원소들의 상대적인 순서는 그대로 유지된다.

여기서 유의해야 할 점은 remove 알고리즘을 수행한 후에도 컨테이너의 사이즈는 변하지 않는다는 것이다. remove 알고리즘은 주어진 값과 일치하지 않는 원소들을 인자로 주어진 구간의 앞쪽에 몰아넣고, 이 원소들이 끝나는 위치에 해당하는 반복자를 리턴 값으로 리턴한다. 이 리턴 값이 가리키는 부분부터 벡터의 끝 사이에 위치한 원소들의 순서는 정의되어 있지 않으며, 이 부분에 위치한 원소들은 벡터의 멤버 함수인 erase를 사용하여 비로소 삭제된다.

remove 알고리즘들의 시간 복잡도는 모두 선형적이다.

 

3.7 replace

제네릭 replace 알고리즘은 지정된 구간 내에서 특정 값과 일치하는 원소들을 다른 값으로 치환한다.

모든 replace 알고리즘의 시간 복잡도는 선형적이다.

 

3.8 reverse

제네릭 reverse 알고리즘은 구간 내의 모든 원소들의 순서를 반대로 뒤집는다. 구간을 지정하는 반복자는 양방향 반복자이어야 한다.

reverse 알고리즘의 시간 복잡도는 선형적이다.

 

3.9 rotate

제네릭 rotate 알고리즘은 지정된 구간을 특정 위치를 중심으로 한 바퀴 돌린다. 다음과 같이 호출하면

rotate(first, middle, last)

구간 [first, last)에 속하는 원소들을 middle - first 만큼 왼쪽으로 돌아간다. 이 알고리즘을 호출하고 나면, 원래는 [middle, last)에 위치해 있던 원소들이 [first, first+k) (여기서, k = last-middle)로 옮겨지고, 원래 [first, middle)에 위치해 있던 원소들은 [first+k, last)에 나타나게 된다. 구간을 지정하는 rotate의 인자들은 양방향 반복자이어야 한다.

rotate 알고리즘의 시간 복잡도는 선형적이다.

 

3.10 swap

제네릭 swap 알고리즘은 두 개의 값을 서로 맞바꾼다.

이 알고리즘은 내장 타입에 적용되는 경우뿐만 아니라, 한 쌍의 STL 컨테이너에 적용할 때에도 상수 시간 복잡도를 가진다. 두 벡터를 서로 바꿔치기 할 때는 벡터의 대입 연산자를 사용하지 않는다. 왜냐하면, 벡터의 대입 연산은 O(N)의 시간이 소요되는 int 대입 연산이 뒤따르기 때문이다(여기서, N은 두 벡터 중 더 긴 벡터의 사이즈이다). vector에는 swap이란 멤버 함수가 있기 때문에, 이 멤버 함수를 사용하면 된다.

 

3.11 swap_ranges

 제네릭 swap_ranges 알고리즘은 두 구간에 속하는 값들을 서로 맞바꾼다. 이 두 구간이 서로 다른 컨테이너에 속해 있어도 상관 없다.

swap_ranges 알고리즘의 시간 복잡도는 선형적이다.

 

3.12 transform

제네릭 transform 알고리즘은 주어진 구간에 속하는 원소들 각각에 대해, 지정된 함수를 적용하여 얻은 결과 값들을 다른 구간에 저장한다. transform 알고리즘에는 두 가지 버전이 있는데, 구간에 속하는 원소 각각에 인자로 받은 단항 함수를 적용하는 단항 함수 버전이 있고, 구간 두 개로부터 얻은 한 쌍의 원소에 인자로받은 이항 함수를 적용하는 이항 함수 버전이 있다.

transform 알고리즘의 시간 복잡도는 선형적이다.

 

3.13 unique

제네릭 unique 알고리즘은 입력 시퀀스에서 모든 연속 중복 원소들을 모두 제거한다. 시퀀스 상에서 자신의 왼쪽에 위치한 원소와 값이 동일하면, 그 원소는 중복 원소에 해당한다. 따라서, 원소들로 구성된 그룹이 있다면 그 그룹의 맨 앞의 원소를 제외한 나머지 원소는 unique 알고리즘을통해 제거된다. remove 알고리즘과 마찬가지로, unique는 컨테이너 사이즈를 변경하지 않는다. 대신, 연속 중복 원소가 아닌것들("unique"한 원소들)을 구간의 왼편으로 몰아 넣고, "unique"한 원소들이 끝나는 위치를 가리키는 반복자를 리턴한다.

중복되어 있다고 해서 무조건 제거되는 것이 아니라 반드시 연속적으로 중복되어 있는 경우에만 삭제되는 것이다. 만약 연속적으로 중복된 것뿐만 아니라 중복된 원소들 전체를 삭제하고 싶다면, 우선 원하는 구간에 속하는 원소들을 모두 정렬하고 나서, unique를 적용하면 된다. 단 여기서 유의할 점은, 이 방법을 사용할 때는 중복되지 않는 원소들의 순서가 바뀌어도 상관없을 경우에만 적용해야 한다는 것이다.

unique의 시간 복잡도는 선형적이다.

 

 

4. 정렬 관련 알고리즘

STL은 정렬과 관련된 알고리즘을 제공하고 있는데, 시퀀스를 정렬하거나 머지하는 알고리즘, 그리고 정렬된 시퀀스에 대해 검색 연산이나 셋 관련 연산을 수행하는 알고리즘 등이 있다.

 

4.1 비교 관계

정렬 알고리즘에서는 시퀀스의 원소들을 비교하는 것이 가장 핵심적인 부분이다. 정렬 알고리즘중에는 < 연산자를 이용하여 비교를 수행하는 알고리즘이 있는가 하면, 인자로 넘겨받은 비교 객체를 이용하여 비교를 수행하는 알고리즘이 있다.

 

비교 객체는 이항 조건자 객체이어야 하며, 이 비교 객체에 정의되어 있는 이항 관계는 몇 가지 기본 규칙들을 잘 준수하고 있어야만 정렬 관련 알고리즘의 수행 결과를 정확히 정의할 수 있다.

 

우선, 실제로 사용되고 있는 요구 사항보다 좀 더 강화된 요구 사항들을 먼저 살펴보자. 집합 S상에서 정의되어 있는 이항 관계 R이 다음 두 가지 규칙을 만족하면, 관계 R은 집합 S상에서 strict total ordering이라고 한다.

- (Transitivity) S에 속한 모든 x,y,z에 대해서 xRy인 동시에 yRz이면 xRz이다. - (Trichotomy) S에 속한 모든 x, y에 대하여 다음 세 가지 조건 중 오직 한가지 조건에 대해서만 참이된다.   : xRy, yRx, x = y

strict total ordering을 만족하는 비교 관계는 STL의 정렬 관련 알고리즘과 함께 사용할 수 있는 관계이다.

strict total ordering은 시퀀스 내에서의 원소 간의 순서를 완전하게 결정한다(이 때문에, 이름에 "total"이란 단어가 들어간 것이다). 하지만 때로는 원소들의 순서가 어떻게 되더라도 상관없는 경우가 있다. 이런식으로 처리해야 하는 상황이 정렬 연산에서는 매우 흔하기 때문에, STL의 정렬 관련 알고리즘들은 모두 strict total ordering보다 더 완화된 관계에서 동작하도록 설계되어 있다.

 

실제로 STL의 정렬 관련 알고리즘에 적용되고 있는 요구 사항은 stric weak ordering이다. 여기서 "weak"란 단어는 요구 사항들이 모든 원소들의 순서를 결정지을 수 있을 만큼 강한 것이 아니라는 뜻에서 사용된 것이다.

 

4.2 오름차순과 내림차순

STL의 정렬 알고리즘과 머지 알고리즘은 출력 결과를 비교 관계 R에 따라 오름차순(nondecreasing order)으로 배치한다. 이것은 시퀀스 내의 원소 x를 가리키는 모든 반복자 i와 음수가 아닌 모든 정수 N에 대해서 i+N이 시퀀스 원소 y를 가리킬때, yRx는 항상 거짓이라는 것을 의미한다.

 

오른차순이 필요한 경우도 있는데, 이 때는 R의 역관게가 필요하다. 일반적으로 R이 S상에서 이항관계일 때, 이것의 역관계는 "yRx이면 반드시 xCy가 성립"하는, S상의 관계 C를 의미한다. 따라서, 내장 타입에 대한 < 연산자의 역관계는 >연산자에 정의되어 있는 관계와 동일한 것이다. 사용자 정의 타입에서는 < 연산자만 정의되어 있으며, > 연산자가 < 의 역관계가 되도록 다음과 같이 정의한 STL 템플릿 함수(utility 헤더에 있음)를 제공하고 있다.

template <typename T> inline bool operator>(const T& x, const T& y) {     return y > x; }

 

오름차순이라는 의미를 가진 용어로 nondecreasing과 ascending이 함께 사용되며,

내림차순이라는 의미를 가진 용어로는 nonincreasing과 descending이 함께 사용된다.

 

4.3 sort, stable_sort, partial_sort

STL은 sort, partial_sort, stable_sort, 이 세 개의 제네릭 정렬 알고리즘을 제공한다. 이들 각각은 임의 접근 시퀀스를 정렬하며, 정렬 결과는 알고리즘이 적용된 컨테이너 내에 반영된다(이러한 알고리즘을 in-place 알고리즘이라고 한다).

partial_sort는 상수 분량의 메모리만을 추가로 필요로 하며, sort는 로그 분량만큼의 메모리를 추가로 필요로 한다. 따라서, 이 두 알고리즘은 본질적으로 in-place알고리즘이라고 할 수 있지만, stable_sort는 선형적 분량의 추가 메모리를 사용한다.

 

이 세 알고리즘은 수행 소요 시간과 stability 측면에서 서로 차이가 난다. sort 함수는 길이 N의 시퀀스를 정렬하는데 수행하는 비교 연산의 횟수가 평균 O(N log N)번이어야 한다. 하지만 최악 조건에서는 O(N²)의 소요 시간도 허용할 수 있다. 반드시 O(N log N)시간 내에 정렬을 수행하고 싶다면, partial_sort 알고리즘을 사용하면 된다. sort와 partial_sort는 반드시 stable한 알고리즘일 필요는 없다. 다시 ㅁ라해, 동등한 원소의 상대적 위치가 반드시 유지될 필요는 없다는 것이다. stability가 필요하다면, stable_sort를 사용하면 된다. stable_sort 알고리즘은 메모리 공간이 부족하지 않은 경우에는 O(N log N)의 시간의 바운드를 가지지만, 그렇지 않은 경우에는 더 많은 시간이 소요된다.

 

4.4 nth_element

제네릭 nth_element 알고리즘은 N번째 위치에, 시퀀스가 정렬되었을 경우 높이게 되는 원소가 놓여지도록 하며, 또한 N번째 원소의 왼쪽에 있는 모든 원소가 오른쪽에 위치한 원소들보다 모두 작거나 동등하도록 시퀀스를 파티션한다.

 

4.5 binary_search, lower_bound, upperbound, equal_range

제네릭 이진 검색 알고리즘은 전통적인 이진 검색 방법을 사용하여 정렬 시퀀스에서 원하는 원소를 찾아내는 알고리즘이다. 미리 정렬되어 있는 구간 [first, last)와 원소 x가 주어진 경우, 제네릭 binary_search 알고리즘은 주어진 구간에서 원소 x를 찾으면 true를 리턴하고, 찾지 못한 경우에는 false를 리턴한다. 이와 동일한 입력이 주어졌을 때, lower_bound와 upper_bound 알고리즘은 각각, 원소들의 정렬 상태를 그대로 유지하면서 주어진 값을 삽입할 수 있는 위치 중 가장 첫 번째와 가장 마지막 위치를 가리키는 반복자 i를 리턴한다(그리고 구간 내에 x와 동등한 원소가 이미 있는지 여부와는 관계없이 삽입될 위치를 결정한다는 점을 유의하기 바란다). equal_range 알고리즘은 lower_bound와 upper_bound의 리턴 값으로 구성된 반복자 한 쌍을 리턴한다.

 

4.6 merge

제네릭 merge 알고리즘은 두 개의 정렬된 구간을 머지하여 이 두 입력 구간과 겹치지 않는 구간에 출력 결과를 집어넣는다. inplace_merge 알고리즘은 두 개의 연속된 정렬 구간을 머지하며, 머지한 결과는 이 두 구간을 대체한다.

merge 알고리즘의 시간 복잡도는 선형적이다. inplace_merge의 시간 복잡도는 추가로 화보할 수 있는 메모리 공간의 양에 따라 좌우된다. 메모리를 추가로 확보할 수 없는 경우에는 소요 시간이 O(N log N)이며, 그렇지 않은 경우에는 선형적이다.

 

4.7 정렬된 데이터 구조에서의 집합 연산

STL은 정렬된 시퀀스에 대해 집합 관련 연산을 수행하는 다섯 개의 알고리즘, includes, set_union, set_intersection, set_difference, set_symmetric_difference를 제공하고 있다.

includes 알고리즘은 주어진 구간 [first1, last1)의 원소들이 다른 구간 [fisrt2, last2)에 포함되는지를 확인하여 적절한 불 값을 리턴한다.

set_union 알고리즘은 두 개의 구간 [first1, last1)과 [first2, last2)으로 표현된 두 집합의 합집합을 구하여 구간 [result, last)에 집어넣고, 결과 시퀀스의 끝경과(past-the-end) 값에 해당하는 last를 리턴한다.

제네릭 set_difference 알고리즘은 첫 번째 구간에 속하는 원소들 중에서 두 번째 구간에 속하지 않은 원소들로 구성된 집합을 만들어낸다.

 

set_intersection 알고리즘은 두 구간에 모두 속해있는 원소들로 구성된 집합을 만들어 낸다.

set_symmetric_difference는 양쪽 구간에 동시에 속해있지 않고, 한쪽 구간에만 속해 있는 원소들로 구성된 집합을 만들어 낸다.

set_union과 마찬가지로, 이들 알고리즘은 모두 결과 시퀀스를 [result, last)에 집어넣으며, 결과시퀀스의 끝경과 값에 해당하는 last를 리턴한다.

 

집합연산의 시간 복잡도는 모두 선형적이다.

 

4.8 힙(heap) 연산

힙은 특별한 구조를 가진 임의 접근 데이터 구조이다. 구간 [first, last)가 주어졌을 때, 다음 두 가지 특성을 만족하면 이 구간은 힙을 표현하고 있다고 말할 수 있다.

- first가 가리키는 값이 가장 큰 값이다.  - 로그 시간 내에 pop 연산으로 first가 가리키는 값을 제거하거나, push 연산으로 새로운 원소를 추가할 수 있다.   그리고 pop과 push 연산을 수행한 후에도 주어진 구간은 여전히 힙이다.

 

STL은 힙을 생성하고 다루는데 사용하는 네 개의 알고리즘, make_heap, pop_heap, push_heap, sort_heap을 제공하고 있다.

 

4.9 min과 max

제네릭 min 알고리즘과 max 알고리즘은 두 개의 원소를 받아 각각 둘 중 더 작은 값과 더 큰 값을 리턴한다.

min_element 알고리즘과 max_element 알고리즘은 각각 입력 시퀀스에 담긴 원소들의 최소 값과 최대 값을 가리키는 반복자를 리턴한다.

 

4.10 lexicographicla_compare

제네릭 lexicographical_compare 알고리즘은 두 개의 입력 시퀀스를 다음과 같이 비교한다. 시퀀스 1과 2로부터 선택한 e1과 e2, 한쌍의 원소를 비교한다. e1 < e2이면 알고리즘은 즉시 true를 리턴하고, e2 <e1이면 즉시 false를 리턴한다. 그 외의 경우에는 다음 쌍으로 넘어가서 비교를 한다. 이렇게 계속 하다가 첫 번째 시퀀스에 비교할 원소가 더 이상 없고 두 번째 시퀀스는 아직 비교할 원소가 남아 있게 되면, 알고리즘은 true를 리턴한다. 그렇지 않은 경우에는 false을 리턴한다.

시퀀스에 포함된 원소에는 strict weak ordering에 해당하는 정의된 < 연산자가 정의되어 있어야 한다(아니면, strict weak ordering을 정의하는 비교 객체를 lexicographical_compare의 인자로 넘겨도 된다). 만약에 < 또는 비교 객체가 strict total ordering을 정의하고 있다면, lexicographical_compare로 결정되는 순서도 역시 strict total ordering이며, 그렇지 않다면 strict weak ordering이다.

 

4.11 순열 생성기

STL은 두 개의 순열 알고리즘을 제공한다.

next_permutation은 주어진 시퀀스를 사전식 순서 상에서 그 다음에 해당하는 시퀀스로 변경한다.

반면에, prev_permutation은 주어진 시퀀스를 사전식 순서 상에서 바로 앞에 위치하는 시퀀스로 변경한다.

입력 시퀀스는 반드시 양방향 반복자를 지원해야 한다. 이 두 알고리즘은 사전식 순서(lexicographical ordering)를 이용하고 있기 때문에 시퀀스에 속하는 원소들은 strict weak ordering에 해당하는 < 연산자가 있어야 한다(또는, strict weak ordering을 정의한 비교 객체를 이들 알고리즘의 인자로 넘겨줘도 된다).

 

 

5 범용 수치 알고리즘

STL은 네 개의 수치 알고리즘, accumulate, partial_sum, adjacent_difference, inner_product들을 제공하고 있다.

 

5.1  accumulate

제네릭 accumulate 함수는 주어진 구간에 속하는 값들을 모두 더한다

 

5.2 partial_sum

시퀀스  x0, x1, ..., xn-1이 주어졌을 때, 제네릭 partial_sum 알고리즘은 합의 시퀀스 x0, x0+x1, x0+x1+x2, ..., x0+x1+...+xn-1

 

을 만들어낸다. 이 알고리즘은 이 부분합들을 인자로 주어진 원래 시퀀스에 집어넣을 수도 있고, 다른 구간에 집어 넣을 수도 있다.

 

5.3 adjacent_difference

시퀀스  x0, x1, ..., xn-1이 주어졌을 때, 제네릭 adjacent_difference 알고리즘은 한 시퀀스 내의 이웃하는 두 값의 차를 계산하여

 

동일 시퀀스나 다른 시퀀스에 계산결과 x0, x1-x0, x2-x1, ..., xn-1-xn-2를 집어 넣는다.

 

 

5.4 inner_product

제네릭 inner_product 알고리즘은 두 입력 시퀀스 내적(inner product)을 계산한다.

다음 예제 프로그램에서는 우선 먼저, +와 *로 정의되는 일반적인 정의를 사용하여 1, 2, 3, 4, 5와 2, 3, 4, 5, 6의 내적을 계산하여 다음과 같은 결과 값을 얻는다. 

1×2 + 2×3 + 3×4 + 4×5 + 5×6 = 70

이 알고리즘은 내적을 계산할 때 기본적으로 +와 * 연산자를 사용한다. 하지만 inner_product의 함수 객체를 넘겨주면 다른 연산자를 대신 사용할 수도 있다.

 

 

 

 

- STL 튜토리얼·레퍼런스 가이드 제2판 中 -