c++ - 更新 std::set 以仅保留最小值

Question

对于某些算法，我必须在 n 整数元素集的所有排列上调用函数 f 范围从 1 到 n。最后，我对产生最小 f 值的 100 个排列感兴趣。

我能找到的最佳解决方案如下。但它有一个严重的缺点。当 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;
    }
}