algorithm 2 copy,swap,transform,replace,fill,generate,remove,unique,..

cpp algorithm

include <algorithm>

순서 변경,  수정 api

+copy 

OutputIterator copy(InputIterator first, last, OutputIterator result) ;

[first, last) 범위의 데이터를 result 위치에 복사한다. 

리턴값은 목적지 범위의 마지막 이터레이터.

while(first!=last) {

 *result = *first ;

 result++ ; first++ ;

}

return result ;

ex) 

int myints[]={10,20,30,40,50,60,70} ;

std::vector<int> myvec(7) ;

std::copy(myints, myints+7, myvec.begin()) ;    // myints의 모든 요소를 벡터로 복사.

+copy_n(first, n, result) ;    // c++11

first위치에서 n개 까지만 result로 복사한다.

std::copy_n(myints, 7, myvec.begin()) ;    // myints에서 7개의 요소를 벡터로 복사.

+copy_if(first, last, result, UnaryPredicate pred) ;    // c++11

지정범위에서 조건을 만족하는 것만 복사.

auto it = std::copy_if( foo.begin(), foo.end(), bar.begin(), [](int i) { return i>=0; } ) ;    // 양수만 복사.

bar.resize( std::distance(bar.begin(), it) ;    // 요소크기만큼 크기를 줄임.

+copy_backward() ; 뒤에서 부터 복사.

myvec ; 10,20,30,40,50

myvec.resize( myvec.size()+3) ;    // 크기를 3 늘림.

std::copy_backward( myvec.begin(), myvec.begin()+5, myvec.end() ) ; // myvec의 [0,5) 범위를 myvec.size()의 가장 뒤에서 부터 거꾸로 채움.  

10,20,30,40,50, ? , ? ,? ==> 

10,20,30,10,20,30,40,50

+move() ; 요소를 이동시킴 // c++11

이동한 데이터는 남아있음.

move와 copy의 차이는 기본적으로 같은데, move는 같은 버퍼내에서의 복사를 보장해 준다.

[first, last)의 데이터는 유효하고 unspecified로 남아있다.

- move_backward()    // c++11

-swap ;  두 값이나 컨테이너를 바꾼다.

int x=10, y=20 ;

std::swap(x,y) ;        // x, y의 값이 바뀐다. 따라서 x=20, y=10

std::vector<int> foo(4,x),   bar(6,y) ;    // foo=20,20,20,20,    bar=10,10,10,10,10,10

std::swap(foo, bar) ;        // foo=10,10,10,10,10,10, bar=20,20,20,20

-swap_ranges ; 범위내에서 바꿈.

std::vector<int> foo(5,10) ;    // foo=10,10,10,10,10

std::vector<int> bar(5,33) ;    // bar=33,33,33,33,33

std:;swap_ranges(foo.begin()+1, foo.end()-1, bar.begin()) ;    // foo의 범위 [1,4) ; 즉 가운데 3개를 bar의 시작부터 3개와 바꾼다.

// foo = 10,33,33,33,10,    bar=10,10,10,33,33

-iter_swap ; 두 개의 이터레이터가 가리키는 값을 서로 바꾼다.

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

std::vector<int> myvec(4, 99) ;    // 99,99,99,99

std::iter_swap( myints, myvec.begin() ); // myints=99,20,30,40,50,   myvec=10,99,99,99

std::iter_swap( myints+3, myvec.begin()+2) ; // myints=99,20,30,99,50,  myvec=10,99,40,99

-transform() ; 한개의 값 또는  두 컨테이너의 값을 순차적으로 어떤 작업을 하여 저장한다.

transform(InputIterator first1, last1, OutputIterator result, UnaryOperation op) ;

transform(first1, last1, first2, result, BinaryOperation binary_op) ;

ex)  모든 원소를 1씩 증가

int op_increase(int i) { return ++i ; } 

std::vector<int> bar ;

bar.resize(foo.size()) ;

std::transform( foo.begin(), foo.end(), bar.begin(), op_increase) ;

ex) 두 컨테이너의 값을 더함.

std::transform( foo.begin(), foo.end(), bar.begin(), scott.begin(), std::plus<int>()) ;

// foo, bar의 각각 요소를 순차적으로 더해서 scott에 추가.   plus는 include <functional>

-replace() ; [first, last) 범위에서 old_value를 new_value로 교체한다.

std::replace( myvec.begin(), myvec.end(), 20, 99) ;    // 20을 99로 모두 교체함. 

-replace_if() ; [first, last) 범위에서 조건에 따라 new_value로 바꾼다.

ex) 홀수를 0으로 바꿈.

bool isodd(int i) { return (i%2)==1 ; }

std::replace_if( myvec.begin(), myvec.end(), isodd, 0) ;

-replace_copy, replace_copy_if ; replace와 비슷하지만 원본 자체를 변경하지 않고, 대상으로 복사한다.

std::replace_copy( myints, myints+8, myvec.begin(), 20, 99) ;    // myints에서 20을 99로 바꾸어 myvec에 복사.

std::replace_copy_if( foo.begin(), foo.end(), bar.begin(), isodd, 0) ;

-fill ; 특정 값으로 채움.

fill(first, last, value)

std::vector<int> myvec(8) ;            // 0,0,0,0,0,0,0,0

