C++ 11 sort collezione di oggetti personalizzati con diverse proprietà

Question

V'è una raccolta di elementi struct personalizzato:

struct MyStruct 
{ 
    int id; 
    std::string currencyCode; 
    int month; 
    int year; 
    int amount; 
}; 

Questi dati saranno visualizzati in una certa tabella che permette l'ordinamento per più colonne (cliccando su colonne della tabella tenendo premuto il tasto Ctrl).

Ordinamento una collezione di oggetti del cliente per una proprietà è semplice come:

vector<MyStruct> values; 

std::sort(values.begin(), values.end(), [ ](const MyStruct& lhs, const MyStruct& rhs) 
{ 
    return lhs.key < rhs.key; 
}); 

o

struct MyStruct_x_Greater 
{ 
    bool operator()(const MyStruct& lMyStruct, const MyStruct& rMyStruct) const { 
     return lMyStruct.x < rMyStruct.x; 
    } 
}; 

std::sort(values.begin(), values.end(), MyStruct_x_Greater()); 

Ma come fare l'ordinamento per diverse proprietà uno da altro (qualcosa di simile a SQL ORDER BY column1 DESC, column2 ASC)?

Answer 1

Basta cambiare il comparatore. Si supponga di voler ordinare per anno, poi per mese, poi per importo, quindi:

std::sort(values.begin(), values.end(), [ ](const MyStruct& lhs, const MyStruct& rhs) 
{ 
    return std::tie(lhs.year, lhs.month, lhs.amount) < 
      std::tie(rhs.year, rhs.month, rhs.amount); 
}); 

s' std::tupleoperator< fa un confronto lessicografico, quindi non c'è bisogno di rotolare il proprio (e il rischio di sbagliare). Per eseguire un ordine discendente per un attributo, scambiare semplicemente lhs e rhs per quell'attributo.

Answer 2

Ordinare in base a più attributi significa definire un ordine di importanza. Ad esempio, ordinando per anno, mese: anno è più importante del mese:

vector<MyStruct> values; 
std::sort(values.begin(), values.end(), [ ](const MyStruct& lhs, const MyStruct& rhs) 
{ 
    return lhs.year < rhs.year || (lhs.year == rhs.year && lhs.month < rhs.month); 
}); 

Answer 3

Usare tasto successivo solo se i valori di chiave corrente sono uguali:

[ ](const MyStruct& lhs, const MyStruct& rhs) 
{ 
    if(lhs.key1 != rhs.key1) 
     return lhs.key1 < rhs.key1; 

    if(lhs.key2 != rhs.key2) 
     return lhs.key2 < rhs.key2; 

    ...  

    return lhs.keyN < rhs.keyN; 
} 

In questo esempio, entrata verrà ordinato accroding key1, che, key2 e così via fino al keyN.

Answer 4

vostra necessità di scegliere il tipo di ordinamento in fase di esecuzione si differenzia dalla maggior parte delle domande simili (e un paio di risposte impulsive che hai ricevuto). Io suggerisco di dare ogni campo un numero di identificazione, e aggiunge una funzione per confrontare un campo specificato da ID:

template <typename T> 
int cmp(const T& lhs, const T& rhs) 
{ 
    return lhs < rhs ? -1 : lhs == rhs ? 0 : 1; 
} 

struct MyStruct 
{ 
    int id; // 0 
    std::string currencyCode; // 1 
    int month; // 2 
    int year; // 3 
    int amount; // 4 

    int cmp(int field_id, const MyStruct& rhs) const 
    { 
     switch (field_id) 
     { 
      case 0: return cmp(id, rhs.id); 
      case 1: return cmp(currencyCode, rhs.currencyCode); 
      case 2: return cmp(month, rhs.month); 
      case 3: return cmp(year, rhs.year); 
      case 4: return cmp(amount, rhs.amount); 
      default: throw ...cases out of sync with code...; 
     } 
    } 
}; 

// update this as your column heading are clicked... 
std::vector<int> sort_field_ids = ...; 

std::sort(begin(values), end(values), 
    [&](const MyStruct& lhs, const MyStruct& rhs) 
    { 
     for (auto fid : sort_field_ids) 
     { 
      int cmp = lhs.cmp(fid, rhs); 
      if (cmp) return cmp == -1; 
     } 
     // fall back on something stable and unique 
     return lhs.id < rhs.id; 
    }); 

Per sostenere decrescente sorta, mantenere una bandiera in più (ad es std::vector<std::pair<int, bool>> sort_field_ids) poi return (cmp == -1)^descending; (dove fid,descending sono estratti da il tuo pair, o fare riferimento ad essi come .first/.second se preferisci).

Meglio ancora, trovare una libreria grafica con un widget griglia/tabella decente che esegue l'ordinamento internamente.

Answer 5

Un modo ingombrante po 'per realizzare che cosa il vostro cercando di farlo in diversi passaggi (questo dovrebbe funzionare in C++ 03 oltre)

struct ColumnOneDESC{...}; 
struct ColumnTwoASC{...}; 
... 
std::stable_sort(values.begin(), values.end(), ColumnTwoASC()); 
std::stable_sort(values.begin(), values.end(), ColumnOneDESC()); 
... 

E di cource si potrebbe rendere più generico utilizzando std :: non o come

Answer 6

Risolvendo questa assegnando ID ai campi presenta diversi inconvenienti:

