일반 클래스의 비교 함수 전달

Question

배열을 사용하여 힙을 사용하는 우선 순위 큐를 만들고 싶습니다. 우선 순위 큐는 클라이언트가 비교 함수를 통과하는 한 모든 데이터 형식을 허용합니다. 두 유형을 비교하는 생성자입니다.

compare 함수를 매개 변수로 사용하는 생성자는 어떻게 만들 수 있습니까? 또한 확인할 때 비교 함수를 호출 할 수있는 방법은 무엇입니까?

return (Type a==Type b) 

예 :

struct node{ 
    string val1; 
    string val2; 
    vector<node *> connectedNodes; 
}; 

int compareNode(node a,node b){ 
//describe the compare 
} 

int main(){ 
PQueue<node> q(compareNode); 
} 

PQueue 클래스는 배열로 구현됩니다. 추가, 버블 링 - 업 (bobling-up), heapifying은 두 ValType을 비교해야하는데 compareNode를 사용하여 이들을 비교하기를 원합니다.

Answer 1

이 작업을 수행 할 필요가 없습니다. 배열을 사용하지 말고 C++에서 STL 라이브러리의 기본 우선 순위 대기열을 사용하십시오. 그것은 당신이 변경할 수있는 자체 비교 기능이 있습니다.

참조 : http://www.cplusplus.com/reference/queue/priority_queue/

또한 (알고리즘 사용에 대한) 탑 코더 자습서를 볼 수 있습니다.

Answer 2

먼저 간단한 대답을 한 다음 더 다양한 대답을 알려주십시오.

매개 변수의 유형을 포인터 함수의 유형으로 선언하여 함수를 매개 변수로 간단히 전달할 수 있습니다. 함수에 대한 포인터 유형의 변수를 가질 수도 있습니다. 예를 들어, 경우 함수의 선언은

int compareNode(node a, node b) 

는 다음과 같이 뭔가를 할 수 있습니다 :

#include <iostream> 
#include <vector> 
#include <string> 
using namespace std; 

struct node{ 
    string val1; 
    string val2; 
    vector<node *> connectedNodes; 
}; 

int compareNode(node a,node b){ 
//describe the compare 
return a.val2.compare(b.val2); // or any other code 
} 

template <class T> 
class PQueue { 
    protected: 
    // this declares a protected member named compareFunction of type pointer to a function which takes 2 T parameters and returns a int. Note that all the parenthesis are mandatory 
    int (*compareFunction)(T, T); 

    public: 

    PQueue (int (*compareFunctionParameter)(T, T)) : compareFunction(compareFunctionParameter) { 
     // this constructor receives a pointer to function and initializes it's member to that pointer. If the constructor initialization list confuses you, you can read 'compareFunction = compareFunctionParameter ' 
    } 

    int someMethod() { 
    // call the function through the pointer you have: 
    node n1, n2; 
    n1.val1 = "node1_val1"; 
    n1.val2 = "zzz"; 

    n2.val1 = "node2_val1"; 
    n2.val2 = "aaa"; 
    return compareFunction(n1, n2); 
    } 
}; 

int main() { 
    PQueue<node> pq(compareNode); 
    cout << pq.someMethod() << endl; 
    return 0; 
} 

http://ideone.com/EPjbya

희망이 당신이 사용할 수 있습니다.

이제 더 다양한 예를 살펴보십시오.

C++ 11은 람다를 도입합니다. http://www.cprogramming.com/c++11/c++11-lambda-closures.htmlhttp://www.stroustrup.com/C++11FAQ.html#lambda

#include <iostream> 
#include <vector> 
#include <string> 
#include <functional> 
using namespace std; 

struct node{ 
    string val1; 
    string val2; 
    vector<node *> connectedNodes; 
}; 

int compareNode(node a,node b){ 
//describe the compare 
return a.val2.compare(b.val2); // or any other code 
} 

template <class T, class Comparator> 
class PQueue { 
    protected: 
    Comparator compareFunction; 

    public: 

    PQueue (Comparator compareFunctionParameter) : compareFunction(compareFunctionParameter) { 
    } 

    int someMethod() { 
    // call the function 
    node n1, n2; 
    n1.val1 = "node1_val1"; 
    n1.val2 = "zzz"; 

    n2.val1 = "node2_val1"; 
    n2.val2 = "aaa"; 
    return compareFunction(n1, n2); 
    } 
}; 

int main() { 
    // queue with pointer to function 
    PQueue<node, int (*)(node, node)> pq(compareNode); 
    cout << pq.someMethod() << endl; 

    // queue with lamda (anonimous function) 
    PQueue<node, std::function<int (node, node)>> pq_lambda([](node a, node b) -> int {return a.val1.compare(b.val1);}); 
    cout << pq_lambda.someMethod() << endl; 
    return 0; 
} 

당신은 C++ 11 표준이 코드를 컴파일 할 필요가있다.

여기서 템플릿 비교기는 함수와 람다에 대한 포인터가 될 수 있습니다. 람다에 관심이 있다면 위에 제공된 두 개의 링크를 시작해야합니다.