C++ 펑터의 장점 - 상태 유지하기

Question

펑터에 대한 전체적인 아이디어를 연구했지만 불행히도 일반적인 함수에 비해 펑터의 실질적인 이점을 이해할 수 없습니다.

일부 학술적 글에 따르면 펑터는 상태와 다른 기능을 유지할 수 있습니다. 누구나 간단하고 이해하기 쉬운 예제로이 내용을 자세히 설명 할 수 있습니까?

나는 전형적인, 일반적인 기능이 동일한 것을 할 수없는 이유를 정말로 이해할 수 없다. 초심자 질문의이 종류를 위해 진짜로 유감 스럽다.

Answer 1

정말 간단한 데모로 빠른 정렬을 고려해 보겠습니다. 값 (일반적으로 "피벗"이라고 함)을 선택하고 입력 컬렉션을 피벗보다 작게 비교하고 피벗 보다 크거나 같은 값으로 분리합니다.

표준 라이브러리에는 이미 파티션을 수행 할 수있는 std::partition이 있습니다. 컬렉션을 지정된 조건을 만족하는 항목과 그렇지 않은 항목으로 분리합니다. 따라서 우리는 파티셔닝을하기 위해 적절한 술어를 제공해야합니다.

이 경우 간단한 비교가 필요합니다 (예 : return x < pivot;). 피벗 값을 매번 전달하는 것은 어려워집니다. std::partition 그냥 컬렉션에서 값을 전달하고 묻습니다 : "이 테스트 통과 여부?" std::partition에 현재 피벗 값이 무엇인지 말할 수있는 방법이 없으며 호출 될 때이를 루틴에 전달해야합니다. 물론 은 일 수 있습니다 (예 : Windows의 많은 열거 함수가 이러한 방식으로 작동합니다). 그러나 꽤 어색해집니다.

std::partition을 호출 할 때 이미 피벗 값을 선택했습니다. 우리가 원하는 것은 ... 그 값을 비교 함수에 전달할 매개 변수 중 하나에 바인딩하는 것입니다. 그 한 가지 정말 추한 방법은 전역 변수를 통해 그것을 "통과"하는 것입니다 :

int pivot; 

bool pred(int x) { return x < pivot; } 

void quick_sort(int *begin, int *end) { 
    if (end - begin < 2) 
     return; 

    pivot = choose_pivot(begin, end); 

    int *pos = std::partition(begin, end, pred); 
    quick_sort(begin, pos); 
    quick_sort(pos, end); 
} 

I 정말 우리가 오히려 이것에 대한 글로벌을 사용하지 않는 게 좋을 것을 지적 할 필요가 없습니다 희망 우리가 도울 수 있다면. 이것을 피하는 쉬운 방법은 function 객체를 만드는 것입니다. 우리는 개체를 만들 때 우리는 현재의 피벗 값을 전달하고, 객체의 상태로 그 값을 저장 :이 추가 코드의 작은 비트를 추가했습니다

class pred { 
    int pivot; 
public: 
    pred(int pivot) : pivot(pivot) {} 

    bool operator()(int x) { return x < pivot; } 
}; 

void quick_sort(int *begin, int *end) { 
    if (end-begin < 2) 
     return; 

    int pivot = choose_pivot(begin, end); 

    int *pos = std::partition(begin, end, pred(pivot));   
    quick_sort(begin, pos); 
    quick_sort(pos, end); 
} 

,하지만 대가로 우리는 global-을 제거했습니다 - 상당히 합리적인 교환.

물론 C++ 11에서는 더 나은 결과를 얻을 수 있습니다. 언어에는 "lambda expressions"이 추가되어 우리를위한 클래스를 만들 수 있습니다. 이 사용하여, 우리의 코드는 다음과 같이 보입니다 :

이

void quick_sort(int *begin, int *end) { 
    if (end-begin < 2) 
     return; 

    int pivot = find_pivot(begin, end); 

    auto pos = std::partition(begin, end, [pivot](int x) { return x < pivot; }); 
    quick_sort(begin, pos); 
    quick_sort(pos, end); 
} 

이것은 우리가/클래스를 지정 함수 객체를 생성하는 데 사용구문을 변경,하지만 그것은 거의 여전히 앞의 코드와 같은 기본적인 아이디어 다음은 컴파일러는 생성자와 operator()이있는 클래스를 생성합니다. 대괄호로 묶인 값은 생성자에 전달되며 (int x) { return x < pivot; }은 기본적으로 해당 클래스 에 대한 operator()의 본문이됩니다.

이렇게하면 코드를 훨씬 쉽게 작성하여 과을 훨씬 쉽게 읽을 수 있습니다. 그러나 객체를 생성하고 생성자의 일부 상태를 "캡처"하고 오버로드 된 비교를 위해 operator().

물론 비교는 우연히 정렬과 같은 것에 필요한 것입니다. 은입니다. 일반적으로 람다 식과 함수 객체를 공통적으로 사용하지만 더 확실하게 제한하지는 않습니다. 또 다른 예를 들어, 복식 컬렉션을 "정규화"하는 것을 고려해 보겠습니다. 우리는 그 다음 가장 큰 하나를 찾아 그하여 컬렉션의 모든 값을 나눌, 각각의 항목은 범위 0.0 ~ 1.0에 있지만 그들이 이전에 가지고 모든 서로 같은 비율을 유지 :

double largest = * std::max_element(begin, end); 
std::for_each(begin, end, [largest](double d) { return d/largest; }); 

여기에도 비슷한 패턴이 있습니다. 몇 가지 관련 상태를 저장하는 함수 객체를 만든 다음이 함수 객체의 operator()을 반복 적용하여 실제 작업을 수행합니다.

---

1. 우리는 대신보다 작거나 같은, 더 큰으로 분리 할 수있다. 또는 우리는 세 가지 그룹을 만들 수 있습니다 :보다 작음, 같음, 더 큼. 후자는 많은 복제본이있을 때 효율성을 향상시킬 수 있지만, 현재로서는 신경 쓰지 않습니다.
2. 람다 표현식에 관해서는 이것보다 훨씬 더 알아야 할 것이 있습니다 - 저는 어떤 것을 단순화하고 있으며 현재 우리가 신경 쓰지 않는 다른 것들을 완전히 무시하고 있습니다.