Multi-Key ordinamento personalizzato in C++

Question

problema dichiarazione:

voglio ordinare un std::vector di una struttura con mia abitudine criteri di ordinamento.

La struttura è:

struct Node 
{ 
    int x; 
    int y; 
    float value; 
} 

Ho un vettore

std::vector<Node> vec;

mio ordinamento personalizzato criteri è che il vettore deve prima essere allineati secondo y e poi da x. (Proprio come in Microsoft Excel)

Esempio:

ingresso

x y 

5 6 
2 4 
1 1 
1 0 
8 10 
4 7 
7 1 
5 4 
6 1 
1 4 
3 10 
7 2 

uscita:

x y 

1 0 
1 1 
6 1 
7 1 
7 2 
1 4 
2 4 
5 4 
5 6 
4 7 
3 10 
8 10 

Può il sopra citato ordinamento essere raggiunto attraverso una delle le funzioni di ordinamento della libreria standard C++ ? Se no, allora c'è qualche altra libreria che posso usare?

Answer 1

Sì, è possibile farlo utilizzando std::sort utilizzando una funzione di confronto.

bool comparison(const Node& node1, const Node& node2) 
{ 
    if (node1.y < node2.y) return true; 
    if (node1.y == node2.y) return node1.x < node2.x; 

    return false; 
} 

int main() { 
    std::sort(vec.begin(), vec.end(), comparison); 
} 

Answer 2

std::sort accetta una funzione di confronto personalizzata. Non ho ancora testato questo, ma la tua potrebbe essere simile:

bool cmp (const Node& lhs, const Node& rhs) 
{ 
    if (lhs.y < rhs.y) return true; 
    else if (lhs.y == rhs.y) return (lhs.x < rhs.x); 
    else return false; 
} 

Answer 3

In generale, operatori di confronto di attuazione (e funzioni) di più campi è più chiaramente espresso in termini di tie quando è richiesta lexicographical ordinare.

static bool compare(Node const& l, Node const& r) { 
    // Note the alignment so that both expressions only differ in their `l` and `r` ? 
    return std::tie(l.y, l.x) 
     < std::tie(r.y, r.x); 
} 

Tuttavia, anche questo lascia alcune duplicazioni e percorso per incoerenza. Il seguente aiutante provvede a che:

static std::tuple<int&,int&> tuplize(Node const& n) { return std::tie(n.y, n.x); } 

che possono poi essere applicato semplicemente:

static bool compare(Node const& l, Node const& r) { 
    return tuplize(l) < tuplize(r); 
} 

Taaadaaam :)