alrorigthm 3 partition, sort, search

cpp

+is_partitioned(first, last, UnaryPredicate pred) ; c++11

범위가 나눠졌는지 확인. true/false 리턴

std::array<int, 7> foo {1,2,3,4,5,6,7} ;

std::is_partitioned(foo.begin(), foo.end(), isodd) ; // foo -> 파티션 안됨.

+partition(first, last, pred)    ; 두 개로 나눈다.

pred가 true인 그룹과 false인 그룹으로 나눈다. 순서가 바뀜.

리턴값은 두 번째 그룹의 첫번째 요소의 이터레이터.

컨테이너에서 앞에서 부터 하나씩 pred가 true인 동안 계속 다음으로 진행하고 false인 곳에서 멈춘다음, 컨테이너 뒤에서 부터 앞으로 하나씩 멈춘곳까지 진행하면서 pred가 true이면 값을 멈춘곳의 값과 바꾸고 멈춘 지점 인덱스를 증가시킨다. 

// myvec ; 1~9

std::vector<int>::iterator bound ;

bound = std::partition(myvec.begin(), myvec.end(), isodd) ;    // 홀수 그룹과 짝수그룹으로 나누고, 짝수 그룹 시작 위치를 리턴한다.

// 홀수그룹은 [myvec.begin(), bound )  ; 1 9 3 7 5

// 짝수 그룹은 [bound, myvec.end() ) ; 6 4 8 2

+stable_partition(first, last, pred) ; 두 개의 그룹으로 나누는데, 원래의 순서를 보장한다.

// 1 3 5 7 9 , 2 4 6 8

+partition_copy(first, last, result_true, result_false, pred) ; c++11

두 그룹으로 나눈다. 원본은 유지. 

std::partition_copy( foo.begin(), foo.end(), odd.begin(), even.begin(), isodd) ;

+partition_point(first, last, pred) ; 파티션 구분 이터레이터 (두 번째 그룹 시작위치)를 리턴 ; c++11

auto it = std::partition_point( foo.begin(), foo.end(), isodd) ;

odd.assign( foo.begin(), it ) ;

++ sorting

+sort ; 정렬

void sort(first, last) ;    // 디폴트 오름차순.

void sort(first, last, Compare comp) ;    // 앞, 뒤 요소가 comp 조건을 만족하도록 정렬된다. 

std::sort( myvec.begin(), myvec.begin()+4) ;    // 앞에서 4개만 소팅함. 뒤에는 그대로 유지. (오름차순 정렬,)

std::sort(myvec.begin()+4, myvec.end(), myfunc) ;    // 앞에 4개뺀 나머지를 myfunc로 정렬.

bool myfunc(int i, int j) { return (i<j); }     // 오름 차순 정렬

std::sort(myvec.begin(), myvec.end(), myobj) ;    // 전체를 myobj 객체로 정렬.

struct myclass {

bool operator()(int i, int j) { return (i<j); } // 오름차순 정렬

} myobj ;

+stable_sort() ; sort와 같다. 단, 크기가 같은 항목(==)에 대해서는 원본 순서를 보장해 준다.

+partial_sort(first, middle, last) ; 일부를 구간까지를 정렬순서를 만든다. 

[first, middle) 위치까지 오름 차순 정렬을 만드는데, 전체요소들에서 순서대로 만들어 준다.  middle위치 부터는 정렬되지 않는다.

+partial_sort_copy(first, last, result_first, result_last) ; (,comp)

result의 범위가 더 작으면 할당된 크기만큼만 복사된다.

+is_sorted() ; 정렬 여부 // c++11 

ex) //정렬될때까지 permutation 시도.

do {

std::prev_permutation( foo.begin(), foo.end() ) ;

for (int&x :foo) std::cout << ' ' <<x ;

std::cout << '\n' ;

} while ( !std::is_sorted(foo.begin(), foo.end()) ) ;

+ is_sorted_until() ; // c++11

처음 발견된 비정렬 데이터의 위치를 리턴

it = std::is_sorted_until( foo.begin(), foo.end() ) ;

// foo ; 2 3 4 1 ; it = point 1.  it-foo.begin() => 3(index) ; 3개까지 유효한 정렬임.

+nth_element() ; 오름차순 정렬시 index n번의 요소를 기준으로 좌(low) 우(over)로 나눈다. 순서보장 안 됨.

// myvec; 0~9 까지 랜덤한 순서로 있을 때.

std::nth_element(myvec.begin(), myvec.begin()+5, myvec.end() ) ;

// 숫자 5 (오름차순 정렬시 인덱스 5번)를 기준으로 작은 값, 큰 값으로 구분하여 정렬된다. (작은 값, 큰 값 내부는 정렬이 안된다.)

++ binary search

+lower_bound() ; lower bound를 리턴한다. [first, last) 범위내에서 val보다 작지 않은 첫번째 위치를 리턴. 

+upper_bound() ; upper bound ; [first, last)범위내에서 val보다 큰 첫번째 위치.

즉, val값에 해당되는 영역의 [시작,끝) 위치를 찾는다. 

// myvec ; 10 10 10 20 20 20 30 30 

std::vector<int>::iterator low,up ;

low = std::lower_bound(myvec.begin(), myvec.end(), 20) ;    // 3

up = std::upper_bound(myvec.begin(), myvec.end(), 20) ;    // 6

// 따라서 20에 해당되는 영역은 [3, 6) 가 된다. 

3번재 파라미터로 Compare 함수를 주어 비교루틴을 적용할 수도 있다.! (특정 값이 아닌 특정범위에 해당되는 영역 검색)

+equal_range() ; 특정 값의 영역을 가져온다. 리턴결과는 범위 pair<iterator, iterator>

equal_range(first, last, val) ;

equal_range(first, last, val, comp) ;

std::pair<std::vector<int>::iterator, std::vector<int>::iterator> bounds ;

bounds = std::equal_range( v.begin(), v.end(), 20) ; // lower, upper bound를 리턴한다.

bounds.first, bounds.second

+binary_search(); 정렬된 컨테이너에서 값이 존재하는지 테스트한다. true/false

std::binary_search(v.begin(), v.end(), 3) ;    // 3이 존재하면 true