CODEWITHSUNDEEP
c++vectorindexing
KingAzaiez
KingAzaiez

Reputation: 113

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

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);
}

Upvotes: 3

Views: 1377

Answers (3)

G. Sliepen
G. Sliepen

Reputation: 7973

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

Upvotes: 0

ubaid shaikh
ubaid shaikh

Reputation: 453

Link to the code https://onlinegdb.com/rJcYs-slD

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;

bool MyComp(pair<int,int> a, pair<int,int> b)
{
    if(a.first>=b.first) return true;
    return false;
}

int main()
{
    
    vector<int> vMetric={5,6,1,4,10};
    
    vector<pair<int,int>> vMetricWithIndex;
    
    for(int i=0;i<vMetric.size();++i) vMetricWithIndex.push_back({vMetric[i],i});
    
    sort(vMetricWithIndex.begin(),vMetricWithIndex.end(),MyComp);

    for(auto i:vMetricWithIndex)
    {
        cout<<"Element :"<<i.first<<" | Index:"<<i.second<<endl;
    }
    
    return 0;
}

Logic:

  1. Just create a vector of pairs with first element of each pair as element of vMetric and second element as index of this vMetric element.
  2. Now sort this vMetricWithIndex in decreasing order. Please note that we need a helper function (like the MyComp in above code) to sort vector of pairs.
  3. Voila! The second element of the first 5 pairs of vMetricWithIndex represents the required indices.

Upvotes: 0

wcochran
wcochran

Reputation: 10896

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.

Upvotes: 6

Related Questions