CODEWITHSUNDEEP
c++
vlad_tepesch
vlad_tepesch

Reputation: 6891

How to find indexes of the n greatest elements

I have a container (Vector) of some arbitrary type and i want to get a vector with indices of the n greatest (or smallest) elements.

Is there a standard way to do so?

Upvotes: 0

Views: 108

Answers (1)

Alessandro Teruzzi
Alessandro Teruzzi

Reputation: 3968

This is exactly the topic of one of the guru of the week http://www.gotw.ca/gotw/073.htm

I am reporting the preferred solution, however, I strongly recommend you to read the article (and the blog in general), it is really good.

#include <vector>
#include <map>
#include <algorithm>

namespace Solution3
{
  template<class T>
  struct CompareDeref
  {
    bool operator()( const T& a, const T& b ) const
    { return *a < *b; }
  };


  template<class T, class U>
  struct Pair2nd
  {
    const U& operator()( const std::pair<T,U>& a ) const
    { return a.second; }
  };

  template<class IterIn, class IterOut>
  void sort_idxtbl( IterIn first, IterIn last, IterOut out )
  {
    std::multimap<IterIn, int, CompareDeref<IterIn> > v;
    for( int i=0; first != last; ++i, ++first )
      v.insert( std::make_pair( first, i ) );
    std::transform( v.begin(), v.end(), out,
                Pair2nd<IterIn const,int>() );
  }
}

#include <iostream>

int main()
{
  int ai[10] = { 15,12,13,14,18,11,10,17,16,19 };

  std::cout << "#################" << std::endl;
  std::vector<int> aidxtbl( 10 );


  // use another namespace name to test a different solution
  Solution3::sort_idxtbl( ai, ai+10, aidxtbl.begin() );


  for( int i=0; i<10; ++i )
  std::cout << "i=" << i
            << ", aidxtbl[i]=" << aidxtbl[i]
            << ", ai[aidxtbl[i]]=" << ai[aidxtbl[i]]
            << std::endl;
  std::cout << "#################" << std::endl;
}

Upvotes: 1

Related Questions