C++中的仿函数
class Solution { public: struct cmp { bool operator()(const pair<string,int>&kv1,const pair<string,int>&kv2) { if(kv1.second<kv2.second) return true; if(kv1.second==kv2.second&&kv1.first>kv2.first) return true; return false; } }; vector<string> topKFrequent(vector<string>& words, int k) { map<string,int>mp; for(auto& w:words) { mp[w]++; } priority_queue<pair<string,int>,vector<pair<string,int>>,cmp>pq(mp.begin(),mp.end()); vector<string>res; while(k--) { res.push_back(pq.top().first); pq.pop(); } return res; } };
对于以上代码一开始存在一点疑问，为什么自定义一下堆的排序规则还需要定义一个类、结构体然后再在类里面重写
operator()，于是我跑去看了一下文档对priority_queue的定义。
嚯，比较器是一个类
这里的
value_type是一个模板参数。可以看到
less<>当中没有具体的参数，typename是显示的告诉编译器后面是一个类型，这里是告诉编译器，在Container这个类(容器)当中的value_type是一个类型。
less是一个函数对象（即仿函数）或者函数模板，它不需要具体的变量名来执行比较操作。
<>用于指定类型，好让less的模板参数识别类型。
template <class T> struct less : binary_function <T,T,bool> { bool operator() (const T& x, const T& y) const { return x<y;//升序，小的在前 } };
再来看之前模拟实现的priority_queue代码，真的是边学边忘。
template<class T, class Container = vector<T>,class Compare=std::less<T>> class priority_queue { public: priority_queue() {} template<class InputIterator> priority_queue(InputIterator first, InputIterator last) { while (first != last) { _con.push_back(*first); first++; } for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--) { Adjust_down(i); } } size_t size() { return _con.size(); } void Adjust_up(size_t child) { Compare compare; size_t parent = (child - 1) / 2; while (child>0) { if (compare(_con[parent],_con[child])) { std::swap(_con[parent], _con[child]); child = parent; parent = (child - 1) / 2; } else { break; } } } void Adjust_down(size_t parent) { Compare com; size_t child = parent * 2 + 1; while (child < _con.size()) { // 选出左右孩子中大的那一个 //if (child+1 < _con.size() && _con[child+1] > _con[child]) //if (child + 1 < _con.size() && _con[child] < _con[child + 1]) if (child + 1 < _con.size() && com(_con[child], _con[child + 1])) { ++child; } //if (_con[child] > _con[parent]) //if (_con[parent] < _con[child]) if (com(_con[parent], _con[child])) { std::swap(_con[child], _con[parent]); parent = child; child = parent * 2 + 1; } else { break; } } } void push(const T& val) { _con.push_back(val); Adjust_up(_con.size()-1);//调堆 } void pop() { std::swap(_con[0], _con[_con.size() - 1]); _con.pop_back(); Adjust_down(0); } const T& top()const { return _con[0]; } bool empty() { return (_con.size() == 0); } bool empty() const { return (_con.size()==0); } private: Container _con;//容器 };
将重点抠出来
template<class T, class Container = vector<T>,class Compare=std::less<T>> • 1
void Adjust_down(size_t parent) { Compare com;//比较器 size_t child = parent * 2 + 1; while (child < _con.size()) { if (child + 1 < _con.size() && com(_con[child], _con[child + 1])) { ++child; } if (com(_con[parent], _con[child])) { std::swap(_con[child], _con[parent]); parent = child; child = parent * 2 + 1; } else { break; } } }
Compare com;//比较器 com(_con[child], _con[child + 1]);//直接调用重载的运算符operator()
就是这样通过重载
operator()来改变排序规则的。
总结：less是一个类、通过调用operator()来实现排序规则