std::fill(myvec.begin(), myvec.begin()+4, 5) ;    // 5,5,5,5,0,0,0,0

std::fill(myvec.begin()+3, myvec.end()-2, 8) ;    // 5,5,5,8,8,8,0,0

-fill_n ; 특정 값으로 채움. 시작위치, 개수, 값.

std::fill_n(myvec.begin(), 4, 20) ;    // 앞에서 부터 4개를 20으로 채움.

std::fill_n(myvec.begin()+3, 3, 30) ;    // 인덱스3번(네번째요소) 부터 3개를 30으로 채움.

-generate ; 컨테이너의 일부 범위를 gen함수로 만든 값으로 채움.

include ; iostream, algorithm, vector, 

ctime ; for std::time

cstdlib ; for std::rand, std::srand

int RandomNumber() { return (std::rand()%100) ; }

struct c_unique() {

   int current ;

   c_unique() { current=0 ; }

   int operator() { return ++current ; }

} UniqueNumber ;

std::srand( unsigned(std::time(0)) ) ;

std::vector<int> myvec(8) ;

std::generate(myvec.begin(), myvec.end(), RandomNumber) ; // 0~99범위 랜덤하게 8개.

std::generate(myvec.begin(), myvec.end(), UniqueNumber) ;    // 1,2,3,4,5,6,7,8

-generate_n(first, n, generator) ; 상동.

-remove ; 범위에서 값과 일치하는 것을 삭제하여 붙임. 뒤에는 빈공간. 삭제된 결과의 마지막 위치를 리턴.  원본 size가 수정되지 않음. 주의!

remove(first, last, val) ;

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

int* pbegin = myints ;

int* pend = myints+sizeof(myints)/sizeof(int) ;

pend = std::remove( pbegin, pend, 20) ;    // 20을 삭제.  10,30,30,10,10,?,?,?

// pend는 마지막 10 뒤의 ? 위치.

-remove_if(first, last, UnaryPredicate pred) ;

pred가 true리턴하면 요소 삭제. 삭제방식은 remove와 같다.

pend = std::remove_if(pbegin, pend, isodd) ;

bool isodd(int i) { return (i%2)==1 ; } 

-remove_copy(first, last, result, val) ;

원본을 수정하지 않고, 결과를 복사한다.

std::vector<int> myvec(8) ;

std::remove_copy( myints, myints+8, myvec.begin(), 20) ;    // myints의 해당 범위에서 20을 제외하고 복사함.

myvec에서 복사된 크기를 알려면 리턴결과의 iterator를 통해 길이 계산이 필요함. 위에서 pend 

std::vector<int>::iterator iend = std::remove_copy(...) ;

데이터 유효범위는 [myvec.begin(), iend) 이다.

-remove_copy_if(first, last, result, UnaryPredicate pred) ;

-unique(first, last) ; 연속된 중복 제거. 주의; 전체에서 유일한 값이 아님.  컨테이너 크기는 변하지 않음.

// myvec ; 10,20,20,20,30,30,2020,10

it = std::unique( myvec.begin(), myvec.end()) ;    // 10,20,30,20,10,?,?.?,?

// shrink 하려면

myvec.resize( std::distance(myvector.begin(), it) ) ;    // 10,20,30,20,10

-unique(first, last, BinaryPredicate pred) ;

-unique_copy(first, last, result) ;

-unique_copy(first, last, result, pred) ;

-reverse() ; 순서를 거꾸로 만든다.

reverse(first, last) ;

myvec ; 1,2,3,4,5

std::reverse(myvec.begin(), myvec.end()) ;    // 5 4 3 2 1

-reverse_copy(first, last, result) ;    

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

std::vector<int> myvec(5) ; // or myvec.resize(5) ;

std::reverse)copy(myints, myints+5, myvec.begin()) ;

// 원본은 그대로고, myvec은 5 4 3 2 1

-rotate(first, middle, last) ;    // 쉬프트 시킨다.

middle부터 있는 데이터들을 first위치부터 일련되게 이동한다.

// myvec ; 1 2 3 4 5 6 7 8 9

std::rotate( myec.begin(), myvec.begin()+3, myvec.end() ); // 인덱스3을 인덱스0으로 이동. 일련되게 모든 요소를 이동.

// myvec ; 4 5 6 7 8 9 1 2 3

// left shift

std::rotate(myvec.begin(), myvec.begin()+1, myvec.end()) ;    // 2 3 4 5 6 7 8 9 1

// right shift

std::rotate(myvec.begin(), myvec.end()-1, myvec.end()) ;     // 9 1 2 3 4 5 6 7 8

-rotate_copy(first, middle, last, result) ; 결과를 복사. 원본 유지

-random_shuffle(first, last) ;순서를 랜덤하게 섞는다.

std::random_shuffle(myvec.begin(), myvec.end()) ;

랜덤함수 지정 가능.

std::random_shuffle(myvec.begin(), myvec.end(), gen) ;

int gen(int i) { return std::rand()%i; }     // 0~ (i-1) 까지 랜덤.

마지막원소를 gen(n)으로 발생시킨 인덱스 원소와 바꾸고, 마지막 전 원소를 gen(n-1)의 인덱스와 바꾸고 계속 한다.

-shuffle(first, last, g) ; C++11

순서를 랜덤하게 섞는다. 랜덤은 uniform random number generator를 사용한다.