Как добавить bool в структуру без увеличения sizeof (если в структуре есть отступы)?

Question

Я создаю хеш-таблицу. Узел хеш-таблицы хранит KEY, VALUE и флаг (используется или нет):

template <typename KEY, typename VALUE>
struct Node {
    union { KEY key; };
    union { VALUE value; };
    bool used;

    Node() { }
};

key и value находятся в объединении, потому что они создаются только тогда, когда Node фактически используется (это важно).

Теперь предположим, что в KEY или VALUE есть некоторые отступы. Поэтому разумно поместить used в область заполнения (так что Node может быть меньше).

Возможно ли сделать это (автоматически)?

Если это вообще невозможно, возможно ли это сделать, если KEY или VALUE имеют отступы?

---

Заметьте, у меня есть идея, как использовать хвостовую подкладку, однако она имеет неопределенное поведение. По сути, идея состоит в том, чтобы получить из KEY или VALUE и поместить туда bool used (в этом случае текущие компиляторы помещают bool used в хвост, если объект имеет нестандартную компоновку). Но, к сожалению, used нельзя использовать до тех пор, пока KEY или VALUE фактически не будут созданы (new 'd) - это проблема, потому что при создании пустого узла не создается ни KEY, ни VALUE (это хеш-таблица с открытой адресацией) пустые узлы существуют).

Примечание 2: Я использую этот подход, только когда нет специального значения пусто KEY или VALUE. Если KEY или VALUE имеет специальное пустое значение, то, конечно, мне не нужно использовать отдельное bool used.

Answer 1

Поэтому я немного подумал об этом и понял, что, хотя вы не можете использовать заполнение внутри хранимых объектов, вы можете попытаться расположить элементы Node так, чтобы они занимали наименьшее количество места. Конечно, вы можете написать это жестко, но я подумал, что более элегантный способ - это автоматизировать его.

Чтобы найти наименьшую аранжировку, нам нужно сгенерировать все возможные аранжировки и выбрать наименьшую. Генерация всех аранжировок может быть выполнена с метафункцией permutations, которая генерирует все перестановки пакета типов:

template <typename P1, typename P2>
struct merge {};

template <template <typename...> class P, typename... Ts, typename... Us>
struct merge<P<Ts...>, P<Us...>> {
    using type = P<Ts..., Us...>;
};

template <typename T, typename P>
struct prepend {};

template <typename T, template <typename...> class P, typename... Packs>
struct prepend<T, P<Packs...>> {
    using type = P<typename merge<P<T>, Packs>::type...>;
};

// N is the number of rotations to go
template <std::size_t N, typename Pack, typename = void>
struct permutations_impl {};

template <template <typename...> class P, typename... Ts>
struct permutations_impl<0, P<Ts...>> {
    // All rotations done, break the recursion
    using type = P<>;
};

template <std::size_t N, template <typename...> class P, typename T>
struct permutations_impl<N, P<T>> {
    using type = P<P<T>>;
};

template <std::size_t N, template <typename...> class P, typename F, typename... Rest>
struct permutations_impl<N, P<F, Rest...>, std::enable_if_t<(sizeof...(Rest) && N != 0)>> {
    using PermuteRest = typename permutations_impl<sizeof...(Rest), P<Rest...>>::type;
    using NextRotation = typename permutations_impl<N-1, P<Rest..., F>>::type;

    using type = typename merge<typename prepend<F, PermuteRest>::type, NextRotation>::type;
};

template <typename Pack>
struct permutations {};

template <template <typename...> class P, typename... Ts>
struct permutations<P<Ts...>> {
    using type = typename permutations_impl<sizeof...(Ts), P<Ts...>>::type;
};

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

template <typename Pack>
struct min_size_element {
    static constexpr std::size_t min_index(std::initializer_list<std::size_t> l) {
        std::size_t min = *l.begin();
        std::size_t idx = 0, result = 0;
        for(auto it = l.begin(); it != l.end(); ++it, ++idx) {
            if(*it < min) min = *it, result = idx;
        }
        return result;
    }
};

template <typename... Ts>
struct min_size_element<std::tuple<Ts...>> : min_size_element<void> {
    using type = std::tuple_element_t<min_index({sizeof(Ts)...}), std::tuple<Ts...>>;
};

template <typename... Ts>
struct smallest_tuple {
    using tuples = typename permutations<std::tuple<Ts...>>::type;
    using type = typename min_size_element<tuples>::type;
};

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

template <typename K, typename V>
class Node {
    union KeyWrap {
        struct{} _;
        K key;

        constexpr KeyWrap() : _() {}
    };
    union ValueWrap {
        struct{} _;
        V value;

        constexpr ValueWrap() : _() {}
    };
    // Need to wrap key and value types because tuple elements are accessed by type
    using Storage = typename detail::smallest_tuple<bool, KeyWrap, ValueWrap>::type;

    Storage mStorage;

public:
    constexpr Node() = default;

    ~Node() {
        if(this->used()) {
            this->key().~K();
            this->value().~V();
        }
    }

    Node& operator=(std::pair<K, V> entry) {
        if(this->used()) {
            this->key() = std::move(entry.first);
            this->value() = std::move(entry.second);
        } else {
            new(&std::get<KeyWrap>(mStorage).key) K(std::move(entry.first));
            new(&std::get<ValueWrap>(mStorage).key) V(std::move(entry.second));
            std::get<bool>(mStorage) = true;
        }
        return *this;
    }

    bool used() const {
        return std::get<bool>(mStorage);
    }

    K& key() {
        assert(this->used());
        return std::get<KeyWrap>(mStorage).key;
    }

    V& value() {
        assert(this->used());
        return std::get<ValueWrap>(mStorage).value;
    }
};

Живая демоверсия

---

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