如何将元素添加到排序列表中？(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()"的工作版本,但我使用普通数组和插入新值的最低效方法.写作时我意识到我实际上有两个不同的问题:

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

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

干杯和提前谢谢

Answer 1

首先,你可能不想要std::list,但是std::vector.然后std::lower_bound用来查找要插入的位置,如果结果向量包含的元素数量超过了您感兴趣的元素数量,则std::vector<>::pop_back可以去除多余的元素.