Как я могу спроектировать хранилище, которое соответствует реализации стандарта std::any?

Question

В стандартном рабочем проекте (n4582, 20.6.3, p.552) изложено следующее предложение для реализации std::any:

Реализации должны избегать использования динамически выделяемой памяти для небольшого ограниченного объекта. [Пример: где построенный объект содержит только int. - конец примера] Такая оптимизация небольших объектов должна применяться только к типам T, для которых is_nothrow_move_constructible_v имеет значение true.

Насколько я знаю, std::any может быть легко реализовано через стирание типа / виртуальные функции и динамически распределенную память.

Как может std::any избегать динамического выделения и все еще уничтожать такие значения, если во время уничтожения не известна информация времени компиляции; Как будет разработано решение, которое следует предложению стандарта?

---

Если кто-то хочет увидеть возможную реализацию не динамической части, я разместил ее на Code Review: https://codereview.stackexchange.com/questions/128011/an-implementation-of-a-static-any-type

Это слишком долго для ответа здесь. Это основано на предложениях Kerrek SB на комментарии ниже.

Answer 1

Как правило, any берет что-нибудь и динамически выделяет из него новый объект:

struct any {
    placeholder* place;

    template <class T>
    any(T const& value) {
        place = new holder<T>(value);
    }

    ~any() {
        delete place;
    }
};

Мы используем тот факт, что placeholder полиморфно обрабатывать все наши операции - уничтожение, приведение и т. д. Но теперь мы хотим избежать выделения, что означает, что мы избегаем всех приятных вещей, которые дает нам полиморфизм, - и должны переопределить их. Для начала, у нас будет некоторый союз:

union Storage {
    placeholder* ptr;
    std::aligned_storage_t<sizeof(ptr), sizeof(ptr)> buffer;
};

где у нас есть некоторые template <class T> is_small_object { ... } решить, делаем ли мы ptr = new holder<T>(value) или же new (&buffer) T(value), Но конструирование - это не единственное, что мы должны сделать - мы также должны выполнить уничтожение и поиск информации о типе, которые выглядят по-разному в зависимости от того, в каком случае мы находимся. delete ptr или мы делаем static_cast<T*>(&buffer)->~T();последний из которых зависит от отслеживания T!

Итак, мы представляем нашу собственную vtable-подобную вещь. наш any затем будет держать на:

enum Op { OP_DESTROY, OP_TYPE_INFO };
void (*vtable)(Op, Storage&, const std::type_info* );
Storage storage;

Вместо этого вы можете создать новый указатель на функцию для каждой операции, но, возможно, здесь есть несколько других операций, которые я пропускаю (например, OP_CLONE, что может потребовать изменения передаваемого аргумента на union...) и ты не хочешь просто раздувать any размер с кучей функциональных указателей. Таким образом, мы теряем чуть-чуть производительности в обмен на большую разницу в размерах.

На строительстве мы затем заполняем оба storage и vtable:

template <class T,
          class dT = std::decay_t<T>,
          class V = VTable<dT>,
          class = std::enable_if_t<!std::is_same<dT, any>::value>>
