Использует std:: optional <int> так же эффективно, как и использование int?

У меня есть структура данных quad/octree. Im хранит дочерние индексы /ptrs ячейки в массиве. Каждая позиция в массиве представляет местоположение дочернего элемента относительно его родителя, например. в 2D:

// _____________
// |     |     |
// |  2  |  3  |
// |_____|_____|
// |     |     |
// |  0  |  1  |
// |_____|_____|
// for each cell, 4 children are always stored in row-major order
std::vector<std::array<Integer,4>> children;

Я знаю, что максимальное количество детей является подмножеством значений, которые может представлять тип Integer. Таким образом, я могу определить, отсутствует ли в ячейке дочерний элемент, используя значение '' magic '', например -1 для Integer = int, или std::numeric_limits<unsigned>::max() для Integer = unsigned. Это то, что std::optional<Integer> не может принять.

Насколько я понял, это использование магических значений является одним из значений raison d'être std::optional. Тем не менее, я беспокоюсь о производительности std::vector<std::optional<int>> во внутренних циклах.

Итак,

Будет ли производительность std::vector<std::optional<int>> хуже, чем у std::vector<int>? (Я уже делаю сравнение для "несуществующего" значения).
Или можно оптимизировать реализацию std::optional, чтобы предлагать такую же производительность, как raw int? И как?

Смешение std::optional в возвращаемом типе моих функций и магических значений в моей структуре данных звучит как очень плохая идея. Я предпочитаю быть последовательным и использовать один или другой (по крайней мере, в том же контексте). Хотя я могу перегрузить функцию, которая выполняет сравнение с магическим числом:

template<T> bool is_valid(const T& t) { 
  return /* comparison with magic value for t */; 
}

для дополнительных типов.

Ответ 1

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

Я не считаю неправильным иметь другое значение, хранящееся внутри вашей структуры данных, от того, которое открыто публичным API, если внутреннее представление полностью скрыто от пользователей.

Кроме того, я предлагаю вам выделить магическое число в одну пару функций преобразования inline.

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

class CompressedOptionalUInt
{
    static const unsigned SENTINEL_MISSING = std::numeric_limits<unsigned>::max();
    unsigned value;

public:
    CompressedOptionalUInt(std::optional<unsigned> val) : value(!val? SENTINEL_MISSING: *val) {}
    operator std::optional<unsigned>() const { ... }
};

а затем используйте std::array<CompressedOptionalUInt>.

Применять это в шаблон с помощью только той, которая должна быть определена для каждого типа, должна быть довольно простой.

Ответ 1

Ответ 2