Classificação em C ++ e acompanhamento de índices

216

Usando C ++, e espero que a biblioteca padrão, eu queira classificar uma sequência de amostras em ordem crescente, mas também quero lembrar os índices originais das novas amostras.

Por exemplo, eu tenho um conjunto ou vetor ou matriz de amostras A : [5, 2, 1, 4, 3]. Quero classificá-los B : [1,2,3,4,5], mas também quero lembrar os índices originais dos valores, para que eu possa obter outro conjunto que seria: C : [2, 1, 4, 3, 0 ]- que corresponde ao índice de cada elemento em 'B', no original ' UMA'.

Por exemplo, no Matlab, você pode:

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

Alguém pode ver uma boa maneira de fazer isso?

Mingus
fonte

Respostas:

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

Agora você pode usar o vetor de índice retornado em iterações como

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

Você também pode optar por fornecer seu vetor de índice original, função de classificação, comparador ou reordenar automaticamente v na função sort_indexes usando um vetor extra.

Łukasz Wiklendt
fonte
4
Adoro esta resposta.Se o seu compilador não suportar lambdas, você poderá usar uma classe: template <typename T> class CompareIndicesByAnotherVectorValues ​​{std :: vector <T> * _values; public: CompareIndicesByAnotherVectorValues ​​(std :: vector <T> * valores): _valores (valores) {} public: operador bool () (const int & a, const int & b) const {return ( _values) [a]> ( _values) [ b]; }};
Yoav
2
Eu amo essa resposta também, não há necessidade de copiar o vetor original para criar o vetor de pares.
headmyshoulder
29
Mais do que a mão-trabalhada for (size_t i = 0; i != idx.size(); ++i) idx[i] = i;prefiro o padrãostd::iota( idx.begin(), idx.end(), 0 );
Wyck
6
use #include <numeric>for iota ()
kartikag01
6
iotaé o algoritmo menos obviamente nomeado em toda a biblioteca padrão do C ++.
Seth Johnson
87

Você pode classificar std :: pair em vez de apenas ints - primeiro int são dados originais, segundo int é índice original. Em seguida, forneça um comparador que classifique apenas no primeiro int. Exemplo:

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

Classifique a nova instância do problema usando um 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

O resultado de std :: sort no v_prime, usando esse comparador, deve ser:

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

Você pode separar os índices caminhando pelo vetor, pegando .second de cada std :: pair.

RAC
fonte
1
É exatamente assim que eu faria isso. A função de classificação básica não rastreia as posições antiga e nova, pois isso acrescentaria uma sobrecarga desnecessária extra.
the_mandrill
8
A desvantagem desta função é que ela requer que você realoque a memória para todos os valores.
Yoav
1
Essa é obviamente uma abordagem viável, mas há uma desvantagem de que você precisa alterar o contêiner original de "contêiner de números" para "contêiner de pares".
precisa
18

Suponha que o vetor dado seja

A=[2,4,3]

Crie um novo vetor

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

Classifique V e, ao classificar, em vez de comparar os elementos de V, compare os elementos correspondentes 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];} );
MysticForce
fonte
Ame sua resposta. você ainda pode usar std::iota()para uma inicialização mais elegent demap
Nimrod Morag
Sim, podemos usá-lo! Obrigado pela sugestão
MysticForce
12

Eu escrevi versão genérica de classificação 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 ; }) ;
}

O uso é o mesmo que std :: sort, exceto por um contêiner de índice para receber índices classificados. teste:

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

você deve obter 2 1 0 3. para os compiladores sem suporte ao c ++ 0x, substitua a expressão lamba como um modelo 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) ; }        
} ;

e reescreva std :: classifique como

std::sort(pv.begin(), pv.end(), PairComp(comp)()) ;
hkyi
fonte
Oi hkyi! Como instanciamos essa função de modelo? Ele tem dois nomes de tipo de modelo e um deles é um iterador que torna essa situação muito rara. Você pode ajudar?
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";
}

