Как реализован std :: tuple?

Question

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

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

Answer 1

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

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

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

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

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

Answer 2

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

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

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

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

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

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

Answer 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;
}

Answer 4

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

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