Is using std::optional<int> as efficient as using int?

Question

I have a quad-/octree data structure. Im storing the children indexes/ptrs of a cell in an array. Each position in the array represents the location of a child with respect to its parent, e.g. in 2D:

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

I know that the max number of children is a subset of the values that an Integer type can represent. Thus I can identify if a cell is missing a child by using a ''magic'' value like -1 for Integer = int, or std::numeric_limits<unsigned>::max() for Integer = unsigned. This is something that std::optional<Integer> cannot assume.

As far as I understood, this usage of magic values is one of the raison d'être of std::optional. Still, I'm worried about the performance of std::vector<std::optional<int>> in inner loops.

So,

• Will the performance of std::vector<std::optional<int>> be worse than that of std::vector<int>? (I'm already doing the comparison for "non-existent" value).

• Or, can the implementation of std::optional be optimized to offer the same performance as a raw int? And how?

Mixing std::optional in the return type of my functions and magic values in my data structure sounds like a very bad idea. I prefer to be consistent and either use one or the other (at least within the same context). Although I could overload the function that performs the comparison with the magic number:

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

for optional types.

Answer 1

std::optional is going to require additional storage and fit fewer values into cache (it appears you already know the reason for this).

I don't think it's wrong to have a different value stored internally in your data structure from the one exposed by the public API, as long as the internal representation is completely hidden from users.

Furthermore, I suggest you isolate the magic number into a single pair of inline conversion functions.

The compiler should help you remember to use the conversion functions consistently, by generating type errors if you forget. You might even use a thin struct wrapper for an int in your internal data structure, to ensure that no implicit conversion exists (or define a user-defined conversion).

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 { ... }
};

and then use std::array<CompressedOptionalUInt>.

Making that into a template, with just the sentinel needing to be defined for each type, should be pretty straightforward.

Answer 2

No, it's not as efficient. As you can see from the reference implementation it has to store, update and check an extra value.