C++ che ordina e tiene traccia degli indici

Question

Utilizzando C++, e si spera che la libreria standard, voglio ordinare una sequenza di campioni in ordine ascendente, ma voglio anche ricordare gli indici originali dei nuovi campioni.

Ad esempio, ho un set, o vettore o matrice di campioni A : [5, 2, 1, 4, 3]. Voglio ordinare questi per essere B : [1,2,3,4,5], ma voglio anche ricordare gli indici originali dei valori, quindi posso ottenere un altro set che sarebbe: C : [2, 1, 4, 3, 0 ] - che corrisponde all'indice di ogni elemento in "B", in l'originale "A".

Per esempio, in Matlab si può fare:

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

Qualcuno può vedere un buon modo per fare questo?

Answer 1

Se è possibile, è possibile creare l'array di posizioni utilizzando la funzione Trova, quindi ordinare l'array.

O forse è possibile utilizzare una mappa dove la chiave sarebbe l'elemento, ed i valori di una lista della sua posizione in vista delle prossime array (A, B e C)

Dipende poi usi di che gli array .

Answer 2

Gli elementi nel vettore sono unici? In tal caso, copia il vettore, ordina una delle copie con STL Sort, quindi puoi trovare l'indice di ciascun elemento nel vettore originale.

Se il vettore deve gestire elementi duplicati, penso che sia meglio implementare la propria routine di ordinamento.

Answer 3

Si potrebbe ordinare std :: pair invece di solo ints: first int è i dati originali, secondo int è l'indice originale. Quindi fornire un comparatore che ordina solo sul primo int. Esempio:

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

ordine alla nuova istanza problema utilizzando un comparatore come:

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 

Il risultato di std :: sort su v_prime, utilizzando tale confronto, dovrebbe essere:

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

È possibile sbucciare gli indici camminando sul vettore, afferrando .secondo da ogni coppia :: coppia.

Answer 4

Ho scritto la versione generica di ordinamento indice.

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

utilizzo è la stessa di quella di std :: sort tranne per un contenitore di indice per ricevere indici ordinati. 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)) ; 

si dovrebbe ottenere 2 1 0 3. per i compilatori C++ 0x, senza supporto, sostituire l'espressione Lamba come un modello di 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 riscrivere std :: sort come

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

Answer 5

con C++ 11 lambda

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 
    sort(idx.begin(), idx.end(), 
     [&v](size_t i1, size_t i2) {return v[i1] < v[i2];}); 

    return idx; 
} 

Ora è possibile utilizzare il vettore indice restituito in iterazioni quali

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

Ovviamente, è anche possibile scegliere di fornire il proprio vettore indice, funzione di ordinamento, comparatore o riordinare automaticamente v nella funzione sort_indexes utilizzando un vettore aggiuntivo.

Answer 6

Mi sono imbattuto in questa domanda e ho capito che ordinare gli iteratori direttamente sarebbe un modo per ordinare i valori e tenere traccia degli indici; Non è necessario definire un contenitore aggiuntivo di pair s (valore, indice) utile quando i valori sono oggetti di grandi dimensioni; Gli iteratori fornisce l'accesso sia il valore e l'indice:

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

come per l'esempio di utilizzo:

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

ora, per esempio, l'elemento più piccolo 5 ° nel vettore ordinato avrebbe valore **idx[ 5 ] e il suo indice nel vettore originale sarebbe distance(A.begin(), *idx[ 5 ]) o semplicemente *idx[ 5 ] - A.begin().

Answer 7

Fare un std::pair in funzione quindi ordinare coppia:

versione generica:

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

ideone

Answer 8

C'è un altro modo per risolvere questo, utilizzando una mappa:

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

Questo però sradicherà elementi non univoci. Se questo non è accettabile, utilizzare un 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())); 

Al fine di uscita degli indici, iterare la mappa o multimap:

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

Answer 9

Beh, la mia soluzione usa la tecnica residui. Possiamo collocare i valori sotto classificare nelle superiori 2 byte e gli indici degli elementi - nei 2 byte inferiori:

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

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

quindi ordinare l'array myints come al solito:

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

Dopo di che si può accedere agli indici degli elementi tramite residui.Il codice seguente stampa gli indici dei valori ordinati in ordine crescente:

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

Naturalmente, questa tecnica funziona solo per i valori relativamente piccoli nell'array originale myints (cioè quelli che possono inserirsi in superiori 2 byte di int). Ma ha il vantaggio aggiuntivo di distinguere i valori identici di myints: i loro indici verranno stampati nell'ordine corretto.

Answer 10

Per questo tipo di domanda Memorizza i dati dell'array originale in un nuovo dato e quindi esegue la ricerca binaria sul primo elemento dell'array ordinato nell'array duplicato e tale indice deve essere memorizzato in un vettore o array.

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

Qui BinarySearch è una funzione che prende la matrice, dimensione della matrice, ricerca voce e ritornerei la posizione dell'elemento cercato

Answer 11

La sua più facile di quello che sembra essere.

Supponiamo vettoriale Dato è

A=[2,4,3] 

creare un nuovo vettore

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

ordine V e mentre ordinamento invece di elementi di V confronto, confronta elementi di A

//Assume A is a given vector with N elements 
vector<int> V(N); 
int j=0; 
std::iota(V.begin(),V.end(),j++); //Initializing 
for(int i=0;i<N;i++) 
     V[i]=i; 
sort(V.begin(),V.end(), [&](int x,int y){return A[x]<A[y];}); 

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

corrispondente

Ora a contiene sia i nostri valori sia i rispettivi indici in ordine.

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

a[i].second = idx nella matrice iniziale.

Answer 13

Bella soluzione di @Lukasz Wiklendt! Anche se nel mio caso avevo bisogno di qualcosa di più generico così ho modificato un po ':

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

Esempio: Trova indici di ordinamento un vettore di stringhe di lunghezza, tranne che per il primo elemento che è un manichino.

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; 

stampe:

abc 
ab 
a