• casi non possono essere coperti (come indicato dalla throw)
• ordinamento inverso richiede una bandiera in più
• Non è evidente dal codice che ID sta per quale campo
• Non è facilmente estendibile (è sempre necessario aggiornare le mappature ID)

---

In alternativa, è possibile definire "comparatori", che restituiscono -1, 0 o 1, a seconda che il primo argomento sia inferiore, uguale o maggiore del secondo, rispettivamente. Questi comparatori possono quindi essere combinati e invertiti in modo abbastanza generico e utilizzati come predicati di ordinamento.

Dato un insieme di questi comparatori per i campi della vostra struct, si può comporre di loro in questo modo:

Comparator byYearReverseAndMonth = compose(reverse(byYear), byMonth); 
std::sort(values.begin(), values.end(), with(byYearReverseAndMonth)); 

Modifica in risposta al commento:

Naturalmente non è necessario per definire ciascuna combinazione di comparatori e comparatori inversi al momento della compilazione. Invece, è possibile raccogliere i comparatori desiderati per il prossimo ordinamento in fase di esecuzione, ad esempio, in un vector<Comparator>. Gli esempi di confronto potrebbero, per esempio, essere associate le colonne di una tabella:

vector<Comparator> comparators; 
for (each selected column) { 
    comparators.push_pack(comparatorFor(column)); 
} 

Questi comparatori possono essere costituiti in un unico, con un semplice ciclo su tutti i comparatori:

Comparator composedComparator = comparators[0]; 
for (int i=1; i<comparators.size(); ++i) { 
    composedComparator = compose(comparator, comparators[i]); 
} 

sort(v.begin(),v.end(),with(composedComparator)); 

un abbozzo di ciò che questo può apparire come:

#include <algorithm> 
#include <functional> 
#include <iostream> 
#include <vector> 

struct MyStruct 
{ 
    int id; 
    std::string currencyCode; 
    int month; 
    int year; 
    int amount; 
}; 

typedef std::function<int(const MyStruct& s0, const MyStruct& s1)> Comparator; 
typedef std::function<bool(const MyStruct& s0, const MyStruct& s1)> Predicate; 

template <typename T> 
std::function<int(const T&, const T&)> compose(
    std::function<int(const T&, const T&)> c0, 
    std::function<int(const T&, const T&)> c1) 
{ 
    return[c0, c1](const T& t0, const T& t1) -> int 
    { 
     int r0 = c0(t0, t1); 
     if (r0 != 0) 
     { 
      return r0; 
     } 
     return c1(t0, t1); 
    }; 
} 

template <typename T> 
std::function<int(const T&, const T&)> reverse(
    std::function<int(const T&, const T&)> c) 
{ 
    return[c](const T& t0, const T& t1) -> int 
    { 
     return -c(t0, t1); 
    }; 
} 

template <typename T> 
std::function<bool(const T&, const T&)> with(
    std::function<int(const T&, const T&)> comparator) 
{ 
    return[comparator](const T& t0, const T& t1) 
    { 
     return comparator(t0, t1) < 0; 
    }; 
} 


void print(std::vector<MyStruct>& values) 
{ 
    for (auto it = values.begin(); it != values.end(); ++it) 
    { 
     std::cout << (*it).month << "-" 
      << (*it).year << " id " 
      << (*it).id << std::endl; 
    } 
} 

int main(int argc, char** argv) 
{ 
    std::vector<MyStruct> values; 

    MyStruct m; 
    m.year = 1981; m.month = 1; m.id = 4; values.push_back(m); 
    m.year = 1980; m.month = 2; m.id = 5; values.push_back(m); 
    m.year = 1980; m.month = 4; m.id = 2; values.push_back(m); 
    m.year = 1980; m.month = 3; m.id = 3; values.push_back(m); 
    m.year = 1980; m.month = 4; m.id = 1; values.push_back(m); 

    std::cout << "Before sorting" << std::endl; 
    print(values); 

    Comparator byMonth = [](const MyStruct& s0, const MyStruct& s1) 
    { 
     if (s0.month < s1.month) return -1; 
     if (s0.month > s1.month) return 1; 
     return 0; 
    }; 
    Comparator byYear = [](const MyStruct& s0, const MyStruct& s1) 
    { 
     if (s0.year < s1.year) return -1; 
     if (s0.year > s1.year) return 1; 
     return 0; 
    }; 
    Comparator byId = [](const MyStruct& s0, const MyStruct& s1) 
    { 
     if (s0.id < s1.id) return -1; 
     if (s0.id > s1.id) return 1; 
     return 0; 
    }; 

    Comparator byYearAndMonth = compose(byYear, byMonth); 
    std::sort(values.begin(), values.end(), with(byYearAndMonth)); 

    std::cout << "After sorting by year and month:" << std::endl; 
    print(values); 


    Comparator byYearReverseAndMonth = compose(reverse(byYear), byMonth); 
    std::sort(values.begin(), values.end(), with(byYearReverseAndMonth)); 

    std::cout << "After sorting by year reverse and month:" << std::endl; 
    print(values); 


    Comparator byYearAndMonthAndId = compose(byYearAndMonth, byId); 
    std::sort(values.begin(), values.end(), with(byYearAndMonthAndId)); 

    std::cout << "After sorting by year and month and id:" << std::endl; 
    print(values); 

    return 0; 
} 

_{(Ci scusiamo per i potenziali gaffe, io sono un C++ newb ie)}