Una lattina di span

I documenti che saranno discussi alla prossima riunione del comitato C++ sono fuori. L'elenco contiene una serie di documenti interessanti e controversi. Tra questi, Herbceptions, una serie di proposte di concorrenza simultanea, una proposta che richiede importanti modifiche al design delle coroutine TS, E una proposta di 200 pagine di facile revisione per unificare la gamma TS nel std spazio dei nomi.

In totale, ci sono circa 140 articoli tutti piuttosto interessanti.

Non sorprende quindi che l'argomento più caldo su Cpp Slack in questi ultimi giorni sia std::span .

Aspetta, cosa?

Prima di tutto, se non sei su Cpp Slack, dovresti, è una grande community.

Secondo, forse hai sentito che std::span era già unito nella bozza di C++ 20 l'ultima riunione, quindi perché parlarne e perché una modesta aggiunta alla libreria dovrebbe fare così tanto flusso di inchiostro virtuale?

O forse non hai mai sentito parlare di std::span e ti stai chiedendo cosa std::span anche è.

Cercando di non rompere le uova, direi che può essere descritto come un involucro di dimensioni fisse, non proprietario su una sequenza contigua di oggetti che ti consente di iterare e mutare i singoli elementi in quella sequenza .


#include <vector>
#include <gsl/span>
#include <iostream>

int main() {
 std::vector<std::string> greeting = {"hello", "world"};
 gsl::span<std::string> span (greeting);
 for(auto && s : span) {
 s[0] = std::toupper(s[0]);
 }
 for (const auto& word: greeting) {
 std::cout << word << ' ';
 }
}

Questo stampa semplicemente Hello World e illustrare la mutevolezza del contenuto di span.

span può rappresentare qualsiasi sequenza contigua, incluso std::array , std::string , T[] , T* + size , o un sottoinsieme o una matrice o un vettore.

Naturalmente, non tutti i contenitori sono span , ad esempio né std::list o std::deque sono contigui nella memoria.

span è una vista?

Non sono sicuro di come rispondere. Mi chiedo cosa dice la proposta. Quindi leggiamo la proposta di span:

Il tipo span è un'astrazione che fornisce una vista su una sequenza contigua di oggetti, la cui memorizzazione è di proprietà di qualche altro oggetto.

Potresti anche aver notato che il documento è intitolato "span:bounds-safe views ”.

(sottolineatura mia)

Quindi uno span è un view . Tranne che si chiama span . Ho chiesto in giro perché view chiamato span , e il motivo sembra essere che il comitato aveva voglia di chiamarlo span quel giorno. Infatti, quando lo span paper è stato presentato per la prima volta davanti al comitato, si chiamava array_view .Un array in c++ è analogo a una sequenza di elementi contigui in memoria. Almeno, il vocabolario Span esiste in C# praticamente con la stessa semantica.

Ma ora dobbiamo parlare di stringhe.

Con questo intendo dire che dobbiamo parlare di std::string . A tutti gli effetti, std::string è un std::vector<char> .Ma le persone pensano che le stringhe siano dei fiocchi di neve speciali che hanno bisogno del loro contenitore speciale con un sacco di metodi speciali.Quindi string ottiene un length() metodo perché size() probabilmente non era abbastanza buono per la principessa, alcuni find*() metodi e comparatori lessicografici.

E voglio dire, è giusto. Molte applicazioni gestiscono i testi più di altri tipi di dati, quindi avere una classe speciale per farlo ha perfettamente senso. Ma fondamentalmente, l'unica differenza tra un vettore e una stringa è quella che viene trasmessa dall'intento dei programmatori.

