C++, Ordina un vettore basato su un altro

Question

L'esempio migliore che ho è quello di ordinare i nomi in base al loro punteggio.

vector <string> Names {"Karl", "Martin", "Paul", "Jennie"}; 
vector <int> Score{45, 5, 14, 24}; 

Quindi, se io a ordinare il punteggio di {5, 14, 24, 45}, i nomi dovrebbero essere ordinati in base al loro punteggio.

Answer 1

Come già suggerito in altre risposte: Combinare il nome e il punteggio di ogni individuo è probabilmente la soluzione più semplice.

Generalmente, questo può essere ottenuto con un'operazione a volte denominata "zip": combinazione di due vettori in un vettore di coppie - insieme a un "decompressione" corrispondente.

Implementato genericamente, questo può apparire come segue:

#include <vector> 
#include <string> 
#include <algorithm> 
#include <iostream> 
#include <iterator> 

// Fill the zipped vector with pairs consisting of the 
// corresponding elements of a and b. (This assumes 
// that the vectors have equal length) 
template <typename A, typename B> 
void zip(
    const std::vector<A> &a, 
    const std::vector<B> &b, 
    std::vector<std::pair<A,B>> &zipped) 
{ 
    for(size_t i=0; i<a.size(); ++i) 
    { 
     zipped.push_back(std::make_pair(a[i], b[i])); 
    } 
} 

// Write the first and second element of the pairs in 
// the given zipped vector into a and b. (This assumes 
// that the vectors have equal length) 
template <typename A, typename B> 
void unzip(
    const std::vector<std::pair<A, B>> &zipped, 
    std::vector<A> &a, 
    std::vector<B> &b) 
{ 
    for(size_t i=0; i<a.size(); i++) 
    { 
     a[i] = zipped[i].first; 
     b[i] = zipped[i].second; 
    } 
} 


int main(int argc, char* argv[]) 
{ 
    std::vector<std::string> names {"Karl", "Martin", "Paul", "Jennie"}; 
    std::vector<int> score {45, 5, 14, 24}; 

    // Zip the vectors together 
    std::vector<std::pair<std::string,int>> zipped; 
    zip(names, score, zipped); 

    // Sort the vector of pairs 
    std::sort(std::begin(zipped), std::end(zipped), 
     [&](const auto& a, const auto& b) 
     { 
      return a.second > b.second; 
     }); 

    // Write the sorted pairs back to the original vectors 
    unzip(zipped, names, score); 

    for(size_t i=0; i<names.size(); i++) 
    { 
     std::cout << names[i] << " : " << score[i] << std::endl; 
    } 
    return 0; 
} 

Answer 2

Il modo migliore per farlo sarebbe avere una struttura che combini i nomi con i loro punteggi e abbia un vettore.

struct Person 
{ 
    std::string Name; 
    int Score; 
}; 

Poi si può dichiarare il vostro vettore:

std::vector<Person> people{ { "Karl", 45 }, { "Martin", 5 }, { "Paul", 14 } }; 

e l'ordinamento è facile con std::sort da <algorithm>:

std::sort(people.begin(), people.end(), 
       [](const auto& i, const auto& j) { return i.Score < j.Score; }); 

Oppure si può cambiare il lambda, se si desidera ordinare in ordine decrescente:

std::sort(people.begin(), people.end(), 
       [](const auto& i, const auto& j) { return i.Score > j.Score; }); 

Answer 3

Un modo che si possa fare questo sarebbe per memorizzare i nomi ed i punteggi in una singola struttura di dati come ad esempio un std::vector<std::pair<std::string,int>> e quindi di ordinamento può essere fatto come segue:

#include <algorithm> 
#include <vector> 
#include <string> 
#include <utility> 
//... 
std::vector<std::pair<std::string, int>> names_scores_vec; 
// ... populate names_scores_vec... 
// lambda for sorting, change to > for descending order 
auto sort_by_scores = [](const std::pair<string,int>& _lhs, 
    const std::pair<string,int>& _rhs) { return _lhs.second < _rhs.second; }; 
