Реализуем эффективный тупль с помощью C++26

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

Многие пытливые умы на протяжении десятилетий задавались вопросом: как же реализован std::tuple, как мне реализовать свой тупль (кортеж)? [1]

И немало было дано на эти вопросы ответов и написано статей ([2]). Однако я берусь утверждать, что все они имеют один критический недостаток! Конкретнее, они все рассматривают в основном лишь один (и при этом неэффективный) способ реализации: с помощью множественного наследования или рекурсивного инстанцирования, имеющий в свой очередь множество своих недостатков, главный из которых — неэффективное использование памяти.

В то время как современный C++ позволяет реализовать тупль гораздо проще (без обилия шаблоноты) и эффективнее.

Design notes

Краеугольный камень этой идеи эффективной реализации — простой массив байт (далее — хранилище), размер которого будет достаточен для хранения всех членов тупля. Конечно, он налагает на нас требование подумать о выравнивании: члены имеют разные типы, имеющие разные требования к выравниванию, и мы должны будем учесть это при размещении их в хранилище.

Но как именно нам нужно размещать члены, чтобы получить максимальную эффективность по занимаемой памяти?

Предположим, имеем тип tuple<char, double, int> — наивный вариант его размещения в памяти (см. рисунок и листинг ниже), в котором мы просто располагаем члены (с учетом выравнивания) один за другим в их исходном порядке, нам явно не подходит.

struct tuple  /* size: 24, align: 8 */ {   char a;                         /* offset: 0, size: 1   char __padding[7];                            size: 7 */   double b;                       /* offset: 8, size: 8 */   int c;                          /* offset: 16, size: 4   char __padding[4];                            size: 4 */ };

Он требует 24 байт памяти в то время как эти же члены можно разместить гораздо более эффективно. Так, следующий вариант оптимален и требует всего 16 байт:

struct tuple  /* size: 16, align: 8 */ {   double b;                       /* offset: 0, size: 8 */   char a;                         /* offset: 8, size: 1   char __padding[3];                            size: 3 */   int c;                          /* offset: 12, size: 4 */ };

Но как нам для любого сочетания типов найти оптимальный вариант их размещения в памяти? Для этого существует алгоритм: достаточно просто отсортировать типы по их требованиям к выравниванию в убывающем порядке. В нашем случае, так как alignof(double) > alignof(int) > alignof(char), это будет выглядеть так:

struct tuple  /* size: 16, align: 8 */ {   double b;                       /* offset: 0, size: 8 */   int c;                          /* offset: 8, size: 4 */   char a;                         /* offset: 12, size: 1   char __padding[3];                            size: 3 */ };

Мы получили те же 16 байт — это минимальный размер, который может иметь наш тупль с учетом требований к выраниванию.

С учетом высказанных соображений мы уже можем реализовать наш тупль на псевдокоде:

template <typename... T> struct tuple {     constexpr tuple(T&&... args) {       /* Инициализируем хранилище */       1) Отсортировать типы T по их требованиям к выравниванию       2) Для каждого T:         2.1) Разместить его на требуемом месте в массиве         2.2) Инициализировать его соответствующим значением args     }      template <std::size_t I>     constexpr auto& get() noexcept {       1) Отсортировать типы T по их требованиям к выравниванию,          сохраняя информацию об их исходном индексе (относительно T...)          IOriginal       3) Получить тип TOriginal, имевший исходный индекс IOriginal       2) Получить информацию о смещении (=offset) внутри storage для          TOriginal       return *std::launder(reinterpret_cast<TOriginal*>(storage + offset))     } private:     alignas(T...) std::byte storage[(sizeof(T) + ...)]; };

Звучит как что-то, требующее сложной шаблонной магии: «отсортировать типы» звучит страшно (даже с учетом того, что на самом деле для наших целей мы можем свести это к сортировке обычных объектов). И это действительно требует сложной шаблонной магии, если мы говорим о C++11, C++14 и даже о C++17.

Но с тех пор как значительно расширились возможности constexpr, так и в языке появились такие приятные фичи как pack indexing (cppreference). Так что на деле всё будет выглядеть довольно просто и понятно. Приступим же к настоящей реализации.

Implementation

В качестве основы возьмем наш предыдущий листинг (из которого, конечно, уберем весь псевдокод) (godbolt):

#include <cstddef>  template <typename... T> struct tuple {   constexpr tuple(T&&... args) { }      template <std::size_t I>   constexpr auto& get() noexcept { } private:   alignas(T...) std::byte storage[(sizeof(T) + ...)]; };  // Corner case: пустой tuple // Проще всего реализовать его как специализацию template <> struct tuple<> { };

Первое, что нам потребуется, чтобы реализовать конструктор — вспомогательный тип MemberInfo, который мы будем использовать для хранения информации о каждом T (каждом члене нашего тупля): его оригинальный индекс в T..., выравнивание, размер и смещение относительно &storage[0] (другим языком — то, где этот член в storage будет расположен).

И вместе с этим же реализуем метод get_members_info, заполняющий в компайл-тайме MemberInfo для каждого T (godbolt):

// ...  #include <utility> #include <array> #include <algorithm>  template <typename... T> struct tuple {   // ... private:   struct MemberInfo {     std::size_t original_idx;     std::size_t align;     std::size_t sizeof_;     std::size_t offset;   };    template <std::size_t... I>   consteval static auto get_members_info(std::index_sequence<I...> idx) {     // Для каждого T сохраняем его исходный индекс относительно T...,     // alignof и sizeof     std::array<MemberInfo, sizeof...(T)> res = {       MemberInfo { I, alignof(T), sizeof(T), 0 }...     };     // Сортируем полученный массив по требуемым выравниваниям, чтобы     // получить оптимальное размещение     std::sort(res.begin(), res.end(), [](const auto& lhs, const auto& rhs) {       return lhs.align > rhs.align;     });     // Считаем смещение относительно &storage[0] для каждого из членов     for (std::size_t idx = 1, size = res.size(); idx != size; ++idx) {       res[idx].offset = res[idx - 1].offset + res[idx - 1].sizeof_;     }     return res;   }      consteval static auto get_members_info() {     return get_members_info(std::make_index_sequence<sizeof...(T)>());   }   // ... };  // ...

