Efficiency of std::get with std::tuple

Question

I'm curious as to the lookup time that a call to std::get<> on a std::tuple<> takes. Some brief googling (including the reference pages which usually have this information) turned up no results.

My initial intuition (and fear) is that the recursive structure of tuple (if it is implemented as a variadic template) would lead to get requiring an order of N lookups (A call to get<3>(t) looking like t.rest().rest().first(). I'm hoping I'm way off here...

Then again, I would hope the compiler would be able to optimize this to directly return the correct offset without the overhead of N of calls.

Basically what I want: is there a specced guarantee on runtime? does this restrict how std::tuple is implemented?

Answer 1

The answer to the first question (how long std::get takes) depends on how your library chooses to implement std::tuple and std::get. But typically, libraries will choose to use a non-recursive approach, similar to the one outlined here: http://mitchnull.blogspot.com/2012/06/c11-tuple-implementation-details-part-1.html. With that type of approach, the access time of std::get will be constant, and roughly equivalent to the time it takes to access a member of a struct.

In answer to whether the standard provides any guarantees: as others have said, no, the standard makes no guarantees here. An evil library writer could choose to make std::get exponential in N, and they'd still be standard-compliant.

Answer 2

The C++ specification does not provide a guarantee on the runtime performance of any function. Even when it states asymptotic requirements, that only guarantees the relative number of operations, not the performance of those operations. O(1) doesn't mean fast, nor does O(n) mean slow.

You can either trust your compiler/optimizer/standard library implementation, or you can rewrite it all yourself to get whatever performance you want. std::get, under most reasonable compilers (with optimizations on), should perform more or less equivalently to directly accessing the value from a struct. But the spec doesn't require that at any point.

Answer 3

The efficiency will be comparable to accessing a member of a struct. The get<> is resolved at compile time.