std::sort(names_scores_vec.begin(), names_scores_vec.end(), sort_by_scores); 

In alternativa, stoccaggio utilizzo come ad esempio un std::map o std::multimap se vuoi tasti ripetuti (es nomi ripetuti consentiti).

Answer 4

Se non è possibile unire i dati in un vettore di coppie o struct con entrambi, è possibile creare un vettore di iteratori o gli indici da 0 a size-1. Quindi ordina questo utilizzando un comparatore personalizzato. Infine, crea un nuovo vettore, popolandolo usando gli iteratori o gli indici.

template<class T1, class A1, class T2, class A2> 
std::vector<T1, A1> sort_by(
    std::vector<T1,A1> const& vin, std::vector<T2,A2> const& keys 
){ 
    std::vector<std::size_t> is; 
    is.reserve(vin.size()); 
    for (auto&& unused:keys) 
    is.push_back(is.size()); 
    std::sort(begin(is),end(is),[&](std::size_t l, std::size_t r){ 
    return keys[l]<keys[r]; 
    }); 
    std::vector<T1, A1> r; 
    r.reserve(vin.size()); 
    for(std::size_t i:is) 
    r.push_back(vin[i]); 
    return r; 
} 

Answer 5

non potrebbe questo essere fatto attraverso un tipo di iteratore personalizzato?

EDIT:

Quello che sto pensando nella sua forma più semplice - l'ordinamento di una coppia di vettori basati sul primo - è di avere un iteratore cui funzioni quali dereferenziazione, subscripting, accesso membri e l'uguaglianza e l'ordinazione i confronti chiamerebbero le funzioni corrispondenti sul primo iteratore, tutte le altre funzioni (copia, aritmetica, scambio, ...) che agiscono su entrambi gli iteratori.

template <typename Driver, typename Passenger> 
struct duo_iterator { . . . }; 

template <typename D, typename P> 
auto make_duo_iterator(D d, P p) -> duo_iterator<D, P> { . . . } 

sort(make_duo_iterator(begin(v1), begin(v2)), 
    make_duo_iterator(end(v1), end(v2))); 

L'iteratore potrebbe essere esteso in un multi_iterator per funzionare con qualsiasi algoritmo di riordino, indicando in un numero qualsiasi di sequenze piggybacking extra.
Potrebbe essere un piccolo progetto divertente. O forse qualcosa di simile esiste già, in Boost o altrove.

EDIT2:

Dimenticare quanto sopra.
Eric Niebler's Range-v3 library ha un wrapper view::zip che "Dati gli intervalli N, restituisce un nuovo intervallo in cui l'elemento Mth è il risultato della chiamata di make_tuple sugli elementi Mth di tutti gli intervalli N."
L'ordinamento dell'intervallo con un predicato sul primo elemento delle tuple potrebbe semplicemente fare il trucco.

Answer 6

Così tanti hanno fatto questa domanda e nessuno ha trovato una risposta soddisfacente. Ecco un helper std :: sort che consente di ordinare due vettori contemporaneamente, tenendo conto dei valori di un solo vettore. Questa soluzione si basa su un costume RadomIt (iterator casuale), e opera direttamente sui dati vettoriali originali, senza copie temporanee, struttura riassetto o indici aggiuntivi:

