C++ STL - Algorithm[4]
이번 시간에는 STL의 알고리즘에 관해 살펴보겠습니다.
Algorithm basic
1. 멤버 함수가 아닌 일반 함수로 되어 있음
- STL 알고리즘은 특정한 컨테이너가 아닌 다양한 컨테이너에 대해서 사용 할 수 있는 일반 함수로 되어 있다.
2. STL 알고리즘을 사용하기 위한 헤더
3. 알고리즘은 컨테이너를 알지 못함
- remove를 호출해도 실제 제거가 되지 않음(컨테이너 마다 메모리 해제 방법이 다르기 때문)
int main()
{
vector<int> v = { 1,2,3,1,2,3,1,2,3,1 };
auto p = remove(begin(v), end(v), 3);
show(v); // 1,2,1,2,1,2,1, 2,3,1
v.erase(p, end(v)); // 지울 때는 멤버 함수
show(v); // 1,2,1,2,1,2,1
return 0;
}
4. 알고리즘 보다 컨테이너의 멤버 함수가 좋은 경우가 있음
- list는 요소 제거시 메모리를 재정렬 하도록 처리 하는 것이 더 비효율적임
int main()
{
list<int> v = { 1,2,3,1,2,3,1,2,3,1 };
v.remove(3); // 당기는 것이 아니라 메모리 제거
return 0;
}
Algorithm & function
1. Functor
- 함수 객체 : () 연산을 재정의 해서 함수처럼 사용하는 모든 객체
- 장점 : 함수 객체는 인라인 치환 가능, 상태를 갖을 수 있음
#include <iostream>
using namespace std;
// ()를 사용해서 호출하는 것
// 1. 함수
// 2. 함수 포인터
// 3. ()를 재정의한 클래스
// 4. 람다표현식...
struct Plus
{
int operator()(int a, int b) const
{
return a + b;
}
};
int main()
{
Plus p;
int n = p(1,2); // p.operator()(1,2)
cout << n << endl;
// a + b; // a.operator+(b)
// a - b; // a.operator-(b)
// a(); // a.operator()()
// a(1,2);// a.operator()(1,2)
}
2. 알고리즘에 Functor 전달
- STL 알고리즘은 함수를 인자로 가지는 경우가 있음(전달하는 함수의 매개변수는 보통 2개를 넘지 않음)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
vector<int> v = {1,2,3,4,5,6,7,8,9,10};
// 1. 일반 함수 전달.
for_each(begin(v), end(v), foo );
// 2. 함수 객체를 전달.
for_each(begin(v), end(v), s );
// 3. 람다표현식
for_each(begin(v), end(v), [](int a){ cout << a << endl;} );
return 0;
}
- transform 알고리즘 : 인자로 전달된 모든 요소에 연산을 적용 후 다른 컨테이너에 복사
- 단항함수 버전과 이항함수 버전 존재
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <functional> // plus<>
#include "ecourse_stl.hpp"
using namespace std;
int foo( int a, int b) { return a + b;}
int main()
{
list<int> s1 = {1,2,3,4,5};
list<int> s2 = {1,2,3,4,5};
list<int> s3 = {0,0,0,0,0};
//transform( begin(s1), end(s1), begin(s2) , foo);
//transform( begin(s1), end(s1), begin(s2), begin(s3), foo);
//transform( begin(s1), end(s1), begin(s2), begin(s3),
// multiplies<int>());
transform( begin(s1), end(s1), begin(s2), begin(s3),
[](int a,int b) { return a + b;});
return 0;
}
Algorithm의 변형
1. 조건자(Predicator)
- bool 타입을 리턴 하는 함수 객체
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool foo( int a) { return a % 3 == 0;}
int main()
{
vector<int> v = { 6, 9, 3, 1, 2};
// find 는 정말 generic 한가 ?
// 주어진 구간에서 첫번째 나오는 3의 배수를 찾고 싶다.
//auto p = find( begin(v), end(v), 3);
//auto p = find_if( begin(v), end(v), foo);
auto p = find_if( begin(v), end(v),
[](int a) { return a % 3 == 0;});
cout << *p << endl;
}
2. STL 알고리즘의 4가지 형태
- 기본 버전
- 조건자 버전 : _if
- 복사 버전 : _copy
- 조건자 복사 버전 _copy_if
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
vector<int> v1 = {1,2,3,4,5,6,7,8,9,10};
vector<int> v2 = {0,0,0,0,0,0,0,0,0,0};
// 기본 버전
//remove( begin(v1), end(v1), 3);
// 조건자 버전
//remove_if( begin(v1), end(v1), [](int a) { return a % 3 == 0;});
// 복사 버전. 리턴 값 p는 v2의 반복자..
//auto p = remove_copy( begin(v1), end(v1), begin(v2), 3);
//
auto p = remove_copy_if( begin(v1), end(v1), begin(v2),
[](int a) { return a % 3 == 0;});
v2.erase(p, end(v2));
}
3. std::bind -> 함수 인자를 미리 설정 해 놓을 수 있음
- find_if에 이항 함수를 전달 하고 싶을 때
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
using namespace std::placeholders;
// 4항 함수
void foo( int a, int b, int c, int d)
{
printf("%d, %d, %d, %d\n", a, b, c, d);
}
int main()
{
foo(1,2,3,4); // 4항 함수..
// 4항 함수 => 2항으로
bind(&foo, 10, _2, _1, 20 )(1,2);// 10, 2, 1, 20
// 4항 함수 => 3항으로
bind(&foo, _3, _2,_1, 100 )(30,20,10); // 10, 20, 30, 100
// 4항을 => 무항으로..
bind(&foo, 1,2,3,4)();
modulus<int> m;
cout << m(10,3) << endl; // 10 % 3;
bind(m, 10, 3)(); // 10 % 3
bind(m, _1, 3)(7); // 10 % 3
int x[3] = { 1,2,3};
// 3의 배수가 아닌것 찾기.
auto p = find_if( x, x+3, bind(m , _1 , 3 ) );
cout << *p << endl; // 1
}