ordinamento stl: ordinamento debole e rigoroso

Question

Perché STL funziona con una funzione di confronto ordinamento debole e rigoroso?Perché non può essere un ordinamento parziale?

Answer 1

ordine parziale non sarebbe sufficiente per implementare alcuni algoritmi, come ad esempio un algoritmo di ordinamento. Dal momento che un insieme parzialmente ordinato non necessariamente definire una relazione tra tutti gli elementi del set, come è possibile ordinare un elenco di due elementi che non hanno un rapporto ordine entro l'ordine parziale?

Answer 2

Semplicemente, un ordinamento debole rigoroso è definito come un ordinamento che definisce una relazione di equivalenza (calcolabile)..Le classi di equivalenza sono ordinate secondo l'ordinamento debole rigoroso: un ordinamento debole rigoroso è un ordinamento rigoroso sulle classi di equivalenza.

Un ordinamento parziale (che non sia un ordinamento debole stretto) non definisce quindi una relazione di equivalenza qualsiasi specificazione che utilizzi il concetto di "elementi equivalenti" è priva di significato con un ordinamento parziale che non sia un ordinamento debole e rigoroso. Tutti i contenitori associativi STL utilizzano questo concetto ad un certo punto, quindi tutte queste specifiche sono prive di significato con un ordinamento parziale che non è un ordinamento debole rigoroso.

Poiché un ordinamento parziale (che non è un ordinamento debole e rigoroso) non definisce necessariamente alcun ordinamento rigoroso, non è possibile "ordinare gli elementi" nel senso comune secondo un ordinamento parziale (tutto ciò che si può fare è un "ordinamento topologico" che ha proprietà più deboli ).

Dato

• un insieme matematico S
• un ordinamento parziale < Sopra S
• un valore x In S

è possibile definire una partizione di S (ogni elemento di S è dentro L(x), I(x) O G(x)):

L(x) = { y in S | y<x }
I(x) = { y in S | not(y<x) and not(x<y) }
G(x) = { y in S | x<y }

 L(x) : set of elements less than x
 I(x) : set of elements incomparable with x
 G(x) : set of elements greater than x

Una sequenza viene ordinata in base a < eff per ogni x nella sequenza, elementi di L(x) appaiono per primi nella sequenza, seguiti dagli elementi di I(x), seguito da elementi di G(x).

Una sequenza è ordinata topologicamente eff per ogni elemento y che appare dopo un altro elemento x nella sequenza, y non è inferiore a x.È un vincolo più debole dell'essere ordinati.

È banale dimostrare che ogni elemento di L(x) è inferiore a qualsiasi elemento di G(x).Non esiste una relazione generale tra gli elementi di L(x) ed elementi di I(x), o tra elementi di I(x) ed elementi di G(x).Tuttavia, se < è un ordinamento debole e rigoroso, rispetto a ogni elemento di L(x) è inferiore a qualsiasi elemento di I(x), e di qualsiasi elemento di I(x) è minore di qualsiasi elemento di G(x).

Se < è un ordinamento debole rigoroso, e x<y quindi qualsiasi elemento di L(x) U I(x) è inferiore a qualsiasi elemento I(y) U G(y):qualsiasi elemento non maggiore di x è inferiore a qualsiasi elemento non inferiore a quello y. Ciò non vale necessariamente per un ordinamento parziale.

Answer 3

Citando la risposta data qui :

  

Poiché internamente, questi algoritmi implementano "è uguale a" come !(a < b) && !(b < a).

     

Se è stato utilizzato <= per l'attuazione del operatore minore, poi il sopra   restituirebbe false quando a == b. Un controllo di uguaglianza rotta sarà rovinare   quasi qualsiasi algoritmo.

     

Analogamente, implementano "non è uguale a" come (a < b) || (b < a)   , E ancora una volta, se implementato l'operatore < utilizzando <=, allora   restituisce true quando sono uguali tra loro, mentre in realtà   non sono uguali. Quindi il controllo di uguaglianza è rotto in entrambe le direzioni.

     

Lo scopo di limitare la libreria a un operatore minore è   che tutti gli operatori logici può essere implementato in termini di esso:

     

  
• <(a, b): (a < b)
  
• <=(a, b): !(b < a)
  
• ==(a, b): !(a < b) && !(b < a)
  
• !=(a, b): (a < b) || (b < a)
  
• >(a, b): (b < a)
  
• >=(a, b): !(a < b)
  

     

Questo funziona a patto che il proprio operatore previsto soddisfa le condizioni di un   rigoroso ordinamento debole. Gli operatori <= e >= standard non lo fanno.

Answer 4

Non è possibile eseguire la ricerca binaria con ordinamento parziale. Non è possibile creare un albero binario di ricerca con ordinamento parziale. Quali funzioni / tipi di dati da algoritmo hanno bisogno di ordine e può lavorare con ordinamento parziale?