c++ - 如何将元素添加到排序列表中......？ (C++)

Question

我刚刚第一次接触 std::vector，现在我想改掉使用纯 C 风格数组的坏习惯。我发现 std::list 是排序时要使用的容器。但是，我不是 100% 如何完成以下操作:

我正在做一些计算，其结果取决于两个指​​数(i 和 j)。最后我只对 100 个最小的结果感兴趣(不一定是 100 个，但肯定比我的计算值总数小得多，下面代码中的 m*n)。

const int L = 100;
int i_list[L];
int j_list[L];
double value_list[L];

for (int i=0;i<m;i++){
    for (int j=0;j<n;j++){
        double x = doSomeCalculations(i,j);
        insertTheValueAndIndices(i,j,x,i_list,j_list,value_list);
    }
}

完成后，value_list 应包含 100 个最小值(递增顺序)和 i_list/j_list 相应的索引。我有一个“insertValuesAndIndices()”的工作版本，但我使用普通数组和插入新值的最低效方式。在写作时我意识到我实际上有 2 个不同的问题:

1. 计算值的数量 (m*n) 远远大于我想要保留在列表中的数量，因此简单地保留所有值并最终只排序一次并不是真正的选择。另一方面，我只需要最后以正确的顺序排列结果，所以也许有一种方法可以只对列表进行一次排序。是否有任何“标准”的巧妙且有效的方法来进行这种排序？

2. 即使我可以存储所有结果并在之后进行排序，我也不确定如何使用 std::list.sort() 以正确的顺序获取索引数组。我想到的是定义一些包含结果和两个索引的类，将这些元素放在一个列表中，然后使用一个只检查值的比较器来进行排序。但是，也许有更直接的方法来做到这一点？

提前干杯和感谢

Answer 1

首先，您可能不想要 std::list ，但是std::vector . 然后使用 std::lower_bound 找到插入的位置，如果 结果 vector 包含的元素数量超过 你感兴趣，std::vector<>::pop_back摆脱 额外的一个。