C ++ ordenar y hacer un seguimiento de los índices

216

Usando C ++, y con suerte la biblioteca estándar, quiero ordenar una secuencia de muestras en orden ascendente, pero también quiero recordar los índices originales de las nuevas muestras.

Por ejemplo, tengo un conjunto, o vector, o matriz de muestras A : [5, 2, 1, 4, 3]. Quiero ordenarlos para que sean B : [1,2,3,4,5], pero también quiero recordar los índices originales de los valores, para poder obtener otro conjunto que sería: C : [2, 1, 4, 3, 0 ]- que corresponde al índice de cada elemento en 'B', en el original ' UNA'.

Por ejemplo, en Matlab puedes hacer:

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

¿Alguien puede ver una buena manera de hacer esto?

Mingus
fuente

Respuestas:

298

Usando C++11 lambdas:

#include <iostream>
#include <vector>
#include <numeric>      // std::iota
#include <algorithm>    // std::sort, std::stable_sort

using namespace std;

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

  // initialize original index locations
  vector<size_t> idx(v.size());
  iota(idx.begin(), idx.end(), 0);

  // sort indexes based on comparing values in v
  // using std::stable_sort instead of std::sort
  // to avoid unnecessary index re-orderings
  // when v contains elements of equal values 
  stable_sort(idx.begin(), idx.end(),
       [&v](size_t i1, size_t i2) {return v[i1] < v[i2];});

  return idx;
}

Ahora puede usar el vector índice devuelto en iteraciones como

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

También puede elegir suministrar su vector índice original, función de clasificación, comparador o reordenar automáticamente v en la función sort_indexes utilizando un vector adicional.

Łukasz Wiklendt
fuente
44
Me encanta esta respuesta. Si su compilador no admite lambdas, puede usar una clase: template <typename T> class CompareIndicesByAnotherVectorValues ​​{std :: vector <T> * _values; public: CompareIndicesByAnotherVectorValues ​​(std :: vector <T> * values): _values ​​(values) {} public: bool operator () (const int & a, const int & b) const {return ( _values) [a]> ( _values) [ si]; }};
Yoav
2
También me encanta esta respuesta, no hay necesidad de copiar el vector original para crear el vector de pares.
headmyshoulder
29
En lugar de hacerlo a mano, for (size_t i = 0; i != idx.size(); ++i) idx[i] = i;prefiero el estándarstd::iota( idx.begin(), idx.end(), 0 );
Wyck
66
use #include <numeric>for iota ()
kartikag01
66
iotaes el algoritmo menos obvio en toda la biblioteca estándar de C ++.
Seth Johnson
87

Puede ordenar std :: pair en lugar de solo ints: el primer int son datos originales, el segundo int es el índice original. Luego, proporcione un comparador que solo se clasifique en el primer int. Ejemplo:

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

Ordene la nueva instancia del problema utilizando un comparador como:

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

El resultado de std :: sort en v_prime, usando ese comparador, debería ser:

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

Puede despegar los índices recorriendo el vector, tomando .second de cada std :: pair.

RAC
fuente
1
Así es exactamente como lo haría también. La función de clasificación básica no rastrea las posiciones antiguas versus las nuevas ya que eso agregaría una sobrecarga innecesaria adicional.
the_mandrill
8
El inconveniente de esta función es que requiere reasignar memoria para todos los valores.
Yoav
1
Obviamente, este es un enfoque viable, pero tiene el inconveniente de que tiene que cambiar su contenedor original de "contenedor de números" a "contenedor de pares".
Ruslan
18

Supongamos que el vector dado es

A=[2,4,3]

Crea un nuevo vector

V=[0,1,2] // indicating positions

Ordene V y mientras ordena en lugar de comparar elementos de V, compare los elementos correspondientes de A

 //Assume A is a given vector with N elements
 vector<int> V(N);
 int x=0;
 std::iota(V.begin(),V.end(),x++); //Initializing
 sort( V.begin(),V.end(), [&](int i,int j){return A[i]<A[j];} );
Fuerza mística
fuente
Amo tu respuesta. incluso se puede utilizar std::iota()para una inicialización de elegentPackage másmap
Nimrod Morag
Sí, podemos usarlo! Gracias por la sugerencia
MysticForce
12

Escribí una versión genérica de clasificación de índice.

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

El uso es el mismo que el de std :: sort excepto para un contenedor de índice para recibir índices ordenados. pruebas:

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

debería obtener 2 1 0 3. para los compiladores sin soporte de c ++ 0x, reemplace la expresión lamba como plantilla de clase:

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

