How to find indexes of 5 the biggest elements in vector?

Question

How to find indexes of 5 the biggest elements in vector ? For example std::vector<int> how to find indexes of 5 biggest values but not to change original vector ?

Answer 1

std::partial_sort( v.begin(), v.begin()+5, v.end() ) sorts a vector in a way, that the 5 smallest values are sorted and at the beginning of v. The rest is left unsorted.

Since you want the indices and keep the original:
Fill a new vector with numbers from 0..n-1 and supply a comparison function that does v[a] > v[b] instead of a > b:

struct Comp{
    Comp( const vector<int>& v ) : _v(v) {}
    bool operator ()(int a, int b) { return _v[a] > _v[b]; }
    const vector<int>& _v;
}

vector<int> vx;
vx.resize(v.size());
for( int i= 0; i<v.size(); ++i ) vx[i]= i;
partial_sort( vx.begin(), vx.begin()+5, vx.end(), Comp(v) );

vx[0..4] contains the indices.

Answer 2

You can make a copy from the original vector, and partially sort it with a dedicated algorithm from the STL nth_element :

bool cmp (int i,int j) { return (i<j); }    
int main () {
      vector<int> myvector;
      vector<int>::iterator it;

      // set some values:
      for (int i=1; i<10; i++) myvector.push_back(i);   // 1 2 3 4 5 6 7 8 9

      random_shuffle (myvector.begin(), myvector.end());

      // using default comparison (operator <):
      std::vector<int> copy_of_orig = myvector;
      nth_element (copy_of_orig.begin(), copy_of_orig.begin()+5, copy_of_orig.end(), cmp);
      // Display the first five biggest elts.
      for (int i = 0; i < 5; ++i)
        std::cout << copy_of_orig[i] << std::endl;
}

Answer 3

1 solution:

The solution is O(n), where n is the number of elements in the vector being examined.

create a dequeue of vector iterators of length 5, initialized with NULL read the elements of the vector under examination and push_back the index {the idea is to push the new index in the front or back depending upon whether the new element data read is smaller than rear index's data or greater than the front index's data, if the data already in the dequeue is NULL, then whether you push_front or push_back, it doesn't matter}. This would maintain the dequeue in the sorted from from front to back.

If the new data being read is greater than the front data, then remove the rear and push the current data's iterator in front; else do nothing

At the end of the iteration the dequeue will have top five element's iterators.

Answer 4

There might be a more elegant way, but I'm to tired to find it right now. You could do something like this (untested, so no guarantees it works out of the box, particulary in corner cases, but it should):

std::array<int, 5> indices = {-1,-1,-1,-1,-1};//-1 used as invalid index for cases where myVec.size()<5
for(int i = 0; i < myVec.size(); ++i)
{
    for(int j = 0; j < 5; ++j)
        if((indices[j] == - 1) || (myVec[i] > myVec[indices[j]]))
        {
            std::copy_backward(indices.begin() + j, indices.end() - 1, indices.end());
            indices[j] = i;
            break;
        }
}

It maintains a list of the 5 biggest elements. For each element of the vector it will start with the biggest element, test if the new one is bigger, if yes shift the indices down and insert as the first, otherwise test for the second biggest and so on. Doesn't modify the vector and runs in O(n) with pretty low overhead.

In case you can't use C++11, you can always use an std::vector (or int[5] if you really want to) instead of std::array.

Answer 5

You will need to do something like this:

  int largestNumbers [5]{0, 0, 0, 0, 0};

  for each( const int i in data ){
  {
    for (int index = 0; index < 5; index++){
       if (i > largestNumber[index]){
          largestNumber[index] = i;
       }
     }
  }