14

我有一个四/八叉树数据结构。我将一个单元格的子索引/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因此，我可以通过使用诸如forInteger = int或std::numeric_limits<unsigned>::max()for之类的“魔术”值来确定单元格是否缺少孩子Integer = unsigned。这是std::optional<Integer>不能假设的。

据我了解，这种魔法值的使用是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 */; 
}

对于可选类型。

4

2 回答 2

14

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

将其制作成模板，只需要为每种类型定义哨兵，应该非常简单。

于 2013-06-26T15:39:13.107 回答
3

不，它没有那么有效。从参考实现中可以看出，它必须存储、更新和检查一个额外的值。

于 2013-06-26T15:43:10.140 回答