[STL] partition

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

/*   partition 알고리즘은 한 개의 구간 [first, last) 와 하나의 단항 조건다 pred 가 주어졌 을 때, pred 를 true가 되게 하는 원소들이 pred를 false가 되게 하는 원소들보다 앞에 위치하도록 구간에 속한 원소들을 모두 재배치한다. stable_partition 알고리즘은 원소들을 재배치할 때, 앞쪽 그룹과 뒤쪽 그룹 내에서의 원소들의 상대적 위치가 그래도 유지되도록 해준다. 이 두 알고리즘은 리턴 값으로 앞쪽 그룹의 끝이면서 뒤쪽 그룹의 시작에 해당하는 부분을 가리키는 반복자를 리턴한다.   partition 과 stable_partition의 시간 복잡도는 선형적이다. */     #include <algorithm> #include <vector> #include <string> #include <iostream>   using namespace std;   bool above40(int n){ return (n>40); }   int main() {     cout<< "Illustrating the generic partition and"         << " stable_partition algorithms." << endl;       const int N = 7;     int array0[N] = {50, 30, 10, 70, 60, 40, 20};     int array1[N];       copy(&array0[0], &array0[N], &array1[0]);     ostream_iterator<int> out(cout, " ");       cout<< "Original sequence:                 ";     copy(&array1[0], &array1[N], out);    cout<< endl;       // 40보다 큰 수는 앞쪽에, 40보다 작거나 같은 수는 뒤쪽에 위치하도록     // array1을 파티션한다.     int* split = partition(&array1[0], &array1[N], above40);       cout<< "Result of (unstable) partitioning: ";     copy(&array1[0], split, out); cout<< "| ";     copy(split, &array1[N], out); cout<< endl;       // array1의 내용을 array0의 값들로 원상 복귀시킨다.     copy(&array0[0], &array0[N], &array1[0]);       // 다시 한 번 40보다 큰 수는 앞쪽에, 40보다 작거나 같은 수는 뒤쪽에     // 위치하도록 array1을 파티션하되, 각 그룹 내에서의 상대 위치는 그대로     // 유지되도록 한다.     split = stable_partition(&array1[0], &array1[N], above40);       cout<< "Result of stable partitioning:     ";     copy(&array1[0], split, out); cout<< "| ";     copy(split, &array1[N], out); cout<< endl;       return 0; }