Определить структуру с минимальным размером

Question

Я хочу определить структуру, например. type, так что sizeof(type) не меньше некоторого значения.

Мотивация:

У меня есть вектор std::vector<type> и я удалить некоторые элементы из него. Кроме того, я сохранил индексы некоторых элементов в других местах, поэтому хочу просто пометить его как не использованный и повторно использовать его в будущем. Это приводит меня к тому, чтобы сохранить следующую доступную позицию в списке в удаленных положениях. В результате sizeof(type) должен быть не менее sizeof(size_t), а type должен быть правильно выровнен.

Возможные решения:

1. boost::variant<type, size_t>

   Это имеет две проблемы, с моей точки зрения. Если I use boost::get<type>, производительность значительно снизится. Если я использую boost::apply_visitor, синтаксис будет странным, а производительность также уменьшится в соответствии с моим профилем.

2. union{type t; size_t s;}

   Это, конечно, работает на двух дефицитов за исключением. Во-первых, синтаксис для ссылки на член type был бы более грязным. Во-вторых, я должен определить конструктор, конструктор копирования и т. Д. Для этого объединения.

3. Продлить type по char[sizeof(size_t) - sizeof(type)]

   Это почти соответствует моим требованиям. Тем не менее, это риск массива нулевой длины, который не поддерживается стандартом C++ и, возможно, неправильным выравниванием.

Поскольку я не буду использовать type как size_t часто, я хотел бы, чтобы просто обеспечить в случае необходимости можно использовать reinterpret_cast<size_t>.

Дополняет

После прочтения комментариев, я думаю, что лучшее решение для моей проблемы должно быть boost::variant. Но мне все еще интересно, есть ли способ сочетать преимущества решений 2 и 3, то есть

a. Я могу получить доступ к членам type без изменений.

b. Получите гарантию на то, что работает reinterpret_cast<size_t>.

Answer 1

Вы можете смягчить беспокойство по поводу решения 3 с чем-то вроде:

struct data 
{ 
    // ... 
}; 

template<class T, bool> class pad_; 
template<class T> class pad_<T, true> { char dummy[sizeof(T) - sizeof(data)]; }; 
template<class T> class pad_<T, false> {}; 

template<class T> using pad = pad_<T, (sizeof(T) > sizeof(data))>; 

class type : public data, pad<size_t> 
{ 
    // ... 
}; 

Этот код:

• предполагает empty base optimization так, что pad может быть полностью оптимизирован из type макета при sizeof(data) >= sizeof(size_t)
• не имеет риска для массива нулевой длины

Answer 2

Хотя это интересная проблема, дизайн сам по себе сомнительный.

1. При добавлении новых элементов, отмеченных неиспользованными, рассматриваются прежде, чем развить вектор. Это означает, что относительный порядок предметов непредсказуем. Если это приемлемо, вы могли бы просто использовать вектор (умных) указателей.

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

2. Все элементы одного размера; распределение их с использованием пула может быть быстрее, чем использование системного распределителя.

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

3. Что касается первоначального дизайна, то громоздко перечислять элементы в векторе, так как реальные элементы смешиваются с «дырами», логика будет запутана дополнительными проверками.

Возможно, есть некоторые проданные аргументы за оригинальный дизайн; к сожалению @ user1535111 не сообщает подробности.