Efektywność std :: get z std :: tuple

Question

Jestem ciekawy co do czasu wyszukiwania, że ​​trwa połączenie std::get<> na std::tuple<>. Niektóre krótkie wyszukiwania (w tym strony z informacjami, które zwykle zawierają te informacje) nie przyniosły rezultatów.

Moja początkowa intuicja (i strach) jest to, że struktura rekurencyjne krotki (jeśli jest on zaimplementowany jako zmiennej liczbie argumentów szablonu) doprowadziłoby do dostać wymagające kolejność N wyszukiwań (A wezwanie do get<3>(t) patrząc jak t.rest().rest().first(). Jestem Potem znowu nadzieję, że jestem daleko tutaj ...

, to mam nadzieję, że kompilator będzie w stanie zoptymalizować to bezpośrednio powrócić poprawne przesunięcie bez obciążania N połączeń.

Zasadniczo co chcę : czy istnieje określona gwarancja w środowisku wykonawczym? czy to ogranicza implementację std::tuple?

Answer 1

Specyfikacja C++ nie zapewnia gwarancji na wydajność w czasie wykonywania funkcji dowolnej funkcji. Nawet jeśli określa wymagania asymptotyczne, gwarantuje to jedynie względną liczbę operacji, a nie wydajność tych operacji. O (1) nie oznacza szybkiego, ani też O (n) nie oznacza spowolnienia.

Możesz zaufać implementacji kompilatora/optymalizatora/standardowej biblioteki lub możesz napisać wszystko samodzielnie, aby uzyskać żądaną wydajność. std::get, zgodnie z najbardziej uzasadnionymi kompilatorami (z włączonymi optymalizacjami), powinien wykonywać mniej więcej równoważny dostęp do bezpośredniego dostępu do wartości ze struktury. Ale specyfikacja nie wymaga tego w żadnym momencie.

Answer 2

Efektywność będzie porównywalna z dostępem do członka struktury. The get<> jest rozwiązany w czasie kompilacji.

Answer 3

Odpowiedź na pierwsze pytanie (jak długo trwa std::get) zależy od sposobu, w jaki biblioteka wybiera do wdrożenia std::tuple i std::get. Zazwyczaj jednak biblioteki będą korzystać z podejścia nierekurencyjnego, podobnego do przedstawionego tutaj: http://mitchnull.blogspot.com/2012/06/c11-tuple-implementation-details-part-1.html. Przy takim podejściu czas dostępu std::get będzie stały i będzie mniej więcej równy czasowi dostępu do elementu struktury.

W odpowiedzi na to, czy standard zapewnia gwarancje: jak powiedzieli inni, nie, standard nie daje tutaj gwarancji. Zły autor bibliotek mógł wybrać wykładniczy w N, i nadal byłby zgodny ze standardami.