Efficienza di std :: get con std :: tupla

Question

Sono curioso di sapere quanto tempo richiede una chiamata a std::get<> su un std::tuple<>. Alcuni brevi googling (incluse le pagine di riferimento che di solito contengono queste informazioni) non hanno dato risultati.

mia intuizione iniziale (e paura) è che la struttura ricorsiva di tupla (se viene implementato come un modello variadic) porterebbe ad ottenere che richiede un ordine di N lookup (Una chiamata a get<3>(t) cercando come t.rest().rest().first(). Sono sperando sono lontano qui ...

Poi di nuovo, mi auguro che il compilatore sarebbe in grado di ottimizzare questo per tornare direttamente l'offset senza il sovraccarico di N di chiamate corretta.

Fondamentalmente quello che voglio : esiste una garanzia specifica sul runtime? Ciò limita il modo in cui viene implementato std::tuple

Answer 1

Le specifiche C++ non forniscono una garanzia sulle prestazioni di runtime di alcuna funzione. Anche quando afferma requisiti asintotici, ciò garantisce solo il numero relativo di operazioni, non le prestazioni di quelle operazioni. O (1) non significa veloce, né O (n) significa lento.

Puoi fidarti del tuo compilatore/ottimizzatore/implementazione della libreria standard, oppure puoi riscriverlo tutto da solo per ottenere le prestazioni che desideri. std::get, nella maggior parte dei compilatori ragionevoli (con ottimizzazioni attivate), dovrebbe eseguire più o meno in modo equivalente per accedere direttamente al valore da una struttura. Ma le specifiche non lo richiedono in nessun momento.

Answer 2

L'efficienza sarà paragonabile all'accesso a un membro di una struttura. Il get<> viene risolto in fase di compilazione.

Answer 3

La risposta alla prima domanda (per quanto tempo std::get accetta) dipende da come la libreria sceglie di implementare std::tuple e std::get. Ma in genere, le biblioteche sceglieranno di utilizzare un approccio non ricorsivo, simile a quello delineato qui: http://mitchnull.blogspot.com/2012/06/c11-tuple-implementation-details-part-1.html. Con questo tipo di approccio, il tempo di accesso di std::get sarà costante e approssimativamente equivalente al tempo necessario per accedere a un membro di una struttura.

In risposta a se lo standard fornisce garanzie: come altri hanno già detto, no, lo standard non fornisce alcuna garanzia in questo caso. Uno scrittore di librerie malvagio potrebbe scegliere di rendere esponenziale std::get in N, e sarebbero comunque conformi agli standard.