priority_queues in C++

Question

Je suis un peu un noob aux itérateurs. J'essaie de créer une priority_queue, triée par longueur de vecteur. (Par exemple, je veux pop afin de les vecteurs les plus longs.)

Ceci est la ressource que je l'ai utilisé:

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

J'ai essayé ce code, et il semble faire ce que Je veux:

// 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; 
} 

Mes questions: 1. Est-ce que cela me donne toujours le vecteur le plus long? Cela semble être le cas. 2. Sinon, que dois-je faire d'autre? La syntaxe de l'itérateur sur la page de référence est comme ... o_O

Merci!

Answer 1

priority_queues en C++ utilise un objet de comparaison pour déterminer quel est le plus grand élément. Par défaut, il s'agit de l'opérateur < (inférieur à) sur les objets contenus dans la file d'attente priority - vous devez donc savoir ce que < signifie sur les vecteurs. Cette page http://www.cplusplus.com/reference/stl/vector/operators/ a quelques informations à ce sujet.

Answer 2

Non, le code ne répond pas à vos attentes. Il compare les vecteurs lexicographiquement plutôt que par la longueur. Pour comparer par longueur utiliser un comparateur personnalisé:

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; 

Notez également que vos magasins de file d'attente des copies des vecteurs, ce qui pourrait être pas si efficace parce qu'il peut les copier quand il construit le tas. Stockez des pointeurs (intelligents) à la place.