Va notato che std::string ( o std::wstring e l'altro std::*string ) è completamente inadatto a gestire testo che non è codificato come ASCII.

Se sei una delle 6 miliardi di persone sulla terra che non parlano inglese, passerai un brutto periodo se pensi a std::string può fare qualsiasi cosa per te. (Scusate il mio cinese). Nella migliore delle ipotesi, puoi sperare che se non lo muti in alcun modo o lo guardi in modo strano, potrebbe ancora sembrare a posto quando lo visualizzerai da qualche parte. Ciò include anche i comparatori lessicografici e il find*() metodi. Non fidarti di loro con il testo.

(Aspetta, il comitato C++ sta lavorando sodo su questi problemi!)

Per il momento, è meglio vedere std::*string come contenitori opachi di byte. Come faresti con un vettore.

Ahimè string , essendo il bambino preferito, ha avuto il suo involucro che non lo possiede 3 anni prima di chiunque altro. Quindi in C++17 è stato introdotto ~~string_span~~ .No, in realtà è string_view .

È un string , è un span . È l'api di entrambi mescolati insieme. Ma si chiama view .

Ha tutti gli stessi metodi speciali per i fiocchi di neve che string ha.

Voglio dire, quei metodi non sono poi così male. L'autore del string_view la carta aveva qualcosa di molto carino da dire su di loro:

Molte persone hanno chiesto perché non stiamo rimuovendo tutti i metodi find*, dal momento che sono ampiamente considerati una verruca su std::string. Innanzitutto, vorremmo semplificare al massimo la conversione del codice per utilizzare string_view , quindi è utile mantenere l'interfaccia il più possibile simile a std::string.

Ecco qua:una verruca di compatibilità con le versioni precedenti.

Quindi, forse potremmo effettivamente definire std::string_view in termini di span ?

template <typename CharT>
class basic_string_view : public std::span<CharT> {
 std::size_t length() const {
 return this->size();
 }
};

Semplice e facile!

Tranne questo è completamente sbagliato perché a differenza di span, std::string_view è un non mutabile visualizza.

Quindi in realtà è più simile a più simile a

template <typename CharT>
class basic_string_view : public std::span<const CharT> {/**/};

Tornando al string_view carta, l'autore spiega che:

Il caso costante è abbastanza più comune del caso mutabile che deve essere il valore predefinito. Rendere il caso mutabile predefinito impedirebbe il passaggio di valori letterali stringa nei parametri string_view, il che annullerebbe un caso d'uso significativo per string_view. In una situazione alquanto analoga, LLVM ha definito una classe ArrayRef nel febbraio 2011 e non ha trovato la necessità del MutableArrayRef corrispondente fino a gennaio 2012. Non hanno ancora bisogno di una versione mutabile di StringRef. Una possibile ragione di ciò è che la maggior parte degli usi che necessitano di modificare una stringa devono anche essere in grado di cambiarne la lunghezza, cosa impossibile anche attraverso una versione mutabile di string_view.

È difficile discuterne, soprattutto considerando quello che ho appena detto sugli archi. Quindi basic_string_view non è modificabile perché è un valore predefinito ragionevole per le stringhe .

Potremmo usare typedef basic_string_view string_view per rendere il caso immutabile il valore predefinito pur continuando a supportare il caso mutabile usando lo stesso modello. Non sono andato in questo modo perché complicherebbe la definizione del modello senza aiutare in modo significativo gli utenti.

Tuttavia, C++ è modificabile per impostazione predefinita e constness è opt-in. Quindi avere un tipo è const per impostazione predefinita, anche se più attraente per la nostra sensibilità moderna e più saggia potrebbe non essere così eccezionale:non c'è modo di rinunciare a basic_string_view constness.Da mutable è sempre l'impostazione predefinita, la lingua non fornisce un modo per costruire un basic_string_view<mutable char> .

Metodi speciali per i fiocchi di neve a parte, c'è 0 differenza tra typedef basic_string_view<const char> string_view e basic_string_view : public std::span<CharT> .Quindi, std::span è una vista, std::view è un intervallo, entrambe le classi sono fondamentalmente la stessa cosa e hanno lo stesso layout di memoria.

Tanto simile in effetti che un'anima coraggiosa suggerì che potessero essere fusi. Era il 2015 quando span era ancora chiamato array_view .

Sfortunatamente, alcune persone ora pensano al termine view in qualche modo implica immutabile.

Ma l'unico motivo per cui si potrebbe pensare così si riduce a string dirottare un tipo di vocabolario tutto per sé. E indovina qual è l'ultima cosa che dovresti fare su una stringa codificata utfX? Tagliarlo casualmente in viste al limite di unità di codice/byte.

Nelle gamme TS , nulla implica che le visualizzazioni siano immutabili:

Il concetto di visualizzazione specifica i requisiti di un tipo di intervallo che ha operatori di copia, spostamento e assegnazione a tempo costante, ovvero il costo di queste operazioni non è proporzionale al numero di elementi nella visualizzazione.

TL;DR:view e span:stessa cosa; string_view :speciale fiocco di neve confuso.

Andando avanti...

L'intervallo è un intervallo?

In C++20, un intervallo è semplicemente qualcosa con un begin() e un end() , quindi un span è un intervallo. Possiamo verificare che sia effettivamente così:


static_assert(std::experimental::ranges::Range<std::vector<int>>);
static_assert(std::experimental::ranges::Range<gsl::span<int>>);

Possiamo perfezionarlo ulteriormente, span è un intervallo contiguo :un intervallo i cui elementi sono contigui nella memoria.

Mentre attualmente né la nozione di contiguous iterator o il ContiguousRange concept fanno parte di C++20, c'è una proposta.~~Stranamente, non sono riuscito a trovare una proposta per ContiguousRange~~ ¹ . Fortunatamente, è implementato in cmcstl2 così possiamo provarlo.


static_assert(std::experimental::ranges::ext::ContiguousRange<gsl::span<int>>);

Quindi, dato che sappiamo che span è fondamentalmente un wrapper su un intervallo contiguo, forse possiamo implementarlo noi stessi?

Ad esempio, potremmo aggiungere della copertura di zucchero su un paio di iteratori:


#include <gsl/span>
#include <stl2/detail/range/concepts.hpp>
#include <vector>

template <
 std::experimental::ranges::/*Contiguous*/Iterator B,
 std::experimental::ranges::/*Contiguous*/Iterator E
>
class span : private std::pair<B, E> {
public:
 using std::pair<B, E>::pair;
 auto begin() { return this->first; }

 auto end() { return this->second; }

 auto size() const { return std::count(begin(), end()); }

 template <std::experimental::ranges::ext::ContiguousRange CR>
 span(CR &c)
 : std::pair<B, E>::pair(std::begin(c), std::end(c)) {}
};

template <std::experimental::ranges::ext::ContiguousRange CR>
explicit span(CR &)->span<decltype(std::begin(CR())), decltype(std::end(CR()))>;

template <std::experimental::ranges::/*Contiguous*/Iterator B,
 std::experimental::ranges::/*Contiguous*/Iterator E>
explicit span(B && e, E && b)->span<B, E>;

int main() {
 std::vector<int> v;
 span s(v);
 span s2(std::begin(v), std::end(v));
 for (auto &&e : s) {
 }
}

Non è carino e dandy?

Bene... tranne, ovviamente, questo non è un span<int> per niente . È una cosa da pazzi

span<
 __gnu_cxx::__normal_iterator<int*, std::vector<int>>,
 __gnu_cxx::__normal_iterator<int*, std::vector<int>>
>

Abbastanza inutile, vero?

Vedi, possiamo pensare a views e span e tutte quelle cose come fondamentalmente la "cancellazione del modello" su intervalli. Invece di rappresentare un intervallo con una coppia di iteratori il cui tipo dipende dal contenitore sottostante, useresti una vista/estensione.

Tuttavia, un intervallo non è un intervallo. Dato un ContiguousRange - o una coppia di contiguous_iterator ,non è possibile costruire un span .

Questo non verrà compilato:


int main() {
 constexpr int uniform_unitialization_workaround = -1;
 std::vector<int> a = {0, 1, uniform_unitialization_workaround};
 gsl::span<int> span (std::begin(a), std::end(a));
}

Quindi, da un lato, span è un intervallo, dall'altro non funziona bene con gli intervalli. Per essere onesti, span è stato votato nella bozza prima che potesse essere presentato il grande documento Contiguous Ranges. Ma poi di nuovo, quel documento non è stato aggiornato in seguito e gli intervalli contigui sono stati discussi dal 2014, anche da thestring view paper.

Speriamo che questo venga risolto prima del 2020!

Nel frattempo, l'utilizzo di span con gli algoritmi std dovrà essere fatto in questo modo, immagino.


 auto begin = std::begin(names);
 auto end = std::find_if(begin, std::end(names), [](const std::string &n) {
 return std::toupper(n[0]) > 'A';
 });
 gsl::span<std::string> span {
 &(*begin),
 std::distance(begin, end)
 };
}

