function to return top 5 indexes of highest values of a vector

Question

is there a function to do this ?

I want to extract the top 5 index of the highest values in an index .

I can only get the index of the highest value but then I have to delete it and do it again, any other method ?

for (unsigned i = 0; i < 5 ; i++){
     int index = std::distance(vMetric.begin(),std::max_element(vMetric.begin(), vMetric.end()));
     vMetric.erase(vMetric.begin()+ index);
}

Answer 1

Create an index array and partially sort that:

std::vector<size_t> indices(vMetric.size());
std::iota(indices.begin(), indices.end(), 0);
std::partial_sort(indices.begin(), indices.begin() + 5, indices.end(),
                  [&](size_t A, size_t B) {
                     return vMetric[A] > vMetric[B];
                  });

The first 5 elements of indices contain your answer and the original vector is not mutated.

Answer 2

There are several possible solutions. Most answers suggest creating a (partially) sorted copy of the array, or of an array of indices. However, that potentially requires a lot of extra storage. If the size of the input is very large, the extra storage might not fit in the cache anymore, and then this might become slow.

As an alternative, you can scan the input array only once, and keep a set of 5 indices of the largest elements seen so far. Below is a possible implementation, that is a bit more generic and works on any container that provides ForwardIterators:

template<typename Iterator>
std::vector<size_t> n_largest_indices(Iterator it, Iterator end, size_t n) {
    struct Element {
        Iterator it;
        size_t index;
    };

    std::vector<Element> top_elements;
    top_elements.reserve(n + 1);

    for(size_t index = 0; it != end; ++index, ++it) {
        top_elements.insert(std::upper_bound(top_elements.begin(), top_elements.end(), *it, [](auto value, auto element){return value > *element.it;}), {it, index});
        if (index >= n)
            top_elements.pop_back();
    }

    std::vector<size_t> result;
    result.reserve(top_elements.size());

    for(auto &element: top_elements)
        result.push_back(element.index);

    return result;
}

The above could probably be improved further, and specialized for RandomAccessIterators so you don't need to have a struct element anymore, and just have to store the top n indices. It could also easily be modified to return the n largest values themselves or to return iterators to the n largest values.

Example usage:

std::vector<int> v{1, 35, 12, 69, 2, 5,1, 6, 99, 53, 2};
auto indices = n_largest_indices(v.begin(), v.end(), 5);

// Print indices
for(auto i: indices)
    std::cout << i << " ";
std::cout << "\n";

// Print values corresponding to the indices
for(auto i: indices)
    std::cout << v[i] << " ";
std::cout << "\n";

Result:

8 3 9 1 2 
99 69 53 35 12