Обновление std :: set для сохранения только наименьших значений

Question

Для некоторого алгоритма мне нужно вызвать функцию f на все перестановки n -элемент набора целых чисел в диапазоне от 1 до n. Наконец, меня интересуют 100 перестановок, дающих наименьшее значение f.

Лучшим решением, которое я смог решить, было следующее. Но это имеет серьезный недостаток. Пока n увеличивается fPerm может потреблять большой объем памяти.

Какое оптимальное решение для обрезки fPerm, так что оно содержит только лучшие 100 найденных решений?

#include <vector> 
#include <set> 
#include <algorithm> 
#include <numeric> 
#include <boost/random.hpp> 

boost::random::mt19937 rng; 

// Actually, f is a very complex function, that I'm not posting here. 
double f(const std::vector<int>& perm) { 
    boost::random::uniform_real_distribution<> gen; 
    return gen(rng); 
} 

typedef std::pair<std::vector<int>, double> TValue; 

void main(int argc, int args) { 
    auto comp = [](const TValue& v1, const TValue& v2) { return v1.second < v2.second; }; 
    std::set<TValue, decltype(comp) > fPerm(comp); 
    int n = 7; 
    std::vector<int> perm(n); 
    std::iota(perm.begin(), perm.end(),1); 
    do { 
     fPerm.insert(TValue(perm, f(perm))); 
    } while (std::next_permutation(perm.begin(), perm.end())); 

    // Get first smallest 100 values, if there are such many. 
    int m = 100 < fPerm.size() ? 100 : fPerm.size(); 
    auto iterEnd = fPerm.begin(); 
    std::advance(iterEnd, m); 
    for (auto iter = fPerm.begin(); iter != iterEnd; iter++) { 
     std::cout << iter->second << std::endl; 
    } 
} 

Answer 1

Я пересмотрел свое решение выше, реализовав функцию отделки, стирающую самый большой элемент набора. Как указано ниже, использование std::priority_queue может быть еще более коротким.

#include <vector> 
#include <set> 
#include <algorithm> 
#include <numeric> 
#include <boost/random.hpp> 

boost::random::mt19937 rng; 

double f(const std::vector<int>& perm) { 
    boost::random::uniform_real_distribution<> gen; 
    return gen(rng); 
} 

typedef std::pair<std::vector<int>, double> TValue; 

void main(int argc, int args) { 
    auto comp = [](const TValue& v1, const TValue& v2) { return v1.second < v2.second; }; 
    std::set<TValue, decltype(comp) > fPerm(comp); 
    int n = 7; 
    std::vector<int> perm(7); 
    std::iota(perm.begin(), perm.end(),1); 
    do { 
     fPerm.insert(TValue(perm, f(perm))); 
     if (fPerm.size() > 100) { 
      fPerm.erase(*fPerm.rbegin()); 
     } 
    } while (std::next_permutation(perm.begin(), perm.end())); 

    // Get first smallest 100 values, if there are such many. 
    int m = 100 < fPerm.size() ? 100 : fPerm.size(); 
    auto iterEnd = fPerm.begin(); 
    std::advance(iterEnd, m); 
    for (auto iter = fPerm.begin(); iter != iterEnd; iter++) { 
     std::cout << iter->second << std::endl; 
    } 
}