y reescribir std :: ordenar como

std::sort(pv.begin(), pv.end(), PairComp(comp)()) ;
hkyi
fuente
Hola hkyi ¿Cómo instanciamos esta función de plantilla? Tiene dos nombres de tipo de plantilla y uno de ellos es un iterador que hace que esta situación sea muy rara. ¿Podrías ayudar?
Scott Yang
12
vector<pair<int,int> >a;

for (i = 0 ;i < n ; i++) {
    // filling the original array
    cin >> k;
    a.push_back (make_pair (k,i)); // k = value, i = original index
}

sort (a.begin(),a.end());

for (i = 0 ; i < n ; i++){
    cout << a[i].first << " " << a[i].second << "\n";
}

Ahora a contiene tanto nuestros valores como sus respectivos índices en el ordenado.

a[i].first = value a i 'th.

a[i].second = idx en la matriz inicial

Aditya Aswal
fuente
Considere agregar una descripción de su código para que los usuarios que visiten esta publicación puedan entender cómo funciona.
BusyProgrammer
En realidad, me gusta más esta solución: mi vector es de tamaño 4 más o menos y estoy atascado antes de C ++ 11 y no puedo usar lambdas. Gracias Aditya Aswal.
stephanmg
6

Me encontré con esta pregunta, y descubrí que ordenar los iteradores directamente sería una forma de ordenar los valores y realizar un seguimiento de los índices; No es necesario definir un contenedor adicional de pairs de (valor, índice) que es útil cuando los valores son objetos grandes; Los iteradores proporcionan acceso tanto al valor como al índice:

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

en cuanto al ejemplo de uso:

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

ahora, por ejemplo, el quinto elemento más pequeño en el vector ordenado tendría valor **idx[ 5 ]y su índice en el vector original sería distance( A.begin( ), *idx[ 5 ] )o simplemente *idx[ 5 ] - A.begin( ).

behzad.nouri
fuente
3

Hay otra forma de resolver esto, usando un mapa:

vector<double> v = {...}; // input data
map<double, unsigned> m; // mapping from value to its index
for (auto it = v.begin(); it != v.end(); ++it)
    m[*it] = it - v.begin();

Sin embargo, esto erradicará elementos no únicos. Si eso no es aceptable, use un mapa múltiple:

vector<double> v = {...}; // input data
multimap<double, unsigned> m; // mapping from value to its index
for (auto it = v.begin(); it != v.end(); ++it)
    m.insert(make_pair(*it, it - v.begin()));

Para generar los índices, itere sobre el mapa o el mapa múltiple:

for (auto it = m.begin(); it != m.end(); ++it)
    cout << it->second << endl;
Ulrich Eckhardt
fuente
3

Hermosa solución por @Lukasz Wiklendt! Aunque en mi caso necesitaba algo más genérico, lo modifiqué un poco:

template <class RAIter, class Compare>
vector<size_t> argSort(RAIter first, RAIter last, Compare comp) {

  vector<size_t> idx(last-first);
  iota(idx.begin(), idx.end(), 0);

  auto idxComp = [&first,comp](size_t i1, size_t i2) {
      return comp(first[i1], first[i2]);
  };

  sort(idx.begin(), idx.end(), idxComp);

  return idx;
}

Ejemplo: Encuentre índices ordenando un vector de cadenas por longitud, excepto por el primer elemento que es un ficticio.

vector<string> test = {"dummy", "a", "abc", "ab"};

auto comp = [](const string &a, const string& b) {
    return a.length() > b.length();
};

const auto& beginIt = test.begin() + 1;
vector<size_t> ind = argSort(beginIt, test.end(), comp);

for(auto i : ind)
    cout << beginIt[i] << endl;

huellas dactilares:

abc
ab
a
sigvaldm
fuente
3

Considere usar std::multimapsegún lo sugerido por @Ulrich Eckhardt. Solo que el código podría hacerse aún más simple.

Dado

std::vector<int> a = {5, 2, 1, 4, 3};  // a: 5 2 1 4 3

Ordenar en el tiempo medio de inserción

std::multimap<int, std::size_t> mm;
for (std::size_t i = 0; i != a.size(); ++i)
    mm.insert({a[i], i});

Para recuperar valores e índices originales

std::vector<int> b;
std::vector<std::size_t> c;
for (const auto & kv : mm) {
    b.push_back(kv.first);             // b: 1 2 3 4 5
    c.push_back(kv.second);            // c: 2 1 4 3 0
}

La razón para preferir a std::multimapa a std::mapes permitir valores iguales en vectores originales. También tenga en cuenta que, a diferencia de for std::map, operator[]no está definido para std::multimap.