Il che è bello, sicuro e ovvio.

Poiché stiamo parlando di memoria contigua, esiste una relazione equivalente tra una coppia di (begin, end) puntatori e un begin puntatore + la dimensione.

Detto questo, possiamo riscrivere la nostra classe span


template <typename T>
class span : private std::pair<T*, T*> {
public:
 using std::pair<T*, T*>::pair;
 auto begin() { return this->first; }

 auto end() { return this->second; }

 auto size() const { return std::count(begin(), end()); }

 template <std::experimental::ranges::ext::ContiguousRange CR>
 span(CR &c)
 : std::pair<T*, T*>::pair(&(*std::begin(c)), &(*std::end(c))) {}

 template <std::experimental::ranges::/*Contiguous*/Iterator B,
 std::experimental::ranges::/*Contiguous*/Iterator E>
 span(B && b, E && e)
 : std::pair<T*, T*>::pair(&(*b), &(*e)) {}
};

template <std::experimental::ranges::ext::ContiguousRange CR>
explicit span(CR &)->span<typename CR::value_type>;

template <std::experimental::ranges::/*Contiguous*/Iterator B,
 std::experimental::ranges::/*Contiguous*/Iterator E>
explicit span(B && b, E && e)->span<typename B::value_type>;

Questo si comporta concettualmente come lo standard std::span eppure è più facile da capire e ragionare.

