Post thumbnail

김대리, 너무 팡션? 사용하지 마세요. 성능 잡는 데는 Functor가 있읍니다.

· by 박승재

함자(Functor)는 “함수를 흉내 내는 객체“입니다.

객체이기 때문에 struct나 class 문법을 이용해 정의하고, 함수처럼 동작해야 하므로 () 연산자를 오버로딩합니다.

함수 객체 클래스 자체를 타입으로 활용 가능하기 때문에 C++ 템플릿과 결합하여 사용할 수 있습니다.

또한, 함자는 함수와 달리, 함수 인자에 포인터 형식으로 전달되지 않기 때문에 인라인(Inline)되어 성능 향상을 기대할 수도 있습니다.

인라인(Inline)

컴파일러가 자주 사용되는 간결한 함수를, 해당 함수 호출 코드에 복사-붙여넣기 하여 함수 호출 생략을 통해 성능을 끌어올리는 기법

Before:

int addmul(int a, int b, int c) {
    return a + (b * c);
}

int main() {
    int i = addmul(1, 2, 3);
    return 0;
}

After:

int main() {
    int i = 1 + (2 * 3);
    return 0;
}

Functor vs Function

Functor Function
struct 또는 class로 생성된 객체 함수
멤버 변수를 이용해 각 Functor마다 다른 값을 저장할 수 있음 전역 변수를 이용해 값을 저장
인라인 가능(더 빠르게 동작) 함수 포인터는 인라인 불가

Functor는 일반적으로 구조체에 () 연산자를 오버로딩하여 구현합니다.

struct Functor {
    void operator()(...) const {
        // ...
    }
};

구조체의 기본 접근제어자는 public이기 때문에, class보다 struct를 사용합니다.

Functor의 활용

배열을 내림차순으로 정렬:

#include <algorithm>
#include <iostream>

struct Compare {
    bool operator()(int a, int b) const {
        return a > b;
    }
};

int main() {
    int B[10] = { 1, 0, 2, 5, 8, 9, 4, 7, 3, 6 };

    // 내림차순: Functor
    std::sort(B, B + 10, Compare());
    for (const int i : B) {
        std::cout << i << ' '; // 9 8 7 6 5 4 3 2 1 0
    }
    std::cout << '\n';
    return 0;
}

STL을 이용한 내림차순 정렬:

#include <algorithm>
#include <functional>
#include <iostream>

int main() {
    int B[10] = { 1, 0, 2, 5, 8, 9, 4, 7, 3, 6 };

    // 내림차순: STL Functor
    std::sort(B, B + 10, std::greater<int>());
    for (const int i : B) {
        std::cout << i << ' ';
    }
    std::cout << '\n';
    return 0;
}

functional 헤더에는 std::greater와 std::less 등의 Functor가 존재

std::greater는 Functor로 구현되어 있습니다.

Possible implementation:

constexpr bool operator()(const T &lhs, const T &rhs) const {
    return lhs > rhs; // assumes that the implementation uses a flat address space
}

참고: std::greater

타입으로 사용되는 Functor:

#include <functional>
#include <iostream>
#include <queue>
#include <vector>

int main() {
    int A[10] = { 3, 6, 5, 8, 2, 1, 0, 7, 9, 4 };

    std::cout << "A: ";
    for (int i : A) {
        std::cout << i << ' ';
    }
    std::cout << '\n';

    // 오름차순 우선순위 큐
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq(A, A + 10);
    pq.push(15);
    pq.push(-3);
    pq.push(13);
    pq.push(14);
    pq.push(-2);
    pq.push(11);
    pq.push(-4);
    pq.push(-5);
    pq.push(12);
    pq.push(-1);

    std::cout << "pq: ";
    while (!pq.empty()) {
        std::cout << pq.top() << ' ';
        pq.pop();
    }
    std::cout << '\n';
    return 0;
}

Fuctor는 구조체이기 때문에 템플릿 인자로 전달될 수 있습니다.

std::priority_queue의 세 번째 템플릿 인자 typename Compare의 기본값은 std::less이며, Compare는 priority_queue 생성자에서 make_heap으로 전달됩니다.

template<typename T, typename Container = std::vector<T>, typename Compare = std::less<typename Container::value_type>>
class priority_queue {
public:
    template<class InputIt>
    priority_queue(InputIt first, InputIt last, const Compare &compare = Compare());
};

참고: std::priority_queue

template<typename RandomIt, typename Compare>
constexpr void make_heap(RandomIt first, RandomIt last, Compare comp);

참고: std::make_heap