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를 사용한다.