any(T&& value)
: vtable(V::vtable)
, storage(V::create(std::forward<T>(value))
{ }

где наш VTable типы что-то вроде:

template <class T>
struct PolymorphicVTable {
    template <class U>
    static Storage create(U&& value) {
        Storage s;
        s.ptr = new holder<T>(std::forward<U>(value));
        return s;
    }

    static void vtable(Op op, Storage& storage, const std::type_info* ti) {
        placeholder* p = storage.ptr;

        switch (op) {
        case OP_TYPE_INFO:
            ti = &typeid(T);
            break;
        case OP_DESTROY:
            delete p;
            break;
        }
    }
};

template <class T>
struct InternalVTable {
    template <class U>
    static Storage create(U&& value) {
        Storage s;
        new (&s.buffer) T(std::forward<U>(value));
        return s;
    }

    static void vtable(Op op, Storage& storage, const std::type_info* ti) {
        auto p = static_cast<T*>(&storage.buffer);

        switch (op) {
        case OP_TYPE_INFO:
            ti = &typeid(T);
            break;
        case OP_DESTROY:
            p->~T();
            break;
        }
    }
};

template <class T>
using VTable = std::conditional_t<sizeof(T) <= 8 && std::is_nothrow_move_constructible<T>::value,
                   InternalVTable<T>,
                   PolymorphicVTable<T>>;

а затем мы просто используем этот vtable для реализации наших различных операций. Подобно:

~any() {
    vtable(OP_DESTROY, storage, nullptr);
}

Answer 2

Как std::any может избежать динамического выделения и все еще уничтожить такие значения, если во время уничтожения не известна информация времени компиляции

Это похоже на загруженный вопрос. Последний проект требует этого конструктора:

template <class ValueType> any(ValueType &&value);

Я не могу понять, почему вам нужно иметь "стирание типа", если вы не хотите, чтобы код обрабатывал как маленькие, так и большие случаи одновременно. Но тогда почему бы не иметь что-то подобное?¹

template <typename T>
  struct IsSmallObject : ...type_traits...

• Небольшие объекты: используйте размещение новых и явных вызовов деструкторов.
• Большой объект: используйте распределитель

В первом случае у вас может быть указатель на ваше неинициализированное хранилище:

union storage
{
    void* ptr;
    typename std::aligned_storage<3 * sizeof(void*), 
                std::alignment_of<void*>::value>::type buffer;
};

Использование объединения, как предложено @KerrekSB.

Обратите внимание, что тип не должен быть известен для класса хранения. Используя какую-то систему обработки / отправки (не уверенную в истинном названии идиомы), система становится тривиальной на этом этапе.

Сначала рассмотрим, как будет выглядеть разрушение:

  template <typename T>
  struct SmallHandler
  {
    // ...

    static void destroy(any & bye)
    {
        T & value = *static_cast<T *>(static_cast<void*>(&bye.storage.buffer));
        value.~T();
        this.handle = nullptr;
    }

    // ...
   };

Тогда any учебный класс:

// Note, we don't need to know `T` here!
class any
{
  // ...

  void clear() _NOEXCEPT
  {
    if (handle) this->call(destroy);
  }

  // ...
  template <class>
  friend struct SmallHandler;
};

Здесь мы выделяем логику, которая должна знать тип времени компиляции для системы обработчика / диспетчеризации, тогда как основная масса any класс должен иметь дело только с RTTI.

---

¹: Вот условия, которые я бы проверил:

1. nothrow_move_constructible
2. sizeof(T) <= sizeof(storage), В моем случае это 3 * sizeof(void*)
3. alignof(T) <= alignof(storage), В моем случае это std::alignment_of<void*>::value

Answer 3

Вдохновленный бустом, я придумал это (протестируйте его на ideone) (я создал минимальный пример, чтобы показать, как уничтожить стертый контейнер типа any без динамической памяти. Я сосредоточился только на конструкторе / деструкторе, пропуская все остальное, игнорируя семантику перемещения и другие вещи)

#include <iostream>
#include <type_traits>

using std::cout;
using std::endl;

struct A { ~A() { cout << "~A" << endl; }};
struct B { ~B() { cout << "~B" << endl; }};

struct Base_holder {
  virtual ~Base_holder() {}
};

template <class T>
struct Holder : Base_holder {
  T value_;

  Holder(T val) : value_{val} {}
};

struct Any {  
  std::aligned_storage_t<64> buffer_;
  Base_holder* p_;

  template <class T>
  Any(T val)
  {
    p_ = new (&buffer_) Holder<T>{val};
  }

  ~Any()
  {
    p_->~Base_holder();
  }
};

auto main() -> int
{  
  Any a(A{});
  Any b(B{});

  cout << "--- Now we exit main ---" << endl;
}

Выход:

~A
~A
~B
~B
--- Now we exit main ---
~B
~A

Конечно, первый - это временные уничтожения, последние два доказывают, что уничтожение Any называет правильный деструктор.

Хитрость заключается в том, чтобы иметь полиморфизм. Вот почему мы имеем Base_holder а также Holder, Мы инициализируем их путем размещения новых в std::aligned_storage и мы явно называем деструктором.

Это просто для того, чтобы доказать, что вы можете вызвать правильный деструктор, не зная типа Any, Конечно, в реальной реализации у вас будет объединение для этого или указатель на динамически распределенную память и логическое значение, указывающее, какая у вас есть.