크레이지J의 탐구생활

cpp functional

#include <functional>

++ operator class

++ 파라미터 바인더

+bind1st ; 함수객체를 리턴한다. 첫번째 파라미터를 지정.

ex) 10을 값으로 갖는 요소의 개수.

cnt = count_if( numbers, numbers+6,  bind1st( equal_to<int>(), 10 ) ) ;

+bind2nd ; 함수 객체를 리턴한다. 두번째 파라미터를 지정.

ex) 0보다 작은 값의 요소 개수.

cnt = count_if( numbers, numbers+6, bind2nd( less<int>(), 0 ) ) ;

++ 연산

+plus ; 두 객체를 더함.

template <class T> struct plus : binary_function <T,T,T> {

T operator() (const T&x, const T&y) const { return x+y ; }

ex) 두 컨테이너를 순서대로 요소별로 더하기

int first[]={1,2,3,4,5} ;

int second[]={10,20,30,40,50} ;

int results[5] ;

std::transform( first, first+5, second, results, std::plus<int>()) ;

+minus: 두 객체를 뺌.

상동

ex)

int numbers[]={10,20,30} ;

int result ;

result = std::accumulate( numbers, numbers+3, 100, std::minus<int>() ) ;

// 100 -10-20-30 = 40

+multiplies ; 두 객체를 더함.

int numbers[]={1,2,3,4,5,6,7,8,9} ;

int factorials[9] ;    // 각각의 factorial을 구함.

std::partial_sum( numbers, numbers+9, factorials, std::multiplies<int>() ) ;

// 시작값=1, 두개의 곲=2, 다음 곱=6, ...

//factorials =  1! 2! 3! 4! 5! 6! 7! 8! 9! 

+divides ; 두 객체를 나눔. first/second

// first = 10, 40, 90, 40, 10 

// second=1,2, 3, 4, 5

std::transform(first, first+5, second, second+5, results, std::divides<int>() ) ;

// results=10, 20, 30, 10, 2

+modulus ; 나눈 나머지. first%second

// numbers= 1,2,3,4,5

std::transform(numbers, numbers+5, remainders, std::bind2nd( std::modulus<int>(), 2) ) ;

// remainders = 1 0 1 0 1

+negate ; nagative   ; -1*x

std::transform(numbers, numbers+5, numbers, std::negate<int>() ) ;

// numbers 값들의 부호를 모두 바꿈.

++비교함수

+equal_to  ; 두 값이 같은 지 확인. 같으면 true, 다르면 false.

// foo = 10,20,30,40,50

// bar = 10,20,40,80,160

// 두 개를 비교하여 처음으로 다른 부분의 값을 각각 구하면

std::pair<int*,int*> ptiter = std::mismatch( foo, foo+5, bar,  std::equal_to<int>() ) ;

// *ptiter.first, *ptiter.second  = 30, 40

+not_equal_to

// 처음으로 나온 다른 값 찾기

// numbers = 10,10,10,20,20

int *pt = std::adjacent_find( numbers, numbers+5, std::not_equal<int>() ) +1 ;

// *pt = 20

+greater

// 내림차순 정렬

std::sort(numbers, numbers+5, std::greater<int>() ) ;    // prev > next

+less

// 오름차순 정렬

std::sort(numbers, numbers+5, std::less<int>() ) ;    // prev < next

+greater_equal

// 0이상인 원소의 개수

cnt = std::count_if( numbers, numbers+5, std::bind2nd(std::greater_equal<int>(), 0) ) ;

+less_equal

// 100이하인 원소의 개수

cnt = std::count_if( numbers, numbers+5, std::bind2nd(std::less_equal<int>(), 100) ) ;

++ 논리 연산

logical_and

logical_or

logical_not

ex) 

bool foo[]={true,false, true,false} ;

bool bar[]={true, true, false, false} ;

bool result[4] ;

std::transform(foo, foo+4, bar, result, std::logical_and<bool>() ) ;

// and 결과 ; true, false, false, false

std::transform(foo, foo+4, bar, result, std::logical_or<bool>() ) ;

// or 결과 ; true, true, true, false

std::transform(foo, foo+4, result, std::logical_not<bool>() ) ;

// not 결과 ; false, true, false, true

+not1  ; 결과를 not한 unary function 객체를 리턴함.

// 홀수가 아닌 원소의 개수.

struct isodd {

bool operator() (const int &x) { return i%2==1 ; }

typedef int argument_type ;

} ;

cx = std::count_if(values, values+5, std::not1(isodd()) ) ;

+not2 ; 결과를 not한 binary function 객체를 리턴함.

firstmismatch = std::mismatch( foo, foo+5, bar, std::not2( std::equal_to<int>() ) ) ;

+ptr_fun ; 함수포인터를 함수객체로 만들어 리턴해 준다.

char* foo[]={"10","20","30"} ;

int bar[3] ;

transform( foo, foo+5, bar, ptr_fun(atoi)) ;

