Riassunto di tre metodi per definire funzioni di confronto in C++

Una delle ragioni per cui C++ è migliore di Pascal è la presenza di STL (Standard Template Library) in C++. STL offre molti metodi utili.

Molte funzioni della libreria di template C++ richiedono parametri ordinati, come Sort(). Ovviamente, se vuoi ordinare un insieme, devi sapere quali oggetti sono nell'insieme, chi viene prima e chi viene dopo. Pertanto, imparare come definire il metodo di confronto è molto importante.

Molte container della libreria di template C++ necessitano di tipi ordinati, come set<T> e priority_queue<T>.

Questo articolo ha lo scopo di insegnare a tutti come definire un metodo di ordinamento per una classe, in modo che possa essere utilizzato in contenitori o metodi STL. Come programmatore C++, dovresti conoscere questi metodi.

Come definire l'ordinamento?

In breve, definire l'ordinamento per una classe ci permette di sapere chi viene prima e chi viene dopo tra due oggetti di questa classe durante il processo di ordinamento. Possiamo implementare questo tramite un metodo che restituisce un valore bool che indica chi viene prima. Chiaramente, vorremmo implementare un metodo simile a f(x,y), che accetta due oggetti dello stesso tipo come parametri e restituisce un valore che indica chi verrà prima.

Strict weak ordering

Quasi tutti i metodi o i contenitori necessitano di un'ordinazione per soddisfare la strict weak ordering nel senso matematico, altrimenti il comportamento di questi metodi o contenitori sarà imprevedibile.

Supponiamo che f(x,y) sia una funzione di confronto. Se questa funzione soddisfa le seguenti condizioni, è una weak ordering stricta.

1. f(x,x) = false;

2. if f(x,y) then !f(y,x)

3. if f(x,y) and f(y,z) then f(x,z)

4. if !f(x,y) && !f(y,x) then x == y; if x == y and y == z then x == z;

Sembra un po' confusionario, ma non preoccuparti, purché il tuo metodo di confronto restituisca sempre false per elementi uguali, il tuo metodo soddisfa i requisiti.

Tre metodi di implementazione:

1. Definisci l'operatore <.

　Questo metodo ci permette di conferire alla nostra classe una capacità di ordinamento innata. Ad esempio, se abbiamo una classe come questa:

struct Edge
{
int from, to, weight;
};

Poiché desideri implementare l'algoritmo di Kruskal, vorresti che tutti gli archi del grafo fossero ordinati in ordine decrescente in base al peso. Definisci l'operatore < in questo modo:

struct Edge
{
    int from, to, weight;
    bool operator<(Edge other) const
    {
        return weight > other.weight;
    }   
};  

Il metodo che definisci deve essere dichiarato come segue:

bool operator<(T other) const

Attenzione: la parola chiave const è obbligatoria.

Se non ti piace questo metodo, ad esempio, se vuoi confrontare due oggetti ma il metodo ha solo un parametro, puoi scegliere il seguente metodo:

　

struct Edge
{
　　int from, to, weight;
　　friend bool operator<(Edge a, Edge b)
　　{
　　　　return a.weight > b.weight;
　　}
};

La pair<T1,T2> di STL ha una capacità di ordinamento innata. La comparazione tra due oggetti pair avviene in questo modo: prima si confronta il primo parametro, se il primo parametro è lo stesso si confronta poi il secondo parametro.

Tutti i tipi nativi hanno la capacità di ordinamento innata, che è attribuita dal compilatore.

2. Metodi di ordinamento personalizzati.

Questo metodo viene spesso utilizzato nelle seguenti situazioni:

a. Confronto di tipi nativi

b. Non può modificare il tipo da confrontare

c. Metodi di confronto personalizzati oltre al tipo di confronto personalizzato

In poche parole, un metodo di confronto accetta due oggetti dello stesso tipo come parametri e restituisce un valore bool, come segue:

bool name(T a, T b);
　
3. Soveraccaricare l'operatore ()

Possiamo passare la funzione di confronto come primo parametro del costruttore del contenitore STL e specificare il tipo di funzione come parametro di modello. Ad esempio:

set<int,bool (*)(int,int)> s(cmp);

Questo può essere un po' confuso. Vediamo come utilizzare le funzioni di copia per risolvere i tuoi dubbi.

Dobbiamo definire una nuova classe e sovraccaricare l'operatore ()

vector<int> occurrences; 
struct cmp 
{ 
  bool operator()(int a, int b) 
  { 
    return occurrences[a] < occurrences[b];
  } 
};

Ora possiamo passare questa classe come parametro di modello ai contenitori STL.

set<int, cmp> s;
priority_queue<int, vector<int>, cmp> pq;

STL ha anche funzioni di copia integrate, come less<T>, greater<T> ecc.

Le funzioni di copia possono essere inizializzate e utilizzate come funzioni normali. Il modo più semplice è aggiungere () alla fine della funzione di copia.

sort(data.begin(), data.end(), greater<int>());

Questo è un riassunto di tutte le tre modalità di definizione di funzioni di confronto in C++, che spero riceverà il vostro supporto e applausi. ~ Tutorial del redattore