Why priority_queue<> template self-defined compare function need a wrapper struct


  • 0
    B

    Simple C++ with overloaded priority_queue and BFS, the tricky part is wrapper struct for dvComp, we need an object/class type here, and need to overload operator ().

    Should we use function object here?
    Does any compiler support lambda in priority_queue template?

    Thanks!

    https://msdn.microsoft.com/en-us/library/aa985932.aspx
    http://en.cppreference.com/w/cpp/utility/functional/function

    	vector<int> closestKValues(TreeNode* root, double target, int k) {
    	typedef struct {
    		double dist;
    		int val;
    	} DistVal;
    
    	struct dvComp {
    		bool operator() (const DistVal& a, const DistVal& b) const {
    			return a.dist < b.dist;
    		}
    	};
    
    	assert(root != NULL);
    	priority_queue < DistVal, vector<DistVal>, dvComp> topk;
    	DistVal closestVal = { abs(root->val - target), root->val };
    	queue<TreeNode*> qTN;
    
    	// BFS All
    	qTN.push(root);
    	while (qTN.size()) {
    		TreeNode *rt = qTN.front();
    		if (rt) {
    			DistVal tmp = { abs(rt->val - target), rt->val };
    			topk.push(tmp);
    			if ((int)topk.size()>k) topk.pop();
    			qTN.push(rt->left);
    			qTN.push(rt->right);
    		}
    		qTN.pop();
    	}
    
    	vector<int> ret;
    	for (int i = 0; i<k; i++) {
    		ret.push_back(topk.top().val);
    		topk.pop();
    	}
    
    	return ret;
    }

  • 1
    X

    You could use function object here, as shown below. It is supposed to be supported in both the latest GCC and VC++ compiler.

    auto lessDistVal = [](DistVal const &d1, DistVal const &d2) {return d1.dist < d2.dist;};
    priority_queue<DistVal, vector<DistVal>, decltype(lessDistVal)> topk(lessDistVal);
    

    As for the request about "why ... need a wrapper struct", it is because the default "Compare" of the priority_queue does not support the type "DistVal" and you need to provide your own "Compare" version. The following is the priority_queue definition obtained from http://en.cppreference.com/w/cpp/container/priority_queue.

    template<
        class T,
        class Container = std::vector<T>,
        class Compare = std::less<typename Container::value_type>
    > class priority_queue;
    

    The "T", "Container" and "Compare" stand for type rather than object. That is why we "need a wrapper struct" and why we use the 'decltype' to obtain the type and pass this type in (instead of directly passing the object "lessDistVal ").


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.