C++ Contiguous Sequence Concept

Question

La libreria standard C++ offre una varietà di "concetti" che vengono utilizzati per specificare un'interfaccia per gli oggetti contenitore. Ad esempio, std::vector implementa i concetti Container, Sequence, RandomAccessContainer e ReversibleContainer.

v'è un concetto, specificato sia in C++ 03 o C++ 11, che descrive un Sequence che garantisce memoria contigua tra elementi, in modo che:

static_cast<void*>(&some_sequence[N]) == static_cast<void*>(&some_sequence[0] + N)>

Questo sarebbe un utile concetto perché indica se è possibile utilizzare il contenitore con qualsiasi funzione che prevede un buffer di memoria contiguo, ad esempio std::istream::read.

so che, in pratica, solo std::vector (e ritengo std::string in C++ 11 solo) effettivamente garantire un buffer contiguo sottostante - ma è presente garanzia unica per std::vector o c'è un definito "Concept" che indica un classe generica Sequence che fornisce memoria contigua?

Answer 1

Dalla C++ 03, solo std::vector garantisce che (23.2.4.1):

Gli elementi di un vettore sono memorizzati contiguo, cioè se V è un vettore dove T è un certo tipo diverso da bool, poi obbedisce l'identità & v [n] == & v [0] + n per tutti 0 < = n < V.SIZE().

C++ 11 ha aggiunto std :: array, che è un wrapper attorno a matrici di dimensioni fisse e avrebbe anche le stesse proprietà. Non penso che ci sia un modo per sapere se qualche contenitore ha tale proprietà.

Answer 2

Mi sono ritrovato a dover identificare i tipi che soddisfano questa funzione molte volte. Non so se inventare un tale "concetto" speciale sia elegante (immagina che sia un concetto che riguarda la memoria, che non è molto astratto) ma sono d'accordo che qualcosa del genere sarà utile.

Nel frattempo per essere pratico e tradurre questo concetto/esigenza in un requisito di sintassi pura, cerchiamo di camminare all'indietro. Se ci limitiamo allo standard, quali sono le classi che garantiscono (o quasi garantiscono) contiguità? in ordine di importanza:

std::vector<T> 
T[N] // !! 
std::array<T, N> 
std::string 
std::initializer_list<T> 
std::valarray<T> 

Di tutti questi, std::vector, std::array, std::string hanno una funzione membro chiamata .data(). Quindi, se questo è sufficiente per te, puoi fare affidamento sulla presenza del membro .data() -> T* per indicare la memoria contigua.

Sono disponibili due opzioni:

1) Fai la sforzo di utilizzare la funzione di membro .data() di sollevare un errore di sintassi se il tipo non è contiguo. (Non difficile se si sostituisce ad esempio t[0] da *t.data())

2) Utilizzare un tipo di SFINAE su .data().

template<class ContiguousSequence, typename = decltype(std::declval<ContigiousSequence>().data())> 
void fun(ContiguousSequence&& s){...} // this function will only work with contiguous data 

Inoltre, C++ 17 ha std::data che generalizza a tutti i tipi con .data() e sovraccarichi in aggiunta, per T[N] e std::initializer_list<T>. Quindi, è possibile sostituire ....data() per std::data(...) sopra.

La conclusione, ritengo sia una buona convenzione è che se un tipo ha una funzione data (o .data() in C++ 11) che restituisce un puntatore al tipo di valore allora gli elementi contigue.

(Ok, che dire std::valarray<T>? Non funziona, a meno che non si sovraccarica std::data(std::valarray<T>&). Ma chi usa std::valarray comunque? Si tratta di un caratteristico angolo abbandonato di C++, credo)

Infine, nota per esempio che ovviamente std::map e meno ovviamente std::deque non hanno una funzione .data() (o std::data(...)). boost::multi_array<..., N> ha un membro .data() e restituisce un puntatore all'elemento dell'array, non è chiaro se si tratta di una sequenza contigua nel senso desiderato (perché l'ordine non è evidente) ma in un certo senso è anche un'allocazione contigua della memoria.

EDIT: Ci sono due proposte che affrontano questo problema (ma a livello dei iteratori) http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3884.pdfhttp://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4284.html

Answer 3

"contenitore contigue" si specifed in C++ 17. Da $23.2.1/13 General container requirements [container.requirements.general]:

Un contenitore contigua è un contenitore che supporta iteratori ad accesso casuale ([random.access.iterators]) e il cui membro tipi iteratore e const_iterator sono iteratori contigui ([iterator.requirements.general]).

E di "iteratori contigue", $24.2.1/5 In general [iterator.requirements.general]:

Iteratori che soddisfano inoltre l'esigenza che, per valori interi n e iteratore dereferenceable valori A e (a + n), * (a + n) è equivalente a * (addressof (* a) + n), sono chiamati iteratori contigui.

std::vector (eccetto std::vector<bool>), std::array e std::basic_string sono contenitori contigui.