aafulei
fuente
2

Hacer una std::pair función in y luego ordene el par:

Versión genérica :

template< class RandomAccessIterator,class Compare >
auto sort2(RandomAccessIterator begin,RandomAccessIterator end,Compare cmp) ->
   std::vector<std::pair<std::uint32_t,RandomAccessIterator>>
{
    using valueType=typename std::iterator_traits<RandomAccessIterator>::value_type;
    using Pair=std::pair<std::uint32_t,RandomAccessIterator>;

    std::vector<Pair> index_pair;
    index_pair.reserve(std::distance(begin,end));

    for(uint32_t idx=0;begin!=end;++begin,++idx){
        index_pair.push_back(Pair(idx,begin));
    }

    std::sort( index_pair.begin(),index_pair.end(),[&](const Pair& lhs,const Pair& rhs){
          return cmp(*lhs.second,*rhs.second);
    });

    return index_pair;
}

ideona

uchar
fuente
1

¿Son únicos los elementos del vector? Si es así, copie el vector, ordene una de las copias con STL Ordenar luego puede encontrar qué índice tenía cada elemento en el vector original.

Si se supone que el vector maneja elementos duplicados, creo que es mejor implementar su propia rutina de clasificación.

Mizipzor
fuente
1

Bueno, mi solución usa la técnica de residuos. Podemos colocar los valores bajo ordenación en los 2 bytes superiores y los índices de los elementos, en los 2 bytes inferiores:

int myints[] = {32,71,12,45,26,80,53,33};

for (int i = 0; i < 8; i++)
   myints[i] = myints[i]*(1 << 16) + i;

Luego ordena la matriz myintscomo de costumbre:

std::vector<int> myvector(myints, myints+8);
sort(myvector.begin(), myvector.begin()+8, std::less<int>());

Después de eso, puede acceder a los índices de los elementos a través de residuum. El siguiente código imprime los índices de los valores ordenados en orden ascendente:

for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it)
   std::cout << ' ' << (*it)%(1 << 16);

Por supuesto, esta técnica funciona solo para los valores relativamente pequeños en la matriz original myints(es decir, aquellos que pueden caber en los 2 bytes superiores de int). Pero tiene el beneficio adicional de distinguir valores idénticos de myints: sus índices se imprimirán en el orden correcto.

Macmep
fuente
1

Si es posible, puede construir la matriz de posición utilizando la función de búsqueda y luego ordenar la matriz.

O tal vez pueda usar un mapa donde la clave sería el elemento, y los valores una lista de su posición en las siguientes matrices (A, B y C)

Depende de los usos posteriores de esas matrices.

HyLian
fuente
0

Para este tipo de pregunta Almacene los datos del conjunto original en un nuevo dato y luego binario busque el primer elemento del conjunto ordenado en el conjunto duplicado y ese índice debe almacenarse en un vector o conjunto.

input array=>a
duplicate array=>b
vector=>c(Stores the indices(position) of the orignal array
Syntax:
for(i=0;i<n;i++)
c.push_back(binarysearch(b,n,a[i]));`

Aquí binarysearch es una función que toma la matriz, el tamaño de la matriz, el elemento de búsqueda y devolvería la posición del elemento buscado

Mohit Vachhani
fuente
-1

Hay muchas maneras. Una solución bastante simple es usar un vector 2D.

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

int main() {
 vector<vector<double>> val_and_id;
 val_and_id.resize(5);
 for (int i = 0; i < 5; i++) {
   val_and_id[i].resize(2); // one to store value, the other for index.
 }
 // Store value in dimension 1, and index in the other:
 // say values are 5,4,7,1,3.
 val_and_id[0][0] = 5.0;
 val_and_id[1][0] = 4.0;
 val_and_id[2][0] = 7.0;
 val_and_id[3][0] = 1.0;
 val_and_id[4][0] = 3.0;

 val_and_id[0][1] = 0.0;
 val_and_id[1][1] = 1.0;
 val_and_id[2][1] = 2.0;
 val_and_id[3][1] = 3.0;
 val_and_id[4][1] = 4.0;

 sort(val_and_id.begin(), val_and_id.end());
 // display them:
 cout << "Index \t" << "Value \n";
 for (int i = 0; i < 5; i++) {
  cout << val_and_id[i][1] << "\t" << val_and_id[i][0] << "\n";
 }
 return 0;
}

Aquí está la salida:

   Index   Value
   3       1
   4       3
   1       4
   0       5
   2       7
Gokul
fuente