Индексы наименьших значений N в векторе

Question

У меня есть QVector<float>, и мне нужно получить массив итераторов/указателей на наилучшие (минимальные) значения N от него. Как я могу это сделать, предпочтительно используя алгоритмы STL?

Answer 1

Что-то вдоль этих линий, может быть:

QVector<float> data; // populated somehow 
int N; // some value <= data.size() 

std::vector<int> indices; 
int i = 0; 
std::generate_n(std::back_inserter(indices), data.size(), 
    [&i]() { return i++; }); 

std::partial_sort(indices.begin(), indices.begin() + N, indices.end(), 
    [&data](int ind1, int ind2) { return data[ind1] < data[ind2]; }); 
/* Now indices[0] through indices[N-1] contain indices 
    of the N smallest elements in data. */ 

Answer 2

Существует простой способ, чтобы дать вам вектор из лучших N индексов (не только значения), как вы хотите.
Он очень похож на ответ Игоря, но он дает вам вектор результата с точно N лучшими индексами.

Этот код очень прост и использует мощность STL, так же, как вы просили. Посмотрите:

QVector<int> findBestIndices(QVector<float> &times, const int &N) 
{ 
    QVector<int> indices(times.size()); 
    std::iota(indices.begin(), indices.end(), 0); // fill with 0,1,2,... 

    std::partial_sort(indices.begin(), indices.begin()+N, indices.end(), 
        [&times](int i,int j) {return times[i]<times[j];}); 

    return QVector<int>(indices.begin(), indices.begin()+N); 
} 

int main() 
{ 
    QVector<float> times = {3.14, 0.29, 3.50, 59.38, 2.39}; 

    const int N = 3; // N best times 
    QVector<int> best = findBestIndices(times, N); 

    for(const auto &index : best) { 
     std::cout << '#' << index << " => " << times[index] << "s\n"; 
    } 

    return 0; 
} 

Это будет печатать:

#1 => 0.29s 
#4 => 2.39s 
#0 => 3.14s 

---

Тем не менее, если вы когда-нибудь хотели сделать то же самое, но значения будет достаточно ...
Вы можете получить отсортированный вектор ваших лучших элементов с помощью std::partial_sort_copy Функция:

const int N = 3; 
QVector<float> best(N); 
QVector<float> times = {3.14, 0.29, 3.50, 59.38, 2.39}; 

std::partial_sort_copy(times.begin(), times.end(), best.begin(), best.end()); 

for(const auto &mytime : best) std::cout << mytime << '\n';