Aspetta, di cosa stiamo parlando? dimenticavo...

template <typename T>
struct {
 T* data;
 std::size_t size;
};

Oh, giusto, dannato span !

Immagino che il mio punto sia che contiguous ranges sono la soluzione generale per span . span può essere facilmente descritto in termini di un intervallo contiguo. Implementazione o ragionamento su span senza contiguous ranges tuttavia è più complicato.string_view essendo un ulteriore affinamento dell'intervallo, è chiaro che la commissione ha iniziato con la soluzione più specializzata e sta procedendo ai casi generali, lasciandosi dietro strane incongruenze.

Finora abbiamo stabilito che span è una vista con qualsiasi altro nome e un intervallo ingombrante. Ma qual è il vero problema?

Qualcosa di molto, molto sbagliato con span

Direi che span (e view , stessa cosa) interrompe C++.

La libreria standard è costruita su una tassonomia di tipi e in particolare sul concetto di Regular tipo. Non pretendo di spiegare quella metà come ha fatto Barry Revzin, quindi vai a leggere il suo fantastico post sul blog che spiega il problema in dettaglio.

Fondamentalmente, gli algoritmi generici standard fanno alcune ipotesi su un tipo per garantire che gli algoritmi siano corretti. Queste proprietà del tipo vengono verificate staticamente in fase di compilazione, tuttavia, se una definizione di tipo non corrisponde al suo comportamento, l'algoritmo compilerà ma potrebbe produrre risultati errati.

Fortunatamente, span è la definizione di un Regular genere. Puoi costruirlo, copiarlo e confrontarlo. Quindi può essere inserito nella maggior parte degli algoritmi standard. Tuttavia, gli operatori di confronto in realtà non confrontano due span , confrontano i dati span indica . E come ha illustrato Barry, ciò può facilmente portare a un codice errato.

Tony Van Eerd, avendo un talento per distillare le verità fondamentali, ha osservato che mentre la definizione di Regular era abbastanza preciso (ma, a quanto pare, non abbastanza preciso per gestire struct {T* ptr }; ), il suo intento era garantire che la gestione di Regular gli oggetti non dovrebbero avere effetti sul resto del programma. Essendo oggetti proxy, span sfida questa aspettativa.

Dall'altro lato della tabella, gli utenti dell'STL possono ragionevolmente aspettarsi span essere un sostituto immediato di un const vector & .E succede per lo più, puoi confrontarlo con un vettore, scorrere su di esso... Finché, ovviamente, non provi a copiarlo o a cambiarne il valore, quindi smette di comportarsi come un vector .