namespace std { 

namespace sort_helper { 

template <typename _Data, typename _Order> 
struct value_reference_t; 

template <typename _Data, typename _Order> 
struct value_t { 
    _Data data; 
    _Order val; 
    inline value_t(_Data _data, _Order _val) : data(_data), val(_val) {} 
    inline value_t(const value_reference_t<_Data,_Order>& rhs); 
}; 

template <typename _Data, typename _Order> 
struct value_reference_t { 
    _Data* pdata; 
    _Order* pval; 
    value_reference_t(_Data* _itData, _Order* _itVal) : pdata(_itData), pval(_itVal) {} 
    inline value_reference_t& operator = (const value_reference_t& rhs) { *pdata = *rhs.pdata; *pval = *rhs.pval; return *this; } 
    inline value_reference_t& operator = (const value_t<_Data,_Order>& rhs) { *pdata = rhs.data; *pval = rhs.val; return *this; } 
    inline bool operator < (const value_reference_t& rhs) { return *pval < *rhs.pval; } 
}; 

template <typename _Data, typename _Order> 
struct value_iterator_t : 
    iterator< random_access_iterator_tag, value_t<_Data,_Order>, ptrdiff_t, value_t<_Data,_Order>*, value_reference_t<_Data,_Order> > 
{ 
    _Data* itData; 
    _Order* itVal; 
    value_iterator_t(_Data* _itData, _Order* _itVal) : itData(_itData), itVal(_itVal) {} 
    inline ptrdiff_t operator - (const value_iterator_t& rhs) const { return itVal - rhs.itVal; } 
    inline value_iterator_t operator + (ptrdiff_t off) const { return value_iterator_t(itData + off, itVal + off); } 
    inline value_iterator_t operator - (ptrdiff_t off) const { return value_iterator_t(itData - off, itVal - off); } 
    inline value_iterator_t& operator ++() { ++itData; ++itVal; return *this; } 
    inline value_iterator_t& operator --() { --itData; --itVal; return *this; } 
    inline value_iterator_t operator ++ (int) { return value_iterator_t(itData++, itVal++); } 
    inline value_iterator_t operator -- (int) { return value_iterator_t(itData--, itVal--); } 
    inline value_t<_Data,_Order> operator *() const { return value_t<_Data,_Order>(*itData, *itVal); } 
    inline value_reference_t<_Data,_Order> operator *() { return value_reference_t<_Data,_Order>(itData, itVal); } 
    inline bool operator < (const value_iterator_t& rhs) const { return itVal < rhs.itVal; } 
    inline bool operator == (const value_iterator_t& rhs) const { return itVal == rhs.itVal; } 
    inline bool operator != (const value_iterator_t& rhs) const { return itVal != rhs.itVal; } 
}; 

template <typename _Data, typename _Order> 
inline value_t<_Data,_Order>::value_t(const value_reference_t<_Data,_Order>& rhs) 
    : data(*rhs.pdata), val(*rhs.pval) {} 

template <typename _Data, typename _Order> 
bool operator < (const value_t<_Data,_Order>& lhs, const value_reference_t<_Data,_Order>& rhs) { 
    return lhs.val < *rhs.pval; } 

template <typename _Data, typename _Order> 
bool operator < (const value_reference_t<_Data,_Order>& lhs, const value_t<_Data,_Order>& rhs) { 
    return *lhs.pval < rhs.val; } 

template <typename _Data, typename _Order> 
void swap(value_reference_t<_Data,_Order> lhs, value_reference_t<_Data,_Order> rhs) { 
    std::swap(*lhs.pdata, *rhs.pdata); 
    std::swap(*lhs.pval, *rhs.pval); } 


} // namespace sort_helper 

} // namespace std 

e questo è un esempio di utilizzo che ordina sia Nomi e Età sulla base di Età valori, che impiegano di serie std :: sorta:

char* Names[] = { "Karl", "Paul", "Martin", "Jennie" }; 
int Age[] = { 45, 14, 5, 24 }; 
typedef std::sort_helper::value_iterator_t<char*,int> IndexIt; 
std::sort(IndexIt(Names, Age), IndexIt(Names+4, Age+4)); 

ordinate per:

{ "Martin", "Paul", "Jennie", "Karl" }; 
{ 5, 14, 24, 45 }; 

codice testato su Visual Studio 2017 eGCC 5.4.0.