Повысить производительность кортежа

Question

Согласно документации boost :: tuple , доступ к одному элементу кортежа имеет ту же производительность, что и доступ к переменной-члену. Например, с учетом следующего объявления:

tuple<A, B, C> t1(A(), B(), C());
struct T { A a; B b; C c; }
T t2;

Эти два утверждения должны иметь одинаковую (или с незначительной разницей) производительность:

t1.get<2>();
t2.c;

Я посмотрел на источники boost :: tuple и, если я их правильно понял (я не уверен, что понял), функция get<N> фактически выполняет это действие:

C get<2>(tuple<A, B, C>& t)
{
    return t.tail.tail.head;
    //Generally:  return t.tail. <<N times>> .head;
}

Это больше похоже на поиск в связанном списке, чем на прямой доступ, и, насколько я понимаю, имеет сложность O (N) вместо O (1), что ожидается от доступа к элементу. Исходя из моего прошлого опыта с наддувом, я бы предположил, что понял это неправильно; но в чем моя ошибка? Как get действительно работает?

Answer 1

Вы правы насчет представления, подобного списку. Тем не менее, он может быть разрешен во время компиляции и, следовательно, сводится к O (1) во время выполнения. (Учитывая достаточно хороший оптимизирующий компилятор.)

Answer 2

Помните, что в C ++ оператор точки - это не указатель, а вычисление с прямым смещением.Общий ответ - да, i1.i2.i3.in для всех n - операция с постоянным временем, вычисляемая во время компиляции.

Если вы хотите немного узнать об этом изнутри компилятора, не копаясь очень глубоко,посмотрите на LLVM getelementptr http://llvm.org/docs/LangRef.html#i_getelementptr Именно так компилятор C ++, такой как CLANG, нацелился на LLVM при компиляции ссылки на структуру.