Aspettative non soddisfatte

span è un Regular genere. span è un puntatore a un blocco di memoria. span è un valore. span è SemiRegular , non Regular .span sembra ricino e morde come un serpente, ma in realtà è un ornitorinco dal becco d'anatra, un mostruoso ibrido che sventa ogni tentativo di classificazione.

span ha una doppia natura, un'ambivalenza inconciliabile che fa sì che metà del comitato si affretti senza speranza per trovare una qualche forma di conforto negli insegnamenti di Alexander Stepanov mentre l'altra metà è stata sorpresa a sussurrare che forse dovremmo riscrivere tutto in ruggine.

Puoi smetterla con la drammatizzazione dei testi?

Ehm, giusto. Scusa.

Ma in realtà, span cerca di accontentare sia gli scrittori di biblioteche in quanto si comportano bene con algoritmi generici sia gli scrittori non di biblioteche in quanto offrono un'API piacevole e facile da usare. Obiettivi davvero nobili.

Tuttavia, non puoi avere la tua torta e mangiarla anche tu. E così è male per essere un proxy di container e male come uno standard ben educato Regular type.Per la sua duplice natura, la sua API è facile da usare in modo improprio e il suo aspetto umile lo fa sembrare un contenitore innocente piuttosto che la trappola mortale che è. È logico che se l'API è in qualche modo facile da usare in modo improprio, lo sarà . E quindi span non è altro che una testata nucleare senza pretese.

In breve, non soddisfa le aspettative, perché alcuni dei suoi obiettivi di progettazione sono antitetici. Nello specifico:

È un oggetto simile a un puntatore il cui confronto confronta il contenuto dei dati sottostanti.
È un oggetto simile a un contenitore la cui assegnazione non modifica effettivamente i dati sottostanti.

Campo di fissaggio

Un mostro del genere può anche essere domato?

Credo che possa, e in realtà non richiederebbe molto.

In effetti, non c'è nulla di intrinsecamente sbagliato in span , abbiamo solo bisogno che lasci cadere la maschera ed essere chiari sulla sua vera natura. Si può dire molto sull'importanza di nominare le cose in modo corretto e fino a span preoccupa, ci sono più di pochi nomi sbagliati.

Disimballiamo

span::operator==()

Ci sono interi campi della matematica dedicati a descrivere come le cose siano "uguali" o comparabili. Si sono fatte carriere, si sono scritti libri, si sono riempite biblioteche, si è teorizzato, organizzato, ricercato e portato su Haskell. Ecco perché, nella sua infinita saggezza, perl 6 ha dedicato alcuni token per descrivere l'uguaglianza delle cose:

==
eq
===
aqv
=:=
=~=
~~

Nel frattempo, std::span sta riducendo l'intera teoria dei gruppi in 2 caratteri. E, naturalmente, c'è solo così tanto significato che si può infondere in un token da 2 byte.

Molte discussioni tra i membri del comitato hanno riguardato se operator== dovrebbe confrontare l'identità (se due span puntano agli stessi dati sottostanti) o gli elementi.