Agora acontém nossos valores e seus respectivos índices no ordenados.

a[i].first = valueàs i.

a[i].second = idx na matriz inicial.

Aditya Aswal
fonte
Considere adicionar uma descrição do seu código para que os usuários que visitam esta postagem possam entender como ele funciona.
precisa saber é o seguinte
Na verdade, eu gosto mais dessa solução - meu vetor é do tamanho 4 ou mais e estou preso antes do C ++ 11 e não posso usar lambdas. Obrigado Aditya Aswal.
stephanmg
6

Eu me deparei com essa pergunta e descobri que classificar os iteradores diretamente seria uma maneira de classificar os valores e acompanhar os índices; Não há necessidade de definir um contêiner extra de pairs de (valor, índice) que seja útil quando os valores forem objetos grandes; Os iteradores fornecem o acesso ao valor e ao í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 ) );
}

como no exemplo 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 > ( ) );

agora, por exemplo, o quinto elemento menor no vetor classificado teria valor **idx[ 5 ]e seu índice no vetor original seria distance( A.begin( ), *idx[ 5 ] )ou simplesmente *idx[ 5 ] - A.begin( ).

behzad.nouri
fonte
3

Há outra maneira de resolver isso, usando um 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();

Isso irá erradicar elementos não exclusivos. Se isso não for aceitável, use um multimap:

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 gerar os índices, itere sobre o mapa ou multimap:

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

Bela solução por @Lukasz Wiklendt! Embora no meu caso eu precisasse de algo mais genérico, modifiquei-o um pouco:

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

Exemplo: encontre índices classificando um vetor de seqüências por comprimento, exceto o primeiro elemento que é um manequim.

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;

impressões:

abc
ab
a
sigvaldm
fonte
3

Considere usar std::multimap como sugerido por @Ulrich Eckhardt. Só que o código poderia ser ainda mais simples.

Dado

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

Para classificar o tempo médio de inserção

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 originais

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
}

O motivo para preferir a std::multimapa std::mapé permitir valores iguais nos vetores originais. Observe também que, diferentemente de std::map, operator[]não está definido para std::multimap.

aafulei
fonte
2

Crie uma std::pairfunção in e classifique o par:

versão 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
fonte
1

Os itens do vetor são exclusivos? Nesse caso, copie o vetor, classifique uma das cópias com STL Sort e encontre o índice de cada item no vetor original.

Se o vetor deve manipular itens duplicados, acho melhor você implementar sua própria rotina de classificação.

Mizipzor
fonte
1

Bem, minha solução usa a técnica de resíduos. Podemos colocar os valores em ordem de classificação nos 2 bytes superiores e os índices dos elementos - nos 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;

Em seguida, classifique a matriz myintscomo de costume:

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

Depois disso, você pode acessar os índices dos elementos via residuum. O código a seguir imprime os índices dos valores classificados na ordem crescente:

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

Obviamente, essa técnica funciona apenas para valores relativamente pequenos na matriz original myints(ou seja, aqueles que podem caber nos 2 bytes superiores de int). Mas tem o benefício adicional de distinguir valores idênticos de myints: seus índices serão impressos na ordem correta.

Macmep
fonte
1

Se for possível, você pode criar a matriz de posição usando a função find e classificar a matriz.

Ou talvez você possa usar um mapa onde a chave seria o elemento e os valores de uma lista de sua posição nas próximas matrizes (A, B e C)

Depende dos usos posteriores dessas matrizes.

HyLian
fonte
0

Para esse tipo de pergunta Armazene os dados da matriz original em novos dados e, em seguida, procure binário no primeiro elemento da matriz classificada na matriz duplicada e esse índice deve ser armazenado em um vetor ou matriz.

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

Aqui binarysearch é uma função que pega a matriz, tamanho da matriz, item de pesquisa e retornaria a posição do item pesquisado

Mohit Vachhani
fonte
-1

Existem muitos caminhos. Uma solução bastante simples é usar um vetor 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;
}

Aqui está a saída:

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