Come si ordina in modo efficiente una struttura quadrupla in C++?

Question

Ho una struttura con membri x, y, z e w. Come faccio a ordinare in modo efficiente prima da x, poi da y, da z e infine da w in C++?

Answer 1

Se si desidera implementare un ordinamento lessicografico, quindi il modo più semplice è quello di utilizzare std::tie per implementare un minore di o maggiore di operatore di confronto o funtore, e quindi utilizzare std::sort su una raccolta di strutture.

struct Foo 
{ 
    T x, y, z, w; 
}; 

....  
#include <tuple> // for std::tie 

bool operator<(const Foo& lhs, const Foo& rhs) 
{ 
    // assumes there is a bool operator< for T 
    return std::tie(lhs.x, lhs.y, lhs.z, lhs.w) < std::tie(rhs.x, rhs.y, rhs.z, rhs.w); 
} 

.... 

#include <algorithm> // for std::sort 

std::vector<Foo> v = ....; 
std::sort(v.begin(), v.end()); 

Se non esiste un ordinamento naturale per Foo, potrebbe essere meglio definire funtori confronto invece di implementare operatori di confronto. È quindi possibile passare questi per ordine:

bool cmp_1(const Foo& lhs, const Foo& rhs) 
{ 
    return std::tie(lhs.x, lhs.y, lhs.z, lhs.w) < std::tie(rhs.x, rhs.y, rhs.z, rhs.w); 
} 

std::sort(v.begin(), v.end(), cmp_1); 

Se non si dispone di C++ 11 tuple supporto, è possibile implementare questo utilizzando std::tr1::tie (uso intestazione <tr1/tuple>) oppure utilizzando boost::tie dal boost.tuple library.

Answer 2

È possibile trasformare una struttura in std::tuple utilizzando std::tie e utilizzare il confronto lessicografico std::tuple::operator<. Ecco un esempio utilizzando un lambda per std::sort

#include <algorithm> 
#include <tuple> 
#include <vector> 

struct S 
{ 
    // x, y, z, w can be 4 different types! 
    int x, y, z, w; 
}; 

std::vector<S> v; 

std::sort(std::begin(v), std::end(v), [](S const& L, S const& R) { 
    return std::tie(L.x, L.y, L.z, L.w) < std::tie(R.x, R.y, R.z, R.w); 
}); 

Questo esempio fornisce std:sort con un operatore di confronto on-the-fly. Se si desidera sempre utilizzare il confronto lessicografico, è possibile scrivere un membro non membro bool operator<(S const&, S const&) che verrà selezionato automaticamente da std::sort o da contenitori associativi ordinati come std::set e std::map.

Per quanto riguarda l'efficienza, da un online reference:

Tutti gli operatori di confronto sono in corto circuito; non hanno accesso agli elementi della tupla oltre a quanto necessario per determinare il risultato del confronto .

Se si dispone di un ambiente C++ 11, preferire std::tie rispetto alle soluzioni scritte a mano fornite qui. Sono più soggetti a errori e meno leggibili.

Answer 3

Se si rotola il proprio operatore di confronto, è possibile lanciare liberamente oggetti in std::map o invocare std::sort. Questa implementazione è progettata per essere semplice in modo da poterla facilmente verificare e modificare se necessario. Utilizzando solo operator< per confrontare x, y, zew, riduce al minimo il numero di operatori che potrebbe essere necessario implementare se tali variabili non sono già comparabili (ad esempio se sono le tue strutture piuttosto che ints, double, std :: stringhe ecc.).

bool operator<(const Q& lhs, const Q& rhs) 
{ 
    if (lhs.x < rhs.x) return true; 
    if (rhs.x < lhs.x) return false; 
    if (lhs.y < rhs.y) return true; 
    if (rhs.y < lhs.y) return false; 
    if (lhs.z < rhs.z) return true; 
    if (rhs.z < lhs.z) return false; 
    if (lhs.w < rhs.w) return true; 
    return false; 
} 

volte tipi definiranno una funzione di confronto che restituisce -1, 0 o 1 per indicare minore di, uguale o maggiore di, sia come un modo per sostenere l'attuazione del <, <=, ==, != , >= e > e anche perché a volte facendo un < allora un != o > ripeterebbe un sacco di lavoro (si consideri il confronto lungo stringhe testuali in cui solo l'ultimo carattere differisce).Se x, y, z e w capita di essere di tali tipi e hanno un più alto rendimento funzione di confronto, si può eventualmente migliorare il rendimento complessivo con:

bool operator<(const Q& lhs, const Q& rhs) 
{ 
    int c; 
    return (c = lhs.x.compare(rhs.x) ? c : 
      (c = lhs.y.compare(rhs.y) ? c : 
      (c = lhs.z.compare(rhs.z) ? c : 
      lhs.w < rhs.w; 
} 

Answer 4

Questa soluzione ha al massimo 4 confronti per elemento confrontare e non richiede la costruzione di altri oggetti:

// using function as comp 
std::sort (quadrupleVec.begin(), quadrupleVec.end(), [](const Quadruple& a, const Quadruple& b) 
{ 
    if (a.x != b.x) 
     return a.x < b.x; 

    if (a.y != b.y) 
     return a.y < b.y; 

    if (a.z != b.z) 
     return a.z < b.z; 

    return a.w < b.w; 
});