Теперь несложно реализовать и сам конструктор (godbolt):

// ...  #include <new>  template <typename... T> struct tuple {   constexpr tuple(T&&... args) {     initialize_storage(std::make_index_sequence<sizeof...(T)>(), std::forward<T>(args)...);   }   // ... private:   // ...   template <std::size_t... I>   constexpr auto initialize_storage(std::index_sequence<I...> idx, T&&... args) {     // Получаем всю необходимую нам информацию о членах     constexpr static auto info = get_members_info();     // Размещаем каждый член с помощью placement new в storage     // Обратите внимание: мы не можем написать T...[I] или args...[I],     // так как мы отсортировали члены по их выравниваниям     /// и на I-ой позиции в info может оказаться совсем другой член.     // Именно поэтому мы сохраняем в info original_idx     (       new (storage + info[I].offset)       T...[info[I].original_idx](         std::forward<T...[info[I].original_idx]>(           args...[info[I].original_idx]         )       ),       ...     );   }   // ... };  // ...

И этот код мы уже можем начать покрывать тестами: в частности, удостоверимся, что наш тупль действительно оптимален по занимаемой памяти (сравнивая его размер с размером аналогичного std::tuple) (godbolt):

#include <tuple> #include <cassert> #include <string>  // ...  int main() {   // Все эти assertы выполняются без ошибок   tuple<int, double> x1(1, 2.0);   assert(sizeof(x1) == sizeof(std::tuple<int, double>{}));      tuple<double, int> x2(2.0, 1);   assert(sizeof(x2) == sizeof(std::tuple<double, int>{}));      tuple<double, char, int, std::string> x3(2.0, 'A', 1, "ABC");   assert(sizeof(x3) == sizeof(std::tuple<double, char, int, std::string>)); }

Осталось реализовать лишь метод get<I>() (вместе с тестами для него) (godbolt):

// ...  template <typename... T> struct tuple {   // ...   template <std::size_t I>   constexpr auto& get() noexcept {     constexpr static auto info = get_members_info();     // Нас интересует один конкретный член: с original_idx == I     // В частности, нас интересует только его offset — он нам нужен для     // того, чтобы найти этот член в storage     constexpr auto it = std::find_if(info.begin(), info.end(), [](const auto& element) {       return element.original_idx == I;     });     if constexpr (it == info.end()) {       // Если его не оказалось — пользователь указал некорректный индекс       // Выводим красивое сообщение об ошибке       static_assert(false, "get<I>() access out of bounds");     } else {       // Иначе, пользуясь сохраненным offset, находим этот член в storage и       // возвращаем его       constexpr auto type = *it;       return *std::launder(reinterpret_cast<T...[I]*>(storage + type.offset));     }   }   // ... };  // ...  int main() {   // Все эти assertы выполняются без ошибок   tuple<int, double> x1(1, 2.0);   assert(x1.get<0>() == 1 && x1.get<1>() == 2.0);   // ...    tuple<double, int> x2(2.0, 1);   assert(x2.get<0>() == 2.0 && x2.get<1>() == 1);   // ...      tuple<double, char, int, std::string> x3(2.0, 'A', 1, "ABC");   assert(x3.get<0>() == 2.0 && x3.get<1>() == 'A' && x3.get<2>() == 1 && x3.get<3>() == "ABC");   // x3.get<4>();   // ^ Код выше при раскомментировании упадет с красивым сообщением   // ... }

И, конечно же, так как мы размещали объекты в памяти вручную (с помощью placement new), нам вручную же надо в деструкторе ~tuple вызвать деструкторы для всех размещенных объектов. По аналогии с initialize_storage, это можно реализовать следующим образом (godbolt):

// ...  template <typename... T> struct tuple {   // ...   constexpr ~tuple() {     deinitialize_storage(std::make_index_sequence<sizeof...(T)>());   } private:   // ...   template <std::size_t... I>   constexpr auto deinitialize_storage(std::index_sequence<I...> idx) {     // Получаем всю необходимую нам информацию о членах     constexpr static auto info = get_members_info();     // Вызываем деструктор каждого из членов, стараясь при этом     // не запутаться в индексах     (       std::launder(         reinterpret_cast<T...[info[I].original_idx]*>(           storage + info[I].offset         )       )->~T...[info[I].original_idx](),       ...     );   } 

Теперь мы великолепны! Наш самодельный тупль

1. Превосходит std::tuple по эффективности использования памяти. Взгляните сами на результаты тестов, приведенных ниже (godbolt).

// ...  int main() {   // ...    // Наш самодельный tuple blazing fast и уделывает   // стандартный тупль в некоторых кейсах, так как std::tuple   // не оптимизирует размещение членов в памяти   assert(sizeof(tuple<char, double, int>) == 16);   assert(sizeof(std::tuple<char, double, int>) == 24); }

2. Чертовски быстр. Благодаря использованию constexpr и consteval большинство написанных нами строчек даже не появятся в бинарнике, так как будут исполнены в компайл-тайме.

Теперь вы знаете, как легко и эффективно реализовать тупль на собеседовании!

Опубликовано при поддержке C++ Moscow