Как реализуется std:: tuple?

Я хотел бы знать, как кортеж реализован в стандартной библиотеке для С++ 0x. Я попытался прочитать описание в руководстве по libstdС++, а затем прочитать список шаблонов, но очень сложно понять, как это работает, особенно при чтении кода.

Может кто-нибудь объяснить мне в нескольких предложениях идею реализации кортежа? Я хочу знать это, потому что я думаю об использовании кортежей в моем коде, и я хочу понять, как он работает и какой тип накладных расходов он приносит (расширяет время компиляции, выполняет много операций копирования в памяти, выполняет многие другие функции в конструкторе и т.д.).

Ответ 1

Один подход к реализации кортежей - использование множественного наследования. Элементы кортежа удерживаются классами листьев, и сам класс кортежа наследуется от нескольких листов. В псевдокоде:

template<typename T0, typename T1, ..., typename Tn>
class PseudoTuple : TupleLeaf<0, T0>, TupleLeaf<1, T1>, ..., TupleLeaf<n, Tn> {
   ...
};

Каждый лист имеет индекс, поэтому каждый базовый класс становится уникальным, даже если типы, которые они содержат, идентичны, поэтому мы можем получить доступ к n-му элементу с помощью простой static_cast:

static_cast<TupleLeaf<0, T0>*>(this);
// ...
static_cast<TupleLeaf<n, Tn>*>(this);

Я написал подробное объяснение этой "плоской" реализации кортежей здесь: С++ 11 деталей реализации кортежа (часть 1)

Ответ 2

Кортеж обычно реализуется как связанный список времени компиляции.

Код немного запутан с помощью шаблона-синтаксиса, но обычно присутствуют следующие элементы:

цепочка классов с элементами головы и хвоста (cons-elements)
пустой экземпляр хвоста для указания конца списка.
рекурсивный код для перехода к определенному индексу, реализуемый как рекурсивный экземпляр шаблонов (созданный при компиляции).

Существуют разумные реализации в С++ 03 (например, boost).

Шаблоны Variadic позволяют неограниченное количество элементов, как упоминалось Motti.

Обычно это время компиляции. Скопировать конструкторы можно вызвать во время инициализации (макс. 1) и при копировании самих кортежей.

Ответ 3

Я думал, что я бы добавить непсевдокодную простую рекурсивную реализацию для справки

#include <iostream>

// Contains the actual value for one item in the tuple. The 
// template parameter 'i' allows the
// 'Get' function to find the value in O(1) time
template<std::size_t i, typename Item>
struct TupleLeaf {
    Item value;
};

// TupleImpl is a proxy for the final class that has an extra 
// template parameter 'i'.
template<std::size_t i, typename... Items>
struct TupleImpl;

// Base case: empty tuple
template<std::size_t i>
struct TupleImpl<i>{};

// Recursive specialization
template<std::size_t i, typename HeadItem, typename... TailItems>
struct TupleImpl<i, HeadItem, TailItems...> :
    public TupleLeaf<i, HeadItem>, // This adds a 'value' member of type HeadItem
    public TupleImpl<i + 1, TailItems...> // This recurses
    {};

// Obtain a reference to i-th item in a tuple
template<std::size_t i, typename HeadItem, typename... TailItems>
HeadItem& Get(TupleImpl<i, HeadItem, TailItems...>& tuple) {
    // Fully qualified name for the member, to find the right one 
    // (they are all called 'value').
    return tuple.TupleLeaf<i, HeadItem>::value;
}

// Templated alias to avoid having to specify 'i = 0'
template<typename... Items>
using Tuple = TupleImpl<0, Items...>;

int main(int argc, char** argv) {
    Tuple<int, float, std::string> tuple;
    Get<0>(tuple) = 5;
    Get<1>(tuple) = 8.3;
    Get<2>(tuple) = "Foo";
    std::cout << Get<0>(tuple) << std::endl;
    std::cout << Get<1>(tuple) << std::endl;
    std::cout << Get<2>(tuple) << std::endl;
    return 0;
}

Ответ 4

Реализация std::tuple возможна через вариативные шаблоны, которые были введены на основной язык.

Я знаю, что это попрошайничает вопрос, но он дает вам лучшую поисковую фразу для исследования.