Ci sono sostenitori di entrambi i significati, ed entrambi sono ~~sbagliati~~ giusto. No davvero, credo che siano sbagliati . (Farò così tanti amici con quell'articolo...).

Se entrambi i lati dell'argomento hanno tanto senso quanto l'altro, è perché non c'è una risposta. Inizia a trattarsi di argomenti inventati per sostenere le proprie preferenze personali che di solito si trovano da qualche parte tra questi due estremi:

Dovremmo attenerci alle categorie di tipo e alla correttezza della libreria standard, altrimenti inevitabilmente ci salteremo il piede.
Dovremmo soddisfare le aspettative degli utenti, altrimenti si faranno saltare i piedi e poi ci daranno la testa.

Entrambe sono posizioni molto giuste e sensate da mantenere ed è necessario rispettare entrambi questi punti di vista.

L'unico modo per evitare un bagno di sangue è, quindi, rimuovere completamente tutti gli operatori di confronto .Se non puoi confrontarli, non puoi confrontarli in modo errato.

Sfortunatamente, se un tipo non è comparabile, il stl kinda smette di funzionare - il tipo smette di essere Regular e concretamente gli algoritmi di ordinamento e ricerca non funzioneranno.

Una soluzione potrebbe essere quella di ricorrere ad alcuni ADL trucco per creare span comparabile solo nel contesto della libreria standard. Ciò può essere dimostrato:


#include <vector>
#include <algorithm>

namespace std {
 class span { };
}

namespace __gnu_cxx::__ops {
 bool operator<(const std::span &a, std::span &b);
}

void compile() {
 std::vector<std::span> s;
 std::sort(s.begin(), s.end());
}

//void do_no_compile() {
// std::span a, b;
// a < b;
//}

Ciò renderebbe span veramente regolare all'interno dello stl e impedire alle persone di confrontare la cosa sbagliata. Il confronto tra gli elementi verrebbe eseguito tramite std::equal .

span::operator=()

A seconda che lo span sia visto come un puntatore o un contenitore, si può presumere che stiamo impostando il puntatore dello span oi dati sottostanti; sfortunatamente, non possiamo usare lo stesso trucco ADL di == e non vedo altre soluzioni ragionevoli. C'è un altro modo per correggere operator= tuttavia:rendendo molto chiaro che span si comporta come un puntatore...

Intervallo di ridenominazione

span si chiamava array_view . È facile vedere un view come puntatore (non nel contesto dell'intervallo TS però).view rende ancora più chiaro che si tratta di una vista e quindi non di proprietà.

array porta che è un puntatore a un segmento di memoria contiguo perché è ciò che gli array sono nel modello di memoria C.

E sì, ciò significherebbe che array_view è mutevole e string_view è costante.

Non ha senso. Tuttavia, ha molto più senso che avere un span molto confuso tipo che i migliori esperti del mondo non sono abbastanza sicuri di cosa pensare.

Non si ferma qui...

Un paio di articoli stavano pubblicando, alleviando più problemi con lo span

[La sua dimensione è, per qualche motivo, firmata] (https://wg21.link/p1089)
[La sua API presenta alcune incongruenze] (https://wg21.link/p1024)

Cambiare le persone?

Alcuni credono che dovremmo insegnare alle persone che gli ornitorinchi sono anatre perché sicuramente sarebbe conveniente. Ma, mentre soddisfare le aspettative è difficile e talvolta impossibile, cercare di far cambiare completamente le loro aspettative alle persone sembra un po' irragionevole esserlo. Nella migliore delle ipotesi ci vogliono decenni e quando la conoscenza e la saggezza collettiva inizieranno a cambiare, gli esperti in prima linea avranno bisogno di persone che abbiano una serie di aspettative completamente nuove.

Certo, a volte nulla può sostituire l'istruzione, i discorsi ei libri. Tuttavia, gli insegnanti hanno battaglie più grandi su cui concentrarsi rispetto a span .

Una storia più semplice per visualizzazioni e intervalli

Dopo aver ordinato i mammiferi su un grafico e gli uccelli sugli altri, immagino che i biologi fossero piuttosto incazzati nel vedere uno scoiattolo volante.

Tuttavia, il comitato non sta solo classificando i tipi esistenti, ma li sta progettando. E mi chiedo se, per quanto possa essere divertente vederli saltare sopra il baldacchino, abbiamo davvero bisogno di scoiattoli volanti non mutabili.

Ranges sono... intervalli rappresentati da una coppia di iteratori. O possiedi(Containers ) o non proprietario(Views )
Views sono... visualizzazioni non proprietarie su intervalli.
array_view e string_view offrire la cancellazione di una vista su un intervallo rappresentato da una coppia di iteratori che sono dei puntatori.
I contenitori possiedono i dati

Forse non è del tutto esatto. Ma abbiamo bisogno di una teoria unificante di tutto.

Per concludere questa breve introduzione di span , ti lascio con questa foto di una giraffa.

Inizialmente ho menzionato in modo errato quel ContiguousRange non è stato proposto per l'inclusione nello standard C++. Questo non è corretto ↩︎