Qual è la differenza tra una sentinella e un iteratore finale?

Question

Durante la lettura di Eric Niebler's range proposal,
mi sono imbattuto nel termine sentinella come sostituto per l'iteratore finale.
Ho difficoltà a comprendere i vantaggi della sentinella su un iteratore finale.
Qualcuno potrebbe fornire un chiaro esempio di ciò che il sentintel porta sul tavolo che non può essere fatto con coppie di iteratori standard?

"Un sentinella è un'astrazione di un iteratore past-the-end. Sentinelle sono tipi regolari che possono essere utilizzati per indicare la fine di un intervallo. A sentinella e un iteratore che denotano una gamma deve be EqualityComparable Un sentinella denota un elemento quando un iteratore i è uguale alla sentinella e i punti a tale elemento. " - N4382

Penso che le sentinelle funzionano come funzioni nel determinare la fine di un intervallo, anziché solo la posizione?

Answer 1

Sentinel consente semplicemente all'endanale di avere un tipo diverso.

Le operazioni consentite su un iteratore passato-fine sono limitate, ma questo non si riflette nel suo tipo. Non è ok a * un iteratore .end(), ma il compilatore ti lascerà.

Una sentinella non ha un dereference unario, o ++, tra le altre cose. In genere è limitato come gli iteratori più deboli uno dopo l'iteratore finale, ma viene applicato in fase di compilazione.

C'è un pagamento. Rilevare spesso lo stato finale è più facile che trovarlo. Con una sentinella, == può inviare "a rilevare se l'altro argomento è passato alla fine" al momento della compilazione, invece del tempo di esecuzione.

Il risultato è che un codice che prima era più lento dell'equivalente C ora compila fino alla velocità del livello C, come la copia di una stringa terminata null usando std::copy. Senza sentinelle, dovevi scansionare per trovare la fine prima della copia, o passare in iteratori con una bandiera bool che diceva "I am the end sentinel" (o equivalente), e controlla su ==.

Ci sono altri vantaggi simili quando si lavora con intervalli basati sul conteggio.Inoltre, alcuni aspetti come gli intervalli di zip diventano più facili da esprimere (il finale zip sentinel può contenere entrambe le sentinelle di origine e restituire uguale se fa il sentinel: gli iteratori di zip possono solo confrontare il primo iteratore o confrontare entrambi).

Un altro modo di pensarci è che gli algoritmi tendono a non utilizzare la piena ricchezza del concetto di iteratore sul parametro passato come iteratore finale e che l'iteratore viene gestito in modo diverso nella pratica. Sentinel significa che il chiamante può sfruttare quel fatto, che a sua volta consente al compilatore di sfruttarlo più facilmente.

---

Una gamma zip è quello che si ottiene quando si inizia con 2 o più intervalli, e "zip" insieme come una chiusura lampo. L'intervallo ora supera le tuple dei singoli elementi dell'intervallo. L'avanzamento di un iteratore zip fa avanzare ciascuno degli iteratori "contenuti" e idem per il dereferenziamento e il confronto.

Answer 2

Le sentinelle e gli iteratori finali sono simili in quanto contrassegnano la fine di un intervallo. Differiscono nel modo in cui viene rilevata tale fine; o stai testando l'iteratore stesso o stai testando il valore dei dati sull'iteratore. Se stai già eseguendo test sui dati, una sentinella può consentire al tuo algoritmo di terminare "gratuitamente" senza ulteriori test. Questo può semplificare il codice o renderlo più veloce.

Un sentinella molto comune è il byte zero utilizzato per contrassegnare la fine di una stringa. Non è necessario mantenere un iteratore separato per la fine della stringa, può essere determinato mentre si lavora con i caratteri della stringa stessa. Lo svantaggio di questa convenzione è che una stringa non può contenere un carattere zero.

Nota che ho scritto questa risposta prima di leggere la proposta nel link; questa è la classica definizione di sentinella che potrebbe non essere d'accordo con la definizione proposta qui.

Answer 3

La motivazione centrale per l'introduzione di una sentinella è che ci sono molte operazioni di iteratore che sono supportate ma di solito non sono mai necessarie per l'iteratore finale end(). Ad esempio, non vi è quasi alcun punto nel dereferenziamento tramite lo *end(), nell'incrementarlo tramite ++end() e così via (*).

Al contrario, l'utilizzo principale di end() consiste semplicemente nel confrontarlo con un iteratore it per segnalare se it è alla fine della cosa che viene semplicemente iterata. E, come sempre nella programmazione, requisiti diversi e diverse applicazioni suggeriscono un nuovo tipo.

La libreria range-v3 trasforma questa osservazione in un'ipotesi (che è implementata attraverso un concetto): introduce un nuovo tipo per end() e richiede solo che sia uguaglianza-paragonabile al corrispondente iteratore - ma non richiede le solite operazioni di iteratore). Questo nuovo tipo di end() è chiamato sentinella.

Il vantaggio principale qui è l'astrazione acquisita e una migliore separazione delle preoccupazioni, in base alla quale il compilatore è eventualmente in grado di eseguire una migliore ottimizzazione. Nel codice, l'idea di base è questa (questo è solo per la spiegazione e non ha nulla a che fare con la libreria gamma-v3):

struct my_iterator; //some iterator 
struct my_sentinel 
{ 
    bool is_at_end(my_iterator it) const 
    { 
     //here implement the logic when the iterator is at the end 
    } 
}; 

auto operator==(my_iterator it, my_sentinel s) //also for (my_sentinel s, my_iterator it) 
{ 
    return s.is_at_end(it); 
} 

Vedi l'astrazione? Ora, è possibile realizzare qualsiasi controllo che si desidera nella funzione is_at_end, ad esempio:

• fermata mai (ottenere una gamma infinita)
• fermata dopo N incrementi (per ottenere una gamma contati)
• arresto quando una \0 viene rilevato, ovvero *it = '\0' (per il loop su stringhe a C)
• fermarsi quando è 12'o orologio (per pranzare) e così via.

Inoltre, riguardo alle prestazioni, si è in grado di fare uso di tempo-informazione compilazione nel controllo (ad esempio, pensare al N sopra come parametro in fase di compilazione). In questo caso, il compilatore potrebbe essere in grado di ottimizzare meglio il codice.

---

(*) Si noti che questo non significa che in generale non è utile per questo tipo di operazioni.Ad esempio, --end() può essere utile in alcuni luoghi, vedi ad es. this question. Tuttavia, è apparentemente possibile implementare la libreria standard senza questi - questo è ciò che ha fatto la libreria range-v3.