+mem_fun ; 멤버함수를 함수객체로 만들어 리턴해 준다.

vector<string> v ; 

v.push_back( new string("one") ) ;

v.push_back( new string("three") ) ;

vector<int> lens ( v.size() ) ;

transform( v.begin(), v.end(), lens.begin(),  mem_fun( &string::length ) ) ;

+mem_fun_ref ;상동.  레퍼런스 버전.

+ref ; c++11

reference_wrapper 생성자.

객체의 적절한 참조 타입을 생성.

ex)

int foo (10) ;

auto bar = std::ref(foo) ;

bar++ ;

// foo => 11로 업데이트 된다. (참조형인 bar 변경의 영향)

cpp algorithm

++merge

+merge() ; 정렬된 범위를 합친다. 자동 정렬됨.

merge(first1, last1, first2, last2, result (,comp) )

std::merge( first, first+5, second, second+5, v.begin()) ;    // first와 second는 이미 sort 상태여야 함. 둘 을 합쳐 오름차순으로 v에 기록.

+includes() ; 범위 [first1, last1)내에 범위[fisrt2, last2)를 포함하는지 테스트. 둘 다 정렬된 상태여야 함.

bool includes(first1, last1, first2, last2 (,comp)) ;

+set_union ; 합집합. 두 개의 소팅된 범위를 합친다. 중복 제거.

std::sort(first, first+5) ;

std::sort(second, second+5) ;

it = std::set_union(first, first+5, second, second+5, v.begin()) ;

v.resize( it-v.begin() ) ;

+set_intersection ; 교집합. 두 개의 영역에 모두 해당되는 값들을 추출. (정렬상태)

it = std::set_intersection(first, first+5, second, second+5, v.begin()) ;

v.resize(it-v.begin()) ;

+set_difference ; 차 집합. A-B. (정렬상태)

 상동

+set_symmetric_difference ; 차이 집합 (A-B , B-A). 다른 것들로 구성

상동 

++heap ; 정렬된 컨테이너. 검색이나 추가가 빠르다.

+make_heap(first, last (,comp)) ; 요소들을 재배열한다. first가 항상 최대값이 오게 한다.

std::make_heap(v.begin(), v.end()) ;

v.front() ==> 최대값.

+push_heap() ; 요소를 힙에 푸시함. [first, last-1)이 힙인데, last의 값을 힙에 포함시킨다. [first, last) 로 구간이 확장됨.

데이터 추가시

v.push_back(99) ;

std::push_heap(v.begin(), v.end()) ;    // 마지막에 추가한 99를 힙 영역에 넣는다.

+pop_heap() ; first가 가리키는 값을 힙에서 뺀다. first의 값은 가장 뒤로 가게 되고, 힙은 재구성됨.

데이터 제거시

std::pop_heap(v.begin(), v.end()) ;

v.pop_back() ;

+sort_heap() ;오름차순으로 힙을 소팅한다.

std::sort_heap(v.begin(), v.end()) ;

++min/max

+min() ; 작은값을 찾는다.

const T & min(const T&a, const T&b) 

const T & min(const T&a, const T&b, Compare comp)

std::min(1,2) ;

std::min('a','z') ;

+max() ; 큰값을 찾는다.

상동

+min_element() ; 범위에서 최소값을 찾는다. 이터레이터 리턴 주의

iterator min_element(first, last, (comp)) ;

*std::min_element(v.begin(), v.end()) ;    // 최소값

+max_element() ; 범위에서 최대값을 찾는다.

상동

+minmax() ; c++11 , 최소값, 최대값 결과를 pair로 리턴. 리스트도 가능.

auto result = std::minmax({5,4,3,2,1}) ;

result.first => 1

result.second => 5

+minmax_element() ; c++11 ; 최소위치, 최대위치 결과를 pair로 리턴. pair의 요소는 이터레이터

auto result = std::minmax_element( foo.begin(), foo.end() ) ;

*result.first => 최소값.  *result.second=>최대값.

+lexicographical_compare(first1, last1, first2, last2 (,comp)) ; 사전식 비교

char foo[]="Apple" ;

char bar[]="apartment" ;

std::lexicographical_compare(foo, foo+5, bar, bar+9);         // => true ; foo < bar

std::lexicographical_compare(foo, foo+5, bar, bar+9, mycomp);         // => false ; foo > bar

bool mycomp(char c1, char c2) { return std::tolower(c1)<std::tolower(c2) ; }     // case-insensitive compare

+next_permutation(first, last) ; 

lexicographically 큰 다음 순열로 재배열한다.

// myints; 1 2 3

std::next_permutation(myints, myints+3) ;

// 1 3 2 로 변경. 마지막 두 개를 변경.

// 게속 permutation 반복시 

// 2 1 3 ,  2 3 1,    3 1 2,  3 2 1,    1 2 3 (처음으로 다시 환원됨). n! 개의 순열

반대 방향은 prev_permutation()

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