C++中的priority_queues

Question

我对迭代器来说有点像菜鸟.我正在尝试创建一个priority_queue,按矢量长度排序.(即,我想按顺序弹出最长的矢量.)

这是我一直在使用的资源:

http://www.cplusplus.com/reference/stl/priority_queue/priority_queue/

我尝试了这个代码,它似乎做了我想要的:

// testing to make sure that a priority queue will always give me the longest vector
priority_queue< vector<int> > q;

vector<int> f;
f.push_back(1);

vector<int> g;
g.push_back(19);
g.push_back(80);

vector<int> y;
y.push_back(62);
y.push_back(10);
y.push_back(11);

q.push(f);
q.push(g);
q.push(y);

vector<int> out = q.top();

for (unsigned int i = 0; i < out.size(); i++) {
    cout << out[i] << endl;
}

我的问题:1.这总是给我最长的载体吗？这似乎是这种情况.如果没有,我还能做什么？参考页面上的迭代器语法类似于... o_O

谢谢!!

Answer 1

不,代码不符合您的期望.它按字典顺序比较矢量而不是长度.要按长度比较,请使用自定义比较器:

struct LengthCompare {
    bool operator() (const vector<int>& a, const vector<int>& b) {
        return a.size() < b.size();
    }
};

priority_queue<vector<int>, vector<vector<int> >, LengthCompare> q;

另请注意,您的队列存储了向量的副本,这些副本可能效率不高,因为它可能在构建堆时复制它们.改为存储(智能)指针.