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

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

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

Так,

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

  • Или, может ли реализация std::optional быть оптимизирован, чтобы предложить ту же производительность, что и сырье int? И как?

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

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

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

Источник

2 ответа

Решение

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>,

Сделать это в шаблоне, для которого нужно определить только часового для каждого типа, должно быть довольно просто.

Источник

Нет, это не так эффективно. Как видно из эталонной реализации, она должна хранить, обновлять и проверять дополнительные значения.

Источник
Другие вопросы по тегам