이번 시간에는 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
}