C++ fonction lambda dans priority_queue avec capture par référence

Question

Je résolvais un problème d'algorithme - "trouver k-ème nombre laid", ci-dessous est l'énoncé du problème et ma mise en œuvre.

Write a program to find the n-th ugly number. 
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. 
For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers. 

vector<int> tmp(1,1); 
vector<int> primes({2,3,5}); 
vector<int> indices(3, 0); 
// lambda function pass in variables are captured by reference 
priority_queue<int, vector<int>, function<bool(const int&, const int&)>> pq([&](const int& a, const int& b){ 
    return primes[a] * tmp[indices[a]] > primes[b] * tmp[indices[b]]; 
}); 
pq.push(0); pq.push(1); pq.push(2); 
while(tmp.size() <= 3) { // find the first three ugly number 
    int primeIndex = pq.top(); 
    pq.pop(); 
    int nextval = primes[primeIndex] * tmp[indices[primeIndex]]; 
    pq.push(primeIndex + 1); 
    indices[primeIndex]++; 

    while(!pq.empty() && primes[pq.top()] & tmp[indices[pq.top()]]) { 
     primeIndex = pq.top(); 
     pq.pop(); 
     pq.push(primeIndex + 1); 
     indices[primeIndex]++; 
    } 
    cout << nextval << endl; 
    tmp.push_back(nextval); 
} 
return 0; 

L'utilisation de priority_queue est une optimisation pour cette solution. Priority_queue trouve le numéro "next laid" en O (logN). Priority_queue utilise l'index des nombres premiers [] comme éléments. Il utilise une fonction lambda comme comparateur et capture toutes les variables externes par référence. J'ai testé mon code pour sortir les 3 premiers nombres moche (devrait être 2, 3, 4), mais mon code m'a donné "2, 6, 0". Je pense qu'il y a quelque chose qui ne va pas dans ma fonction lambda dans priority_queue, mais je n'ai pas pu trouver pourquoi. Quelqu'un pourrait-il me donner un indice sur la résolution de mon bug? Merci beaucoup.

Answer 1

Le problème immédiat avec votre code est que vous accédez au vecteur tmp en dehors des limites. Vous utilisez des éléments de indices comme indices dans tmp, et vous incrémentez les éléments de indices à plusieurs endroits dans l'itération de la boucle while externe (une fois avant la boucle while interne, et potentiellement une ou plusieurs fois dans la boucle while interne), et vous augmentez uniquement la taille de tmp à la fin de l'itération de la boucle while externe. En attendant, dans l'état de la boucle while interne, vous indexez tmp avec les indices que vous avez peut-être augmenté (potentiellement plusieurs fois) avant d'augmenter la taille de tmp.