C++ de tri et de garder la trace des indices

Question

À l'aide de c++, et j'espère que la STL, je veux trier une séquence d'échantillons dans l'ordre croissant, mais je tiens aussi à rappeler l'origine des indices des nouveaux échantillons. Par exemple J'ai un jeu, ou un vecteur ou de la matrice d'échantillons A : [5, 2, 1, 4, 3] Je veux que ces B : [1,2,3,4,5], mais je veux aussi rappeler l'origine des indices des valeurs, donc je peux obtenir une autre série qui serait: C : [2, 1, 4, 3, 0 ] - ce qui correspond à l'index de chaque élément dans le 'B', à l'origine, "Un".

Par exemple, dans matlab que vous pouvez faire:

 [a,b]=sort([5, 8, 7])
 a = 5 7 8
 b = 1 3 2

Quelqu'un peut-il voir une bonne façon de le faire?

Answer 1

À l'aide de C++11 lambdas

template <typename T>
vector<size_t> sort_indexes(const vector<T> &v) {

  // initialize original index locations
  vector<size_t> idx(v.size());
  for (size_t i = 0; i != idx.size(); ++i) idx[i] = i;

  // sort indexes based on comparing values in v
  sort(idx.begin(), idx.end(),
       [&v](size_t i1, size_t i2) {return v[i1] < v[i2];});

  return idx;
}

Maintenant, vous pouvez utiliser le retour de l'indice de vecteur dans itérations comme

for (auto i: sort_indexes(v)) {
  cout << v[i] << endl;
}

Évidemment, vous pouvez également choisir de fournir votre propre indice de départ du vecteur, la fonction de tri, comparateur, ou automatiquement réorganiser v dans le sort_indexes fonction à l'aide d'un supplément de vecteur.

Answer 2

Vous pouvez trier std::pair au lieu de simplement ints - premier int est de données d'origine, la seconde int est l'indice d'origine. Ensuite fournir un comparateur de qui ne tri que sur le premier int. Exemple:

Your problem instance: v = [5 7 8]
New problem instance: v_prime = [<5,0>, <8,1>, <7,2>]

Trier le nouveau problème de l'instance à l'aide d'un comparateur comme:

typedef std::pair<int,int> mypair;
bool comparator ( const mypair& l, const mypair& r)
   { return l.first < r.first; }
// forgetting the syntax here but intent is clear enough

Le résultat de std::sort sur v_prime, à l'aide de ce comparateur, devrait être:

v_prime = [<5,0>, <7,2>, <8,1>]

Vous pouvez peler les indices en marchant le vecteur, l'accaparement .deuxième de chaque std::pair.

Answer 3

J'ai écrit la version générique de tri des index.

template <class RAIter, class Compare>
void argsort(RAIter iterBegin, RAIter iterEnd, Compare comp, 
    std::vector<size_t>& indexes) {

    std::vector< std::pair<size_t,RAIter> > pv ;
    pv.reserve(iterEnd - iterBegin) ;

    RAIter iter ;
    size_t k ;
    for (iter = iterBegin, k = 0 ; iter != iterEnd ; iter++, k++) {
        pv.push_back( std::pair<int,RAIter>(k,iter) ) ;
    }

    std::sort(pv.begin(), pv.end(), 
        [&comp](const std::pair<size_t,RAIter>& a, const std::pair<size_t,RAIter>& b) -> bool 
        { return comp(*a.second, *b.second) ; }) ;

    indexes.resize(pv.size()) ;
    std::transform(pv.begin(), pv.end(), indexes.begin(), 
        [](const std::pair<size_t,RAIter>& a) -> size_t { return a.first ; }) ;
}

L'utilisation est la même que celle de std::sort, sauf pour un indice récipient pour recevoir triés index. test:

int a[] = { 3, 1, 0, 4 } ;
std::vector<size_t> indexes ;
argsort(a, a + sizeof(a) / sizeof(a[0]), std::less<int>(), indexes) ;
for (size_t i : indexes) printf("%d\n", int(i)) ;

vous devriez obtenir 2 1 0 3. pour les compilateurs sans c++0x soutien, remplacer le lamba expression comme un modèle de classe:

template <class RAIter, class Compare> 
class PairComp {
public:
  Compare comp ;
  PairComp(Compare comp_) : comp(comp_) {}
  bool operator() (const std::pair<size_t,RAIter>& a, 
    const std::pair<size_t,RAIter>& b) const { return comp(*a.second, *b.second) ; }        
} ;

et de réécrire std::sort comme

std::sort(pv.begin(), pv.end(), PairComp(comp)()) ;

Answer 4

Je suis tombé sur cette question, et compris le tri des itérateurs directement serait une façon de trier les valeurs et de garder trace des indices; Il n'est pas nécessaire de définir un supplément contenant de l' pairs ( valeur de l'indice ), ce qui est utile lorsque les valeurs sont des objets volumineux; Les itérateurs offre un accès à la fois la valeur et l'index:

/*
 * a function object that allows to compare
 * the iterators by the value they point to
 */
template < class RAIter, class Compare >
class IterSortComp
{
    public:
        IterSortComp ( Compare comp ): m_comp ( comp ) { }
        inline bool operator( ) ( const RAIter & i, const RAIter & j ) const
        {
            return m_comp ( * i, * j );
        }
    private:
        const Compare m_comp;
};

template <class INIter, class RAIter, class Compare>
void itersort ( INIter first, INIter last, std::vector < RAIter > & idx, Compare comp )
{ 
    idx.resize ( std::distance ( first, last ) );
    for ( typename std::vector < RAIter >::iterator j = idx.begin( ); first != last; ++ j, ++ first )
        * j = first;

    std::sort ( idx.begin( ), idx.end( ), IterSortComp< RAIter, Compare > ( comp ) );
}

comme pour l'exemple d'utilisation:

std::vector < int > A ( n );

// populate A with some random values
std::generate ( A.begin( ), A.end( ), rand );

std::vector < std::vector < int >::const_iterator > idx;
itersort ( A.begin( ), A.end( ), idx, std::less < int > ( ) );

maintenant, par exemple, la 5ème plus petit élément dans le vecteur trié aurait la valeur **idx[ 5 ] et son indice dans le vecteur d'origine serait distance( A.begin( ), *idx[ 5 ] ) ou tout simplement *idx[ 5 ] - A.begin( ).

Answer 5

Lorsque vous traitez avec plusieurs points de vue sur un conteneur, toujours considérer que boost::multi_index_container. Il pourrait être un peu exagéré, mais il peut être juste ce dont vous avez besoin. Vous venez d'insérer et de l'accès et de prendre un affichage trié.